P1 回文
我们利用折半,如果i和n-i-1这两个不同,那么增加一个修改次数,直接cnt++即可!
P2 连环画
这个题目非常想梦境盗墓,我们可以直接用队列模拟即可!
while( q.size() > 1 ) { while( f[now] == true ) now ++; q.pop(), q.pop(); q.push(now); f[now] = 1; }
P3 平方数之和
比较明显的双指针碰撞,我们定义l和r指针,注意r取n开方数即可
for(ll l=1; l<r; l++) { while(l*l+r*r>n) r--; if(l*l+r*r==n) cout<<l<<" "<<r<<endl; }
P4 容器
利用左右指针,面积是l*h,这里要注意h取得是短的那一边,如果h[L]<h[R],那么我们可以直接移动l,反之亦然。
while(l < r){ ans = max(ans,min(a[l],a[r])*(r-l)); if(a[l]<a[r])l++; else r--; }
P5 填坑
就是利用双重for循环查找每个点,找到一个有数字的,我们可以尝试去试着计算坑的面积,算出来之后,记得利用max更新一下
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) if(mp[i][j]) { int k=bfs(i,j); ans=max(ans,k); }
这里bfs这里,可以尝试一边记录坑的大小,一边清空,这样子可以节约一个vis数组
for(int i=0; i<4; i++) { int tx=p2.x+nx[i],ty=p2.y+ny[i]; if(mp[tx][ty]) { cnt+=mp[tx][ty]; p1.x=tx,p1.y=ty; mp[tx][ty]=0; q.push(p1); } }
这里只给了一部分代码,请大家自己尝试写完
P6 变数字
这个题目和电梯差不多,我们可以尝试往数字变化的四个方向bfs拓展即可!
但是如果超过b就没必要继续走+1,*2,*3这几个,如果大于b可以走-1这个方向
这里给出一小部分代码,请大家自行尝试!!!!
if(p2.x>b) { long long t=p2.x-1; if(!vis[t]) { p1.x=t,p1.step=p2.step+1; vis[t]=1; q.push(p1); } } if(p2.x<b) { long long t=p2.x*2; if(!vis[t]) { p1.x=t,p1.step=p2.step+1; vis[t]=1; q.push(p1); }