Codeforces Round #652 (Div. 2) 总结
A:问正n边形的一条边和x轴平行的时候有没有一条边和y轴重合，直接判断n是否是4的倍数
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <map> #include <cmath> #include <queue> #include <set> #define rep(i,j,k) for(int i = j; i <= k; i++) #define dow(i,j,k) for(int i = j; i >= k; i--) #define ez(i,x) for(int i = h[x]; i; i = e[i].next) #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int,int> pi; int main() { int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); if (n % 4 == 0) puts("YES"); else puts("NO"); } }
B题：给一个01串每次可以从连续的“10”中删去0或1（不能同时删去），问可以得到的最小字典序字符串。
字符串中开头的0是去不掉的，末尾的1是去不掉的。中间是1开头的01串，可以发现这堆东西能变成一个”0″。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <map> #include <cmath> #include <queue> #include <set> #include <stack> #define rep(i,j,k) for(int i = j; i <= k; i++) #define dow(i,j,k) for(int i = j; i >= k; i--) #define ez(i,x) for(int i = h[x]; i; i = e[i].next) #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int,int> pi; const int N = 1e5 + 100; char s[N]; int top; int n; char a[N]; void solve() { scanf("%d", &n); memset(a, 0, sizeof (a)); memset(s, 0, sizeof (s)); top = 0; scanf("%s", a + 1); int f = 0; rep(i,1,n) { if (!f && a[i] == '0') { putchar(a[i]); continue; } if (a[i] == '1') f = 1, s[++top] = a[i]; if (a[i] == '0') top = 1, s[1] = '0'; } rep(i,1,top) putchar(s[i]); puts(""); } int main() { int t; scanf("%d", &t); while (t--) { solve(); } }
C题：给你n个数字，分给k个小伙伴，每个人分得w_i个数字，小伙伴的快乐值是他得到的数字中的最大值加最小值。求所有小伙伴快乐值的和最大是多少。
首先把小伙伴按分得数字个数从小到大排序，数字按从大到小排序。先把最大的k个按这样的顺序分给大家每人一个，然后剩下的数字从第一个小伙伴开始给，到这个小伙伴拿够，给下一个人。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <map> #include <cmath> #include <queue> #include <set> #include <stack> #define rep(i,j,k) for(int i = j; i <= k; i++) #define dow(i,j,k) for(int i = j; i >= k; i--) #define ez(i,x) for(int i = h[x]; i; i = e[i].next) #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int,int> pi; const int N = 2e5 + 100; int w[N], a[N], n, k; void solve() { scanf("%d %d", &n, &k); ll ans = 0; rep(i,1,n) scanf("%d", &a[i]); rep(i,1,k) scanf("%d", &w[i]); sort(a + 1, a + n + 1); sort(w + 1, w + k + 1); reverse(a + 1, a + n + 1); rep(i,1,k) ans += a[i]; int cnt = k; rep(i,1,k) { if (w[i] >= 1) { if (w[i] == 1) ans += a[i]; else { while (w[i] != 1) { cnt++; w[i]--; } ans += a[cnt]; } } } printf("%lld\n", ans); } int main() { int t; scanf("%d", &t); while(t--) { solve(); } }
D:有一个叫RDB的有根树。一阶RDB只有根结点。i阶RDB是在i-1阶的RDB上发生一些变化：对于没有儿子的节点，长出一个儿子；有一个儿子的节点，再长两个儿子，其余节点不发生变化。钦定一个点和他的三个儿子叫做爪子。然后问你在n阶段RDB上最多能找到多少个不重叠的爪子。
问题在有三个儿子的结点什么时候会被选什么时候不会被选。当这个结点第一次有三个儿子的时候，选这个结点，一定不比选他的父亲那个结点差，这个时候必选这个结点。更高一阶他中间的儿子结点将有三个儿子，更高两阶他的左右两个儿子会有三个儿子，这时候显然不选这个结点。而更高3阶的时候就会选这个结点。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <map> #include <cmath> #include <queue> #include <set> #include <stack> #define rep(i,j,k) for(int i = j; i <= k; i++) #define dow(i,j,k) for(int i = j; i >= k; i--) #define ez(i,x) for(int i = h[x]; i; i = e[i].next) #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int,int> pi; const int N = 2e6 + 100; const int mod = 1e9 + 7; ll f[N][10]; void init(){ f[1][1] = 1; rep(i,2,2000000) { f[i][5] = f[i-1][4]; f[i][4] = f[i-1][3]; f[i][3] = (f[i-1][5] + f[i-1][2]) % mod; //temp = f[2]; f[i][2] = f[i-1][1]; f[i][1] = (f[i-1][1] + 2 * f[i-1][2]) % mod; } } void solve() { int n; scanf("%d", &n); printf("%lld\n",f[n][3] * 4 % mod); } int main() { init(); int t; scanf("%d", &t); while (t--) { solve(); } }
View Code
E:你有一些朋友，每个人有两道爱吃的菜x_i, y_i。然后每道菜有w_i份。当一个朋友来的时候会吃ta喜欢的菜，如果有两道就吃两道，有一道就吃一道，如果没有就会吃了你。请问你应该怎么安排朋友吃菜的顺序，来让大家都吃到至少一道自己喜欢吃的菜，或者无论怎么安排都会有人吃不到。
设喜欢吃某道菜的人数为s_i，如果所有的s_i 都小于 w_i那么就无解，显然最后一个人的菜一定都被别人吃光了。对于wi >= si的菜，这些人多会吃都有关系。所以我们放在后面，这样他们就会吃的少一点。然后按照这种方法一直做就好了。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <map> #include <cmath> #include <queue> #include <set> #include <stack> #define rep(i,j,k) for(int i = j; i <= k; i++) #define dow(i,j,k) for(int i = j; i >= k; i--) #define ez(i,x) for(int i = h[x]; i; i = e[i].next) #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int,int> pi; const int N = 2e5 + 100; const int mod = 1e9 + 7; int n, m; vector<int> d[N]; int s[N], w[N], a[N], b[N], vis[N]; int ans[N], cnt = 0; int main() { scanf("%d%d", &n, &m); rep(i,1,n) scanf("%d", &w[i]); rep(i,1,m) { scanf("%d %d", &a[i], &b[i]); s[a[i]]++; s[b[i]]++; d[a[i]].push_back(i); d[b[i]].push_back(i); } queue<int> q; rep(i,1,n) if (s[i] <= w[i]) q.push(i); while (!q.empty()) { int j = q.front(); q.pop(); int _ = (int)d[j].size(); rep(i,0,_-1) { if (!vis[d[j][i]]) { int u = a[d[j][i]], v = b[d[j][i]]; if (u == j) swap(u, v); s[u]--; if (s[u] == w[u]) q.push(u); vis[d[j][i]] = 1; ans[++cnt] = d[j][i]; } } } if (cnt < m) { puts("DEAD"); return 0; } puts("ALIVE"); reverse(ans + 1, ans + cnt + 1); rep(i,1,cnt) printf("%d ", ans[i]); puts(""); }
f题：有一个游戏，有两个数s，e每次可以把s变成s + 1或者是s * 2，当s大于e时，就输了。有n轮游戏，每轮游戏输的人先手开始下一轮游戏。在最后一轮赢了的人，赢得了游戏。在最后一轮输的人，输掉了游戏。
问先手能否必胜，同时先手能否一定失败。
定义一下win(s,e)和lose(s,e)表示先手是否能一定赢和一定输。
e是奇数的时候s奇数必败s是偶数必胜。（可以自己写一写看一下）。e是偶数的时候，s大于e/2，s是奇数必胜，偶数必败。s大于e/4的时候，无论s是什么都能必胜。否则就是win(s, e/4)
对于先手强制输的情况，如果s * 2 > e一定可以输，否则等价于win(s, e / 2)
然后对于游戏的输赢就是，就是从最后局开始递归，如果这局能先手必胜（败），上一局就必须要输，否则上一局就必须要赢。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 #include <map> 7 #include <cmath> 8 #include <queue> 9 #include <set> 10 #define rep(i,j,k) for(int i = j; i <= k; i++) 11 #define dow(i,j,k) for(int i = j; i >= k; i--) 12 #define ez(i,x) for(int i = h[x]; i; i = e[i].next) 13 #define fi first 14 #define se second 15 using namespace std; 16 17 18 typedef long long ll; 19 typedef pair<int,int> pi; 20 21 const int N = 1e5 + 100; 22 ll e[N], s[N]; 23 bool w[N], l[N]; 24 int n; 25 26 bool Win(ll s, ll e) { 27 if ((e & 1)) { 28 if (s & 1) return 0; 29 return 1; 30 } 31 if (s > e) return 1; 32 if (s * 2 > e) return (bool)(s & 1); 33 if (s * 4 > e) return 1; 34 return Win(s, e / 4); 35 } 36 37 bool Lose(ll s, ll e) { 38 if (s * 2 > e) return 1; 39 return Win(s, e / 2); 40 } 41 42 int getWin(int); 43 int getLose(int); 44 45 int getWin(int x) { 46 if (x == 1) return (int)w[1]; 47 return w[x]? getLose(x - 1) : getWin(x - 1); 48 } 49 50 int getLose(int x) { 51 if (x == 1) return (int)l[1]; 52 return l[x]? getLose(x - 1) : getWin(x - 1); 53 } 54 int main() { 55 //ios::sync_with_stdio(0); 56 scanf("%d", &n); 57 rep(i,1,n) { 58 scanf("%lld %lld", &s[i], &e[i]); 59 w[i] = Win(s[i], e[i]); 60 l[i] = Lose(s[i], e[i]); 61 // cout << w[i] << " " << l[i] << endl; 62 } 63 printf("%d %d\n",getWin(n), getLose(n));
版权声明：本文为Fermat原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。