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;
}