\(\text{ARC}\) 明天再改
\(\text{solution} - 『\textbf{AtCoder ABC339}』\)
比赛被骂的好惨QAQ，但是确实抽象，有点过于简单了，但凡看一眼F题和G题也不至于就过这几道题哈哈
今天放ABC的改题来水闲话，不然我集训纪要就没得写了
ABC339
-
\(\text{Problem - A}\) \(『\)\(\text{TLD}\)\(』\)
-
简要题意：
给你一个字符串\(S\)，输出\(S\)内最后一个
.后的所有字符 -
思路
直接模拟即可，天依的做法比较差QAQ
stack<char> aaa; signed main(){ string a,b; bool f=0; cin>>a; for(int i=a.size()-1;i>=0;i--){ if(a[i]=='.'){ break; } aaa.push(a[i]); } while(!aaa.empty()){ cout<<aaa.top(); aaa.pop(); } }
-
-
\(\text{Problem - B}\) \(『\)\(\text{Langton's Takahashi}\)\(』\)
-
题意
有一个 \(n*m\) 的环形网格，网格中最开始全都是白色的
天依现在站在\((1,1)\)这个点面朝上方，如果站在的点是白色的就把这个点染成黑色的，面朝的方向顺时针旋转\(90°\)并且向前走一步，这样即为一次行动
如果站在的点是黑色的就染成白色的，面朝的方向逆时针旋转\(90°\)并且走一步，同样即为一次行动
同时这是一个环形网络，如果走到了一个方向的尽头就会瞬移到另一个方向的起点
-
思路
题面就是题解啦，模拟即可，但是我写的比较差
char a[3000][3000];int f=1,x=1,y=1;// x,y int n,m,k; void change(int s,int &f){ if(s==1) f=(f+1)%5; if(!f) f=1; if(s==-1) f=((f-1)+5)%5; if(!f) f=4; } inline void add(){ if(f==1||f==3){ x+=(f==1)?(-1):1; } else{ y+=(f==2)?(1):(-1); } if(y==0) y=m; else if(y==m+1) y=1; if(x==0) x=n; else if(x==n+1) x=1; } signed main(){ // fire(); cin>>n>>m>>k; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ a[i][j]='.'; } } for(int i=1;i<=k;i++){ if(a[x][y]=='.'){ a[x][y]='#'; change(1,f); add(); } else if(a[x][y]=='#'){ a[x][y]='.'; change(-1,f); add(); } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cout<<a[i][j]; } cout<<"\n"; } }
-
-
\(\text{Problem - C}\) \(『\)\(\text{Perfect Bus}\)\(』\)
-
题意
有一辆车和 \(n\) 个时刻。初始时刻车上人数未知。第 \(i\) 个时刻车上新增 \(a_i\) 个人。求个时刻之后车上人数的最小可能值
-
思路
直接贪心，找到所有中被减的最多，这个的
abs就是其初始个数，然后直接按照题意模拟就过了QAQ，这题为啥不是B题int l,ans=INF,res; int sum,n; signed main(){ cin>>n; for(int i(1);i<=n;++i){ cin>>l;sum+=l; res+=l; ans=min(ans,res); } cout<<sum-(ans>0?0:ans)<<' '; return 0; }
-
-
\(\text{Problem - D}\) \(『\)\(\text{Synchronized Players}\)\(』\)
-
题意
\(n*n\)的二维网格，有障碍物
#，两个人P每次选定上下左右一个方向，使两人均往同方向移动一格。如果目的地是障碍物或出界，则不动
问最小的操作数，使得两人位于同一个格子。
-
思路
大力朴素BFS即可，复杂度上限 \(60^4\approx 1e7\)
struct butterfly{int x1,y1,x2,y2,step;}sec; const int dx[]={-1,0,1,0},dy[]={0,1,0,-1}; bool vis[65][65][65][65]; char a[1100][1100]; signed main(){ int n,x1,x2,y1,y2; queue<butterfly>q; cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ cin>>a[i][j]; if(a[i][j]=='P'){ a[i][j]='.'; if(!sec.x1) sec.x1=i,sec.y1=j; else sec.x2=i,sec.y2=j; } } q.push(sec); int ans=INF; while(!q.empty()){ butterfly fir=q.front(); q.pop(); if(vis[fir.x1][fir.y1][fir.x2][fir.y2]) continue; vis[fir.x1][fir.y1][fir.x2][fir.y2]=1; if(fir.x1==fir.x2&&fir.y1==fir.y2){ ans=min(ans,fir.step); continue; } for(int i=0;i<4;i++){ x1=fir.x1+dx[i], y1=fir.y1+dy[i], x2=fir.x2+dx[i], y2=fir.y2+dy[i]; if(x1<1||x1>n) x1=fir.x1; if(x2<1||x2>n) x2=fir.x2; if(y1<1||y1>n) y1=fir.y1; if(y2<1||y2>n) y2=fir.y2; if(a[x1][y1]=='#') x1=fir.x1,y1=fir.y1; if(a[x2][y2]=='#') x2=fir.x2,y2=fir.y2; q.push({x1,y1,x2,y2,fir.step+1}); } } cout<<((ans==INF)?-1:ans); }
-
-
\(\text{Problem - E}\) \(『\)\(\text{Smooth Subsequence}\)\(』\)
-
题意
给定一个数组\(a\)和一个数\(D\)，删去若干个数，使得剩余数俩俩差不超过D。
问删去个数的最小值。
-
思路
这DP...有点基础了吧，转移方程
\[f_i=\max\limits_{1\le j\le n,a_j\in[a_i-d,a_i+d]}f_j+1 \]\(O(n^2)\) 过不去，线段树优化一下结束了
没T4难
-
-
\(\text{Problem - F}\) \(『\)\(\text{Product Equality}\)\(』\)
-
题意
给定\(n\)个数 \(ai\)，问\((i,j,k)\)的数量，使得 \(a_i×a_j=ak\)
注意 \(ai≤10^{1000}\)
-
思路
还没改，hash秒了，赛后直接出思路，为啥我赛时不看一眼
-
-
\(\text{Problem - G}\) \(『\)\(\text{Smaller Sum}\)\(』\)
-
思路
这就一主席树板子，评价为史，史王，打完能掉忍者套和皇家凝胶那种
-
牛客多校程序设计竞赛
今天第一次打牛客的题，印象深刻
题\(\text{I}\)的\(std\)是错的，所以造的数据也是错的
官方题解最下面有个星尘的图片！！惊
-
原神题不做评价，前两天好像就是这场月赛
-
我们发现这其实是斐波那契第\(n+2\)项，然后矩阵快速幂加速即可
-
按照题意模拟即可，我直接暴力通过此题，但是
Dragon打错了，打成了Dargon，吃了一发法师 -
不会，官方题解说是倍增暴力计算，没看太懂，明天补\(qwq\)
(正在播放 - 『登陆宇宙』)
-
这题思路很简单
首先判断 \(m\) 为 \(1\) 的情况，此时先手必败
然后去找除了本身以外的最大约数，若比 \(k\) 小则先手必败
然后判断 \(n\) 的奇偶性，若 \(n\) 为偶数先手必败，反之先手必胜
-
直接暴力BFS即可，复杂度上限是\(O(6^6T)\)，可以通过此题
-
线段树/树状数组+二分答案，因为数据比较水可以不用在树上二分，复杂度 \(O(n \log^2 n)\)
-
这道题也是原，参见ARC076-D
只要用那题的排序里暴力加一维即可通过此题
-
这道题是比较难的题，赛时 \(4\) 人通过
\(dp\)题，不想改，明天看看有没有空吧
-
我们发现这道题可以用上限\(1e4\)颗线段树来维护，但是空间不够
考虑直接大力动态开点，空间复杂度\(O(n \log n)\)可过
-
直接看转换的规则，然后把所有敬业福都转化成其他福，用这些福中最小的除以2就是最优解
-
预处理前后缀和，然后枚举\(k_1\)长度区间的最大值然后枚举\(k_2\)长度区间即可
