牛客周赛133 | 部分题解 – 逢絮聆风—

好评！好题！没想到回学校第一把周赛如此有强度。

钝评

跳过这个部分，我们直接开始。

A：小红的闭合标签

签到题。一如既往友善，直接插入一下斜杠即可。

void solve()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    cout<<"





B：小红的众数



同样签到。开一个桶计数。如果 $x$ 这个数字本来就出现过，那么现在数组中的众数出现次数减去 $x$ 的出现次数就是答案。如果没有出现，那么直接输出现在数组中众数的出现次数。



void solve()
{
    int n;
    ll x;
    cin>>n>>x;
    vector a(n);
    unordered_map cnt;
    ll maxc=0;
    ll maxn=-1;
    for(int i=0;i>a[i];
        cnt[a[i]]++;
        maxc=max(maxc,cnt[a[i]]);
    }
    if(cnt[x]==maxc) cout<<"0";
    else cout<




C：小红的数字查找



好题开始了！首先你需要知道一个前置知识：可分解定理。任何一个大于1的自然数 N, 如果N不为质数，那么N可以唯一分解成有限个质数的乘积 N= $P_1^{a_1}*P_2^{a_2}*...*P_n^{a_n}$ ，这里P1<P2<P3......<Pn均为质数，其中指数ai是正整数。这样的分解称为 N 的标准分解式。



那么，对于一个数字 $x$ ，我们可以将  $x$  分解为  $x = a^{2} \times b$ ，其中  $b$  是  $x$  的平方自由部分，即  $b$  中每个质因子的指数为 0 或 1（所有奇数次质因子的乘积）。这样， $x \times y$ 为完全平方数当且仅当  $b \times y$  是完全平方数，即  $y$  可以写成  $y = b \times c^{2}$  的形式，其中 c 为正整数。



所以，我们只需要找到一个正整数  $c$  使得  $y$  在区间内即可。对  $x$  进行质因数分解，将所有出现奇数次幂的质因子乘起来即得  $b$ 。或者先找出  $x$  的最大平方因子  $a^{2}$ （即  $a$  为满足  $a^{2} ∣ x$  的最大整数），则  $b = x / a^{2}$ 



void solve()
{
    ll x,l,r;
    bool flag=false;
    cin>>x>>l>>r;
    int a=1;
    int tmp=x;
    for(int i=2;i*i<=tmp;i++)
        {
            if(tmp%i==0)
            {
                int cnt=0;
                while(tmp%i==0)
                {
                    tmp/=i;
                    cnt++;
                }
                if(cnt%2==1) a*=i;
            }
        }
        if(tmp>1) a*=tmp;
        int lmt=sqrt(r);
        //bool flag=false;
        ll y;
        int t=1;
        while(t*t<=r/a)
        {
            ll val=1ll*a*t*t;
            if(val>=l&&val<=r)
            {
                y=val;
                flag=true;
                cout<




D：小红的异或分组



对我来说在近期写过的题目中EDU意义重大。你肯定还记得异或的性质对吧。为了防止你遗忘，我还是再写一下此处会用到的性质： $x \oplus x=0$ ， $0 \oplus x=x$ 。



联想一下，前缀和可以通过相减的方式在 $O(1)$ 的时间内求出子段的和，而前缀异或和也相似。我们假设前 $i$ 个元素的异或和为 $x$ ，前 $j$ 个元素的异或和为 $y$ （ $j>i$ ），我们希望求出第 $i+1$ 到第 $j$ 个元素的异或和。其中我们可以拆分 $y$ 为 $x \oplus z$ .这个 $z$ 就是我们希望求出来的结果。那么我们不难发现，用 $pref_i$ 代指 $x$ ，用 $pref_j$ 代指 $y$ ，那么：



 $pref_i \oplus pref_j = x \oplus y=x \oplus x \oplus z$ ，由于第一个性质，所以也就有：



 $x \oplus x \oplus z = 0 \oplus z = z$ 



这下懂了吧，这就是前缀异或和。



接下来就好办了。由于三段异或和相等，设每段异或和为  $x$  ，那么就有




 $T = s u m [a] \oplus s u m [b] \oplus s u m [c] = x \oplus x \oplus x = x$ 



第一段  $s u m [a] = p r e [a] = x$ 



第三段  $s u m [c] = p r e [n] \oplus p r e [b] = x \oplus p r e [b] = x \to p r e [b] = 0$ 




所以我们只要找到  $p r e [a] = T$  且  $p r e [b] = 0$  的  $(a, b)$  对的数量即可。



 $n^{2}$  为  $4 \times 1 0^{10}$  量级，注意使用  $64$  位存储。



void solve()
{
    int n;
    cin>>n;
    vector a(n),pref(n+1,0);
    for(int i=0;i>a[i];
        pref[i+1]=pref[i]^a[i];
    }
    ll tot=pref[n];
    ll res=0;
    int cnt=0;
    for(int i=1;i




E：小红的路径



精彩绝伦！在食用题解前请一定要确保您已经充分阅读理解题意并手动把玩过一部分样例。我们会对所有可能的情况进行分类归纳，所以您也不妨试试这么做。



首先先理解，怎么样的情况下我们无法构造。随手画一个长为 3 的矩阵，你就会发现：如果在同一列（但不是最左端或者最右端）或“对角线”位置上，那么肯定会被堵死，构造不出路线。形式化地，我们写为：



if(((x1+x2)%2==(y1+y2)%2)||(y1==y2&&y1!=1&&y1!=n))



如果这一步您无法理解，请先根据我说的进行一些尝试，验证一下上述结论。



接下来我们开始考虑构造方案。首先我们想，如果起点终点分别在矩阵左上角和右下角，那我们可以通过“Z”字形走法填充整个地图。您同样可以构造一些例子手动进行模拟。



那么，如果他们不再如此极端的位置该怎么办呢？非常好说，我们假设起点是偏左的，那么我们只需要先走到最左侧，然后往上/往下走一步，再一直走到起点的正下方/正上方，接下来开始“Z“字蠕动，直到走到终点正上方/正下方，接下来再走到最右端，往上/往下走一步，再向左走到终点。



听起来就很烦对吧，放心！代码写起来更是一坨！当然也可能只是我的代码非常的不优雅。



void solve()
{
    int n,x1,x2,y1,y2;
    cin>>n>>x1>>y1>>x2>>y2;
    string res="";
    if(((x1+x2)%2==(y1+y2)%2)||(y1==y2&&y1!=1&&y1!=n))
    {
        cout<<-1;
        return ;
    }
    // 我们不在乎起点偏左还是右 因为路径可逆
    // 所以我们干脆统一让起点偏左
    // 如果起点在右侧怎么办？对称一下构造方法就好啦！
    else if(y1==y2)
    {
        if(y1==1)
        {
            for(int i=1;i1;i--) cout<<"L";
        if(x1==1) cout<<"D";
        else cout<<"U";
        for(int i=1;i<=y1;i++) cout<<"R";
        int x=(x1+1)%2,y=y1+1;
        while(yy2;i--) cout<<"L";
    }
    else
    {
        for(int i=y1;i=y1;i--) cout<<"L";
        int x=(x1+1)%2,y=y1-1;
        while(y>y2)
        {
            x=(x+1)%2,y--;
            if(x1==1) cout<<"UL";
            else cout<<"DL";
            if(y2==y) break;
            x=(x+1)%2,y--;
            if(x1==1) cout<<"DL";
            else cout<<"UL";
        }
        for(int i=y;i>1;i--) cout<<"L";
        if(x==1) cout<<"D";
        else cout<<"U";
        for(int i=1;i




F题......我是蒟蒻我还不会（）留给各位神犇们解决啦。