Codeforces Round #395 (Div. 2)（未完）-白红宇

Codeforces Round #395 (Div. 2)（未完）

阅读量：6242 次

发布时间：2019-06-22

本文共 3748 字，大约阅读时间需要 12 分钟。

2.2.2017 9:35~11:35

直接模拟

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef long long ll;const int N=1e4+5;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
    if(c=='-')f=-1; c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}    return x*f;}int n,m,z,ans;int vis[N];int main(int argc, const char * argv[]) {    n=read();m=read();z=read();    for(int i=n;i<=z;i+=n) vis[i]=1;    for(int i=m;i<=z;i+=m) ans+=vis[i];    printf("%d",ans);    return 0;}

View Code

奇数位置反转，偶数位置不变

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef long long ll;const int N=2e5+5;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
    if(c=='-')f=-1; c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}    return x*f;}int n,a[N];int main(int argc, const char * argv[]) {    n=read();    for(int i=1;i<=n;i++) a[i]=read();    for(int i=1;i<=n/2;i++) if(i&1) swap(a[i],a[n-i+1]);    for(int i=1;i<=n;i++) printf("%d ",a[i]);    return 0;}

View Code

题意：选一个根使得所有子树同色(每个子树中节点同色不同子树可以不同色)

比赛时先打了个傻逼树形DP发现不对然后就用对于一个点i它的子树用树形DP，它的上面的树用DFS序+线段树/ST表询问颜色相同......反正A掉了

////  main.cpp//  C////  Created by Candy on 2017/2/2.//  Copyright © 2017年 Candy. All rights reserved.//#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;#define mid ((l+r)>>1)#define lson x<<1,l,mid#define rson x<<1|1,mid+1,r#define lc x<<1#define rc x<<1|1typedef long long ll;const int N=2e5+5;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
    if(c=='-')f=-1; c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}    return x*f;}int n,u,v,c[N],a[N];struct edge{    int v,ne;}e[N<<1];int h[N],cnt=0;inline void ins(int u,int v){    cnt++;    e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;    cnt++;    e[cnt].v=u;e[cnt].ne=h[v];h[v]=cnt;}struct node{    int same;}t[N<<2];void build(int x,int l,int r){    if(l==r) t[x].same=a[l];    else{        build(lson);        build(rson);        if(t[lc].same==0||t[rc].same==0||t[lc].same!=t[rc].same) t[x].same=0;        else t[x].same=t[lc].same;    }}int segSame(int x,int l,int r,int ql,int qr){    if(ql>qr) return -1;    if(t[x].same) return t[x].same;    if(ql<=l&&r<=qr) return t[x].same;    else{        int same=-1;        if(ql<=mid) same=segSame(lson,ql,qr);        if(mid

比赛代码

实际上可以发现如果一条边两边节点的颜色不对一定是这两个节点中的一个做根，三遍DFS就行了....好简单

dfs

题意：一些不相交矩形边长都是奇数 4种颜色染色判断可行及一种方案

....最后才看到洛谷群有这道题题解然后最后10s提交失败呜呜呜

超简单边长奇数，所以横边相邻的矩形y坐标奇偶性不同 x同理所以按左下角奇偶性染色就行了

////  main.cpp//  C////  Created by Candy on 2017/2/2.//  Copyright © 2017年 Candy. All rights reserved.//#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef long long ll;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
    if(c=='-')f=-1; c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}    return x*f;}int n,x,y;int main(int argc, const char * argv[]) {    n=read();    puts("YES");    for(int i=1;i<=n;i++){        x=read();y=read();        x=min(x,read());y=min(y,read());        x+=1e9;y+=1e9;        if(x&1){            if(y&1) puts("1");            else puts("2");        }else{            if(y&1) puts("3");            else puts("4");        }    }}