0%

CF Global Round 7

好活当赏

$\text{A}$

这随便构造构造就行了…

我瞎构造了一个 $555….54$ ,按题意也是符合的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;

int t, n;
int main() {
scanf ("%d", &t);
while (t--) {
scanf ("%d", &n);
if (n == 1) puts("-1");
else {
for(int i = 1; i <= n-1; ++i) putchar('5');
puts("4");
}
}
}

$\text{B}$

模拟 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

const int N = 200020;
int t, n, mx, b[N];
int main() {
scanf ("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf ("%d", &b[i]);
}
int nowmx = 0;
for (int i = 1; i <= n; ++i) {
printf("%d ", b[i] + nowmx);
nowmx = max(nowmx, b[i] + nowmx);
}
}

$\text{C}$

考虑一个构造性的最大值证明。

显然最大值不可能超过 $(n-k+1) + (n-k+2) + … +n$,并且我们可以构造出这样的一个上界。

具体怎么构造也很简单,我们把相邻的中间随便插一个小旗子,然后每个 $>n-k$ 的左右两边的旗子所构成的区间就是一个区间。

然后你会了构造的话求方案数也显然了,就是每个旗子独立地乘法原理一下就完事了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
const int N = 200020, MOD = 998244353;
int n, k, p[N], t[N];
int main() {
scanf ("%d%d", &n, &k);
for (int i = 1; i <= n; ++i) scanf ("%d", &p[i]);
vector <int> pos;
long long ans = 1ll * (2 * n - k + 1) * k / 2;
for (int i = 1; i <= n; ++i) if (p[i] > n - k) pos.push_back(i);
long long ways = 1;
for (int i = 1; i < pos.size(); ++i) ways = ways * (pos[i] - pos[i - 1]) % MOD;
cout << ans << " " << ways << endl;
}

$\text{D}$

这个字符串一定可以通过两步贪心得到。

一步是尽可能先匹配头尾。

另一步是求匹配剩余的字符串的最长前后缀回文串。

第一步指针扫完之后第二步二分+hash求,当然也可以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
70
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000010;
const ll p1 = 19260817, m1 = 998244353, p2 = 13331, m2 = 1000000003;
int t, n;
ll pw1[N], pw2[N], h1[N], h2[N], h1_[N], h2_[N];
char s[N];
bool is_palindrome(int l, int r) {
if ((r - l + 1) % 2) {
int t = (l + r) >> 1;
ll hs1 = (h1[t] - h1[l - 1] * pw1[t - l + 1] % m1 + m1) % m1;
ll hs2 = (h1_[t] - h1_[r + 1] * pw1[r - t + 1] % m1 + m1) % m1;
ll hs3 = (h2[t] - h2[l - 1] * pw2[t - l + 1] % m2 + m2) % m2;
ll hs4 = (h2_[t] - h2_[r + 1] * pw2[r - t + 1] % m2 + m2) % m2;
// cerr << hs1 << " " << hs2 << " " << hs3 << " " << hs4 << endl;
return hs1 == hs2 && hs3 == hs4;
} else {
int lt = l-1 + (r - l + 1)/2, rt = lt + 1;
ll hs1 = (h1[lt] - h1[l - 1] * pw1[lt - l + 1] % m1 + m1) % m1;
ll hs2 = (h1_[rt] - h1_[r + 1] * pw1[r - rt + 1] % m1 + m1) % m1;
ll hs3 = (h2[lt] - h2[l - 1] * pw2[lt - l + 1] % m2 + m2) % m2;
ll hs4 = (h2_[rt] - h2_[r + 1] * pw2[r - rt + 1] % m2 + m2) % m2;
return hs1 == hs2 && hs3 == hs4;
}
}
void solv() {
scanf ("%s", s + 1);
n = strlen(s + 1);
for (int i = 1; i <= n; ++i) {
h1[i] = (h1[i - 1] * p1 + s[i]) % m1;
h2[i] = (h2[i - 1] * p2 + s[i]) % m2;
}
h1_[n + 1] = h2_[n + 1] = 0;
for (int i = n; i >= 1; --i) {
h1_[i] = (h1_[i + 1] * p1 + s[i]) % m1;
h2_[i] = (h2_[i + 1] * p2 + s[i]) % m2;
}
int l = 0, r = n + 1, ans = 0, pos = 0, tp = 0;
while (l + 1 < r - 1 && s[l + 1] == s[r - 1]) ++l, --r;
for (int i = l+1; i <= r-1; ++i) {
int len = min(i-l, r-i);
if (is_palindrome(i-len+1, i+len-1)) {
if (ans < 2 * len - 1) ans = 2 * len - 1, pos = i, tp = 1;
}
if (i-1 > l) {
int len = min(i-1-l, r-i);
if (is_palindrome(i-len, i+len-1))
if (ans < 2 * len) ans = 2 * len, pos = i, tp = 2;
}
}
for (int i = 1; i <= l; ++i) putchar(s[i]);

if (tp == 1) {
int i = pos, len = min(i - l, r - i);
for (int j = i-len+1; j <= i+len-1; ++j) putchar(s[j]);
} else if (tp == 2) {
int i = pos, len = min(i-1-l, r-i);
for (int j = i-len; j <= i+len-1; ++j) putchar(s[j]);
}
for (int i = r; i <= n; ++i) putchar(s[i]);
puts("");
}
int main() {
scanf ("%d", &t);
pw1[0] = 1, pw2[0] = 1;
for (int i = 1; i < N; ++i) pw1[i] = pw1[i - 1] * p1 % m1;
for (int i = 1; i < N; ++i) pw2[i] = pw2[i - 1] * p2 % m2;
while (t--) solv();
}

