45°

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));

 

本文转载自博客园,原文链接:https://www.cnblogs.com/Fermat/p/13199033.html

全部评论: 0

    我有话说: