2020ccpc

先写一下我做出来的题目的思路和题解 1010 1007 1003

1010 Reprots

这道题很简单，看看样例就知道满足的条件：0和1间隔出现就行，用异或（^）来完成就可以，只要任意相邻两个数异或的结果是1，就是yes，反之就是no

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int time;//声明次数
        cin>>time;
        int a[time];//建立数组
        int i;
        for(i = 0;i < time;i++ )//输入
        cin>>a[i];
        int flag = 1;//判断条件
        for(i = 0;i < time-1;i++)
        {
            if(a[i]^a[i+1])//判断两个相邻数是否不同
            {
                continue;
            }
            else {
                flag = 0;
                break;
            }
        }
        if(flag)
        {
            cout<<"YES"<<endl;

        }
        else cout<<"NO"<<endl;
    }
}

1007 CCPC Training Class

这个题的关键是读懂套娃的每一个部分都是什么意思（说实话，理解了一段时间）：

Lborderi 是代表把数组的部分或者全部分成两部分之后相同的最大值，

D表示Lborderi的长度，

W表示所有满足条件的字符串数组的最大长度。

刚开始的时候没有思路，也一直在本子上模拟，究竟是啥意思，但是题目最后有一段话

你可以任意地改变字符串s，让你可以随便排列字符串，

那我就把出现最多的字母放到开头就可以了，答案就变成了出现最多字母出现的次数

——————————————————————————————————————————

以上是补题过程中理解到的答案，实际情况是：

看了看样例，每一个样例的答案都是出现最多字母的的个数，然后试了试，，然后莫名其妙的ac了。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;int cnt = 1;
    while(n--)
    {

        int a[26] = {0};//用长度为26的数组来表示26个字母，元素代表出现的次数
        string s;
        cin>>s;
        int len = s.length();
        for(int i = 0;i < len;i++)
        {
            a[s[i]-'a']++;
        }
        cout<<"Case #"<<cnt++<<": "<<*max_element(a,a+26)<<endl;
    }


}

1003 Express Mail Taking

题意是有n个保险柜，m个快递，k是其中一个保险柜，并且打开其他保险柜需要在k这个保险柜来操作，求最短路径的长度

最开始的时候读错题意了，就很纳闷，以为每拿一次快递就必须回到第k个保险柜那里，所以最后的结果是所有的有快递的保险柜距离k的距离乘以2开始和结束两次到k的距离就是最后的答案，这样的话哪还有最短路径啊，然后，，，，wa

但是题中并没有说最后一个快递拿完了还要回到k然后才能走，但实际上不必要，可以找一个比k小并且距离k最大的快递，最后出去的时候顺手拿了，这样就有最短路径了。

所以答案就是，从2*(k-1)+2*abs（i-k)-min(i)

代码是队友的，因为这个题不是我写的

#include<cstdio>
#include<cstring>
#include<algorithm> 
using namespace std;
typedef long long ll;
const int maxn=2000005;
int a[maxn];
int main()
{
    int i,T,n,m,k,mi;
    ll ans;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d%d",&n,&m,&k);
        ans=2ll*(k-1);
        mi=k;
        for (i=1;i<=m;i++) 
        {
            scanf("%d",&a[i]);
            ans+=2ll*abs(a[i]-k);
            if (a[i]<mi) mi=a[i];
        }
        if (mi!=k) ans-=2ll*abs(mi-k);
        printf("%lld\n",ans);
     } 
    return 0;
}

————————————————————————————————————

下面是补充的题目（时间关系只补充了两个题目）

1005 Lunch

一道博弈题，比赛期间没有做出来，本来以为比较简单的问题，但实际上有一定难度

题意：一堆数字，每一回合一个人可以将其中一个数字变成大小为原来的k分之一的k个数字，谁先把所有的数字都变成1谁就赢了，问先手能不能赢。

找了大佬分析了一下，然后得到了nim博弈这么一个新名词

nim博弈：有n堆石子，两人轮流进行操作，每次可从任意一堆石子里取走任意多枚石子，不能不取，问先手必胜还是必败。

结论：判单异或和是否为0，如果为0则必败，否则就改变其中最大的一堆，让分开后的结果异或和为0；

这道题可以理解为石子数目为质因数个数的nim博弈（要考虑平方数字，比如9 = 3*3，这里3 是2两个质因子）。

代码就不贴了。。。。。。。。。

1011 3x3 Convolution

给你一个n阶方阵和一个3阶方阵，定义n阶矩阵C(A,K)，他的每一个元素满足