首页 > 代码库 > Codeforces Round #420 (Div. 2) A-E
Codeforces Round #420 (Div. 2) A-E
本来打算划划水洗洗睡了，突然听到这次的主人公是冈部伦太郎
石头门(《steins;gate》)主题的比赛，岂有不打之理！
石头门真的很棒啊！人设也好剧情也赞曲子也特别好听。
推荐http://music.163.com/#/m/song?id=26259014&userid=115264555
（强行跑题）
Okabe and Future Gadget Laboratory
O(n^4)暴力妥妥的
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 #include<vector> 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<int>r[51],c[51];15 int mp[51][51];16 int check(int a,int x,int y){17 for(int i=0;i<r[x].size();i++){18 for(int j=0;j<c[y].size();j++){19 if(r[x][i]+c[y][j]==a)return 1;20 }21 }22 return 0;23 }24 int main(){25 int i,j;26 int n=read();27 for(i=1;i<=n;i++){28 for(j=1;j<=n;j++){29 mp[i][j]=read();30 r[i].push_back(mp[i][j]);31 c[j].push_back(mp[i][j]);32 }33 }34 for(i=1;i<=n;i++){35 for(j=1;j<=n;j++){36 if(mp[i][j]==1)continue;37 if(!check(mp[i][j],i,j)){38 printf("NO\n");39 return 0;40 }41 }42 }43 printf("YES\n");44 return 0;45 }
Okabe and Banana Trees
枚举 扫描
发现枚举横坐标最多需要枚举1e7次
推一下收益的式子就可以了。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 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 }
Okabe and Boxes
贪心 构造
显然当不能满足要求的出栈序的时候就要把栈内元素排序。
真的都排序的话复杂度受不了，只存还没有排过序的就可以了
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 #include<queue> 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<int>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 }
Okabe and City
图论 最短路 脑洞题
正解是把每行每列看做一个点，在这些点和原有的点之间花式连边跑最短路。
然而博主用非显式建边的方法暴力跑了一发过去了。
只要有1w个点全在一行的数据就能把我的方法卡掉。。
↑然而没有这种数据233
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 #include<vector> 7 #include<queue> 8 #include<map> 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<int>r[mxn],c[mxn]; 32 int f[mxn]; 33 queue<int>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<r[x].size();i++){ 43 int v=r[x][i],cost=(abs(a[u].y-a[v].y)==1)?0:1; 44 if(f[v]>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<r[x+1].size();i++){ 54 int v=r[x+1][i],cost=1; 55 if(f[v]>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<r[x+2].size();i++){ 64 int v=r[x+2][i],cost=1; 65 if(f[v]>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<r[x-1].size();i++){ 74 int v=r[x-1][i],cost=1; 75 if(f[v]>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<r[x-2].size();i++){ 85 int v=r[x-2][i],cost=1; 86 if(f[v]>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<c[y].size();i++){ 98 int v=c[y][i],cost=(abs(a[u].x-a[v].x)==1)?0:1; 99 if(f[v]>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<c[y-1].size();i++){108 int v=c[y-1][i],cost=1;109 if(f[v]>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<c[y-2].size();i++){119 int v=c[y-2][i],cost=1;120 if(f[v]>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<c[y+1].size();i++){130 int v=c[y+1][i],cost=1;131 if(f[v]>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<c[y+2].size();i++){140 int v=c[y+2][i],cost=1;141 if(f[v]>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<int,int>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 }
代码看着长，其实只要写一小段，其他都是复制的
Okabe and El Psy Kongroo
数学问题 递推 矩阵乘法
应该跟D换一下的，明显这个更简单
看到矩阵乘法就能明白了吧233
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 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<lim)bas.x[i][i+1]=1;64 }65 return;66 }67 int main(){68 int i,j;69 n=read();K=read();70 ans.init(15);sz=15;71 LL a,b;int c;72 int last=0;73 for(i=1;i<=n;i++){74 a=read();b=read();c=read();75 if(a>=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 }
Codeforces Round #420 (Div. 2) A-E
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。