9-7贝壳笔试，4题AK

9-7贝壳笔试，4题AK

num1

第一题
题意：石头剪刀布，已知牛妹和牛牛左手出什么右手出什么，但不知道牛牛会出左手还是右手，我们要求一下牛妹出哪只手赢的胜率高一些
思路：用牛妹的左手和牛牛两只手比较算出赢的场数，再用牛妹的右手和牛牛两只手比较算出赢的场数，判断一下牛妹左手赢的场数多一些还是
右手赢的场数多一些即可。

int check(char s,char t)
{
    if(s=='S'&&t=='J')
        return 1;
    if(s=='J'&&t=='B')
        return 1;
    if(s=='B'&&t=='S')
        return 1;
    return 0;
}
int main()
{
    int n,t;
    char a,b,c,d;
    scanf("%d",&t);
    getchar();
    while (t--)
    {
        scanf("%c %c %c %c",&a,&b,&c,&d);
        getchar();
        int y1=0;
        int y2=0;
        if(check(a,c)==1)
            y1++;
        if(check(a,d)==1)
            y1++;
        if(check(b,c)==1)
            y2++;
        if(check(b,d)==1)
            y2++;
        if(y1==y2)
        {
            printf("same\n");
        }
        else if(y1>y2)
        {
            printf("left\n");
        } else
        {
            printf("right\n");
        }
    }
    return 0;
}

num2

懒得写。

#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
const int maxn = 3e5 + 10;
char a[maxn];
int main()
{
   int n,t;
   while (~scanf("%d",&n)){
       scanf("%s",a);
       int ans=n;
       int i=0;
       int j=0;
       int k=1;
       while (k<=n/2){
           bool flag=true;
           j=k;
           i=0;
           while (i<k){
               if(a[i++]!=a[j++]) flag=false;
           }
           if(flag)
               ans=min(ans,k+1+n-2*k);
           k++;
       }
       printf("%d\n",ans);
   }
   return 0;
}

num3

题意：给定M种颜色，M*K种不能相邻关系，稳排序方案。
思路：这类题一般都是可以搜索做，而搜索一般都可以退出DP方案，而DP方案可以转化为矩阵乘法的，可以用矩阵乘法来加速。所以这题：搜索<DP<矩阵乘法。这里只讲DP。我们假设dp[i][j]表示第I位为j颜色的方案数，显然dp[i][j]+=dp[i-1][k]（j、k可以相邻）

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int maxn=1010;
int dp[maxn][11],mp[11][11];
int main()
{
    int T,N,M,K,x;
    scanf("%d",&T);
    while(T--){
        memset(mp,0,sizeof(mp));
        scanf("%d%d%d",&N,&M,&K);
        for(int i=1;i<=M;i++){
            for(int j=1;j<=K;j++){
                scanf("%d",&x);
                mp[x][i]=1;
            }
        }
        dp[0][0]=1;
        for(int i=1;i<=N;i++){
            for(int j=1;j<=M;j++){
                for(int k=0;k<=M;k++){
                    if(!mp[j][k]) {
                        dp[i][j]+=dp[i-1][k];
                        if(dp[i][j]>=mod) dp[i][j]-=mod;
                    }
                }
            }
        }
        int ans=0;
        for(int i=1;i<=M;i++) {
            ans+=dp[N][i];
            if(ans>=mod) ans-=mod;
        }
        printf("%d\n",ans);
    }
    return 0;
}

num4

为了没负数，我们把下标从-N到N，变为1-2N。然后开始区间DP。我们令dp[i][j]表示杀完[i,j]区间的最小代价，那么一般都可以有dp[i][j]=min(dp[i][j-1]+代价1,dp[i+1][j]+代价2)。
所以我们了没有后续性，我们可以把长度设为第一维。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2010;
int a[maxn],b[maxn],suma[maxn],sumb[maxn],dp[maxn][maxn];
int main()
{
    int T,N,M,K,x;
    scanf("%d",&N);
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=N+N;i++) {
        scanf("%d",&a[i]);
        suma[i]=suma[i-1]+a[i];
    }
    for(int i=1;i<=N+N;i++) {
        scanf("%d",&b[i]);
        sumb[i]=sumb[i-1]+b[i];
    }
    for(int L=1;L<=N+N;L++){
       for(int i=1;i<=N+1;i++){
            int j=i+L-1;
            if(i>N+1||j<N||j>N+N) continue;
            if(i==j) {
                 dp[i][j]=a[i];
            }
            else {
                int x=dp[i+1][j],y=dp[i][j-1];
                int nowx=sumb[j]-sumb[i]-suma[j]+suma[i]+dp[i+1][j];
                int nowy=sumb[j-1]-sumb[i-1]-suma[j-1]+suma[i-1]+dp[i][j-1];
                if(nowx<a[i]) x+=a[i]-nowx;
                if(nowy<a[j]) y+=a[j]-nowy;
                dp[i][j]=min(x,y);

            }
        }
    }
    printf("%d\n",dp[1][N+N]+1);
    return 0;
}