Codeforces Round #616 (Div. 2) 简要题解

 

A. Even But Not Even

按题意模拟即可。

Codeforces Round #616 (Div. 2) 简要题解
 1 // Date: 2020-02-02
 2  
 3 #include <bits/stdc++.h>
 4 using namespace std;
 5  
 6 typedef long long LL;
 7 typedef long double LD;
 8 typedef vector<int> VI;
 9 typedef pair<int, int> pii;
10 #define FIO ios::sync_with_stdio(false);cin.tie(0)
11 #define rep(i, a, b) for(int i = int(a); i <= int(b); ++i)
12 #define per(i, b, a) for(int i = int(b); i >= int(a); --i)
13 #define mem(x, y) memset(x, y, sizeof(x))
14 #define all(x) (x).begin(),(x).end()
15 #define mk make_pair
16 #define pb push_back
17 #define fi first
18 #define se second
19 const LL INF = 1e18;
20 const LL mod = 1e9 + 7;
21 const int inf = 0x3f3f3f3f;
22 const int N = 3e5 + 10;
23 LL qpow(LL x, LL y, LL MOD) {LL a=1; while(y){ if(y&1) a=a*x%MOD; x=x*x%MOD; y>>=1; } return a;}
24  
25 int a[N], b[N];
26 int main() {
27     int T; scanf("%d", &T);
28     while(T--) {
29         int n; scanf("%d", &n);
30         rep(i, 1, n) scanf("%d", &a[i]), b[i] = a[i];
31         int l = 1, r = n;
32         a[1] = 0;
33         for(int i = 2; i <= n; i++) {
34             if(a[i] > a[i-1]) l = i, a[i] = a[i-1] + 1;
35             else break;
36         }
37         b[n] = 0;
38         for(int i = n-1; i >= 1; i--) {
39             if(b[i] > b[i+1]) r = i, b[i] = b[i+1] + 1;
40             else break;
41         }
42         if(l >= r) puts("Yes");
43         else puts("No");
44     }
45  
46     return 0;
47 }
View Code

 

B. Array Sharpening

找出能够从左到右递增的最远点 $L$ 和从右到左递增的最远点 $R$ ,判断是否 $L \geq R$ 即可。

Codeforces Round #616 (Div. 2) 简要题解
 1 // Date: 2020-02-02
 2  
 3 #include <bits/stdc++.h>
 4 using namespace std;
 5  
 6 typedef long long LL;
 7 typedef long double LD;
 8 typedef vector<int> VI;
 9 typedef pair<int, int> pii;
10 #define FIO ios::sync_with_stdio(false);cin.tie(0)
11 #define rep(i, a, b) for(int i = int(a); i <= int(b); ++i)
12 #define per(i, b, a) for(int i = int(b); i >= int(a); --i)
13 #define mem(x, y) memset(x, y, sizeof(x))
14 #define all(x) (x).begin(),(x).end()
15 #define mk make_pair
16 #define pb push_back
17 #define fi first
18 #define se second
19 const LL INF = 1e18;
20 const LL mod = 1e9 + 7;
21 const int inf = 0x3f3f3f3f;
22 const int N = 3e5 + 10;
23 LL qpow(LL x, LL y, LL MOD) {LL a=1; while(y){ if(y&1) a=a*x%MOD; x=x*x%MOD; y>>=1; } return a;}
24  
25 int a[N], b[N];
26 int main() {
27     int T; scanf("%d", &T);
28     while(T--) {
29         int n; scanf("%d", &n);
30         rep(i, 1, n) scanf("%d", &a[i]), b[i] = a[i];
31         int l = 1, r = n;
32         a[1] = 0;
33         for(int i = 2; i <= n; i++) {
34             if(a[i] > a[i-1]) l = i, a[i] = a[i-1] + 1;
35             else break;
36         }
37         b[n] = 0;
38         for(int i = n-1; i >= 1; i--) {
39             if(b[i] > b[i+1]) r = i, b[i] = b[i+1] + 1;
40             else break;
41         }
42         if(l >= r) puts("Yes");
43         else puts("No");
44     }
45  
46     return 0;
47 }
View Code

 

C. Mind Control

贪心,由于数据很小,直接暴力枚举控制的人左边多少个和剩下的人左边多少个即可。复杂度 $O(n^2)$,可以预处理达到 $O(n)$

Codeforces Round #616 (Div. 2) 简要题解
 1 // Date: 2020-02-02
 2  
 3 #include <bits/stdc++.h>
 4 using namespace std;
 5  
 6 typedef long long LL;
 7 typedef long double LD;
 8 typedef vector<int> VI;
 9 typedef pair<int, int> pii;
10 #define FIO ios::sync_with_stdio(false);cin.tie(0)
11 #define rep(i, a, b) for(int i = int(a); i <= int(b); ++i)
12 #define per(i, b, a) for(int i = int(b); i >= int(a); --i)
13 #define mem(x, y) memset(x, y, sizeof(x))
14 #define all(x) (x).begin(),(x).end()
15 #define mk make_pair
16 #define pb push_back
17 #define fi first
18 #define se second
19 const LL INF = 1e18;
20 const LL mod = 1e9 + 7;
21 const int inf = 0x3f3f3f3f;
22 const int N = 1e5 + 10;
23 LL qpow(LL x, LL y, LL MOD) {LL a=1; while(y){ if(y&1) a=a*x%MOD; x=x*x%MOD; y>>=1; } return a;}
24  
25 int a[N];
26 int main() {
27     int T; scanf("%d", &T);
28     while(T--) {
29         int n, m, k;
30         scanf("%d%d%d", &n, &m, &k);
31         rep(i, 1, n) scanf("%d", &a[i]);
32         int ans = 0, all = min(k, m-1);
33         rep(i, 0, all) {
34             int l = i+1, r = n-(all-i), tp = inf, rem = m-1-all;
35             for(int j = 0; j <= rem; j++) {
36                 tp = min(tp, max(a[l+j], a[r-(rem-j)]));
37             }
38             ans = max(ans, tp);
39         }
40         printf("%d\n", ans);
41     }
42  
43     return 0;
44 }
View Code

 

D. Irreducible Anagrams

可以直接打表找规律,具体证明参考 [官方题解]

结论是:长度为 $1$ 时YES,其余的仅当字符集大小 $\leq 2$ 且 $s[l]==s[r]$ 时为NO

证明:

1.$s[l]\neq[r]$

将 $s[l]$ 全部堆在右边。

例如 $s = abbab$, $ t = bbbaa$ 即可。

2.$s[l] == s[r]$

- 字符集 $=1$ :有解。
- 字符集 $=2$:设字符集为 $\{a,b\}$ , $s = a...a$ , 显然 $t[1] = b$ ,那么必定存在一个 $x$ 满足 $1 \leq x < n$ 并且 $s[1,x]$ 中 $b$ 的个数等于 $t[1,x]$ 中 $b$ 的个数,那么分割 $[1,x]$ 即可。
- 字符集 $\geq3$:将非 $s[l]$ 的某个字符全部堆在左边,然后堆 $s[l]$ 即可。例如 $s=abcaba$, $t=bbaaac$

Codeforces Round #616 (Div. 2) 简要题解
 1 // Date: 2020-02-02
 2  
 3 #include <bits/stdc++.h>
 4 using namespace std;
 5  
 6 typedef long long LL;
 7 typedef long double LD;
 8 typedef vector<int> VI;
 9 typedef pair<int, int> pii;
10 #define FIO ios::sync_with_stdio(false);cin.tie(0)
11 #define rep(i, a, b) for(int i = int(a); i <= int(b); ++i)
12 #define per(i, b, a) for(int i = int(b); i >= int(a); --i)
13 #define mem(x, y) memset(x, y, sizeof(x))
14 #define all(x) (x).begin(),(x).end()
15 #define mk make_pair
16 #define pb push_back
17 #define fi first
18 #define se second
19 const LL INF = 1e18;
20 const LL mod = 1e9 + 7;
21 const int inf = 0x3f3f3f3f;
22 const int N = 2e5 + 10;
23 LL qpow(LL x, LL y, LL MOD) {LL a=1; while(y){ if(y&1) a=a*x%MOD; x=x*x%MOD; y>>=1; } return a;}
24  
25 char s[N];
26 int cnt[N][26];
27 int main() {
28     scanf("%s", s+1);
29     int n = strlen(s+1);
30     rep(i, 1, n) {
31         rep(j, 0, 25) cnt[i][j] = cnt[i-1][j];
32         cnt[i][s[i]-'a']++;
33     }
34     int q; scanf("%d", &q);
35     while(q--) {
36         int l, r;
37         scanf("%d%d", &l, &r);
38         if(r-l+1 == 1) {
39             puts("Yes");
40             continue;
41         }
42         int num = 0;
43         rep(i, 0, 25) {
44             if(cnt[r][i]-cnt[l-1][i] > 0) num++;
45         }
46         if(num <= 2 && s[l] == s[r]) puts("No");
47         else puts("Yes");
48     }
49  
50     return 0;
51 }
View Code

 

