「CF1209X」Codeforces Round #584
A. Paint the Numbers
从小到大排序以后，每次贪心的把能被最小元素整除的划分到一起
|
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 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; int a[105]; bool mark[105]; int main() { n = read(); for(int i = 1; i <= n; i++) a[i] = read(); sort(a + 1, a + n + 1); int ans = 0; for(int i = 1; i <= n; i++) if(!mark[i]) { for(int j = 1; j <= n; j++) if(a[j] % a[i] == 0) mark[j] = 1; ans++; } cout << ans << endl; return 0; } |
B. Koala and Lights
因为 ab 都很小，枚举时间，暴力模拟灯的开关
|
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<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n, mx; string str; int a[105], b[105], f[105]; int main() { n = read(); cin >> str; for(int i = 1; i <= n; i++) a[i] = read(), b[i] = read(); for(int i = 1; i <= n; i++) f[i] = str[i - 1] - '0'; for(int i = 0; i <= 100000; i++) { int ans = 0; for(int j = 1; j <= n; j++) ans += (f[j] == 1); for(int j = 1; j <= n; j++) if((i - b[j]) % a[j] == 0 && i - b[j] >= 0) f[j] ^= 1; mx = max(mx, ans); } cout << mx << endl; return 0; } |
C. Paint the Digits
枚举一下染色成 1 的最大值 x，则比 x 小的都染色成 1，再从右往左，直到第一个比 x 小的元素出现之前，把所有等于 x 的元素染色成 1
剩下的全染色成 2，check 一下是否合法
|
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 71 72 73 74 75 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n, t; int a[200005], f[200005][10], c[200005]; string str; bool check(int x) { for(int i = 1; i <= n; i++) c[i] = 0; int mx = 0, k = n + 1; for(int i = 1; i <= n; i++) if(a[i] < x) { mx = max(mx, a[i]); if(a[i] < mx)return 0; k = i; c[i] = 1; } for(int i = k; i <= n; i++) if(a[i] == x) c[i] = 1; mx = x; for(int i = 1; i <= n; i++) if(!c[i]) { mx = max(mx, a[i]); if(a[i] < mx)return 0; k = i; c[i] = 2; } return 1; } int main() { t = read(); while(t--) { n = read(); cin >> str; for(int i = 1; i <= n; i++) a[i] = str[i - 1] - '0'; bool flag = 0; for(int i = 0; i <= 9; i++) if(check(i)) { for(int j = 1; j <= n; j++) printf("%d", c[j]); flag = 1; break; } if(flag)puts(""); else puts("-"); continue; } return 0; } |
D. Cow and Snacks
考虑计算最多能满足多少人，把零食建点，顾客建边，则每个连通块都存在一种贡献为连通块大小 – 1 的分配方式
连通块用并查集维护比较方便
|
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 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n, k; int f[100005], size[100005]; int find(int x) { return x == f[x]? x: f[x] = find(f[x]); } int main() { n = read(); k = read(); for(int i = 1; i <= n; i++) { f[i] = i; size[i] = 1; } for(int i = 1; i <= k; i++) { int x = read(), y = read(); int p = find(x), q = find(y); if(p != q) { f[p] = q; size[q] += size[p]; } } int ans = k; for(int i = 1; i <= n; i++) if(find(i) == i) ans -= size[i] - 1; cout << ans << endl; return 0; } |
E1. Rotate Columns (easy version)
这个 hard 版本应该是能状压 dp，用 dp(i, s) 表示前 i 列已经被选择的行构成的集合状态是 s
需要一个关键的优化，按每列的最大值排序以后，只要考虑前 n 列即可
退役选手比赛只能写写 easy 的暴力
我写的搜索是这样的，可以从前 4n 大的元素中，选择 4 个，然后 check 一下能不能把它们转到不同的行上，时限还是比较宽的
|
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 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int t, n, m, mx; int r[105], sel[4]; struct data{ int p, x, y; }a[505]; bool cmp(data p, data q) { return p.p > q.p; } bool check() { for(int i = 0; i <= 3; i++) for(int j = 0; j <= 3; j++) for(int k = 0; k <= 3; k++) { if(n >= 2)r[a[sel[1]].y] = i; if(n >= 3)r[a[sel[2]].y] = j; if(n >= 4)r[a[sel[3]].y] = k; bool tmp[4] = {0}; for(int p = 1; p <= n; p++) tmp[(a[sel[p]].x + r[a[sel[p]].y]) % n] = 1; int tmp_cnt = 0; for(int p = 0; p < n; p++) if(tmp[p]) tmp_cnt++; if(tmp_cnt == n) return 1; } return 0; } int dfs(int i, int k) { int mx = 0; if(k == n) { if(check()) { int sum = 0; for(int p = 1; p <= n; p++) sum += a[sel[p]].p; return sum; } else return 0; } for(int j = i + 1; j <= min(n * m, 30); j++) { sel[k + 1] = j; int ans = dfs(j, k + 1); mx = max(ans, mx); } return mx; } int main() { t = read(); while(t--) { mx = 0; n = read(); m = read(); int cnt = 0; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { cnt++; a[cnt].p = read(); a[cnt].x = i; a[cnt].y = j; } sort(a + 1, a + cnt + 1, cmp); cout << dfs(0, 0) << endl; } return 0; } |
G1. Into Blocks (easy version)
不带修改的版本，最后的 block 其实是确定的
预处理，对于每个元素求与它相等的元素中最右的一个，则它们俩一定是一个 block的
划分出所有的 block 后，每个 block 找众数
|
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 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n, q, ans; int a[200005], cnt[200005], lst[200005], f[200005]; int main() { n = read(), q = read(); ans = n; for(int i = 1; i <= n; i++) { a[i] = read(); cnt[a[i]]++; lst[a[i]] = i; } for(int i = 1; i <= n; i++) f[i] = max(f[i - 1], lst[a[i]]); int L = 1; for(int i = 1; i <= n; i++) if(f[i] == i) { int mx = 0; for(int j = L; j <= i; j++) mx = max(mx, cnt[a[j]]); ans -= mx; L = i + 1; } cout << ans << endl; return 0; } |
计数器 9850850
OI 课件=>
OI 课件=>
yyy想看黄学长切F
就打到easy version 想看黄学长写后面的题解。。
更新了更新了！！