第七届省赛赛前交流赛部分题解

谁践踏了优雅 2022-08-27 04:41 170阅读 0赞

A题： Yougth's Game\[Ⅲ\]（ 区间dp ）

这是在省赛前热身赛出的题目，可能是题目中有用到博弈的思想，很多人都在做，而且在尝试暴力。但是没有人往dp的方向上想。

题目类型：动态规划+博弈 分析：题意描述的很清楚，就是选择在两端取数，当前取的数不仅能够影响下一次的结果，而且能够影响后面的结果。。。又是一个求最优值，那么是不是可以往dp的方向上想了。区间dp 定义状态dp\[ i \] \[ j \] 为从 i 到 j 上A的得分，那么B的得分就是sum（i,j）-dp\[ i \] \[ j \] 转移方程 : **dp\[i\]\[j\]=max(dp\[i\]\[j\],a\[i\]+(sum\[j\]-sum\[i\]-dp\[i+1\]\[j\])); 表示区间i--j取第一个** **dp\[i\]\[j\]=max(dp\[i\]\[j\],a\[j\]+(b\[j-1\]-b\[i-1\]-dp\[i\]\[j-1\])); 表示区间i--j取最后一个**

代码：

#include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    const int N = 1200;
    int a[N],dp[N][N],n;
    int b[N];
    int main()
    {
        while(~scanf("%d",&n)&&n)
        {
            b[0]=0;
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
                b[i]=b[i-1]+a[i];
            }
            for(int l=1;l<=n;l++)
            {
                for(int i=1,j=l;j<=n;i++,j++)
                {
                    dp[i][j]=-99999999;
                    dp[i][j]=max(dp[i][j],a[i]+(b[j]-b[i]-dp[i+1][j]));
                    dp[i][j]=max(dp[i][j],a[j]+(b[j-1]-b[i-1]-dp[i][j-1]));
                }
            }
            printf("%d\n",dp[1][n]-(b[n]-dp[1][n]));
        }
        return 0;
    }

E：Yougth's Game\[II\]

题目类型：组合博弈

其实就是一个sg函数，sg函数讲解：[讲解][Link 1]

分析：题目可以抽象成一个取石子游戏，三堆石子x，y，x\*y，那么就抽象成了经典的取石子游戏。

每次可以取得数目是给定的，谁最后取完谁赢。

求出三个数的sg值，然后异或就是ans

代码：

#include<stdio.h>
    #include<string.h>
    #include <string>
    #include <iostream>
    using namespace std;
    
    const int N = 10008;
    int s[108],t;
    int sg[N];
    bool hash[N];
    void sg_solve(int *s,int t,int N)   //N求解范围 S[]数组是可以每次取的值，t是s的长度。
    {
        int i,j;
        memset(sg,0,sizeof(sg));
        for(i=1;i<=N;i++)
        {
            memset(hash,0,sizeof(hash));
            for(j=0;j<t;j++)
                if(i - s[j] >= 0)
                    hash[sg[i-s[j]]] = 1;
            for(j=0;j<=N;j++)
                if(!hash[j])
                    break;
            sg[i] = j;
        }
    }
    
    int main()
    {
        int x,y;
        while(~scanf("%d%d",&x,&y))
        {
            int n;
            scanf("%d",&n);
            for(int i=0;i<n;i++)
                scanf("%d",&s[i]);
            sg_solve(s,n,N);
            if((sg[x]^sg[y]^sg[x*y])==0)
                printf("Yougth is best\n");
            else
                printf("No\n");
        }
        return 0;
    }

H题：合并游戏

题目类型：状态压缩动态规划

分析：给出每两个石子合并蹦出的金币，求所有石子合并之后蹦出的金币，分析可以发现不同的合并顺序会有不一样的结果，然后满足最优子结构的性质，那就是确定某几个石子合并的到的最大金币永远是确定的，那么我们可以用dp来求解，而这个题目恰好是一个从0到所有合并的一个过程，用二进制压缩来表示状态。

定义状态：dp【st】表示状态st中为1的合并起来的最大值

状态转移方程：dp\[state-(1<<j)\]=max(dp\[state-(1<<j)\], dp\[state\]+a\[i\]\[j\]); （每次都从 i 为1的点转移过来）

代码：

#include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    const int N = 12;
    int a[N][N],dp[1<<N];
    int main()
    {
        int n;
        while(~scanf("%d",&n)&&n)
        {
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    scanf("%d",&a[i][j]);
            memset(dp,0,sizeof(dp));
            for(int state=(1<<n); state>=0; state--)
            {
                for(int i=0; i<n; i++)  //枚举初始合并点
                {
                    if(state&(1<<i))
                        continue;
                    for(int j=0; j<n; j++)   //跟哪一个合并
                    {
                        if(!(state&(1<<j)))
                            continue;
                        if(i==j)
                            continue;
                        int newstate=state-(1<<j);
                        dp[newstate]=max(dp[newstate], dp[state]+a[i][j]);
                    }
                }
            }
            int maxnum=0;
            for(int i=0; i<(1<<n); i++)
                maxnum=max(maxnum, dp[i]);
            printf("%d\n", maxnum);
        }
        return 0;
    }

[Link 1]: http://blog.csdn.net/y990041769/article/details/21406335http://blog.csdn.net/y990041769/article/details/21406335