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 %  == ) 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 + ;

char s[N];

int  top;

int n;

char a[N];

void solve() {

    scanf("%d", &n);

    memset(a, , sizeof (a));

    memset(s, , sizeof (s));

    top = ;

    scanf("%s", a + );

    int f = ;

    rep(i,,n) {

        if (!f && a[i] == '') {

            putchar(a[i]);

            continue;

        }

        if (a[i] == '') f = , s[++top] = a[i];

        if (a[i] == '') top = , s[] = '';

    }

    rep(i,,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 + ;

int w[N], a[N], n, k;

void solve() {

    scanf("%d %d", &n, &k);

    ll ans = ;

    rep(i,,n) scanf("%d", &a[i]);

    rep(i,,k) scanf("%d", &w[i]);

    sort(a + , a + n + );

    sort(w + , w + k + );

    reverse(a + , a + n + );

    rep(i,,k) ans += a[i];

    int cnt = k;

    rep(i,,k) {

        if (w[i] >= ) {

            if (w[i] == ) ans += a[i];

            else {

                while (w[i] != ) {

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

const int mod = 1e9 + ;

ll f[N][];

void init(){

    f[][] = ;

    rep(i,,) {

        f[i][] = f[i-][];

        f[i][] = f[i-][];

        f[i][] = (f[i-][] + f[i-][]) % mod;

        //temp = f[2];

        f[i][] = f[i-][];

        f[i][] = (f[i-][] +  * f[i-][]) % mod;

    }

}

void solve() {

    int n;

    scanf("%d", &n);

    printf("%lld\n",f[n][] *  % mod);

}

int main() {

    init();

    int t;

    scanf("%d", &t);

    while (t--) {

        solve();

    }

}

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

const int mod = 1e9 + ;

int n, m;

vector<int> d[N];

int s[N], w[N], a[N], b[N], vis[N];

int ans[N], cnt = ;

int main() {

    scanf("%d%d", &n, &m);

    rep(i,,n) scanf("%d", &w[i]);

    rep(i,,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,,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,,_-) {

            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]] = ;

                ans[++cnt] = d[j][i];

            }

        }

    }

    if (cnt < m) {

        puts("DEAD");

        return ;

    }

    puts("ALIVE");

    reverse(ans + , ans + cnt + );

    rep(i,,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)

然后对于游戏的输赢就是，就是从最后局开始递归，如果这局能先手必胜（败），上一局就必须要输，否则上一局就必须要赢。

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

 const int N = 1e5 + ;

 ll e[N], s[N];

 bool w[N], l[N];

 int n;

 bool Win(ll s, ll e) {

     if ((e & )) {

         if (s & ) return ;

         return ;

     }

     if (s > e) return ;

     if (s *  > e) return (bool)(s & );

     if (s *  > e) return ;

     return Win(s, e / );

 }

 bool Lose(ll s, ll e) {

     if (s *  > e) return ;

     return Win(s, e / );

 }

 int getWin(int);

 int getLose(int);

 int getWin(int x) {

     if (x == ) return (int)w[];

     return w[x]? getLose(x - ) : getWin(x - );

 }

 int getLose(int x) {

     if (x == ) return (int)l[];

     return l[x]? getLose(x - ) : getWin(x - );

 }

 int main() {

     //ios::sync_with_stdio(0);

     scanf("%d", &n);

     rep(i,,n) {

         scanf("%lld %lld", &s[i], &e[i]);

         w[i] = Win(s[i], e[i]);

         l[i] = Lose(s[i], e[i]);

       //  cout << w[i] << " " << l[i] << endl;

     }

     printf("%d %d\n",getWin(n), getLose(n));

巴特西

Codeforces Round #652 (Div. 2) 总结

最新文章

热门文章