A. Even But Not Even
按题意模拟即可。
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$ 即可。
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)$
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$
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))$
感觉讲的也不太清楚,我是参考评论区的一个大佬的做法:
我的代码:
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 有空再补