Codeforces Round #521 Div. 3 玩耍记-白红宇

Codeforces Round #521 Div. 3 玩耍记

阅读量：4625 次

发布时间：2019-06-09

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

　　A：签到。

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define ll long longchar 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 T;int main(){ T=read(); while (T--) { int a=read(),b=read(),k=read(); if (k&1) cout<<1ll*(a-b)*(k>>1)+a<
            
             >1)<

View Code

　　B：将能提供2贡献的位置先取反再扫一遍即可。

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define ll long long#define N 110char 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],ans=0;int main(){ n=read(); for (int i=1;i<=n;i++) a[i]=read(); for (int i=3;i<=n-2;i++) if (a[i]==1&&a[i-2]==1&&a[i+2]==1&&a[i-1]==0&&a[i+1]==0) ans++,a[i]=0; for (int i=2;i

View Code

　　C：桶记录出现数字次数，枚举删掉的数字即可。

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define ll long long#define N 200010#define M 1000010char 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],b[N],tot[M],cnt;ll sum;int main(){ n=read(); for (int i=1;i<=n;i++) sum+=a[i]=read(),tot[a[i]]++; for (int i=1;i<=n;i++) { ll x=sum-a[i]; if (x<=2000000&&x%2==0&&tot[x/2]>(a[i]==x/2)) b[++cnt]=i; } cout<
            
             <

View Code

　　D：二分答案贪心选取即可。

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define ll long long#define N 200010char 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,cnt[N],id[N],ans[N];struct data{ int x,y; bool operator <(const data&a) const { return y>a.y; }}a[N],b[N];bool check(int k){ for (int i=1;i<=200000;i++) b[i]=a[i]; int s=0; for (int i=1;i<=200000;i++) while (b[i].y>=k&&s
            
             =m;}int main(){ n=read(),m=read(); for (int i=1;i<=n;i++) cnt[read()]++; for (int i=1;i<=200000;i++) a[i].x=i,a[i].y=cnt[i]; sort(a+1,a+200001); int l=0,r=n/m; while (l<=r) { int mid=l+r>>1; if (check(mid)) { for (int i=1;i<=m;i++) ans[i]=id[i];l=mid+1;} else r=mid-1; } for (int i=1;i<=m;i++) printf("%d ",ans[i]); return 0;}

View Code

　　E：枚举序列长度（显然是log级别的），二分首项大小，贪心选取即可。

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define ll long long#define N 200010char 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],b[N],cnt[N],tot;bool check(int k,int s){ int t=0; for (int i=1;i<=n;i++) { if (a[i]>=k) t++,k<<=1; if (t==s) return 1; } return 0;}int main(){ n=read(); for (int i=1;i<=n;i++) b[i]=a[i]=read(); sort(b+1,b+n+1); int t=unique(b+1,b+n+1)-b-1; for (int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+t+1,a[i])-b; for (int i=1;i<=n;i++) cnt[a[i]]++; sort(cnt+1,cnt+t+1); for (int i=1;i<=t;i++) a[i]=cnt[i]; int tmp=n; n=t; for (int i=1;i<=18;i++) { int l=1,r=tmp,ans=0; while (l<=r) { int mid=l+r>>1; if (check(mid,i)) ans=mid,l=mid+1; else r=mid-1; } tot=max(tot,ans*((1<

View Code

　　F1：f[i][j]表示前i个数选取了j个且第i个被选的最大价值，转移枚举上次选哪个即可。

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define ll long long#define N 5010char 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,k,a[N];ll f[N][N];int main(){ n=read(),k=read(),m=read(); for (int i=1;i<=n;i++) a[i]=read(); memset(f,200,sizeof(f)); f[0][0]=0; for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { for (int x=i-1;x>=max(0,i-k);x--) f[i][j]=max(f[i][j],f[x][j-1]+a[i]); } } for (int i=n-1;i>=max(0,n-k+1);i--) f[n][m]=max(f[n][m],f[i][m]); if (f[n][m]<0) cout<<-1; else cout<

View Code

　　F2：在F1基础上单调队列优化即可。

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define ll long long#define N 5010char 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,k,a[N],q[N],head,tail;ll f[N][N];int main(){ n=read(),k=read(),m=read(); for (int i=1;i<=n;i++) a[i]=read(); memset(f,200,sizeof(f)); f[0][0]=0; for (int j=1;j<=m;j++) { head=1,tail=1;q[1]=0; for (int i=1;i<=n;i++) { while (head
            
             
              =max(0,n-k+1);i--) f[n][m]=max(f[n][m],f[i][m]); if (f[n][m]<0) cout<<-1; else cout<