首页 > 其他 > 详细

Codeforces Round 594 Div. 2

时间:2019-11-14 12:04:50      阅读:68      评论:0      收藏:0      [点我收藏+]

比赛传送门

得出经验,打\(CF\)倒着开题比较爽。C题看了好久,没找到规律,看了看其他题,发现最后一题是个半裸的Tarjan
暴涨\(236\)分,飘了
不过新的名字颜色好丑,像\(\color{blue}{\text{电脑蓝屏的那种蓝}}\)


A. Integer Points

偶数会和偶数交于整数点,奇数会和奇数交于整数点

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
LL read() {
    LL k = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
        k = k * 10 + c - 48, c = getchar();
    return k * f;
}
int main() {
    int t = read();
    while(t--) {
        LL odd1 = 0, odd2 = 0, even1 = 0, even2 = 0;
        int n = read();
        for(int i = 1; i <= n; ++i) {
            int x = read();
            if(x & 1) ++odd1;
            else ++even1;
        }
        int m = read();
        for(int i = 1; i <= m; ++i) {
            int x = read();
            if(x & 1) ++odd2;
            else ++even2;
        }
        LL ans = odd1 * odd2 + even1 * even2;
        printf("%lld\n", ans);
    }
    return 0;
}

B. Grow The Tree

如果没有限制,将这几根木棍拼成一条直线显然是最长的
但要求必须水平-竖直-水平-竖直……这样交错着拼
显然,使水平(或竖直)的木棍的长度之和尽量小,答案就会尽量大(因为此时拼出来的图形会趋近于一条直线)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
LL read() {
    LL k = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
        k = k * 10 + c - 48, c = getchar();
    return k * f;
}
LL a[100010];
int main() {
    int n = read();
    LL sum1 = 0, sum2 = 0;
    for(int i = 1; i <= n; ++i) a[i] = read(), sum2 += a[i];
    sort(a+1, a+n+1);
    for(int i = 1; i <= n/2; ++i) sum1 += a[i];
    sum2 -= sum1;
    sum1 *= sum1, sum2 *= sum2;
    printf("%lld\n", sum1 + sum2);
    return 0;
}

C. Ivan the Fool and the Probability Theory

找规律,并不会证明。一开始根本不会做,做完F题后回来找规律,最后压哨AC(最后这道题的分衰减到连B题都不如)

不妨设\(n < m\)
\(f_0 = 2,f_1=2, f_i = f_{i-1} + f_{i-2}, i \leq n\)
\(f2_1 =f_n, f2_i = f2_{i-1} + f_{i-2}, i \leq m\)
最后答案就是\(f2_m\)

翻了翻别人的代码,发现他们找的规律都是\(f_0 = 2,f_1=2, f_i = f_{i-1} + f_{i-2}, i \leq \max{n, m}\),答案是\(f_n + f_m -2\)。其实都是一个道理 (只不过我的规律麻烦一些)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define mod 1000000007
using namespace std;
LL read() {
    LL k = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
        k = k * 10 + c - 48, c = getchar();
    return k * f;
}
LL f[100010], f2[100010];
int main() {
    int n = read(), m = read();
    if(n > m) swap(n, m);
    f[0] = f[1] = 2;
    for(int i = 2; i <= m; ++i) f[i] = (f[i-1] + f[i-2]) % mod;
    f2[1] = f[n];
    for(int i = 2; i <= m; ++i) {
        f2[i] = (f2[i-1] + f[i-2]) % mod;
    }
    cout << f2[m];
    return 0;
}

F. Catowice City

说一说我的心路历程:
C题想了半天,没什么思路,先去看看别的题吧。D题:什么鬼题目,看不懂题意。E题:看不懂+1,而且感觉好麻烦,看看排行榜,woc,AC率好低。
心如死灰的打开F题:题意好歹能读懂,是个图论题,二分图染色?对着样例模拟了一下,不太对。又读了一遍题,画了画样例。等等,这不是道Tarjan缩点裸题吗。遂A之
排行榜上,我周围的人都A了 A、B、C、D1,我这个A了 A、B、F题的人显得如此的格格不入……

回归正题
将自环全部去掉,然后Tarjan缩点,如果缩成了一个点,则无解
否则,找一个入度为零的点,将它集合内的所有点标记为运动员,其他的点标记为陪审团
显然,这样构造一定是符合条件的

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define mod 1000000007
using namespace std;
LL read() {
    LL k = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
        k = k * 10 + c - 48, c = getchar();
    return k * f;
}
struct zzz {
    int f, t, nex;
}e[1000010 << 1]; int head[1000010], tot;
void add(int x, int y) {
    e[++tot].t = y;
    e[tot].f = x;
    e[tot].nex = head[x];
    head[x] = tot;
}
int vis[1000010], dfn[1000010], low[1000010], colnum, belong[1000010], deth, s[1000010], top;
int in[1000010];
void Tarjan(int x) {
    low[x] = dfn[x] = ++deth;
    s[++top] = x; vis[x] = 1;
    for(int i = head[x]; i; i = e[i].nex) {
        if(!dfn[e[i].t]) {
            Tarjan(e[i].t);
            low[x] = min(low[x], low[e[i].t]);
        }
        else
          if(vis[e[i].t]) low[x] = min(low[x], dfn[e[i].t]);
    }
    if(dfn[x] == low[x]) {
        ++colnum; int k=0;
        do {
            k = s[top--];
            belong[k] = colnum;
            vis[k] = 0;
        }while(k != x);
    }
}
int main() {
    int t = read();
    while(t--) {
        int n = read(), m = read(); tot = top = deth = colnum = 0;
        for(int i = 1; i <= n; ++i)
            head[i] = vis[i] = low[i] = belong[i] = dfn[i] = in[i] = 0;
        for(int i = 1; i <= m; ++i) {
            int x = read(), y = read(); if(x == y) continue;
            add(x, y);
        }
        for(int i = 1; i <= n; ++i)
            if(!dfn[i]) Tarjan(i);
        if(colnum == 1) printf("NO\n");
        else {
            int cnt = tot, pos = 0;
            for(int i = 1; i <= cnt; ++i)
                if(belong[e[i].f] != belong[e[i].t])
                    ++in[belong[e[i].t]];
            for(int i = 1; i <= colnum; ++i)
                if(!in[i]) pos = i;
            int num = 0;
            for(int i = 1; i <= n; ++i)
                if(belong[i] == pos) ++num;
            printf("YES\n%d %d\n", n - num, num);
            for(int i = 1; i <= n; ++i)
                if(belong[i] != pos) printf("%d ", i);
            printf("\n");
            for(int i = 1; i <= n; ++i)
                if(belong[i] == pos) printf("%d ", i);
        }
    }
    return 0;
}

Codeforces Round 594 Div. 2

原文:https://www.cnblogs.com/morslin/p/11855923.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!