开始: 2023-08-05 08:20:00

0805算法入门(2)中期测试

结束: 2023-08-05 11:05:00
当前  2025-01-24 17:40:40  类型: IOI  状态: 已经结束 

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