Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 1)-白红宇

Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 1)

阅读量：6068 次

发布时间：2019-06-20

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

A - Toy Train

很显然，一个站有多少个糖，那么就要从这个点运多少次。设第i个点有\(a_i\)个糖，那么就要转\(a_i-1\)圈，然后再走一段。很显然最后一段越小越好。

然后枚举起点后，每个点的答案就是起点到他的距离加上再走的距离。然后取个max就好了。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define qmin(x,y) (x=min(x,y))#define qmax(x,y) (x=max(x,y))#define vi vector
         
          #define vit vector
          
           ::iterator#define pir pair
           
            #define fr first#define sc second#define mp(x,y) make_pair(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=1100000;const ll inf=0x3f3f3f3f3f3f3f3fll; int n,m,a[Maxn],b[Maxn],x,y; signed main() {// freopen("test.in","r",stdin); read(n,m); memset(b,0x3f,sizeof(b)); for(int i=1;i<=m;i++) { read(x,y); a[x]++; if(y>x) qmin(b[x],y-x); else qmin(b[x],y+n-x); } for(int i=1;i<=n;i++) if(!a[i]) b[i]=0; for(int i=1;i<=n;i++) { int ans=0; for(int j=1;j<=n;j++) { int temp; if(j>=i) temp=j-i; else temp=j+n-i; temp+=(a[j]-1)*n+b[j]; qmax(ans,temp); } printf("%d ",ans); } return 0;}

B - Wrong Answer

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define qmin(x,y) (x=min(x,y))#define qmax(x,y) (x=max(x,y))#define vi vector
         
          #define vit vector
          
           ::iterator#define pir pair
           
            #define fr first#define sc second#define mp(x,y) make_pair(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=1100000;const ll inf=0x3f3f3f3f3f3f3f3fll; int k; signed main() {// freopen("test.in","r",stdin); read(k); int temp=1999-k%1999; puts("2000"); for(int i=1;i<=1998;i++) printf("0 "); printf("%d ",-temp); printf("%d\n",(k+temp)/1999+temp); return 0;}

C - Morse Code

首先，直接n方DP求每一段能代表的字符串的个数很简单，然后因为相同的子串只能统计一次答案，那么就用一颗trie树来存就好了。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define qmin(x,y) (x=min(x,y))#define qmax(x,y) (x=max(x,y))#define vi vector
         
          #define vit vector
          
           ::iterator#define pir pair
           
            #define fr first#define sc second#define mp(x,y) make_pair(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=11000000;const int inf=0x3f3f3f3f;const int mod=1000000007;int n,f[5100],a[Maxn],ans,ch[Maxn][2],cnt=1; signed main() {// freopen("test.in","r",stdin); read(n); f[0]=1; for(int i=1;i<=n;i++) read(a[i]); for(int i=1;i<=n;i++) { memset(f,0,sizeof(f)); f[i+1]=1; int now=1; for(int j=i;j>=1;j--) { for(int k=1;k<=3;k++) f[j]=(f[j]+f[j+k])%mod; if(j<=i-3) { if(!a[j]) { if(a[j+1]) { if(a[j+2]||!a[j+3]) f[j]=(f[j]+f[j+4])%mod; } else { if(!a[j+2]||!a[j+3]) f[j]=(f[j]+f[j+4])%mod; } } else if(a[j+3]) { if(!a[j+1]||!a[j+2]) f[j]=(f[j]+f[j+4])%mod; } else if(!a[j+1]||!a[j+2]) f[j]=(f[j]+f[j+4])%mod; } if(!ch[now][a[j]]) { ch[now][a[j]]=++cnt; ans=(ans+f[j])%mod; } now=ch[now][a[j]]; } printf("%d\n",ans); } return 0;}

D - Isolation

枚举右端点，然后把每个数字最后一次出现的位置设为1，倒数第二次出现的位置设为-1，这样，如果一个后缀和小于等于k，就可以转移。

然后进行分块，每一块记总和和后缀小于等于一个数的dp值的和即可。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define qmin(x,y) (x=min(x,y))#define qmax(x,y) (x=max(x,y))#define vi vector
          
           #define vit vector
           
            ::iterator#define pir pair
            
             #define fr first#define sc second#define mp(x,y) make_pair(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;const int mod=998244353;int bn[Maxn],bl[Maxn],br[Maxn],f[Maxn],b[Maxn],a[Maxn],in[Maxn],bf[500][1000],n,k,las[Maxn],pre[Maxn];inline int modd(int x) { return x>=mod?x-mod:x;}void update(int x) { memset(bf[x],0,sizeof(bf[0])); bn[x]=0; for(int i=br[x];i>=bl[x];i--) { bf[x][bn[x]+500]=modd(bf[x][bn[x]+500]+f[i]); bn[x]+=b[i]; } for(int i=1;i<1000;i++) bf[x][i]=modd(bf[x][i]+bf[x][i-1]);}signed main() {// freopen("test.in","r",stdin); read(n,k); int m=sqrt(n); memset(bl,0x3f,sizeof(bl)); memset(las,-1,sizeof(las)); memset(pre,-1,sizeof(pre)); f[0]=1; for(int i=0;i<=n;i++) { in[i]=i/m; qmin(bl[in[i]],i); qmax(br[in[i]],i); } update(0); for(int i=1;i<=n;i++) { read(a[i]); if(~las[a[i]]) { pre[i]=las[a[i]]; b[las[a[i]]]=-1; update(in[las[a[i]]]); if(~pre[las[a[i]]]) { b[pre[las[a[i]]]]=0; update(in[pre[las[a[i]]]]); } } b[i]=1; int now=1; for(int j=i-1;j>=bl[in[i]];j--) { if(now<=k) f[i]=modd(f[i]+f[j]); now+=b[j]; } for(int j=in[i]-1;j>=0;j--) { if(k-now+500>0) f[i]=modd(f[i]+bf[j][min(k-now+500,999)]); now+=bn[j]; } update(in[i]); las[a[i]]=i; } printf("%d\n",f[n]); return 0;}

转载于:https://www.cnblogs.com/shanxieng/p/10429233.html

你可能感兴趣的文章