Codeforces Round 562 题解

A Circle Metro

B Pairs

C Increasing by Modulo

给定一个序列,每次选择一些位置模 $m$ 加一,求最小操作次数使得序列不减。

显然有一个 $\mathcal{O}(nm)$ 的 dp。

考虑二分答案,贪心构造使得每个位置尽量小。

D Good Triple

给定一个 $01$ 串,求有多少子串存在 $3$ 个不同位置间隔相同且字符相同。

注意到串长大于 $10$ 时已经不可能不满足条件,暴力筛掉错误情况即可。

E And Reachability

给定一个序列,询问 $q$ 次,两个位置 $l$ 和 $r$,存在一条路径 $a_l,a_{i_0}, a_{i_1}, \dots , a_r$,满足相邻两个至少二进制表示下有一个共同位置是 $1$。

预处理每个位置到下一个第 $i$ 位为 $1$ 的第一个位置。倒序维护一下全局的每一个二进制位的最后出现位置,对于每个数的每个 $1$ 的二进制位,从全局的后一个转移过来。询问的时候,枚举 $r$ 的二进制即可。

时间复杂度 $\mathcal{O}(n \log^2 n + q \log n)$。

代码

A

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 100000 + 5;

int n, a, b, x, y;

int check1(int p) {
if (a < x) {
if (a <= p && p <= x) return p - a;
return -1;
} else {
if (p >= a) return p - a;
else if (p <= x) return n - a + p;
return -1;
}
}
int check2(int p) {
if (b > y) {
if (b >= p && p >= y) return b - p;
return -1;
} else {
if (p <= b) return b - p;
else if (p >= y) return b + n - p;
return -1;
}
}

int main() {
cin >> n >> a >> x >> b >> y;
int f = 0;
for (int i = 1; i <= n; i++) {
int a = check1(i), b = check2(i);
// cout << i << ": "<< a << ' ' << b << endl;
if (a == -1 || b == -1) continue;
if (a == b) f = 1;
}
if (f) puts("YES");
else puts("NO");
return 0;
}

B

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#include <map>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 300000 + 5;

struct DS {
int bag[maxn], cnt[maxn], mx = 0;
void insert(int x, int t) {
cnt[bag[x]]--;
bag[x] += t;
cnt[bag[x]]++;
if (bag[x] == mx + 1) mx++;
if (cnt[mx] == 0) mx--;
}
} f;

int n, m;
PII a[maxn];
vector<int> bag[maxn];
map<int,int> mp;

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d", &a[i].first, &a[i].second);
if (a[i].first > a[i].second) swap(a[i].first, a[i].second);
bag[a[i].first].push_back(i);
f.insert(a[i].second, 1);
if (a[i].first != a[i].second) {
bag[a[i].second].push_back(i);
f.insert(a[i].first, 1);
}
}
int fl = 0;
for (int i = 1; i <= n; i++) {
for (auto& x: bag[i]) {
f.insert(a[x].second, -1);
if (a[x].first != a[x].second) f.insert(a[x].first, -1);
}
if ((int)bag[i].size() + f.mx >= m) {
fl = 1; break;
}
for (auto& x: bag[i]) {
f.insert(a[x].second, 1);
if (a[x].first != a[x].second) f.insert(a[x].first, 1);
}
}
if (fl) puts("YES");
else puts("NO");
return 0;
}

C

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#ifdef XLor
#define dbg(args...) do {cout << #args << " -> "; err(args);} while (0)
#else
#define dbg(...)
#endif
void err() {std::cout << std::endl;}
template<typename T, typename...Args>
void err(T a, Args...args){std::cout << a << ' '; err(args...);}
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 300000 + 5;

int n, m, a[maxn], b[maxn];

int cal(int a, int x) {
if (a < x) return a + m - x;
return a - x;
}

int check(int x) {
for (int i = 1; i <= n; i++) b[i] = a[i];
for (int i = 1; i <= n; i++) {
if (b[i] + x >= m && (b[i] + x) % m >= b[i - 1]) b[i] = b[i - 1];
else if (b[i] >= b[i - 1]) ;
else if (b[i] + x < m && b[i] + x >= b[i - 1]) b[i] = b[i - 1];
else if (b[i] + x >= m) b[i] = b[i - 1];
else return 0;
// dbg(i, b[i], b[i - 1]);
}
return 1;
}

int dp[maxn];

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", a + i);
// check(0);
// check(1);
int l = 0, r = m - 1, ans = 0;
while (l <= r) {
int m = (l + r) / 2;
if (check(m)) ans = m, r = m - 1;
else l = m + 1;
}
cout << ans;
return 0;
}

D

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#ifdef XLor
#define dbg(args...) do {cout << #args << " -> "; err(args);} while (0)
#else
#define dbg(...)
#endif
void err() {std::cout << std::endl;}
template<typename T, typename...Args>
void err(T a, Args...args){std::cout << a << ' '; err(args...);}
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 300000 + 5;

char s[maxn];
int n;

int main() {
scanf("%s", s + 1); n = strlen(s + 1);
ll ans = 1ll * (n + 1) * n / 2;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
int f = 0;
for (int k = 1; j - 2 * k >= i; k++) {
if (s[j - 2 * k] == s[j - k] && s[j - k] == s[j]) {
dbg(s[j - 2 * k], s[j - k], s[j]);
f = 1; break;
}
}
if (f) break;
ans--;
}
}
cout << ans;
return 0;
}

E

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 <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#ifdef XLor
#define dbg(args...) do {cout << #args << " -> "; err(args);} while (0)
#else
#define dbg(...)
#endif
void err() {std::cout << std::endl;}
template<typename T, typename...Args>
void err(T a, Args...args){std::cout << a << ' '; err(args...);}
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 300000 + 5;

int n, q, a[maxn], nxt[maxn][21], nx[21];

int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) scanf("%d", a + i);
for (int i = 0; i < 21; i++) nxt[n + 1][i] = nx[i] = n + 1;
for (int i = n; i >= 1; i--) {
for (int j = 0; j < 21; j++) nxt[i][j] = n + 1;
for (int j = 0; j < 21; j++) if (a[i] & (1 << j)) {
int p = nx[j];
nx[j] = nxt[i][j] = i;
for (int k = 0; k < 21; k++) {
nxt[i][k] = min(nxt[i][k], nxt[p][k]);
}
}
}
int l, r;
while (q--) {
scanf("%d%d", &l, &r);
int f = 0;
for (int j = 0; j < 21; j++) if (a[r] & (1 << j)) {
if (nxt[l][j] <= r) {
dbg(nxt[l][j]);
f = 1; break;
}
}
if (f) puts("Shi");
else puts("Fou");
}
return 0;
}