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

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

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

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

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

（强行跑题）

O(n^4)暴力妥妥的

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<vector>

 using namespace std;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 vector<int>r[],c[];

 int mp[][];

 int check(int a,int x,int y){

     for(int i=;i<r[x].size();i++){

         for(int j=;j<c[y].size();j++){

             if(r[x][i]+c[y][j]==a)return ;

         }

     }

     return ;

 }

 int main(){

     int i,j;

     int n=read();

     for(i=;i<=n;i++){

         for(j=;j<=n;j++){

             mp[i][j]=read();

             r[i].push_back(mp[i][j]);

             c[j].push_back(mp[i][j]);

         }

     }

     for(i=;i<=n;i++){

         for(j=;j<=n;j++){

             if(mp[i][j]==)continue;

             if(!check(mp[i][j],i,j)){

                 printf("NO\n");

                 return ;

             }

         }

     }

     printf("YES\n");

     return ;

 }

Okabe and Banana Trees

枚举扫描

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

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

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #define LL long long

 using namespace std;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 LL calc(LL x,LL y){

     LL res=(+y)*y/*(x+);

     res+=(+x)*x/*y;

     res+=(+x)*x/;

     return res;

 }

 LL ans=;

 int main(){

     int i,j;

     int m,b;

     m=read();b=read();

     for(int i=;i>=;i++){

         int y=b-ceil((double)i/m);

         if(y<)break;

         ans=max(ans,calc(i,y));

     }

     printf("%I64d\n",ans);

     return ;

 }

Okabe and Boxes

贪心构造

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

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

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<queue>

 using namespace std;

 const int mxn=;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 priority_queue<int>q;

 int last,ord;

 int n,x;

 char s[];

 int st[mxn],top=;

 int main(){

     int i,j;

     n=read();

     int ed=n<<;

     ord=;

     int ans=;

     for(i=;i<=ed;i++){

 //        printf("i:%d\n",i);

         scanf("%s",s);

         if(s[]=='a'){

             scanf("%d",&x);

             q.push(-x);

             st[++top]=x;

             last=x;

         }

         else{//remove

             if(last==ord){

                 q.pop();

                 ord++;

                 if(top)top--;

                 if(top){

                     last=st[top];

                 }

                 else last=-q.top();

             }

             else{

                 ans++;

                 ord++;

                 q.pop();

                 last=-q.top();

                 top=;

             }

         }

 //        printf("top:%d last:%d\n",q.top(),last);

     }

     printf("%d\n",ans);

     return ;

 }

Okabe and City

图论最短路脑洞题

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

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

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

　　↑然而没有这种数据233

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<vector>

 #include<queue>

 #include<map>

 using namespace std;

 const int mxn=;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 struct edge{

     int v,nxt;

 }e[mxn<<];

 int hd[mxn],mct=;

 void add_edge(int u,int v){

     e[++mct].v=v;e[mct].nxt=hd[u];hd[u]=mct;return;

 }

 void insert(int u,int v){

     add_edge(u,v);add_edge(v,u);

 }

 int n,m,K;

 struct point{

     int x,y;

 }a[mxn];

 vector<int>r[mxn],c[mxn];

 int f[mxn];

 queue<int>q;

 bool inq[mxn];

 void SPFA(int st){

     memset(f,0x3f,sizeof f);

     q.push(st);f[st]=;

     while(!q.empty()){

         int u=q.front();q.pop();inq[u]=;

 //        if(f[u]>f[K])continue; // nope!

         int x=a[u].x;

         for(int i=;i<r[x].size();i++){

             int v=r[x][i],cost=(abs(a[u].y-a[v].y)==)?:;

             if(f[v]>f[u]+cost){

                 f[v]=f[u]+cost;

                 if(!inq[v]){

                     inq[v]=;

                     q.push(v);

                 }

             }

         }

         //

         for(int i=;i<r[x+].size();i++){

             int v=r[x+][i],cost=;

             if(f[v]>f[u]+cost){

                 f[v]=f[u]+cost;

                 if(!inq[v]){

                     inq[v]=;

                     q.push(v);

                 }

             }

         }

         for(int i=;i<r[x+].size();i++){

             int v=r[x+][i],cost=;

             if(f[v]>f[u]+cost){

                 f[v]=f[u]+cost;

                 if(!inq[v]){

                     inq[v]=;

                     q.push(v);

                 }

             }

         }

         for(int i=;i<r[x-].size();i++){

             int v=r[x-][i],cost=;

             if(f[v]>f[u]+cost){

                 f[v]=f[u]+cost;

                 if(!inq[v]){

                     inq[v]=;

                     q.push(v);

                 }

             }

         }

         if(x>){

             for(int i=;i<r[x-].size();i++){

                 int v=r[x-][i],cost=;

                 if(f[v]>f[u]+cost){

                     f[v]=f[u]+cost;

                     if(!inq[v]){

                         inq[v]=;

                         q.push(v);

                     }

                 }

             }

         }

         //

         int y=a[u].y;

         for(int i=;i<c[y].size();i++){

             int v=c[y][i],cost=(abs(a[u].x-a[v].x)==)?:;

             if(f[v]>f[u]+cost){

                 f[v]=f[u]+cost;

                 if(!inq[v]){

                     inq[v]=;

                     q.push(v);

                 }

             }

         }

         for(int i=;i<c[y-].size();i++){

             int v=c[y-][i],cost=;

             if(f[v]>f[u]+cost){

                 f[v]=f[u]+cost;

                 if(!inq[v]){

                     inq[v]=;

                     q.push(v);

                 }

             }

         }

         if(y>){

             for(int i=;i<c[y-].size();i++){

                 int v=c[y-][i],cost=;

                 if(f[v]>f[u]+cost){

                     f[v]=f[u]+cost;

                     if(!inq[v]){

                         inq[v]=;

                         q.push(v);

                     }

                 }

             }

         }

         for(int i=;i<c[y+].size();i++){

             int v=c[y+][i],cost=;

             if(f[v]>f[u]+cost){

                 f[v]=f[u]+cost;

                 if(!inq[v]){

                     inq[v]=;

                     q.push(v);

                 }

             }

         }

         for(int i=;i<c[y+].size();i++){

             int v=c[y+][i],cost=;

             if(f[v]>f[u]+cost){

                 f[v]=f[u]+cost;

                 if(!inq[v]){

                     inq[v]=;

                     q.push(v);

                 }

             }

         }

         /*

         for(int i=hd[u];i;i=e[i].nxt){

             int v=e[i].v;

 //            printf("u:%d v:%d\n",u,v);

             if(f[v]>f[u]+1){

                 f[v]=f[u]+1;

                 if(!inq[v]){

                     inq[v]=1;

                     q.push(v);

                 }

             }

         }

         */

     }

     return;

 }

 map<int,int>mp[mxn];

 int main(){

     int i,j;

     n=read();m=read();K=read();

     for(i=;i<=K;i++){

         a[i].x=read();a[i].y=read();

         r[a[i].x].push_back(i);

         c[a[i].y].push_back(i);

         mp[a[i].x][a[i].y]=i;

     }

     //

 /*

     for(i=1;i<=K;i++){

         if(mp[a[i].x+1][a[i].y+1]){

             insert(i,mp[a[i].x+1][a[i].y+1]);

         }

         if(mp[a[i].x-1][a[i].y+1]){

             insert(i,mp[a[i].x-1][a[i].y+1]);

         }

     }

 */

     for(i=;i<=K;i++){

         if(a[i].x== && a[i].y==){

             SPFA(i);break;

         }

     }

     int ans=0x3f3f3f3f;

     for(i=;i<=K;i++){

 //        printf("i:%d f:%d\n",i,f[i]);

         if(a[i].x==n && a[i].y==m)ans=min(ans,f[i]);

         if(a[i].x>=n- || a[i].y>=m-)ans=min(ans,f[i]+);

     }

     if(ans==0x3f3f3f3f)ans=-;

     printf("%d\n",ans);

     return ;

 }

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