E. Prefix Enlightenment

题意:给定一个长度为 $n$ 的 $01$ 串,$k$ 个 $\{1,2,...,n\}$ 的子集,满足任意三个子集交为空,每次操作是将某个子集所对应的位置全部取反,对于每个前缀求最少多少次操作使该前缀全为 $1$。

$1 \leq n,k\leq10^5$

题解:最多只有 $2$ 个集合相交,因此每个点最多只被两个集合包含。将集合作为点,串上每个点为边建图,边权为 $0$ 表示只选它的 $1$ 个端点,为 $1$ 表示两端点全选或全不选。考虑并查集拆点,每个点拆为 $x$ 和 $x+k$, 分别表示不选和选。按顺序加边,每次加边有两种情况:

1. 该边仅 $1$ 个端点,那么若边权为 $0$ 则端点必选,否则必不选。因此可以设置一个特殊点,点权为INF
2. 该边有 $2$ 个端点,根据边权分类讨论即可。

复杂度 $O((n+k)⋅α(k))$

感觉讲的也不太清楚,我是参考评论区的一个大佬的做法:


Codeforces Round #616 (Div. 2) 简要题解

[大佬代码]

我的代码:

Codeforces Round #616 (Div. 2) 简要题解
 1 // Date: 2020-02-03
 2  
 3 #include <bits/stdc++.h>
 4 using namespace std;
 5  
 6 typedef long long LL;
 7 typedef long double LD;
 8 typedef vector<int> VI;
 9 typedef pair<int, int> pii;
10 #define FIO ios::sync_with_stdio(false);cin.tie(0)
11 #define rep(i, a, b) for(int i = int(a); i <= int(b); ++i)
12 #define per(i, b, a) for(int i = int(b); i >= int(a); --i)
13 #define mem(x, y) memset(x, y, sizeof(x))
14 #define all(x) (x).begin(),(x).end()
15 #define mk make_pair
16 #define pb push_back
17 #define fi first
18 #define se second
19 const LL INF = 1e18;
20 const LL mod = 1e9 + 7;
21 const int inf = 0x3f3f3f3f;
22 const int N = 6e5 + 10;
23 LL qpow(LL x, LL y, LL MOD) {LL a=1; while(y){ if(y&1) a=a*x%MOD; x=x*x%MOD; y>>=1; } return a;}
24  
25 int n, k, Never;
26 int p[N], val[N];
27 VI g[N];
28 char s[N];
29  
30 int Find(int x) { return x == p[x] ? x : p[x] = Find(p[x]); }
31  
32 void init() {
33     rep(i, 1, 2*k+1) p[i] = i;
34     rep(i, k+1, 2*k) val[i] = 1;
35     val[Never] = inf;
36 }
37  
38 void merge(int x, int y) {
39     x = Find(x), y = Find(y);
40     if(x != y) p[x] = y, val[y] += val[x];
41 }
42  
43 int cal(int x) {
44     return min(val[Find(x)], val[Find(x+k)]);
45 }
46  
47 int main() {
48     scanf("%d%d%s", &n, &k, s+1);
49     Never = 2*k+1;
50     rep(i, 1, k) {
51         int len; scanf("%d", &len);
52         while(len--) {
53             int x; scanf("%d", &x);
54             g[x].pb(i);
55         }
56     }
57     init();
58     int ans = 0;
59     rep(i, 1, n) {
60         if(g[i].size() == 1) {
61             ans -= cal(g[i][0]);
62             if(s[i] == '0') merge(g[i][0], Never);
63             else merge(g[i][0]+k, Never);
64             ans += cal(g[i][0]);
65         } else if(g[i].size() == 2) {
66             int x = g[i][0], y = g[i][1];
67             if(Find(x) != Find(y) && Find(x) != Find(y+k)) {
68                 ans -= (cal(x) + cal(y));
69                 if(s[i] == '0') merge(x, y+k), merge(x+k, y);
70                 else merge(x, y), merge(x+k, y+k);
71                 ans += cal(x);
72             }
73         }
74         printf("%d\n", ans);
75     }
76  
77     return 0;
78 }
View Code

 

F 有空再补

上一篇:Yarn资源调度器


下一篇:Easy之619:只出现一次的最大数字