Random Mushup
最近事情比较多(比较懒),所以把三场比赛一起补了,过程可能会简略些。
这场比赛比较迷,两题都是直接枚举过,主要是数学,并查集和dp,图论题没做出来。可能以后还会再补吧
- 组合数学
- 贪心,二分
- 扩展欧几里得
- 2-sat并查集处理
- dp
A. Kyoya and Colored Balls
组合数学
每次先确定每种颜色最后一个球的位置,之后该种颜色其他的球就可以在剩下的位置上随便摆放,接着再确定下一种颜色最后一个球的位置,注意,每种颜色最后一个球的位置是确定的,当你已经摆完了所有的4号球后,3号球最后一个只能放在四号球前有空位的最近的地方,所以在求组合数时不能把最后一个球算在内。
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<iostream> #include<stdio.h> #include<cmath> #include<algorithm> #include<cstring> #include<string> #include<vector> using namespace std; #define ll long long const int maxn = 1000; const int mod = 1000000007; int k; int a[maxn]; int sum; ll ans = 1; int C[maxn][maxn]; void init() { for (int i = 0; i < maxn; i++) { C[i][i] = 1; C[i][0] = 1; } for (int i = 1; i < maxn; i++) { for (int j = 1; j < i; j++) { C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod; } } } int main() { init(); cin.sync_with_stdio(false); cin >> k; for (int i = 0; i < k; i++) { cin >> a[i]; sum += a[i]; } for (int i = k - 1; i >= 0; i--) { ans = ans * C[sum - 1][a[i] - 1] % mod; sum -= a[i]; } cout << ans; return 0; }
|
C. Match Points
二分+贪心
看似直接配对就好了,但实际上如果把一个数与第一个符合条件的数就配对,会导致结果变小,类似于以下数据。
1和4配对导致之后数都无法配对。
所以把数据排序后二分,前一半的数只能和后一半的数配对,就不会出现数都配对的挤在前面的情况了。
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
| #include<iostream> #include<stdio.h> #include<cmath> #include<algorithm> #include<cstring> #include<string> #include<vector> using namespace std; #define ll long long const int maxn = 2e5 + 5; int n, z; int a[maxn]; int ans; int main() { cin.sync_with_stdio(false); cin >> n >> z; for (int i = 0; i < n; i++) { cin >> a[i]; } sort(a, a + n); int l, r; l = 0; r = n / 2 ; for (; l < n / 2; l++) { while (r < n&&a[r] - a[l] < z) { r++; } if (r == n) { cout << ans; return 0; } r++; ans++; } cout << ans; return 0; }
|
E. Proper Nutrition
暴力/拓展欧几里得
神奇的题目,按常理来说应该用拓展欧几里得,但是直接暴力搜就过了,而且时间和用欧几里得是一样的。。可能是我优化地不够,但是爆搜时间真的很快。
先上扩展欧几里得版本
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<stdio.h> #include<cmath> #include<algorithm> #include<cstring> #include<string> #include<vector> using namespace std; #define ll long long const int maxn = 1e7 + 5; int n, a, b; int exgcd(int a, int b, ll& x, ll& y) { if (b == 0) { x = 1; y = 0; return a; } int t = exgcd(b, a%b, x, y); ll tmp = x; x = y; y = tmp - (a / b)*y; return t; } int main() { cin.sync_with_stdio(false); cin >> n >> a >> b; ll x, y; int m = exgcd(a, b, x, y); if (n%m != 0) { cout << "NO"; } else { x *= (n / m); y *= (n / m); while (x < 0) { x += b; y -= a; } while (y<0) { x -= b; y += a; } if (x < 0 || y < 0)cout << "NO"; else { cout << "YES" << endl; cout << x << ' ' << y; } } return 0; }
|
然后是爆搜
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
| #include<iostream> #include<algorithm> #include<cstring> #include <functional> #include<string> #include<vector> using namespace std; #define ll long long const int maxn = 1e7 + 5; int n; int a, b; int x, y; int main() { cin >> n; cin >> a >> b; for (int i = 0; i*a <= n; i++) { if ((n - i*a) % b == 0) { cout << "YES" << endl; cout << i << ' ' << (n - i*a) / b; return 0; } } cout << "NO" << endl; return 0; }
|
F. The Door Problem
2-sat模板题
并查集
当初刚学并查集的时候做到过类似题目,但是当时并不知道这是一类问题,也就没记,现在又做到了,以后不能再忘了!
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
| #include<iostream> #include<stdio.h> #include<cmath> #include<algorithm> #include<cstring> #include<string> #include<vector> using namespace std; #define ll long long const int maxn = 2e5 + 5; int n, m; int a[maxn]; vector<int>g[maxn]; int par[maxn], rk[maxn]; void init(int n) { for (int i = 0; i < n; i++) { par[i] = i; rk[i] = 0; } } int find(int x) { if (par[x] == x) { return x; } else { return par[x] = find(par[x]); } } void unite(int x, int y) { x = find(x); y = find(y); if (x == y)return; if (rk[x] < rk[y]) { par[x] = y; } else { par[y] = x; if (rk[x] == rk[y])rk[x]++; } } bool same(int x, int y) { return find(x) == find(y); } int main() { cin.sync_with_stdio(false); cin >> n >> m; init(2 * m); for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 0; i < m; i++) { int t; cin >> t; for (int j = 0; j < t; j++) { int u; cin >> u; g[u].push_back(i); } } for (int i = 1; i <= n; i++) { int x = g[i][0], y = g[i][1]; if (a[i]) { unite(x, y); unite(x + m, y + m); } else { unite(x + m, y); unite(x, y + m); } } for (int i = 0; i < m; i++) { if (same(i, i + m)) { cout << "NO" << endl; return 0; } } cout << "YES" << endl; return 0; }
|
G. The Brand New Function
枚举+剪枝
直接暴力枚举各个区间,set维护答案。
对每一个区间起始点,开始枚举区间结束点前设置一个check变量ck=0,若以后在枚举到某一个区间结束点时,ck与要压入set的答案相等,说明当前点再继续枚举下去的话,和a[i]=0的效果是一样的,那么这时就可以把区间起始点往右移动了。
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
| #include<iostream> #include<stdio.h> #include<cmath> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<set> using namespace std; #define ll long long const int maxn = 1e5 + 5; int n; int a[maxn]; set<int>ans; int main() { cin.sync_with_stdio(false); cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < n; i++) { int tp = a[i]; int ck = 0; ans.insert(a[i]); for (int j = i + 1; j < n; j++) { tp |= a[j]; ck |= a[j]; ans.insert(tp); if (tp == ck) { break; } } } cout << ans.size(); return 0; }
|
H. Barcode
dp
因为前一天刚好在CCPC女生赛中做到String,也是道dp题,感觉差不多,所以自然想到了dp,但是不知道应该dp什么,最后还是看了眼题解。
dp[i] [j] [k]表示处理完第i列,当前列有j列连续,当前列颜色为0或1.
知道dp意义后,之后的都是自己想出来的了,虽然dp意义更重要,但也算是迈了第一步。0.o
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
| #include<iostream> #include<stdio.h> #include<cmath> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<set> using namespace std; #define ll long long int n, m, x, y; char mz[1005][1005]; int dp[1005][1005][2]; int num[1005]; int main() { cin.sync_with_stdio(false); cin >> n >> m >> x >> y; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> mz[i][j]; if (mz[i][j] == '#')num[j]++; } } memset(dp, 0x3f, sizeof(dp)); dp[0][1][0] = num[0]; dp[0][1][1] = n - num[0]; for (int i = 1; i < m; i++) { for (int j = x; j <= y; j++) { dp[i][1][0] = min(dp[i][1][0], dp[i - 1][j][1] + num[i]); dp[i][1][1] = min(dp[i][1][1], dp[i - 1][j][0] + n - num[i]); } for (int j = 2; j <= min(y, i + 1); j++) { dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j - 1][0] + num[i]); dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j - 1][1] + n - num[i]); } } int ans = 0x3f3f3f3f; for (int i = x; i <= y; i++) { ans = min(ans, dp[m - 1][i][0]); ans = min(ans, dp[m - 1][i][1]); } cout << ans; return 0; }
|
I. Producing Snow
优先队列
把当天和之前的V都存在优先队列里,这样方便删除已经V已经变成0的雪堆,而且借助size()不用一个个遍历加。
注意精度
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<iostream> #include<stdio.h> #include<cmath> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<set> #include<queue> using namespace std; #define ll long long const int maxn = 1e5 + 5; int N; int V[maxn], T[maxn]; priority_queue<ll, vector<ll>, greater<ll> >q; int main() { cin.sync_with_stdio(false); cin >> N; for (int i = 1; i <= N; i++) { cin >> V[i]; } ll pre = 0; for (int i = 1; i <= N; i++) { ll ans = 0; int T; cin >> T; q.push(pre + V[i]); while (!q.empty()) { ll tp = q.top(); if (tp <= pre + T) { ans += tp - pre; q.pop(); } else { break; } } ans += q.size()*T; pre += T; cout << ans << ' '; } return 0; }
|
K. Ice Skating
并查集
若两个点的x或者y相同,则把他们放一堆,最后答案=堆数-1.
注意每个点可能不止和一个点合并,所以要检查它之前的所有点,我第一次是找到一个就break了,结果会变大。
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
| #include<iostream> #include<algorithm> #include<cstring> #include <functional> #include<string> #include<vector> using namespace std; #define ll long long int n; int par[105], rk[105]; int x[105], y[105]; void init(int n) { for (int i = 0; i < n; i++) { par[i] = i; rk[i] = 0; } } int find(int x) { if (par[x] == x) { return x; } else { return par[x] = find(par[x]); } } void unit(int x, int y) { x = find(x); y = find(y); if (x == y)return; if (rk[x] < rk[y]) { par[x] = y; } else { par[y] = x; if (rk[x] == rk[y])rk[x]++; } } bool same(int x, int y) { return find(x) == find(y); } int main() { cin >> n; init(n); for (int i = 0; i < n; i++) { cin >> x[i] >> y[i]; for (int j = 0; j < i; j++) { if (x[i] == x[j] || y[i] == y[j]) { unit(i, j); } } } int ans = -1; for (int i = 0; i < n; i++) { if (par[i] == i)ans++; } cout << ans << endl; return 0; }
|