B-NCPC

https://ac.nowcoder.com/acm/contest/120562/B

题意：选手对决：每一轮选两个选手对决如果两人的披萨美味值不同 → 数值低的被淘汰如果两人的披萨美味值相同 → 两人都被淘汰持续对决直到只剩 1 人（获胜）或无人剩下（全部淘汰）问题：对每一个选手，判断是否存在一种对决顺序，让他成为最后的唯一幸存者，是则输出 1，否则输出 0

思路：分两种情况，一、ai不是最大值，小于ai的部分可以跟自己比然后被消掉，大于等于ai的部分可以跟最大值比然后被消掉，最后只要判断最大值个数，如果最大值是偶数那最大值可以两两相消，最后只剩ai，如果最大值是奇数那最后肯定只剩下最大值；二、ai是最大值，小于ai的部分可以跟自己比然后消掉，等于自己的部分如果是偶数那场上就一个不留，如果是奇数那剩下的两两相消剩下ai

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        int n;
        cin>>n;
        vector<int>arr(n);
        int maxx=-1;
        int cnt=0;
        for(int j=0;j<n;j++)
        {
            cin>>arr[j];
            maxx=max(maxx,arr[j]);
        }
        for(int j=0;j<n;j++)
        {
            if(arr[j]==maxx)
            {
                cnt++;
            }
        }
        for(int j=0;j<n;j++)
        {
            if(arr[j]!=maxx)
            {
                if(cnt%2==0)
                {
                    cout<<1;
                }
                else
                {
                    cout<<0;
                }
            }
            else
            {
                if(cnt%2!=0)
                {
                    cout<<1;
                }
                else
                {
                    cout<<0;
                }
            }
        }
        cout<<endl;
    }
    return 0;
}

I-01回文

https://ac.nowcoder.com/acm/contest/120562/I

题意：给你一个由 0 和 1 组成的矩阵，对矩阵里的每一个位置 (i,j)，你需要判断：从 (i,j) 出发，能否找到一条不重复走点的简单路径，走到另一个不同的位置 (x,y)。这条路径上的所有数字按顺序连起来，是一个回文串（正读反读都一样）。如果能找到这样的路径，输出 Y；否则输出 N。

思路：已知100..01,11,011.10,00是回文，所以如果当前是1那只要走到1停止，产生的数就是回文；如果当前是0只要走到0停止，产生的数就是回文。所以题目就变成了遍历1和0的个数，当前是1的话，如果矩阵有两个以上的1，那肯定能产生回文；当前是0的话，如果矩阵有两个以上0，那肯定也能产生回文

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        int n,m;
        cin>>n>>m;
        int x=0;//计算1个数
        int y=0;//计算0个数
        char arr[n][m];
        for(int j=0;j<n;j++)
        {
            for(int l=0;l<m;l++)
            {
                cin>>arr[j][l];
                if(arr[j][l]=='1')
                {
                    x++;
                }
                else
                {
                    y++;
                }
            }
        }
        for(int j=0;j<n;j++)
        {
            for(int l=0;l<m;l++)
            {
                if(arr[j][l]=='1')
                {
                    if(x>=2)
                    {
                      cout<<"Y";
                    }
                    else
                    {
                      cout<<"N";
                    }
                   
                }
                else
                {
                    if(y>=2)
                    {
                        cout<<"Y";
                    }
                    else
                    {
                        cout<<"N";
                    }
                }
            }
            cout<<'\n';
        }
        
    }
    return 0;
}

F-x?y?n!

https://ac.nowcoder.com/acm/contest/120562/F

题意：给你一个整数 n，你需要找到两个整数 x 和 y：满足 gcd(x, y) = n，且 x ≠ y，1 ≤ x, y < 2^63 让 x 和 y 的按位异或尽可能小，输出满足条件的一对解即可

思路：异或：二进制每一位不同为1，相同为0（如1001^0011=1010）所以可以看出异或是不带进位的加法和不退位的减法，可以得出x+y>=x^y>=|x-y|,所以要x^y尽可能小就要是|x-y|;又gcd(x,y)=n，所以x是n的倍数，y是n的倍数（x=an,y=bn，且a与b互质）所以x^y=|x-y|=n。假设n=1011，构造x=10110000,y=10111011，这样x就等于n2的四次，y等于n2的四次+n，保证了相差等于n，且异或也为n

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    long long t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        long long n;
        cin>>n;
        string s=bitset<32>(n).to_string();
        long long lenth=s.size()-s.find('1');//计算n转换为二进制的位数
        long long x=n<<lenth;//n*2的k次
        long long y=x+n;//n*2的k次+n，保证|x-y|=n
        cout<<x<<" "<<y<<endl;
    }
    return 0;
}

H-权值计算

https://ac.nowcoder.com/acm/contest/120562/H

题意：给定一个数组，先计算所有非空子数组的权值，再把这些权值全部相加，输出最终总和。其中：一个子数组的权值= 从左到右遍历该子数组时，到当前位置为止子数组内不同元素的个数的累加和。

思路：直接对每个子数组求权值太过复杂，可以对每个元素求出他对整个权值的贡献，比如131，计子数组的左端点为l，右端为r，第一个1他的l就一个，r有三个，总贡献为1+2+3；对于第二个数2，他的左端l有两个，r有两个，先固定一个左端求他的贡献是1+2,有两个l，再乘2,；对于第三个数1，他在前面有重复的1，所以他要产生贡献l必须从第一个1后面取，则l有两个，r就一个，贡献是1*2，最终得出每一个值的贡献等于，（当前的坐标i-前面重复出现的坐标j）等差数列求和(1+n-i+1)(n-i+1)/2，最后将每个元素的权值相加

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    long long t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        long long n;
        cin>>n;
        vector<long long> arr(n+1);
        map<long long,long long> mp;
        for(int j=1;j<=n;j++)
        {
            cin>>arr[j];
        }
        long long sum=0;
        for(int j=1;j<=n;j++)
        {
            if(mp.find(arr[j])==mp.end())
            {
                sum+=j*(1+n-j+1)*(n-j+1)/2;
                mp[arr[j]]=j;
            }
            else
            {
                sum+=(j-mp[arr[j]])*(1+n-j+1)*(n-j+1)/2;
                mp[arr[j]]=j;
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

题解

B-NCPC

I-01回文

F-x?y?n!

H-权值计算