【CQ18阶梯赛第一场】题解

【A-风格不统一如何写程序】

输入字符串，得到长度，对于每个字符：如果是大写，则改为：‘_’+小写；如果是‘_’则忽略‘_’，并且把后面的小写改为大写。

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

using namespace std;

char c[];

int main()

{

    int N,len,i;

    scanf("%d",&N);

    while(N--){

        scanf("%s",c+);

        len=strlen(c+);

        for(i=;i<=len;i++){

            if(c[i]=='_') {

                i++;

                c[i]=toupper(c[i]);

            }

            else if(c[i]>='A'&&c[i]<='Z'){

                printf("_");

                c[i]=tolower(c[i]);

            }

            printf("%c",c[i]);

        }

        printf("\n");

    } return ;

}

【B-歌德巴赫猜想】

两种解法：

一：先把素数筛选出来，然后试探即可。筛选素数一般是埃氏筛法和欧式筛（不会的请自学）。

二：枚举p，q=n-p，然后判断p，q是否是素数。判断一个数X是否是素数的方式是枚举2-sqrt(X)，是否能被X整除。

代码是第一种解法的欧氏筛。

#include<cmath>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=;

int p[maxn+],vis[maxn+],cnt,N;

void solve()

{

    for(int i=;i<=N;i++){

        if(!vis[i]) p[++cnt]=i;

        for(int j=;j<=cnt&&i*p[j]<=N;j++){

            vis[i*p[j]]=;

            if(i%p[j]==) break;

        }

    }

}

int main()

{

    scanf("%d",&N);solve();

    for(int i=;i<=cnt;i++){

        if(!vis[N-p[i]]) {

            printf("%d %d\n",p[i],N-p[i]);

            return ;

        }

    }

}

【C-数组重排2】

显然，题意是要找最大上升子序列长度X，答案就是N-X，所以倒序检验是否是连续下降的，是则X++。

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#include<memory>

#include<cstring>

using namespace std;

int a[],ans,now;

int main()

{

    int i,j,n;

    scanf("%d",&n);

    for(i=;i<=n;i++) scanf("%d",&a[i]);

    now=n;

    for(i=n;i>=;i--){

        if(a[i]==now){

            ans++;

            now--;

        }

    }

    printf("%d\n",n-ans);

    return ;

}

【D-方格取数】

基础DP（动态规划），为了让两人路径不相交，我们使二人一起走，第一位从(2,1)出发，第二位从(1,2)出发，（保证第一位在第二位的下面，即i>j）在走X步的情况下，第一位走到(i,X-i)，第二位走到(j,X-j)，用dp[X][i][j]表示二人分别走到(i，X-i) (j,X-j)的最大值。

第一位可能从上面或者左边来，第二位同理。那么X的来源有(i,X-i-1)+（j，X-j-1）；(i,X-i-1)+(j-1,X-j);   (i-1,X-i)+(j,X-j-1) ;   (i-1,X-i-1)+(j-1,X-j)；分别取最优解即可。

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int dp[][][],a[][];

int main()

{

    int n,i,k,j;

    scanf("%d",&n);

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

     for(j=;j<=n;j++)

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

    dp[][][]=a[][]+a[][]+a[][]+a[][];

    for(i=;i<=n+n-;i++)

        for(j=;j<=n;j++)

         for(k=;k<=j-;k++){

          dp[i][j][k]=max(dp[i][j][k],dp[i-][j][k-]);

          dp[i][j][k]=max(dp[i][j][k],dp[i-][j][k]);

          dp[i][j][k]=max(dp[i][j][k],dp[i-][j-][k]);

          dp[i][j][k]=max(dp[i][j][k],dp[i-][j-][k-]);

          dp[i][j][k]+=a[j][i-j]+a[k][i-k];

    }

    printf("%d\n",dp[n+n-][n][n-]+a[n][n]+a[n][n]);

    return ;

}