2024牛客寒假算法基础集训营3（B、D、G、M)

B、智乃的数字手串

题目：

解题思路：（博弈论）

n=1时，必然是qcjj赢；（必胜态）

n=2时，无论是奇数还是偶数，qcjj必输；（必败态）

n=3时，qcjj可以取出一个数将其转换为n=2时的状态，这对zn来说必输；（必胜态）

n=4时，同样可以转换到n=3时的转态······

总结得到n是奇数时，qcjj赢；n是偶数时，zn赢。

代码如下：

#include #include #define int long long
#define endl '\n'
using namespace std;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        int a[30];
        for(int i=1;i<=n;i++)
            cin>>a[i];
        if(n%2==0)cout<<"zn"< 
D、chino's bubble sort and maximum subarray sum(easy version)
 
题目：
 
解题思路：
 
此题数组的顺序是一定的，当k=1时，只有相邻的两个元素可以交换。求最大子段和，我看了一下方法有很多，当然复杂度越小越好。
 
（求最大子段和的方法可以参考：连续子数组的最大和问题（五种解法）-CSDN博客）
 
代码如下：
 
#include #include #define int long long
#define endl '\n'
using namespace std;
int n,k,a[1111],sum=-1e10;
void gcd()        //求整个数组的最大子段和
{
    int s=0;
    for(int i=1;i<=n;i++)    //扫描法
    {
        if(s<0)s=a[i];
        else s+=a[i];
        sum=max(sum,s);
    }
    /*
    int s=0,m=0;
    for(int i=1;i<=n;i++)
    {
        s+=a[i]; 
        sum=max(sum,s-m);
        m=min(m,s);
    }    //这是参考某位大佬的代码，暂时没看懂
    */
}
signed main()
{   
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    gcd();
    if(k==1)
    for(int i=1;i 
G.智乃的比较函数(easy version)
 
题目：
 
解题思路：
 
这题理解了半天，发现它是问你是否产生逻辑矛盾，这与顺序没有太大关系。而逻辑矛盾就是指当x和y的值相等时，cmp(x,y)=cmp(y,x)=1；另外当n=2时，如果第一组数据a,b按照一定顺序排列，并且第二组数据与第一组数据a,b相同，那么相应的顺序也要相同，否则也会产生逻辑错误。
 
代码如下：
 
#include #include #define int long long
#define endl '\n'
using namespace std;
signed main()
{   
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n,x1,y1,z1,x2,y2,z2,flag=0;
        cin>>n;
        if(n==1)
        {    
            cin>>x1>>y1>>z1;
            if(z1==1&&x1==y1)flag=1;
        }
        else if(n==2)
        {
            cin>>x1>>y1>>z1>>x2>>y2>>z2;
            if(z1==1&&x1==y1)flag=1;
            if(z2==1&&x2==y2)flag=1;
            if(x1==x2&&y1==y2&&z1!=z2)flag=1;
            if(z1==1&&x1==y2&&x2==y1&&z1==z2)flag=1;
        }
        if(flag==1)cout<<"No"< 
M.智乃的36倍数(normal version)
 
题目：
 
解题思路：
 
拼接后的数为,k为b的位数，然后取模运算分别%36.
 
代码如下：
 
#include #include #define int long long
#define endl '\n'
using namespace std;
int x,n,s[22][38]= {0},m[22],sum=0;
void gcd(int a,int b,int c,int d)
{
    int k;
    k=(b*m[c]+d)%36;    //取模运算
    if(k)return;        //如果不是36倍数，返回
    sum+=s[a][b]*s[c][d];    //用相乘是因为输入的数据可能会有重复
    if(a==c&&b==d)      //当选取的两个数相同时，要舍弃其中一种情况
        sum-=s[a][b];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    m[0]=1;
    for(int i=1; i<=20; i++)
        m[i]=m[i-1]*10%36;    //计算10的k次方的位数
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>x;
        int k=0,y=x;
        while(x)
        {
            x=x/10;
            k++;
        }    //记录每个数据的位数
        s[k][y%36]++;
    }
    for(int a=1; a<=18; a++)    //第一个数位数
        for(int b=0; b<36; b++)    //第一个数余数
            for(int c=1; c<=18; c++)    //第二个数位数
                for(int d=0; d<36; d++)    //第二个数余数
                    gcd(a,b,c,d);
    cout<