Codeforces Round #395 (Div. 2)(ABCD)

柔情只为你懂 2022-07-11 15:24 151阅读 0赞

**ps**:打完这场cf才知道自己真的很菜，还是停留在AB题的水平，有时候CD其实很简单，但就是想不到，别人一眼看出而我就是想不到，有时候想到了点子上但就是突破不了

**题目链接：** [ Codeforces Round \#395 (Div. 2)][Codeforces Round _395 _Div. 2]

A题：

题目思路：这题实际上就是求n序列和m序列公共的部分并且在z的范围内，所以答案就是z/lcm(n,m)(最小公倍数)

AC代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<vector>
    #include<string>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<map>
    #include<set>
    using namespace std;
    
    #define lcr(a,b) memset(a,b,sizeof(a))
    #define ll long long
    #define INF 0x7fffffff
    #define esp 1e-8
    
    int main()
    {
       int n,m,k;
       cin>>n>>m>>k;
       int lcm = n*m/__gcd(n,m);
       cout<<k/lcm<<endl;
       return 0;
    }

\------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

题目分割线

B题：

题目思路：给你一组交换后的序列，要你求原来的序列，交换规则为:每次交换子序列 \[i,n-i+1\]让第i个与第n-i+1个交换

（i<=n-i+1）遍历i到n/2，所以我们知道第一个数只在i==1时交换了一次，第二个数在i==1和i==2交换了，，，所以                               我们就可以知道当i%2==1时数字才交换了，反之交换的次数为偶数相当于没有交换

AC代码：

\------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

题目分割线

C题：

题目思路：给你一颗n个节点的树，每个节点都有对应的颜色，问你可不可以删除一个节点，使得它的每棵子树都只

有一种颜色，这题其实有很多种方法，很多大牛想到用树链剖分，线段树来做，我这渣渣就只会用dfs暴力

来做，刚开始觉得1e5个点如果暴力每个根的话会超时，但是这题如果想通了一个点就很简单了，如果一旦

两个直接相连的点颜色不同那么他们两必定有一个为根，很好想到如果其他点来做根，那么这两个相连的点

一定会使得那个跟不成立，所以这样一来这个题就很简单，只需dfs两次就行，时间复杂度依旧是O(n)

还有其他大神有一种更加简单的方法，也是O(n) ，我们定义br\[i\]为与i相连的点当中有多少对不同颜色的对数

tot为总的不同颜色的对数，所以当br\[i\]==tot时就说明此时跟节点i成立，

AC代码：

方法一：dfs

#include<algorithm>
    #include<iostream>
    #include<stdlib.h>
    #include<cstring>
    #include<stdio.h>
    #include<vector>
    #include<string>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<map>
    #include<set>
    using namespace std;
    
    #define lcr(a,b) memset(a,b,sizeof(a))
    #define ll long long
    #define INF 0x7fffffff
    #define esp 1e-8
    
    const int maxn = 1e5+10;
    
    struct st{
        int v,nex;
    }edge[maxn<<1];
    
    int color[maxn],hed[maxn],e,vis[maxn],flag;
    int n;
    
    void add(int u,int v){
        edge[e].v=v,edge[e].nex=hed[u],hed[u]=e++;
    }
    
    void dfs(int s,int c){
        for(int i=hed[s];~i;i=edge[i].nex){
          int v = edge[i].v;
          if(!vis[v]){
            vis[v]=1;
            if(color[v]!=c){
                flag=0;
                return ;
            }
            dfs(v,c);
          }
       }
    }
    
    void sove(int s){
        lcr(vis,0);
        vis[s]=1;
        for(int i=hed[s];~i;i=edge[i].nex){
            int v = edge[i].v;
            if(!vis[v]){
                vis[v]=1;
                dfs(v,color[v]);
                if(!flag)return ;
            }
        }
    }
    
    int main()
    {
        cin>>n;
        lcr(hed,-1);
        e=1;
        for(int i=0;i<n-1;i++){
            int u,v;scanf("%d%d",&u,&v);
            add(u,v);
            add(v,u);
        }
        for(int i=1;i<=n;i++)scanf("%d",&color[i]);
    
        for(int i=1;i<=n;i++){
            for(int j=hed[i];~j;j=edge[j].nex){
                int v = edge[j].v;
                if(color[v]!=color[i]){
                    flag=1;
                    sove(i);
                    if(flag){
                        printf("YES\n%d\n",i);
                        return 0;
                    }else {
                        flag=1;
                        sove(v);
                        if(flag){
                            printf("YES\n%d\n",v);
                        }else{
                            printf("NO\n");
                        }
                        return 0;
                    }
                }
            }
    
        }
        printf("YES\n1\n");
        return 0;
    }

方法二：

#include<iostream>
    #include<cstdio>
    #include<vector>
    using namespace std;
    
    vector<int>edge[100005];
    int br[100005],c[100005];
    
    int main()
    {
        int n;cin>>n;
        int tot=0;
        for(int i=1;i<n;i++){
            int u,v;scanf("%d%d",&u,&v);
            edge[u].push_back(v);
            edge[v].push_back(u);
        }
    
        for(int i=1;i<=n;i++)scanf("%d",&c[i]),br[i]=0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<edge[i].size();j++){
                int v = edge[i][j];
                if(c[v]!=c[i]){
                    tot++;
                    br[v]++;
                    br[i]++;
                }
            }
        }
        for(int i=1;i<=n;i++){
            if(br[i]==tot){
                printf("YES\n%d\n",i);
                return 0;
            }
        }
        return printf("NO\n"),0;
    
        return 0;
    }