Okabe and El Psy Kongroo

数学问题递推矩阵乘法

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

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

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #define LL long long

 using namespace std;

 const int mod=1e9+;

 LL read(){

     LL x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int sz=;

 struct Mat{

     int x[][];

     void clear(){

         memset(x,,sizeof x);return;

     }

     void init(int n){

         for(int i=;i<=n;i++)x[i][i]=;return;

     }

     Mat operator * (const Mat b){

         Mat res;

         for(int i=;i<=sz;i++){

             for(int j=;j<=sz;j++){

                 res.x[i][j]=;

                 for(int k=;k<=sz;k++){

                     res.x[i][j]=((LL)res.x[i][j]+(LL)x[i][k]*b.x[k][j]%mod)%mod;

                 }

             }

         }

         return res;

     }

     void debug(){

         for(int i=;i<=sz;i++){

             for(int j=;j<=sz;j++){

                 printf("%d ",x[i][j]);

             }

             puts("");

         }

         puts("");

         return;

     }

 };

 Mat ans,bas,aa;

 Mat ksm(Mat a,LL k){

     Mat res;res.clear();res.init(sz);

     while(k){

         if(k&)res=res*a;

         a=a*a;

         k>>=;

     }

     return res;

 }

 int n;LL K;

 void Build(int lim){

     bas.clear();

     for(int i=;i<=lim;i++){

         bas.x[i][i]=;

         if(i)bas.x[i][i-]=;

         if(i<lim)bas.x[i][i+]=;

     }

     return;

 }

 int main(){

     int i,j;

     n=read();K=read();

     ans.init();sz=;

     LL a,b;int c;

     int last=;

     for(i=;i<=n;i++){

         a=read();b=read();c=read();

         if(a>=K)break;

         Build(c);

         b=min(b,K);

         aa=ksm(bas,b-a);

         ans=ans*aa;

     }

     printf("%d\n",ans.x[][]);

     return ;

 }

巴特西

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

最新文章

热门文章