Codeforces Round #354 (Div. 2) ABCD
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Codeforces Round #354 (Div. 2) ABCD,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含12549字,纯文字阅读大概需要18分钟。
内容图文
![Codeforces Round #354 (Div. 2) ABCD](/upload/InfoBanner/zyjiaocheng/1222/2be60f52abea4ad1909600e8820a11a2.jpg)
Codeforces Round #354 (Div. 2)
![技术分享](/upload/getfiles/default/2022/11/8/20221108040648853.jpg)
# | Name | ||
---|---|---|---|
A |
standard input/output
1 s, 256 MB |
![]() ![]() |
![]() |
B |
standard input/output
1 s, 256 MB |
![]() ![]() |
![]() |
C |
standard input/output
1 s, 256 MB |
![]() ![]() |
![]() |
D |
standard input/output
3 s, 256 MB |
![]() ![]() |
![]() |
E |
standard input/output
1 s, 256 MB |
![]() ![]() |
![]() |
题意:允许你交换一次任意两个数位置,要使最大的数和最小的数的距离最大,输出最大值
题解:
大水题,就先找到最小的和最大的,把其中一个交换到尽头。
代码:
![技术分享](/upload/getfiles/default/2022/11/8/20221108040654865.jpg)
![技术分享](/upload/getfiles/default/2022/11/8/20221108040654938.jpg)
1 // #pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set> 10 #include<stack> 11 #include<queue> 12usingnamespace std; 1314#define MZ(array) memset(array, 0, sizeof(array)) 15#define MF1(array) memset(array, -1, sizeof(array)) 16#define MINF(array) memset(array, 0x3f, sizeof(array)) 17#define REP(i,n) for(i=0;i<(n);i++) 18#define FOR(i,x,n) for(i=(x);i<=(n);i++) 19#define ROF(i,x,y) for(i=(x);i>=(y);i--) 20#define RD(x) scanf("%d",&x) 21#define RD2(x,y) scanf("%d%d",&x,&y) 22#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z) 23#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w) 24#define WN(x) printf("%d\n",x); 25#define RE freopen("D.in","r",stdin) 26#define WE freopen("huzhi.txt","w",stdout) 27#define MP make_pair 28#define PB push_back 29#define PF push_front 30#define PPF pop_front 31#define PPB pop_back 32#define lowbit(x) ((x)&(-x)) 33 template<class T>inline void OA(const T &a,constint &st,constint &ed) { 34if(ed>=st)cout<<a[st]; 35int i; 36 FOR(i,st+1,ed)cout<<‘‘<<a[i]; 37 puts(""); 38} 39 typedef longlong LL; 40 typedef unsigned longlong ULL; 41 typedef pair<int,int> PII; 42constdouble PI=acos(-1.0); 43constdouble EPS=1e-10; 44 inline int sgn(double &x) { 45if(fabs(x) < EPS)return0; 46if(x < 0)return -1; 47elsereturn1; 48} 49constint INF=0x3f3f3f3f; 50constint NINF=0x80000001; 51constint MAXN=111111; 52constint MAXM=33; 53constint MOD = 1000000007; 54555657int main() { 58int i; 59int x; 60int q,w,n; 61 RD(n); 62 REP(i,n){ 63 RD(x); 64if(x==n)q=i; 65if(x==1)w=i; 66 } 67if(q>w)swap(q,w); 68 WN(max(n-q-1, w)); 69return0; 70 }
题意:摆了一个高脚杯金字塔,每秒钟往最上面倒一整杯,一杯满了会往两边溢出流到下面两个杯子,求n层高的金字塔,倒水k分钟后,有多少杯是满的。
题解:
直接把k分钟的全倒进最上面的杯子,然后模拟流下去就行。
代码:
![技术分享](/upload/getfiles/default/2022/11/8/20221108040654865.jpg)
![技术分享](/upload/getfiles/default/2022/11/8/20221108040654938.jpg)
1 // #pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set> 10 #include<stack> 11 #include<queue> 12usingnamespace std; 1314#define MZ(array) memset(array, 0, sizeof(array)) 15#define MF1(array) memset(array, -1, sizeof(array)) 16#define MINF(array) memset(array, 0x3f, sizeof(array)) 17#define REP(i,n) for(i=0;i<(n);i++) 18#define FOR(i,x,n) for(i=(x);i<=(n);i++) 19#define ROF(i,x,y) for(i=(x);i>=(y);i--) 20#define RD(x) scanf("%d",&x) 21#define RD2(x,y) scanf("%d%d",&x,&y) 22#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z) 23#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w) 24#define WN(x) printf("%d\n",x); 25#define RE freopen("D.in","r",stdin) 26#define WE freopen("huzhi.txt","w",stdout) 27#define MP make_pair 28#define PB push_back 29#define PF push_front 30#define PPF pop_front 31#define PPB pop_back 32#define lowbit(x) ((x)&(-x)) 33 template<class T>inline void OA(const T &a,constint &st,constint &ed) { 34if(ed>=st)cout<<a[st]; 35int i; 36 FOR(i,st+1,ed)cout<<‘‘<<a[i]; 37 puts(""); 38} 39 typedef longlong LL; 40 typedef unsigned longlong ULL; 41 typedef pair<int,int> PII; 42constdouble PI=acos(-1.0); 43constdouble EPS=1e-10; 44 inline int sgn(double &x) { 45if(fabs(x) < EPS)return0; 46if(x < 0)return -1; 47elsereturn1; 48} 49constint INF=0x3f3f3f3f; 50constint NINF=0x80000001; 51constint MAXN=111111; 52constint MAXM=33; 53constint MOD = 1000000007; 5455int n,t; 5657int farm(){ 58double a[20][20]; 59int i,j; 60 REP(i,11)REP(j,11)a[i][j]=0.0; 61 a[1][1] = t; 62int cnt=0; 63 FOR(i,1,n){ 64 FOR(j,1,i){ 65if(a[i][j]>1.0){ 66double t = (a[i][j] - 1.0)/2.0; 67 a[i+1][j] += t; 68 a[i+1][j+1] += t; 69 a[i][j]=1.0; 70 } 71if(a[i][j]>=1.0)cnt++; 72 } 73 } 74// FOR(i,1,n){ 75// FOR(j,1,i){ 76// printf("%f ",a[i][j]); 77// } 78// puts(""); 79// }80return cnt; 81} 8283int main() { 84int i; 85 RD2(n,t); 86 WN(farm()); 87return0; 88 }
题意:给出一个由a和b两个字母组成的字符串,最多修改其中k个,使得其中最长的连续同一字母子串最长,求最长的长度。
题解:
用双端队列,以a为本体扫一遍,再以b为本体扫一遍。以a为本体的时候,扫到b的话,就加到双端队列里,如果双端队列里超过k个,就从左端弹出,保持里面剩k个。记录全a子序列的区间左端,弹出的时候更新 区间左端L = 弹出的元素的位置+1。时刻更新ans = max(ans , R-L+1),R为当前扫到的位置。
只用扫两遍,O(n)。
代码:
![技术分享](/upload/getfiles/default/2022/11/8/20221108040654865.jpg)
![技术分享](/upload/getfiles/default/2022/11/8/20221108040654938.jpg)
1 // #pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set> 10 #include<stack> 11 #include<queue> 12usingnamespace std; 1314#define MZ(array) memset(array, 0, sizeof(array)) 15#define MF1(array) memset(array, -1, sizeof(array)) 16#define MINF(array) memset(array, 0x3f, sizeof(array)) 17#define REP(i,n) for(i=0;i<(n);i++) 18#define FOR(i,x,n) for(i=(x);i<=(n);i++) 19#define ROF(i,x,y) for(i=(x);i>=(y);i--) 20#define RD(x) scanf("%d",&x) 21#define RD2(x,y) scanf("%d%d",&x,&y) 22#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z) 23#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w) 24#define WN(x) printf("%d\n",x); 25#define RE freopen("D.in","r",stdin) 26#define WE freopen("huzhi.txt","w",stdout) 27#define MP make_pair 28#define PB push_back 29#define PF push_front 30#define PPF pop_front 31#define PPB pop_back 32#define lowbit(x) ((x)&(-x)) 33 template<class T>inline void OA(const T &a,constint &st,constint &ed) { 34if(ed>=st)cout<<a[st]; 35int i; 36 FOR(i,st+1,ed)cout<<‘‘<<a[i]; 37 puts(""); 38} 39 typedef longlong LL; 40 typedef unsigned longlong ULL; 41 typedef pair<int,int> PII; 42constdouble PI=acos(-1.0); 43constdouble EPS=1e-10; 44 inline int sgn(double &x) { 45if(fabs(x) < EPS)return0; 46if(x < 0)return -1; 47elsereturn1; 48} 49constint INF=0x3f3f3f3f; 50constint NINF=0x80000001; 51constint MAXN=111111; 52constint MAXM=33; 53constint MOD = 1000000007; 5455int n,k; 56char s[MAXN]; 5758int gank(char c){ 59 deque<int> d; 60int l=0; 61int cnt=0; 62int re=0; 63int i; 64 REP(i,n){ 65if(s[i]==c){ 66 d.push_back(i); 67if(cnt==k){ 68 l = d.front() + 1; 69 d.pop_front(); 70 }else cnt++; 71 } 72 re = max(re, i-l+1); 73 } 74return re; 75} 7677int farm(){ 78return max(gank(‘a‘), gank(‘b‘)); 79} 8081int main() { 82int i; 83 RD2(n,k); 84 scanf(" %s",s); 85 WN(farm()); 86return0; 87 }
题意:给出一个n*m的地图,英雄从(xt,yt)出发,要到达敌人所在地(xm,ym)。地图每个格子有设定:
^>v<代表向箭头方向有门,其他方向没门;
URDL代表某个方向没门,其他方向都有门,例如U,代表上面没门,其他3个方向各有一个门。
-|代表左右有门、上下有门。
+代表4个门,*代表没有门。
每分钟,英雄可以进行一项操作:
A.将所有方块顺时针转90度。
B.移动到相邻方块,要求自己方块到它的方向有门,它的方块到自己的方向也有门。
给出地图、英雄位置、敌人位置,求英雄到达敌人的最少分钟数,或者不能到达输出-1。
题解:
走迷宫,典型的广搜题。广搜每个节点有5种扩展:旋转90度、往4个方向走。注意记录某个点是否走过,需要save[x][y][z],x,y为该点坐标,z为旋转的次数,z<=3。
比较难写的是判断某个点能否向某个方向走一步,可以写到一个函数里can(x,y,z,j),(x,y)为当前坐标,z为当前旋转了几次(0~3),j为方向,我设定方向0123代表上右下左。
方块旋转、门的位置可以预处理,记到一个数组里,例如rot[‘<‘][2] = ‘>‘,代表<符号旋转2次得到>符号。
例如door[‘-‘] = "0101",代表-符号的门开在右、左。
这块写好了就无敌了。
我就写错了一个符号,卧槽,就一直wa6,比赛结束以后发现一个-写成了|,改了就过了。这种题要认真点写啊。
(可恶,刚才看官方题解,哇,直接预处理出4种方向的地图,a[x][y][z],就是简单的三维地图bfs了,卧槽,我怎么没想到)
代码:
![技术分享](/upload/getfiles/default/2022/11/8/20221108040654865.jpg)
![技术分享](/upload/getfiles/default/2022/11/8/20221108040654938.jpg)
1 // #pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set> 10 #include<stack> 11 #include<queue> 12usingnamespace std; 13 14#define MZ(array) memset(array, 0, sizeof(array)) 15#define MF1(array) memset(array, -1, sizeof(array)) 16#define MINF(array) memset(array, 0x3f, sizeof(array)) 17#define REP(i,n) for(i=0;i<(n);i++) 18#define FOR(i,x,n) for(i=(x);i<=(n);i++) 19#define ROF(i,x,y) for(i=(x);i>=(y);i--) 20#define RD(x) scanf("%d",&x) 21#define RD2(x,y) scanf("%d%d",&x,&y) 22#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z) 23#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w) 24#define WN(x) printf("%d\n",x); 25#define RE freopen("D.in","r",stdin) 26#define WE freopen("huzhi.txt","w",stdout) 27#define MP make_pair 28#define PB push_back 29#define PF push_front 30#define PPF pop_front 31#define PPB pop_back 32#define lowbit(x) ((x)&(-x)) 33 template<class T>inline void OA(const T &a,constint &st,constint &ed) { 34if(ed>=st)cout<<a[st]; 35int i; 36 FOR(i,st+1,ed)cout<<‘‘<<a[i]; 37 puts(""); 38} 39 typedef longlong LL; 40 typedef unsigned longlong ULL; 41 typedef pair<int,int> PII; 42constdouble PI=acos(-1.0); 43constdouble EPS=1e-10; 44 inline int sgn(double &x) { 45if(fabs(x) < EPS)return0; 46if(x < 0)return -1; 47elsereturn1; 48} 49constint INF=0x3f3f3f3f; 50constint NINF=0x80000001; 51constint MAXN=1111; 52constint MAXM=33; 53constint MOD = 1000000007; 54constint gx[4] = {-1,0,1,0}; 55constint gy[4] = {0,1,0,-1}; 56int n,m; 57char s[MAXN][MAXN]; 58int xt,yt,xm,ym; 59 60int save[MAXN][MAXN][4]; 61char rota[222][4]; 62char door[222][5]; 63void init() { 64int i,j; 65 MF1(save); 66 REP(i,4) { 67 rota[‘+‘][i]=‘+‘; 68 rota[‘*‘][i]=‘*‘; 69 } 70for(i=0; i<4; i+=2) { 71 rota[‘-‘][0+i]=‘-‘; 72 rota[‘|‘][0+i]=‘|‘; 73 rota[‘-‘][1+i]=‘|‘; 74 rota[‘|‘][1+i]=‘-‘; 75 } 76char q[5] = "^>v<"; 77char w[5] = "URDL"; 78 REP(i,4) { 79 REP(j,4) { 80int l=(i+j)%4; 81 rota[q[i]][j] = q[l]; 82 rota[w[i]][j] = w[l]; 83 } 84 } 85 REP(i,4) { 86 door[‘+‘][i]=‘1‘; 87 door[‘*‘][i]=‘0‘; 88 door[‘|‘][i]=door[‘-‘][i]=‘0‘; 89 } 90 door[‘|‘][0]=door[‘|‘][2] = ‘1‘; 91 door[‘-‘][1]=door[‘-‘][3] =‘1‘; 92 REP(i,4)REP(j,4) { 93 door[q[i]][j]=‘0‘; 94 door[w[i]][j]=‘1‘; 95 } 96 REP(i,4) { 97 door[q[i]][i]=‘1‘; 98 door[w[i]][i]=‘0‘; 99 } 100} 101102char rot(char x, int n) { 103return rota[x][n%4]; 104} 105106bool cango(char now , char next, int j) { 107int k = (j+2)%4; 108// door[now][4]=‘\0‘; 109// door[next][4]=‘\0‘; 110// printf("%c,%c,%s,%s,%d,%d,%c,%c\n",now,next,door[now],door[next],j,k,door[now][j],door[next][k]);111if (door[now][j]==‘1‘ && door[next][k]==‘1‘)returntrue; 112elsereturnfalse; 113} 114115bool can(int x,int y,int z,int j) { 116int xx=x+gx[j]; 117int yy=y+gy[j]; 118if(xx<0 || xx>=n || yy<0 || yy>=m)returnfalse; 119char now = s[x][y]; 120char next = s[xx][yy]; 121// printf("%c,%c %d->",now,next,z);122 now = rot(now, z); 123 next = rot(next,z); 124// printf("%c,%c\n",now,next);125if(cango(now,next,j))returntrue; 126elsereturnfalse; 127} 128129struct Node { 130int x,y,z; 131int step; 132 Node() {} 133 Node(int _x,int _y,int _z,int _s) { 134 x=_x; 135 y=_y; 136 z=_z; 137 step=_s; 138 } 139}; 140141int farm() { 142 deque<Node> d; 143int i,j; 144 d.clear(); 145 d.push_back(Node(xt,yt,0,0)); 146 save[xt][yt][0]=0; 147while(!d.empty()) { 148 Node now = d.front(); 149int x=now.x, y=now.y, z=now.z, step=now.step; 150 d.pop_front(); 151// if(x==19 && z==1)printf("%d,%d,%d,%d\n",x,y,z,step);152if(x==xm && y==ym)return step; 153154int k = (z+1)%4; 155if(save[x][y][k]==-1 || save[x][y][k]>step+1) { 156 d.push_back(Node(x, y, k, step+1)); 157 save[x][y][k]=step+1; 158 } 159160 REP(i,4) { 161int xx=x+gx[i]; 162int yy=y+gy[i]; 163// printf("%d,%d,%d,%d,%d,[%d,%d,%d],%d\n",x,y,z,i,can(x,y,z,i),xx,yy,z,save[xx][yy][z]);164if(can(x,y,z,i)&&(save[xx][yy][z]==-1 || save[xx][yy][z]>step+1)) { 165 d.push_back(Node(xx,yy,z,step+1)); 166 save[xx][yy][z]=step+1; 167 } 168 } 169 } 170return -1; 171} 172173int main() { 174int i; 175 init(); 176 RD2(n,m); 177 REP(i,n)scanf(" %s",s[i]); 178 RD2(xt,yt); 179 RD2(xm,ym); 180 xt--; 181 yt--; 182 xm--; 183 ym--; 184 WN(farm()); 185return0; 186 }
E比赛时没空看,结束后看了,大概是说一个那样的式子,两个玩家交替操作,要是能使式子P(x) =B(x)Q(x),就算人类胜。其中B(x)是任意一种那样的式子,Q(x)=x-k,k为给出的数。给出当前局面,到人类动,问人类是否有必胜策略。好像有100多人过pre,最后只有五十多个ac,好像有点难,我还是先不看了。
不懂能不能抢到百度之星t恤啊!
原文:http://www.cnblogs.com/yuiffy/p/5529507.html
内容总结
以上是互联网集市为您收集整理的Codeforces Round #354 (Div. 2) ABCD全部内容,希望文章能够帮你解决Codeforces Round #354 (Div. 2) ABCD所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。