AtCoderBeginnerContest225(A,B,C,D,E,F)

作者：刘洁05_836 | 来源：互联网 | 2023-10-10 17:17

A.DistinctStrings三个字母的全排列得到的字符串的种类数ACcode#include#include#include

A. Distinct Strings

三个字母的全排列得到的字符串的种类数
ACcode

#include #include #include #include #include #include #include #include #include #define ll long long #define chushi(a, b) memset(a, b, sizeof(a)) #define endl "\n" const double eps = 1e-8; const ll INF=0x3f3f3f3f; const int mod=1e9 + 7; const int maxn = 1e6 + 5; const int N=1005; using namespace std; int main() { string s; cin >> s; if(s[0] == s[1] && s[1] == s[2]) cout <<1 < else if(s[0] == s[1] || s[0] == s[2] || s[1] == s[2]) cout <<3 < else cout <<6 < return 0; }
B. Star or Not

给 n-1 条边，询问是否为菊花图。
判断入度即可。
ACcode

#include #include #include #include #include #include #include #include #include #define ll long long #define chushi(a, b) memset(a, b, sizeof(a)) #define endl "\n" const double eps = 1e-8; const ll INF=0x3f3f3f3f; const int mod=1e9 + 7; const int maxn = 1e6 + 5; const int N=1005; using namespace std; int in[maxn]; int main() { int n; cin >> n; int u, v; for(int i = 2; i <= n; i++){ cin >> u >> v; in[u]++; in[v]++; } int res = 0; for(int i = 1; i <= n; i++) if(in[i] == n-1) res = 1; if(res) cout <<"Yes" < else cout <<"No" < return 0; }
C. Calendar Validator

判断是否为合法的矩阵。
先判断第一行是否合法，第二行开始判断是否和上一行相差 7。
ACcode

#include #include #include #include #include #include #include #include #include #define ll long long #define chushi(a, b) memset(a, b, sizeof(a)) #define endl "\n" const double eps = 1e-8; const ll INF=0x3f3f3f3f; const int mod=1e9 + 7; const int maxn = 1e4 + 5; const int N=1005; using namespace std; int a[maxn][10]; int main() { int n, m; cin >> n >> m; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ cin >> a[i][j]; } } int res = 1; for(int i = 2; i <= m; i++){ int x = a[1][i-1] % 7; if(x == 0) x = 7; int y = a[1][i] % 7; if(y == 0) y = 7; if(x != y-1 || a[1][i-1] != a[1][i]-1) res = 0; } for(int i = 2; i <= n; i++){ for(int j = 1; j <= m; j++){ if(a[i-1][j] != a[i][j]-7) res = 0; } } if(res) cout <<"Yes" < else cout <<"No" < return 0; }
D. Play Train

模拟链表即可。
ACcode

#include #include #include #include #include #include #include #include #include #define ll long long #define chushi(a, b) memset(a, b, sizeof(a)) #define endl "\n" const double eps = 1e-8; const ll INF=0x3f3f3f3f; const int mod=1e9 + 7; const int maxn = 1e6 + 5; const int N=1005; using namespace std; int pre[maxn]; int suf[maxn]; int main() { int n, m; cin >> n >> m; for(int i = 1; i <= n; i++) pre[i] = suf[i] = -1; int op, x, y; for(int i = 1; i <= m; i++){ cin >> op >> x; if(op == 1){ cin >> y; pre[y] = x; suf[x] = y; } else if(op == 2){ cin >> y; pre[y] = -1; suf[x] = -1; } else{ int head = x, cnt = 1; while(pre[head] != -1) head = pre[head], cnt++; int tmp = x; while(suf[tmp] != -1) tmp = suf[tmp], cnt++; cout < while(head != -1) cout < cout < } } return 0; }
E. 7

几何题，偏思维。
在这里插入图片描述
由图可知：从x轴开始选取，当发生覆盖时，优先选取斜率较小的点比较优。
如图，1 和 2 发生覆盖，选择 1 的同时可以选择 3。
注意精度问题，用 long double。
ACcode

#include #include #include #include #include #include #include #include #include #define ll long long #define chushi(a, b) memset(a, b, sizeof(a)) #define endl "\n" const double eps = 1e-8; const ll INF=0x3f3f3f3f; const int mod=1e9 + 7; const int maxn = 1e6 + 5; const int N=1005; using namespace std; typedef struct Node{ long double l; long double r; } node; bool cmp(node A, node B){ return A.l } node p[maxn]; int main() { int n; cin >> n; long double x, y; for(int i = 1; i <= n; i++){ cin >> x >> y; p[i].r = (y-1) / x; // 靠下 if(x == 1) p[i].l = 1e9; // 靠上 else p[i].l = y / (x-1); } sort(p+1, p+1+n, cmp); // 按照斜率排序 int res = 0; long double l = -1e9; for(int i = 1; i <= n; i++){ if(p[i].r res++; l = max(l, p[i].l); } cout < return 0; }
F. String Cards

DP。
在 n 个字符串中选取 k 个任意连接，得到字典序最小的字符串。
按照 A+B > B+A 的顺序排序。
设

d

p

i

,

j

dp_{i,j}

dpi,j 表示前 i 个字符串取 j 个得到的最小字符。

d

p

i

+

1

,

j

=

d

p

i

,

j

dp_{i+1,j} = dp_{i, j}

dpi+1,j=dpi,j
d

p

i

+

1

,

j

=

m

i

n

(

d

p

i

+

1

,

j

,

s

+

d

p

i

,

j

−

1

)

，

s

表

示

可

选

择

的

字

符

串

dp_{i+1,j} = min(dp_{i+1,j} , s + dp_{i, j-1})，s 表示可选择的字符串

dpi+1,j=min(dpi+1,j,s+dpi,j−1)，s表示可选择的字符串

ACcode

#include #include #include #include #include #include #include #include #include #define ll long long #define chushi(a, b) memset(a, b, sizeof(a)) #define endl "\n" const double eps = 1e-8; const ll INF=0x3f3f3f3f; const int mod=1e9 + 7; const int maxn = 1e6 + 5; const int N=1005; using namespace std; string s[100], dp[55]; bool cmp(string a, string b){ return a+b > b+a; } int main() { int n, k; cin >> n >> k; for(int i = 1; i <= n; i++) cin >> s[i]; sort(s+1, s+n+1, cmp); for(int i = 1; i <= n; i++) dp[i] = "{"; dp[0] = ""; for(int i = 1; i <= n; i++){ for(int j = k-1; j >= 0; j--){ dp[j+1] = min(dp[j+1], s[i] + dp[j]); } } cout < return 0; }