我们的终极目标不是AC，而是获取经验
问题 A: ABB
题意
给定长度为n的字符串，在给定的字符串后面加上长度最短的字符串，使得到的字符串回文，求最少添加几个字符
考点
字符串哈希 or 马拉车算法（Manacher）
const ll inf = 1e15; const ll INF = 0x3f3f3f3f; const int MAXN = 410010; char A[MAXN * 2]; int B[MAXN * 2]; void Manacher(char s[], int len) { int l = 0; A[l++] = '$';//0下标存储为其他字符 A[l++] = '#'; for (int i = 0; i < len; i++) { A[l++] = s[i]; A[l++] = '#'; } A[l] = 0;//空字符 int mx = 0; int id = 0; for (int i = 0; i < l; i++) { B[i] = mx > i ? min(B[2 * id - i], mx - i) : 1; while (A[i + B[i]] == A[i - B[i]]) { B[i]++; } if (i + B[i] > mx) { mx = i + B[i]; id = i; } } return; } int n; char s[MAXN]; bool judge() { int l = 0, r = n - 1; int flag = 0; while (l <= r) { if (s[l] == s[r]) { l++; r--; continue; } else { flag = 1; break; } l++; r--; if (l == r) break; } if (flag) return false; return true; } int main() { cin >> n; cin >> s; int len = (int)strlen(s); if (judge()) { puts("0"); return 0; } Manacher(s, len); int ans = 0; int pos = 0; int siz = 2 * len + 1; for (int i = 0; i < 2 * len + 1; i++) { if (B[i] >= siz - i) { if (i % 2) { pos = max(pos, (B[i] - 1)); } else { pos = max(pos, (B[i] - 1) / 2 * 2 + 1); } } } if (pos == 0) cout << n - 1 << endl; else cout << n - pos << endl; return 0; } /* 6 abcdcb */
问题 C: Bob in Wonderland
题意
将一个树形结构变成链，求出操作的次数(每次可以删除一条边)
考点
从度的角度可以很好的操作，代码很简短
const int N = 300010; int d[N]; int main() { int n; scanf("%d", &n); for (int i = 1;i < n;i++) { int x, y; scanf("%d%d", &x, &y); d[x]++, d[y]++; } int res = 0; for (int i = 1;i <= n;i++) { if(d[i] >= 2) res += d[i] - 2; } cout << res; return 0; } /************************************************************** Problem: 14241 User: 我就不告诉你哈哈哈 Language: C++ Result: 正确 Time:94 ms Memory:3196 kb ****************************************************************/
问题 F: Zeldain Garden
题意
考点
整数分块叭
计算出
x/1+x/2+x/3+x/4…+x/x即为答案，计算为下取整
typedef long long ll; ll get(ll x) { ll res = 0; for (ll l = 1, r;l <= x;l = r + 1) { r = x / (x / l); res += (r - l + 1) * (x / l); } return res; } int main() { ll l, r; scanf("%lld%lld", &l, &r); ll ans = get(r) - get(l - 1); printf("%lld", ans); return 0; } /************************************************************** Problem: 14244 User: 我就不告诉你哈哈哈 Language: C++ Result: 正确 Time:119 ms Memory:2024 kb ****************************************************************/
问题 G: Light Emitting Hindenburg
题意
这个题不是我参与写的可以询问大佬
考点
据说是个贪心
代码仅从参考
虽然没代码，但是可以私信
问题 H: K == S
题意
考点
AC自动机 + 矩阵快速幂
问题 I: Ponk Warshall
/doge这个是我写的
题意
给出两个字符串，从上面字符中选取任意两个来进行交换，从上面的字符串得到下面的字符串，最少的操作步数是多少？
考点
思维 + 暴力
const ll inf = 1e15; const ll INF = 0x3f3f3f3f; string s, t; map<char, int> mp; int a[5][5]; int a1[1000007]; int a2[1000007]; int main() { cin >> s; cin >> t; mp['A'] = 1, mp['C'] = 2, mp['G'] = 3, mp['T'] = 4; int len = s.size(); for (int i = 0; i < len; i++) { a1[i] = mp[s[i]]; a2[i] = mp[t[i]]; } for (int i = 0; i < len; i++) { if (s[i] != t[i]) { a[a1[i]][a2[i]] += 1; } } ll ans = 0; for (int i = 1; i <= 4; i++) { for (int j = 1; j <= 4; j++) { int mini = min(a[i][j], a[j][i]); ans += mini; a[i][j] -= mini; a[j][i] -= mini; } } for (int i = 1; i <= 4; i++) { for (int j = 1; j <= 4; j++) { for (int k = 1; k <= 4; k++) { int mini = min(a[i][j], min(a[j][k], a[k][i])); ans += 2 * mini; a[i][j] -= mini; a[j][k] -= mini; a[k][i] -= mini; } } } //方式1： for (int i = 1; i <= 4; i++) { for (int j = 1; j <= 4; j++) { for (int k = 1; k <= 4; k++) { for (int t = 1; t <= 4; t++) { int mini = min(a[i][j], min(min(a[j][k], a[k][t]), a[t][i])); ans += 3 * mini; a[i][j] -= mini; a[j][k] -= mini; a[k][t] -= mini; a[t][i] -= mini; } } } } //方式2： for (int i = 1; i <= 4; i++) ans += 3 * a[i][2]; //ps:a[i][x],1<=x<=4均可 cout << ans << endl; return 0; } /* */ /************************************************************** Problem: 14247 User: 我就不告诉你哈哈哈 Language: C++ Result: 正确 Time:317 ms Memory:15700 kb ****************************************************************/
