【比赛记录+题解】CET

A题：

由于太菜而一直没有AC。其实是一道01背包。。最后才AC的

01背包什么的自己去了解就行了吧

因为我\(DP\)太烂，所以不会\(DP\)的我也救不了了

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

#define MAXN 222

int f[MAXN][MAXN],d[MAXN],p[MAXN];

int main()

{

    int n,m,s;

    scanf("%d%d%d",&n,&m,&s);

    for (int i=1;i<=n;i++)

    {

        scanf("%d%d",&d[i],&p[i]);

    }

    for (int i=1;i<=n;i++)

    {

        for (int j=m;j>=0;j--)

        {

            if (j>=d[i])

            {

                f[i][j]=max(f[i][j],max(f[i-1][j-d[i]]+p[i],f[i-1][j]+s));

            }

            else

            {

                f[i][j]=f[i-1][j]+s;

            }

        }

    }

    printf("%d",f[n][m]);

}

\(B\)题：

字符串膜你题。

用\(char[]\)存储整个串，判断到四个目标串的首字母的时候直接枚举判断就行了。。

或者每次用\(string\)读入一整个单词，同上，枚举判断。（反正就是裸的字符串暴力膜你咋写都行。。）

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

string s;

int f1=0,f2=0,f3=0,f4=0;

string s1="sing",s2="dance",s3="rap",s4="basketball";

void c1(int l)

{

    int tot=0;

    for (int i=l;i<=l+3;i++)

    {

        if (s[i]!=s1[tot++])

        {

            return;

        }

    }

    f1++;

    return;

}

void c2(int l)

{

    int tot=0;

    for (int i=l;i<=l+4;i++)

    {

        if (s[i]!=s2[tot++])

        {

            return;

        }

    }

    f2++;

    return;

}

void c3(int l)

{

    int tot=0;

    for (int i=l;i<=l+2;i++)

    {

        if (s[i]!=s3[tot++])

        {

            return;

        }

    }

    f3++;

    return;

}

void c4(int l)

{

    int tot=0;

    for (int i=l;i<=l+9;i++)

    {

        if (s[i]!=s4[tot++])

        {

            return;

        }

    }

    f4++;

    return;

}

int main()

{

    bool flag=1;

    while (flag==1)

    {

        cin>>s;

        int len=s.size();

        for (int i=0;i<len;i++)

        {

            if (s[i]=='s')

        	{

        		c1(i);

        		continue;

        	}

        	if (s[i]=='d')

        	{

        		c2(i);

        		continue;

        	}

        	if (s[i]=='r')

            {

        		c3(i);

        		continue;

        	}

        	if (s[i]=='b')

        	{

        		c4(i);

        		continue;

        	}

        }

        if (s[len-1]=='@')

        {

            flag=0;

            break;

        }

    }

    printf("sing : %d\n",f1);

    printf("dance : %d\n",f2);

    printf("rap : %d\n",f3);

    printf("basketball : %d\n",f4);

    return 0;

}

\(C\)题：

是个什么鬼题目

\(30\)分做法：输出\(1\)

\(70\)分做法：输出\(2\)

以上纯属瞎说233，下面是真题解

结论题。应该很多人都发现了结果是\(1\)或者\(2\)（23333）

至于为什么除1之外，都满足偶数答案为\(1\)，奇数答案为\(2\)，

首先需要了解一下位运算。

异或运算（^）：

同0异1。

比如说\(10^2\)，

\(10\)的二进制：\(1\) \(0\) \(1\) \(0\)

\(02\)的二进制：\(0\) \(0\) \(1\) \(0\)

\(00\)计算结果：\(1\) \(0\) \(0\) \(0\)

所以\(10^2=8\)。

就是各个对应二进制位，如果两位相同即为0，不同即为1。

（最后一行的00是用来占位的不用理w）

与运算（&）：

皆1为1否则为0。

\(10&2=2\)

或运算（&）：

皆0为0否则为1。

\(10&2=10\)

（自行膜你）

正题。

对于\(1\)：

\(1\) \(xor\) \(1=0\)。通过上面的解释我们知道 \(n xor n=0\)。

对于一个（非0）偶数\(n\)：

\(n\) \(and\) \(1=0\)。

