https://codeforces.com/contest/1326
A. Bad Ugly Numbers
题意:构造出一个正整数,满足长度为n,不含0,不能被包含的数字整除。
2333333这样就好了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| #include<bits/stdc++.h> using namespace std; #define ll long long const int N = 2e5 + 10; const int INF = 0x3f3f3f3f; int T, n; int main() { scanf("%d", &T); while (T--) { scanf("%d", &n); if (n == 1) { puts("-1"); continue; } printf("2"); for (int i = 0; i < n - 1; i++)printf("3"); puts(""); } return 0; }
|
D2. Prefix-Suffix Palindrome (Hard version)
题意:给定字符串s,要求找到s的不相交的前缀和后缀,拼起来是个回文串,且最长。
Manacher
可以分成两部分,s的对称相等的前缀和后缀,再加上中间与前缀或后缀相连的一个回文串。
预处理出每个位置作为中心的最长回文串(即Manacher),再遍历每个位置,看能否和一对对称的前后缀连起来,能则更新答案。最后找到最大值,记录位置。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
| #include<bits/stdc++.h> using namespace std; #define ll long long const int N = 1e6 + 10; const int INF = 0x3f3f3f3f; int T; char s[N]; char Ma[N * 2]; int Mp[N * 2], re[N * 2]; void Manacher(char s[], int len) { int l = 0; Ma[l++] = '$'; Ma[l++] = '#'; for (int i = 0; i < len; i++) { Ma[l++] = s[i]; re[l - 1] = i; Ma[l++] = '#'; } Ma[l] = 0; for (int i = 0; i <= l; i++)Mp[i] = 0; int mx = 0, id = 0; for (int i = 0; i < l; i++) { Mp[i] = mx > i ? min(Mp[2 * id - i], mx - i) : 1; while (i + Mp[i] < l&&i - Mp[i] >= 0 && Ma[i + Mp[i]] == Ma[i - Mp[i]]) { Mp[i]++; } if (i + Mp[i] > mx) { mx = i + Mp[i]; id = i; } } } char ans[N]; int main() { scanf("%d", &T); while (T--) { scanf("%s", s); int n = strlen(s); Manacher(s, n); int mxpa = 0; for (; mxpa < ceil(1.0*n / 2) && s[mxpa] == s[n - 1 - mxpa]; mxpa++); int id = -1, mx = -1, ia = -1; for (int i = 2; i < (n + 1) * 2; i++) { int r = i + Mp[i] - 1, l = i - Mp[i] + 1; while (r > i&&Ma[r] == '#')r--; while (l < i&&Ma[l] == '#' || Ma[l] == '$')l++; r = re[r]; l = re[l]; int le = min(n - 1 - r, l); int ad = max(0, le); int tmp = r - l + 1; if (ad <= mxpa)tmp += ad * 2; else tmp = 0; if (mx < tmp) { mx = tmp, id = i, ia = ad; } } int cnt = 0; for (; cnt < ia; cnt++)ans[cnt] = s[cnt]; for (int i = id - Mp[id] + 1; i <= id; i++)if (Ma[i] <= 'z'&&Ma[i] >= 'a') ans[cnt++] = Ma[i]; for (int i = mx - 1; cnt < mx; i--, cnt++) { ans[i] = ans[mx - 1 - i]; } for (int i = 0; i < mx; i++)printf("%c", ans[i]); puts(""); } return 0; }
|
E. Bombs
题意:有n个位置,每到一个位置就可以拿到相应的数字,但是如果这个位置有炸弹,就会炸掉最大的那个数,给出了炸弹位置的序列,对于i,q[1],q[2],q[3],⋯,q[i] 有炸弹,问对每个i,最终拿到的数字和为多少。
线段树
考虑从左到右遍历序列,增加炸弹。
可以发现炸弹每增加一个炸弹,答案一定是非递增的,那么可以在遍历序列的同时减小答案,只要check这个答案是否合法。
最终结果小于ans表明所有大于等于ans的数都被炸掉了,从右到左第一个大于等于ans的数右边至少有一个炸弹,第二个大于等于ans的数右边至少有两个炸弹,以此类推,每个位置,包括这个位置的右边大于等于ans的数的个数一定要小于等于右边的炸弹数,也就是说每个位置右边大于等于ans的数的个数-右边的炸弹数≤0,那么只要判断最大值是否小于等于0。对于那些数字小于ans的位置,也是相同情况。所以上述情况可以推广到所有位置。
线段树维护所有位置右边大于等于ans的数的个数-右边的炸弹数的最大值,从左到右遍历炸弹序列,同时递减ans,判断如果线段树的最大值小于等于0,表明ans被炸了,ans就-1,知道最大值大于0。遍历序列的时候处理完当前的就区间插入这个位置的炸弹,并且增加一个区间大于ans的数的个数。
由于本题ans有非递增的性质,所以线段树的更改是无需回退的,这也是解决本题的关键,还有一点就是要发现一个答案不够小等价于每个位置右边大于等于ans的数的个数小于等于右边的炸弹数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
| #include<bits/stdc++.h> using namespace std; #define ll long long const int N = 3e5 + 10; const int INF = 0x3f3f3f3f; int n; int a[N], q[N], pos[N]; #define mid ((l+r)>>1) #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 int tr[N << 2], laz[N << 2]; void up(int rt) { tr[rt] = max(tr[rt << 1], tr[rt << 1 | 1]); } void down(int rt) { int& x = laz[rt]; if (x) { tr[rt << 1] += x; tr[rt << 1 | 1] += x; laz[rt << 1] += x; laz[rt << 1 | 1] += x; x = 0; } } void add(int ql, int qr, int x, int l, int r, int rt) { if (ql <= l && qr >= r) { laz[rt] += x; tr[rt] += x; return; } down(rt); if (ql <= mid)add(ql, qr, x, lson); if (qr > mid)add(ql, qr, x, rson); up(rt); } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); pos[a[i]] = i; } for (int i = 1; i <= n; i++)scanf("%d", &q[i]); int ans = n; printf("%d", n); add(1, pos[n], 1, 1, n, 1); for (int i = 1; i < n; i++) { add(1, q[i], -1, 1, n, 1); while (tr[1] <= 0) add(1, pos[--ans], 1, 1, n, 1); printf(" %d", ans); } puts(""); return 0; }
|