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);
}