\-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------

题目分割线

D. Timofey and rectangles

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

One of Timofey's birthday presents is a colourbook in a shape of an infinite plane. On the plane *n* rectangles with sides parallel to coordinate axes are situated. All sides of the rectangles have **odd** length. Rectangles cannot intersect, but they can touch each other.

Help Timofey to color his rectangles in 4 different colors in such a way that every two rectangles touching each other by side would have different color, or determine that it is impossible.

Two rectangles intersect if their intersection has positive area. Two rectangles touch by sides if there is a pair of sides such that their intersection has non-zero length

![ee10eeb5940e7f1f4dd060ac5ff429fb9c30a72c.png][] The picture corresponds to the first example

Input

The first line contains single integer *n* (1 ≤ *n* ≤ 5·105) — the number of rectangles.

*n* lines follow. The *i*\-th of these lines contains four integers *x*1, *y*1, *x*2 and *y*2 ( - 109 ≤ *x*1 < *x*2 ≤ 109,  - 109 ≤ *y*1 < *y*2 ≤ 109), that means that points (*x*1, *y*1) and (*x*2, *y*2) are the coordinates of two opposite corners of the *i*\-th rectangle.

It is guaranteed, that all sides of the rectangles have **odd** lengths and rectangles don't intersect each other.

Output

Print "NO" in the only line if it is impossible to color the rectangles in 4 different colors in such a way that every two rectangles touching each other by side would have different color.

Otherwise, print "YES" in the first line. Then print *n* lines, in the *i*\-th of them print single integer *c**i* (1 ≤ *c**i* ≤ 4) — the color of *i*\-th rectangle.

Example

input

8
    0 0 5 3
    2 -1 5 0
    -3 -4 2 -1
    -1 -1 2 0
    -3 0 0 5
    5 2 10 3
    7 -3 10 2
    4 -2 7 -1

output

YES
    1
    2
    2
    3
    2
    2
    4
    1

D题：

题目思路：给你n个不想交的矩形并别边长为奇数（很有用）问你可以可以只用四种颜色给n个矩形染色使得相接触的

矩形的颜色不相同，我们首先考虑可不可能，我们分析下最多有几个矩形互相接触，两个时可以都互相接触

三个时也可以互相接触，而四个时怎么摆我们都不能让他们相互都接触，所以我们最多可以用三种不同颜色

的矩形去接触另一个矩形，因此我们就一定可以用四种颜色来染色，然后我们来考虑怎么染色，因为不存在相

交的情况，所以就拿**左下角**来分析，首先我们来分析下，

1，两个矩形要上下接触时：我们考虑纵坐标，**因为边长为奇数**，所以坐标必须的奇偶必须不同，

2，两个矩形左右接触：同理，横坐标奇偶不同，

3，两个矩形永远都不可能接触，通过上面两个结论我们很好得知当横纵坐标奇偶都相同时，不可能接触

有了上面的结论，我们先令横纵坐标都为奇数的矩形为颜色1，所有的1都不可能接触，

当纵坐标为偶数，横坐标为奇数，这样只能与1的矩形上下接触，此时颜色为2

当纵坐标为奇数，横坐标为偶数，这样与1只能左右接触，此时颜色为3

除了上面的就是颜色为4，这个算法的正确性是从上面三个结论得来的！**我们确定每种颜色矩形坐标的奇偶时，**

**                           就能保证相同颜色的矩形不可能相交！结论3**

AC代码：

#include<cstdio>
    
    #define abs(x) (x<0?-x:x)
    
    int x[500005],y[500005];
    
    int main()
    {
        int n;scanf("%d",&n);
        for(int i=1;i<=n;i++){
            int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
            x[i]=abs(a);
            y[i]=abs(b);
        }
        puts("YES");
        for(int i=1;i<=n;i++){
            if(x[i]%2==1&&y[i]%2==1)puts("1");
            else if(x[i]%2==1&&y[i]%2==0)puts("2");
            else if(x[i]%2==0&&y[i]%2==1)puts("3");
            else puts("4");
        }
        return 0;
    }

[Codeforces Round _395 _Div. 2]: http://codeforces.com/contest/764
[ee10eeb5940e7f1f4dd060ac5ff429fb9c30a72c.png]: /images/20220711/f09732c522864487b828c96013914a30.png