Codeforces Round #542 Div. 1-白红宇

Codeforces Round #542 Div. 1

阅读量：4351 次

发布时间：2019-06-07

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

　　A：显然对于起点相同的糖果，应该按终点距离从大到小运。排个序对每个起点取max即可。读题花了一年还wa一发，自闭了。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long long#define N 20010char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,m;int dis(int x,int y){ if (x<=y) return y-x; else return n-x+y;}struct data{ int x,y; bool operator <(const data&a) const { return x
           
            dis(a.x,a.y); }}a[N<<1];signed main(){#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout);#endif n=read(),m=read(); for (int i=1;i<=m;i++) a[i].x=read(),a[i].y=read(); sort(a+1,a+m+1); for (int i=1;i<=n;i++) { int ans=0; for (int j=1;j<=m;j++) { int t=j; while (t

　　B：考虑构造一个长度为n=2000的序列，前1998项都是0，第1999项是负数，第2000项是正数。设1999项绝对值为y，2000项绝对值为x，则要求n*(x-y)-k=x，也即(n-1)x=k+ny。注意到n和n-1互质，所以y取遍0~n-1后一定能找到一个整数x，其作为答案即可。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long long#define N 20010char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n;signed main(){#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout);#endif n=read(); for (int i=1;i<=10000;i++) if ((n+2000*i)%1999==0) { cout<<2000<

　　C：考虑动态添加01时对每个后缀计算贡献（即可以划分成多少个合法字符串）。如果已经有与其本质相同的子串，则贡献为0，这可以建棵trie（也就是反串未压缩的后缀树）来判断。否则设l~r区间的贡献为f[l][r]，其从f[l][r-4~r-1]转移而来即可。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long long#define N 3010#define P 1000000007char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,a[N],id[N][N],f[N*N],trie[N*N][2],cnt,ans;bool isok(int l,int r){ if (a[l]==0&&a[l+1]==0&&a[l+2]==1&&a[l+3]==1) return 0; if (a[l]==0&&a[l+1]==1&&a[l+2]==0&&a[l+3]==1) return 0; if (a[l]==1&&a[l+1]==1&&a[l+2]==1&&a[l+3]==0) return 0; if (a[l]==1&&a[l+1]==1&&a[l+2]==1&&a[l+3]==1) return 0; return 1;}//0011 0101 1110 1111 ������ĸsigned main(){#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout);#endif n=read();f[0]=1; for (int i=1;i<=n;i++) { a[i]=read(); int k=0; for (int j=i;j>=1;j--) { if (!trie[k][a[j]]) { trie[k][a[j]]=++cnt; k=trie[k][a[j]],id[j][i]=k; if (i-j+1==1) f[k]=1; else if (i-j+1==2) f[k]=2; else if (i-j+1==3) f[k]=4; else { f[k]=(f[id[j][i-1]]+f[id[j][i-2]])%P; f[k]=(f[k]+f[id[j][i-3]])%P; if (isok(i-3,i)) f[k]=(f[k]+f[id[j][i-4]])%P; } ans=(ans+f[k])%P; } else k=trie[k][a[j]],id[j][i]=k; } printf("%d\n",ans); } return 0; //NOTICE LONG LONG!!!!!}

　　D：显然可以dp，即f[i]为前i位的划分方案数。考虑优化转移。套路的将每个数字最后一次出现位置设为1，倒数第二次设为-1，其余为0，每次需要的就是后缀和<=m的位置之和。这个东西可以分块维护。然而只有在最后5min才想的到分块的，自闭了。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define ll long long#define N 100010#define P 998244353char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,m,a[N],f[N],pre[N],p[N],s[400][N],lazy[400][400],sum[N],L[N],R[N],pos[N],delta[N],v[N],tree[N],num,block;void tree_add(int k,int x){v[k]+=x;while (k) tree[k]+=x,k-=k&-k;}int tree_query(int k){int s=0;while (k<=n) s+=tree[k],k+=k&-k;return s;}void build(int k){ for (int i=1;i<=R[k]-L[k]+1;i++) s[k][lazy[k][i]]=0; delta[k]=0;sum[k]=0; int S=tree_query(R[k]+1); for (int i=R[k];i>=L[k];i--) { S+=v[i]; s[k][S]=(s[k][S]+f[i-1])%P; lazy[k][R[k]-i+1]=S; if (S<=m) sum[k]=(sum[k]+f[i-1])%P; }}void modify(int l,int r,int op){ if (l>r) return; if (pos[l]==pos[r]) build(pos[l]); else { for (int i=pos[l]+1;i
            
             =0) sum[i]=(sum[i]-s[i][m-delta[i]]+P)%P;} else {if (m-delta[i]+1>=0) sum[i]=(sum[i]+s[i][m-delta[i]+1])%P;} delta[i]+=op; } build(pos[l]),build(pos[r]); }}signed main(){#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout);#endif n=read(),m=read();block=sqrt(n);num=(n-1)/block+1; for (int i=1;i<=n;i++) { a[i]=read(); pre[i]=p[a[i]];p[a[i]]=i; } for (int i=1;i<=num;i++) { L[i]=R[i-1]+1;R[i]=min(n,L[i]+block-1); for (int j=L[i];j<=R[i];j++) pos[j]=i; } f[0]=1;build(1); for (int i=1;i<=n;i++) { tree_add(i,1);if (pre[i]>0) tree_add(pre[i],-2);if (pre[pre[i]]>0) tree_add(pre[pre[i]],1); modify(pre[i]+1,i,1); modify(pre[pre[i]]+1,pre[i],-1); for (int j=1;j<=num;j++) f[i]=(f[i]+sum[j])%P; build(pos[i]); } cout<

　　E：首先随便找个根。考虑我们能干什么。感觉上两个点集都不止一个点的话问出来的东西没什么意义，于是仅考虑一个点到一些点。显然可以问出每个点所拥有的子树大小。

　　我们按子树大小从小到大考虑每个点，考虑完一个点后即确定其所有儿子。显然只需要找到在其子树内的还没有确定父亲的点，也相当于这些点和根在该点两侧。如果只有一个点在其子树内，显然可以通过分治确定。有多个点的话，每次找一个再删掉就行了。

　　如果写的丑注意特判n=2。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;#define ll long long#define N 510char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,p[N],size[N],fa[N],id[N],t,root;vector
             
               nofa;struct data{int to,nxt;}edge[N<<1];void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}int belongtox(int x){ cout<<1<
              
               <
               
                <
                
                 >1; if (calc(x,l,mid)) ans=mid,r=mid-1; else l=mid+1; } return ans;}signed main(){ n=read();if (n==2) {cout<<"ANSWER"<
                 
                  <<1<<' '<<2;return 0;} root=1;size[1]=n; for (int i=2;i<=n;i++) size[i]=belongtox(i); for (int i=1;i<=n;i++) id[i]=i; sort(id+1,id+n+1,cmp); for (int i=1;i<=n;i++) { if (!nofa.empty()) { do { if (nofa.empty()) break; int x=calc(id[i],0,nofa.size()-1); if (!x) break; int y=find(id[i]);fa[nofa[y]]=id[i]; nofa.erase(nofa.begin()+y); }while (1); } nofa.push_back(id[i]); } cout<<"ANSWER"<

　　result：rank 25 rating +121 上红辣！！！？？？

转载于:https://www.cnblogs.com/Gloid/p/10428941.html

你可能感兴趣的文章

Android studio来开发移动App--SQA计划和系统测试规程