2023年多校联训NOIP层测试4

爆零了

T1 幸运数字 \(0pts\)

T2 密码 \(0pts\)

• 没做到，咕了。

T3 小X和他的朋友们 \(0pts\)

• 没做到，咕了。

T4 树上询问 \(0pts\)

• 没做到，咕了。

【LGR-150-Div.2】洛谷 8 月月赛 I & RiOI Round 2

T1 luoguP9496 「RiOI-2」hacker \(100pts\)

• 赛场上读假题了，以为是按位或上一个操作形成的数字，觉得是不可做题，跳到了T2。

• 将 \(n,m\) 分别转成二进制，易知答案结果只有 \(0,1,2\) ,然后进行分类讨论：

  • 若转出二进制后第 \(i\) 位 \(n\)的值为 \(1\) ，\(m\)的值为 \(0\) ,需要进行 「ACCEPT」操作。
  • 若转出二进制后第 \(i\) 位 \(n\)的值为 \(0\) ，\(m\)的值为 \(1\) ,需要进行 「BOTH」操作。

    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define sort stable_sort
    #define endl '\n'
    ll aa[100],bb[100];
    int main()
    {
        ll n,i,j,a,b,la,lb,sum1,sum2;//十年OI一场空，不开 long long见祖宗
        cin>>n;
        for(i=1;i<=n;i++)
        {
            cin>>a>>b;
            if(a==b)
            {
                cout<<"0"<<endl;
            }
            else
            {
                la=lb=sum1=sum2=0;
                while(a>0)//转二进制，倒序储存，方便处理
                {
                    la++;
                    aa[la]=a%2;
                    a/=2;
                }
                while(b>0)
                {
                    lb++;
                    bb[lb]=b%2;
                    b/=2;
                }
                if(la>lb)
                {
                    for(j=lb+1;j<=la;j++)//空位补零，下同
                    {
                        bb[j]=0;
                    }
                    lb=la;
                }
                if(la<lb)
                {
                    for(j=la+1;j<=lb;j++)
                    {
                        aa[j]=0;
                    }
                    la=lb;
                }
                for(j=1;j<=la;j++)
                {
                    if(aa[j]==1&&bb[j]==0)
                    {
                        sum1=1;
                    }
                    if(aa[j]==0&&bb[j]==1)
                    {
                        sum2=1;
                    }
                }
    		    cout<<sum1+sum2<<endl;
            }
        }
        return 0;
    }
    

T2 luoguP9497 「RiOI-2」weight \(100pts\)

• 赛场上又双叒叕读假题了，觉得是不可做题，跳到了T3。

• 正解：将矩阵压缩成一维， \(sort\) 一遍+二分查找即可。

  #include<bits/stdc++.h>
  using namespace std;
  #define ll long long
  #define sort stable_sort
  #define endl '\n'
  int a[20000000];
  int main()
  {
      int n,q,i,j,x,num;
      cin>>n>>q;
      for(i=1;i<=n;i++)
      {
          for(j=1;j<=n;j++)
          {
              cin>>a[j+(i-1)*n];
          }
      }
      sort(a+1,a+1+n*n);
      for(i=1;i<=q;i++)
      {
          cin>>x;
          num=n*n-(lower_bound(a+1,a+1+n*n,x)-a)+1;
          cout<<min(n,num)<<endl;//记得和 n 取min
      }
      return 0;
  }
  

T3 luoguP9498 「RiOI-2」equals \(55pts\)

• 直接从T3开写，起初爆搜骗到了 \(40pts\) ，优化到 \(55pts\) ，才去打的T1和T2。
• 部分分： 爆搜（C++大法好，先剪枝后爆搜）
  • \(55pts\)
    • 隔壁wkh卡到了 \(95pts\)，minecraft418爆搜AC了，但是我这个才 \(55pts\)。
  • \(95pts\)
    • wkh教我的对 \(memset\) 的优化 ，记一个 \(g\) 记录第 \(g\) 次进行搜索，那么当\(vis[x]\ne g\) 则等价于用 \(memset\) 初始化全 \(0\) 的情况。
    • 可以特判一下链的情况，估计能过（口胡）。
• 正解：贪心

T4 luoguP9499 「RiOI-2」change \(0pts\)

• 没做到，咕了。

【LGR-150-Div.1】洛谷 8 月月赛 I & RiOI Round 2

T1 luoguP9498 「RiOI-2」equals \(55pts\)

• 同 \(2C\) 。

T2 luoguP9499 「RiOI-2」change \(0pts\)

• 没做到，咕了。

T3 luoguP9500 「RiOI-2」tnelat \(0pts\)

• 没做到，咕了。

T4 luoguP9501 「RiOI-2」likely \(0pts\)

• 没做到，咕了。