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++);
//cout << Ma[0] << Mp[0] << endl;
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]q[1],q[2],q[3],\cdots ,q[i] 有炸弹,问对每个i,最终拿到的数字和为多少。

线段树

考虑从左到右遍历序列,增加炸弹。

可以发现炸弹每增加一个炸弹,答案一定是非递增的,那么可以在遍历序列的同时减小答案,只要check这个答案是否合法。

最终结果小于ans表明所有大于等于ans的数都被炸掉了,从右到左第一个大于等于ans的数右边至少有一个炸弹,第二个大于等于ans的数右边至少有两个炸弹,以此类推,每个位置,包括这个位置的右边大于等于ans的数的个数一定要小于等于右边的炸弹数,也就是说每个位置右边大于等于ans的数的个数-右边的炸弹数0\leq 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;
}