$\text{E}$

nb,不会

首先样例告诉我们答案肯定非递增,这个显然,因为你多pop答案只会变小不会变大

然后如何 $check$ 当前答案是否比 $x$ 小?那就相当于所有 $\geq x$ 的数都被 pop 掉了,也就是对于任意一个后缀, $\geq x$ 的数的个数肯定小于等于 $bomb$ 的次数。

令 $\geq x$ 的数贡献 +1 , bomb 贡献 -1,那肯定后缀和的最大值要 $\leq 0$.

然后又因为答案非递增的性质,用一个类似于双指针的东西维护逐步递减的答案,也就是判断如果答案 $<$ 目前的 $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
#include <bits/stdc++.h>
using namespace std;

const int N = 300010;
int p[N], q[N], n, pos[N], mx[N], tg[N];
void pd(int p) {
mx[p * 2] += tg[p], mx[p * 2 + 1] += tg[p];
tg[p * 2] += tg[p], tg[p * 2 + 1] += tg[p];
tg[p] = 0;
}
void upd(int p, int l, int r, int L, int R, int v) {
if (L <= l && r <= R) {
mx[p] += v;
tg[p] += v;
return;
}
int mid = (l + r) >> 1;
if (tg[p]) pd(p);
if (L <= mid) upd(p * 2, l, mid, L, R, v);
if (R > mid) upd(p * 2 + 1, mid + 1, r, L, R, v);
mx[p] = max(mx[p * 2], mx[p * 2 + 1]);
}
bool dec(int t) {
upd(1, 1, n, 1, pos[t], 1);
if (mx[1] <= 0) return 1;
else {
upd(1, 1, n, 1, pos[t], -1);
return 0;
}
}
int main() {
scanf ("%d", &n);
for (int i = 1; i <= n; ++i) scanf ("%d", &p[i]), pos[p[i]] = i;
for (int i = 1; i <= n; ++i) scanf ("%d", &q[i]);

int answer = n;
for (int i = 1; i <= n; ++i) {
while (dec(answer)) --answer;
printf("%d ", answer);
upd(1, 1, n, 1, q[i], -1);
}
return 0;
}