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\) 的情况。
  - 可以特判一下链的情况，估计能过（口胡）。
正解：贪心