Codeforces Round #420 (Div. 2) A-E-白红宇

Codeforces Round #420 (Div. 2) A-E

阅读量：6834 次

发布时间：2019-06-26

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

本来打算划划水洗洗睡了，突然听到这次的主人公是冈部伦太郎

石头门(《steins;gate》)主题的比赛，岂有不打之理！

石头门真的很棒啊！人设也好剧情也赞曲子也特别好听。

推荐http://music.163.com/#/m/song?id=26259014&userid=115264555

（强行跑题）

O(n^4)暴力妥妥的

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 using namespace std; 8 int read(){ 9 int x=0,f=1;char ch=getchar();10 while(ch<'0' || ch>'9'){ if(ch=='-')f=-1;ch=getchar();}11 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}12 return x*f;13 }14 vector
            
             r[51],c[51];15 int mp[51][51];16 int check(int a,int x,int y){17 for(int i=0;i

枚举扫描

发现枚举横坐标最多需要枚举1e7次

推一下收益的式子就可以了。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #define LL long long 7 using namespace std; 8 int read(){ 9     int x=0,f=1;char ch=getchar();10     while(ch<'0' || ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}11     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}12     return x*f;13 }14 LL calc(LL x,LL y){15     LL res=(1+y)*y/2*(x+1);16     res+=(1+x)*x/2*y;17     res+=(1+x)*x/2;18     return res;19 }20 LL ans=0;21 int main(){22     int i,j;23     int m,b;24     m=read();b=read();25     for(int i=0;i>=0;i++){26         int y=b-ceil((double)i/m);27         if(y<0)break;28         ans=max(ans,calc(i,y));29     }30     printf("%I64d\n",ans);31     return 0;32 }

贪心构造

显然当不能满足要求的出栈序的时候就要把栈内元素排序。

真的都排序的话复杂度受不了，只存还没有排过序的就可以了

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 using namespace std; 8 const int mxn=300050; 9 int read(){10 int x=0,f=1;char ch=getchar();11 while(ch<'0' || ch>'9'){ if(ch=='-')f=-1;ch=getchar();}12 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}13 return x*f;14 }15 priority_queue
            
             q;16 int last,ord;17 int n,x;18 char s[10];19 int st[mxn],top=0;20 int main(){21 int i,j;22 n=read();23 int ed=n<<1;24 ord=1;25 int ans=0;26 for(i=1;i<=ed;i++){27 // printf("i:%d\n",i);28 scanf("%s",s);29 if(s[0]=='a'){30 scanf("%d",&x);31 q.push(-x);32 st[++top]=x;33 last=x;34 }35 else{ //remove36 if(last==ord){37 q.pop();38 ord++;39 if(top)top--;40 if(top){41 last=st[top];42 }43 else last=-q.top();44 }45 else{46 ans++;47 ord++;48 q.pop();49 last=-q.top();50 top=0;51 }52 }53 // printf("top:%d last:%d\n",q.top(),last);54 }55 printf("%d\n",ans);56 return 0;57 }

图论最短路脑洞题

正解是把每行每列看做一个点，在这些点和原有的点之间花式连边跑最短路。

然而博主用非显式建边的方法暴力跑了一发过去了。

只要有1w个点全在一行的数据就能把我的方法卡掉。。

　　↑然而没有这种数据233

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #include
              9 using namespace std; 10 const int mxn=10005; 11 int read(){ 12 int x=0,f=1;char ch=getchar(); 13 while(ch<'0' || ch>'9'){ if(ch=='-')f=-1;ch=getchar();} 14 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 15 return x*f; 16 } 17 struct edge{ 18 int v,nxt; 19 }e[mxn<<5]; 20 int hd[mxn],mct=0; 21 void add_edge(int u,int v){ 22 e[++mct].v=v;e[mct].nxt=hd[u];hd[u]=mct;return; 23 } 24 void insert(int u,int v){ 25 add_edge(u,v);add_edge(v,u); 26 } 27 int n,m,K; 28 struct point{ 29 int x,y; 30 }a[mxn]; 31 vector
              
               r[mxn],c[mxn]; 32 int f[mxn]; 33 queue
               
                q; 34 bool inq[mxn]; 35 void SPFA(int st){ 36 memset(f,0x3f,sizeof f); 37 q.push(st);f[st]=0; 38 while(!q.empty()){ 39 int u=q.front();q.pop();inq[u]=0; 40 // if(f[u]>f[K])continue; // nope! 41 int x=a[u].x; 42 for(int i=0;i
                
                 f[u]+cost){ 45 f[v]=f[u]+cost; 46 if(!inq[v]){ 47 inq[v]=1; 48 q.push(v); 49 } 50 } 51 } 52 // 53 for(int i=0;i
                 
                  f[u]+cost){ 56 f[v]=f[u]+cost; 57 if(!inq[v]){ 58 inq[v]=1; 59 q.push(v); 60 } 61 } 62 } 63 for(int i=0;i
                  
                   f[u]+cost){ 66 f[v]=f[u]+cost; 67 if(!inq[v]){ 68 inq[v]=1; 69 q.push(v); 70 } 71 } 72 } 73 for(int i=0;i
                   
                    f[u]+cost){ 76 f[v]=f[u]+cost; 77 if(!inq[v]){ 78 inq[v]=1; 79 q.push(v); 80 } 81 } 82 } 83 if(x>1){ 84 for(int i=0;i
                    
                     f[u]+cost){ 87 f[v]=f[u]+cost; 88 if(!inq[v]){ 89 inq[v]=1; 90 q.push(v); 91 } 92 } 93 } 94 } 95 // 96 int y=a[u].y; 97 for(int i=0;i
                     
                      f[u]+cost){100 f[v]=f[u]+cost;101 if(!inq[v]){102 inq[v]=1;103 q.push(v);104 }105 }106 }107 for(int i=0;i
                      
                       f[u]+cost){110 f[v]=f[u]+cost;111 if(!inq[v]){112 inq[v]=1;113 q.push(v);114 }115 }116 }117 if(y>1){118 for(int i=0;i
                       
                        f[u]+cost){121 f[v]=f[u]+cost;122 if(!inq[v]){123 inq[v]=1;124 q.push(v);125 }126 }127 }128 }129 for(int i=0;i
                        
                         f[u]+cost){132 f[v]=f[u]+cost;133 if(!inq[v]){134 inq[v]=1;135 q.push(v);136 }137 }138 }139 for(int i=0;i
                         
                          f[u]+cost){142 f[v]=f[u]+cost;143 if(!inq[v]){144 inq[v]=1;145 q.push(v);146 }147 }148 }149 /*150 for(int i=hd[u];i;i=e[i].nxt){151 int v=e[i].v;152 // printf("u:%d v:%d\n",u,v);153 if(f[v]>f[u]+1){154 f[v]=f[u]+1;155 if(!inq[v]){156 inq[v]=1;157 q.push(v);158 }159 }160 }161 */162 }163 return;164 }165 map
                          
                           mp[mxn];166 int main(){167 int i,j;168 n=read();m=read();K=read();169 for(i=1;i<=K;i++){170 a[i].x=read();a[i].y=read();171 r[a[i].x].push_back(i);172 c[a[i].y].push_back(i);173 mp[a[i].x][a[i].y]=i;174 }175 //176 /*177 for(i=1;i<=K;i++){178 if(mp[a[i].x+1][a[i].y+1]){179 insert(i,mp[a[i].x+1][a[i].y+1]);180 }181 if(mp[a[i].x-1][a[i].y+1]){182 insert(i,mp[a[i].x-1][a[i].y+1]);183 }184 }185 */186 for(i=1;i<=K;i++){187 if(a[i].x==1 && a[i].y==1){188 SPFA(i);break;189 }190 }191 int ans=0x3f3f3f3f;192 for(i=1;i<=K;i++){193 // printf("i:%d f:%d\n",i,f[i]);194 if(a[i].x==n && a[i].y==m)ans=min(ans,f[i]);195 if(a[i].x>=n-1 || a[i].y>=m-1)ans=min(ans,f[i]+1);196 }197 if(ans==0x3f3f3f3f)ans=-1;198 printf("%d\n",ans);199 return 0;200 }

代码看着长，其实只要写一小段，其他都是复制的

数学问题递推矩阵乘法

应该跟D换一下的，明显这个更简单

看到矩阵乘法就能明白了吧233

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #define LL long long 7 using namespace std; 8 const int mod=1e9+7; 9 LL read(){10     LL x=0,f=1;char ch=getchar();11     while(ch<'0' || ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}12     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}13     return x*f;14 }15 int sz=0;16 struct Mat{17     int x[16][16];18     void clear(){19         memset(x,0,sizeof x);return;20     }21     void init(int n){22         for(int i=0;i<=n;i++)x[i][i]=1;return;23     }24     Mat operator * (const Mat b){25         Mat res;26         for(int i=0;i<=sz;i++){27             for(int j=0;j<=sz;j++){28                 res.x[i][j]=0;29                 for(int k=0;k<=sz;k++){30                     res.x[i][j]=((LL)res.x[i][j]+(LL)x[i][k]*b.x[k][j]%mod)%mod;31                 }32             }33         }34         return res;35     }36     void debug(){37         for(int i=0;i<=sz;i++){38             for(int j=0;j<=sz;j++){39                 printf("%d ",x[i][j]);40             }41             puts("");42         }43         puts("");44         return;45     }46 };47 Mat ans,bas,aa;48 Mat ksm(Mat a,LL k){49     Mat res;res.clear();res.init(sz);50     while(k){51         if(k&1)res=res*a;52         a=a*a;53         k>>=1;54     }55     return res;56 }57 int n;LL K;58 void Build(int lim){59     bas.clear();60     for(int i=0;i<=lim;i++){61         bas.x[i][i]=1;62         if(i)bas.x[i][i-1]=1;63         if(i
           
            =K)break;76 Build(c);77 b=min(b,K);78 aa=ksm(bas,b-a);79 ans=ans*aa;80 }81 printf("%d\n",ans.x[0][0]);82 return 0;83 }