Codeforces Round #530 (Div. 1)-白红宇

Codeforces Round #530 (Div. 1)

阅读量：6429 次

发布时间：2019-06-23

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

A - Sum in the tree

就是贪心选尽量让上面的点权尽量大，那么对于偶数层的点，其到根节点的和即为所有儿子中的最大值。

#include
    
     using namespace std;char gc() {//  static char buf[100000],*p1,*p2;//  return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin))?EOF:*p1++;    return getchar();}template
     
      int read(T &ans) {    T f=1;ans=0;    char ch=gc();    while(!isdigit(ch)) {        if(ch==EOF) return EOF;        if(ch=='-') f=-1;        ch=gc();    }    while(isdigit(ch))        ans=ans*10+ch-'0',ch=gc();    ans*=f;return 1;}template
      
       int read(T1 &a,T2 &b) {    return read(a)==EOF?EOF:read(b);}template
       
        int read(T1 &a,T2 &b,T3 &c) {    return read(a,b)==EOF?EOF:read(c);}typedef long long ll;const int Maxn=1100000;const int inf=0x3f3f3f3f;const ll mod=1000000007;int s[Maxn],to[Maxn],nxt[Maxn],first[Maxn],tot=1;int n,x,flag;ll ans;inline void add(int u,int v) {    to[tot]=v;    nxt[tot]=first[u];    first[u]=tot++;}void dfs(int root) {    if(s[root]==-1) {        int temp=inf;        for(int i=first[root];i;i=nxt[i]) {            dfs(to[i]);            temp=min(temp,s[to[i]]);        }        s[root]=temp;        for(int i=first[root];i;i=nxt[i]) {            ans+=s[to[i]]-s[root];        }    }    else {        for(int i=first[root];i;i=nxt[i]) {            dfs(to[i]);            if(s[to[i]]==inf) s[to[i]]=s[root];            if(s[to[i]]

B - Nice table

这个结论就是要么是对于每一行都只有两种字符或每一列都只有两种字符。至于为什么。。自己感性理解一下就好了。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define qmin(x,y) (x=min(x,y))#define qmax(x,y) (x=max(x,y))using namespace std;inline char gc() {// static char buf[100000],*p1,*p2;// return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; return getchar();}template
           
            int read(T &ans) { ans=0;char ch=gc();T f=1; while(!isdigit(ch)) { if(ch==EOF) return -1; if(ch=='-') f=-1; ch=gc(); } while(isdigit(ch)) ans=ans*10+ch-'0',ch=gc(); ans*=f;return 1;}template
            
             int read(T1 &a,T2 &b) { return read(a)!=EOF&&read(b)!=EOF?2:EOF;}template
             
              int read(T1 &a,T2 &b,T3 &c) { return read(a,b)!=EOF&&read(c)!=EOF?3:EOF;}typedef long long ll;const int Maxn=310000;const int inf=0x3f3f3f3f;char t[4]={'A','T','C','G'};string a[Maxn],b[Maxn];int w[Maxn][4][4],w1[Maxn][4][4];int p[4],p1[4],p2[4],n,m;inline bool check() { return p[1]!=1||p[2]!=2||p[3]!=3||p[0]!=0;}int calc() { int ans=0; for(int i=0,t=2;i
              
               >a[i]; for(int i=0;i
               
                w1[j][p1[1]][p1[0]])^(i&1)]]); else putchar(t[p1[(w1[j][p1[2]][p1[3]]>w1[j][p1[3]][p1[2]])^(i&1)+2]]); else for(int i=0;i
                
                 w[i][p2[1]][p2[0]])^(j&1)]]); else putchar(t[p2[(w[i][p2[2]][p2[3]]>w[i][p2[3]][p2[2]])^(j&1)+2]]); return 0;}

C - Construct a tree

首先就是分叉数越大，其对应的所有子树的大小和越小。那么依次枚举判断，如果合法构造即可。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define qmin(x,y) (x=min(x,y))#define qmax(x,y) (x=max(x,y))using namespace std;inline char gc() {//  static char buf[100000],*p1,*p2;//  return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;    return getchar();}template
         
          int read(T &ans) { ans=0;char ch=gc();T f=1; while(!isdigit(ch)) { if(ch==EOF) return -1; if(ch=='-') f=-1; ch=gc(); } while(isdigit(ch)) ans=ans*10+ch-'0',ch=gc(); ans*=f;return 1;}template
          
           int read(T1 &a,T2 &b) { return read(a)!=EOF&&read(b)!=EOF?2:EOF;}template
           
            int read(T1 &a,T2 &b,T3 &c) { return read(a,b)!=EOF&&read(c)!=EOF?3:EOF;}typedef long long ll;const int Maxn=110000;const int inf=0x3f3f3f3f;int n,a[Maxn],p[Maxn];ll s;ll check(int x) { ll res=n,temp=1,ans=0; for(int i=1;res;i++) { qmin(temp,res); ans+=temp*i; res-=temp; temp*=x; } return ans;}void work(int x) { a[1]=1;s--; ll res=n-1,temp=x,t=2; for(;res;t++) { qmin(temp,res); s-=temp*t; a[t]=temp; res-=temp; temp*=x; } for(int i=t-1;s;i--) { while(a[i]>1) { a[i]--; s+=i; if(s>t) { s-=t; a[t++]++; } else { a[s]++; s=0; break; } } } int sum=0,tempp=1; for(int i=1;i
            
             s) { puts("No"); return 0; } for(int i=2;i<=n;i++) if(check(i)<=s) { puts("Yes"); work(i); return 0; } return 0;}