由于\(n\)是一个偶数，所以\(n\)的二进制末位为\(0\)。

\(n\) \(and\) \(1\)即：

\(xxxxxxxxxxxxx0\)

\(0000000000001\)

。

\(and\)运算必须满足对应的二进制位都为\(1\)，对应的结果位才为\(1\)。由于\(1\)的二进制除了末位都为\(0\)，所以\(n\)除了末尾以外的二进制位都被清零。

而\(n\)本身的末位就为\(0\)，所以结果末位也为\(0\)。

所以若\(n\)为偶数，满足\(n\) \(and\) \(1=0\)。

即\(ans=1\)。

对于一个（非1）奇数\(n\)：

由于\(n\)是一个奇数，所以\(n\)的二进制末位为\(1\)。

那么可以通过\(n\) \(xor\) \(1\)使得\(n\)变成一个偶数。

即：

\(xxxxxxxxxxxxx1\)

\(0000000000001\)

\(xxxxxxxxxxxxx0\)

那么我们通过花费\(1\)就使得一个奇数变成了一个偶数。接下来的操作就和偶数的处理方式一样了。

所以若\(n\)为一个（非1）奇数，\(ans=2\)。

所以这道题差不多就是个判断奇偶性233

但是看到数据范围：\(10^{10000}\)

这个时候就可以用字符串存储，直接挑最后一位来判断就行了。。

记得判断\(1\)的时候别忘了判断字符串长度为\(1\)啊23333

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

int n,m;

string s;

int main()

{

    cin>>s;

    int len=s.size();

    int n=s[len-1]-'0';

    if (len==1&&n==1)

    {

        printf("1");

        return 0;

    }

    if (!(n&1))

    {

        printf("1");

        return 0;

    }

    printf("2");

    return 0;

}

\(D\)题：

签到题！

\(AC\)数还是令人满意的。。

等差数列和等比数列的基本性质大家应该都了解w。

正常的等差数列判断：\(b-a==c-b\)

正常的等比数列判断：\(b/a==c/b\)

这个时候的卡点：

在验题的时候发现一个问题，有人用一个\(int\)变量来存储（b/a）以及（c/b）

于是有了这么一个数据：

\(12\) \(23\) \(45\)

然后可想而知233

接着想卡一下\(b/a==c/b\)做法的，于是有了这么三个数据：

1.\(0\) \(0\) \(0\)

2.\(0\) \(0\) \(1\)

3.\(0\) \(1\) \(2\)

这个时候正确的写法是，判断\(a*c==b*b\)。

接着想到输入都在\(int\)范围内，于是又出了两个个数据来卡：

2000000000 1 2000000000 （卡单独\(int\)变量存）

15970 1006110 63384930 （\(ans\)超出\(int\)范围）

记住，输入在\(int\)范围内，并不代表计算过程和输出在int范围内233

别的数据点都正常啦w。。

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

int main()

{

//	freopen("test4.in","r",stdin);

//	freopen("test4.out","w",stdout);

    int a,b,c;

    scanf("%d%d%d",&a,&b,&c);

    if (a==0&&b==0&&c==0)

    {

        printf("Arithmetic progression!\n0\n");

        return 0;

    }

    if (b==0||c==0)

    {

        printf("N0!!!!!\n");

        return 0;

    }

    if (a==0)

    {

        if (b-a==c-b)

        {

            printf("Arithmetic progression!\n%d\n",c+c-b);

            return 0;

        }

    }

    if ((a*c==b*b)&&(b-a==c-b))

    {

        printf("YE5!\n%d %lld\n",c+c-b,(long long)c/b*c);

        return 0;

    }

    if (a*c==b*b)

    {

        printf("Geometric progression!\n%lld\n",(long long)c/b*c);

        return 0;

    }

    if (b-a==c-b)

    {

        printf("Arithmetic progression!\n%d\n",c+c-b);

        return 0;

    }

    printf("N0!!!!!\n");

    return 0;

}

感谢陈浩宇在验题中发现了标程的错误

感谢林倩瑜在验题中给了出题人更加\(duliu\)的数据灵感

最终感谢\(wjd\)，\(xn\)，\(zzx\)学长们辛勤地为了初一OIer们的成长出题（

（我好咸啊233 不刷题在这里写题解）