http://codeforces.com/contest/828
C题直接的思路是模拟把整个字符串都覆盖上去，已经覆盖的，就不需要再覆盖就是了。
这个套路出过很多次了，是一个类似并查集的东西，也就是并查集维护线段吧，我直接dfs回溯弄也可以。
设tonext[i]表示第i个位置的下一个空位是什么，
注意中间空的位置填上'a'就好
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; const int maxn = 3e6 + 20; char str[maxn], sub[maxn]; int tonext[maxn], haha; int mx; void dfs(int cur, int pos, int lef) { mx = max(mx, haha); if (lef <= 0) return; if (tonext[cur] == cur) { str[cur] = sub[pos]; tonext[cur] = cur + 1; haha = cur + 1; dfs(cur + 1, pos + 1, lef - 1); } else { haha = tonext[cur]; dfs(tonext[cur], pos + tonext[cur] - cur, lef - (tonext[cur] - cur)); tonext[cur] = haha; } } void work() { for (int i = 1; i <= maxn - 20; ++i) tonext[i] = i; int n; cin >> n; for (int i = 1; i <= n; ++i) { cin >> sub + 1; int k; cin >> k; int lensub = strlen(sub + 1); for (int j = 1; j <= k; ++j) { int pos; cin >> pos; dfs(pos, 1, lensub); } } for (int i = 1; i < mx; ++i) { if (str[i] == ' ') str[i] = 'a'; } cout << str + 1 << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif IOS; work(); return 0; }
D题想歪了，要使得最远的距离最短，则分两种情况吧，具体思路都是选出一个点，作为树的重心，然后其他非叶子节点连上去，或则叶子节点连上去。
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; void work() { int n, k; cin >> n >> k; int to = 1; if (n - k == 1) { printf("2 "); for (int i = 1; i <= k; ++i) { printf("%d %d ", i, n); } } else if (n - k == 2) { printf("3 "); printf("1 2 "); printf("1 3 "); printf("2 4 "); for (int i = 5; i <= 2 + k; ++i) { printf("1 %d ", i); } } else { if (k >= n - k - 1) { printf("4 "); for (int i = k + 2; i <= n; ++i) { printf("%d %d ", k + 1, i); } int to = 0; for (int i = k + 2; i <= n; ++i) { printf("%d %d ", i, ++to); } while (to < k) { ++to; printf("%d %d ", k + 1, to); } } else { int res = (n - k - 1) % k; int ans; if (res == 0) { ans = 2 * (1 + (n - k - 1) / k); } else if (res == 1) { ans = 2 * (1 + (n - k - 1) / k) + 1; } else ans = 2 * (1 + (n - k - 1) / k) + 2; printf("%d ", ans); for (int i = 1; i <= k; ++i) { printf("%d %d ", k + 1, i); } int one = 1, two = k + 2, pre = k + 2, up = k; for (int i = 1; i <= n - k - 1; ++i) { printf("%d %d ", one, two); one++; two++; if (one > up) { one = pre; up = two - 1; pre = two; } } } } } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }
E题我没什么好方法用了220个bit怼过去了。
就是维护跳跃的区间，不知道其他大佬怎么做的。
做这题的时候发现有4个字母和长度最大是10，应该有点用的。
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; int c[5][57][100000 + 2]; int lenstr; int lowbit(int x) { return x & (-x); } void upDate(int which, int dis, int pos, int val) { while (pos <= lenstr) { c[which][dis][pos] += val; pos += lowbit(pos); } } int ask(int which, int dis, int pos) { int ans = 0; while (pos) { ans += c[which][dis][pos]; pos -= lowbit(pos); } return ans; } char str[111111]; int getID(char ch) { if (ch == 'A') return 0; else if (ch == 'T') return 1; else if (ch == 'G') return 2; else return 3; } char sub[111]; int num[22][22]; int calc(int pos, int dis) { pos %= dis; if (pos == 0) pos = dis; return num[pos][dis]; } void work() { scanf("%s", str + 1); lenstr = strlen(str + 1); for (int i = 1; i <= lenstr; ++i) { int id = getID(str[i]); for (int j = 1; j <= 10; ++j) { // if (j > i) break; upDate(id, calc(i, j), i, 1); } } int q; scanf("%d", &q); while (q--) { int op; scanf("%d", &op); if (op == 1) { int pos; scanf("%d%s", &pos, sub); if (str[pos] == sub[0]) continue; int id = getID(str[pos]); int id2 = getID(sub[0]); for (int i = 1; i <= 10; ++i) { // if (i > pos) break; upDate(id, calc(pos, i), pos, -1); upDate(id2, calc(pos, i), pos, 1); } str[pos] = sub[0]; } else { int L, R; scanf("%d%d%s", &L, &R, sub + 1); int lensub = strlen(sub + 1); int ans = 0; if (lensub >= R - L + 1) { for (int i = L; i <= R; ++i) { ans += str[i] == sub[i - L + 1]; } } else { int newR = R - (L - 1); int res = newR % lensub; for (int i = 1, to = R - res + 1; i <= res; ++i, ++to) { ans += str[to] == sub[i]; } for (int i = R - res - lensub + 1, to = 1; i <= R - res; ++i, ++to, ++L) { int id = getID(sub[to]); ans += ask(id, calc(i, lensub), i) - ask(id, calc(i, lensub), L) + (str[L] == sub[to]); // printf("%d ", ans); } } printf("%d ", ans); } } } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif int to = 0; for (int i = 1; i <= 10; ++i) { for (int j = i; j <= 10; ++j) { num[i][j] = ++to; } } work(); return 0; }