Codeforces Round #395 (Div. 2) A,B,C,D 题解

contest link: 点这里
快20天没打CF了，昨天打了一场，C题最后还FST了，感觉真是妙啊，掉分掉分。

A，水题

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a, b, c;
    cin >> a >> b >> c;
    int ans = 0;
    for(int i = 1; i <= c; i++){
        if(i%a == 0 && i %b == 0) ans++;
    }
    cout << ans << endl;
}

B, 水题

#include <bits/stdc++.h>
using namespace std;
int n, a[200010], ans[200010];
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    bool odd = 1;
        int l1 = 1, r1 = n;
    int l2 = 1, r2 = n;
    while(l1 <= r1)
    {
        if(odd)
        {
            ans[l2++] = a[r1];
            ans[r2--] = a[l1];
            l1++;
            r1--;
        }
        else
        {
            ans[l2++] = a[l1];
            ans[r2--] = a[r1];
            l1++;
            r1--;
        }
        odd ^= 1;
    }
    for(int i = 1; i <= n; i++) cout << ans[i] << " ";
}

C, 题意是让我们找到一个点，值得断开这个点之后，所有子树都要满足只能存在一种颜色，问能不能找到这个点？
我的做法是，直接对于每个点统计与他相连的点并且颜色和它不同的点的数目，最后这些点中>=2的超过两遍肯定无解，否则考虑只有一个，那么遍历找到>=2的就行了，没有的话，就遍历这个树，发现u和它的儿子节点颜色不同输出这个点就好了，如果整个图都相同输出1就好了。但是我这样FST了因为我少写了一个东西，考虑一下这个数据

1 2

1 3

3 5

3 6

1 4

4 7

4 8

1 3 1 1 1 1 1 2

我跑出来的答案是YES，正确应该是NO，因为我少考虑了子节点只有一个和父亲不同的点并且存在多种的情况，我们发现无解的情况肯定这种节点个数>=4，所以特判一下就可以A了，我好弱智啊。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
struct edge{
    int v, nxt;
}E[maxn*2];
int head[maxn], cnt;
void addedge(int u, int v){
    E[cnt].v = v, E[cnt].nxt = head[u], head[u] = cnt++;
}
int n, c[maxn], scc[maxn];
int main(){
    memset(head, -1, sizeof(head)); cnt = 0;
    scanf("%d", &n);
    for(int i = 1; i < n; i++){
        int u, v;
        scanf("%d%d", &u, &v);
        addedge(u, v);
        addedge(v, u);
    }
    int flag = 0;
    for(int i = 1; i <= n; i++) scanf("%d", &c[i]);
    for(int i = 1; i <= n; i++){
        scc[i] = 0;
        for(int j = head[i]; ~j; j = E[j].nxt){
            int v = E[j].v;
            if(v == i) continue;
            if(c[v] != c[i]) scc[i]++;
        }
        if(scc[i] == 1) flag++;
    }
    int tt = 0;
    for(int i = 1; i <= n; i++){
        if(scc[i] >= 2){
            tt++;
        }
    }
    //for(int i = 1; i <= n; i++) cout << scc[i] << " "; cout << endl;
    if(tt >= 2){
        printf("NO\n");
    }
    else if(tt == 1){
        printf("YES\n");
        for(int i = 1; i <= n; i++){
            if(scc[i] >= 2){
                printf("%d\n", i);
                break;
            }
        }
    }
    else{
        if(flag >= 4){
            printf("NO\n");
            return 0;
        }
        printf("YES\n");
        bool ok = 0;
        for(int i = 1; i <= n; i++){
            for(int j = head[i]; ~j; j = E[j].nxt){
                int v = E[j].v;
                if(v == i) continue;
                if(c[v] != c[i]){
                    printf("%d\n", i);
                    ok = 1;
                    break;
                }
            }
            if(ok) break;
        }
        if(ok == 0) printf("1\n");
    }
}

D，一直在想怎么把矩阵转化成图的那种？？？结果赛后看到大佬们说两个左上角的矩形的奇偶性肯定是不同的，仔细想了一下，卧槽？？？智商需要充值了啊，而且根据4色定理，这题肯定是有解的。。附上官方题解：http://codeforces.com/blog/entry/50205

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, x1, y1, x2, y2;
    scanf("%d", &n);
    printf("YES\n");
    while(n--){
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        x1 = abs(x1), y1 = abs(y1);
        printf("%d\n", (x1%2)*2 + (y1%2) + 1);
    }
    return 0;
}

E,留坑，待填，队友爸爸靠你了。