• CF - C. Card Game(博弈,递推)


    https://codeforces.com/contest/1739/problem/C

    题意
    一共 n 张卡片,每张卡片上标有一个数字,标号从 1 到 n 各不相同,分给 Alice 和 Bob 各 n/2 张。
    一共 n/2 轮操作,Alice 和 Bob 两个玩家轮流作为先手,初始 Alice 作为第一轮先手。

    对于每一轮来说:

    • 先手打出一张牌,后手要打出标号大于其的一张牌。如果不存在,那么后手输。

    如果 n/2 轮结束时,未出胜负,那么平局。

    两者都按最优策略操作。
    问,最终在 Alice赢,Bob赢,平局 三种情况下,n 张卡片的分配方案各有多少?

    思路
    首先需要知道,一个玩家如果作为先手的话,一定会打出其拥有的最大牌,要么直接胜利,要么把对方更大的牌引出来,尽量保证自己下一局的安全。

    然后尝试讨论所有情况:

    如果 Alice 有最大牌 n,Alice 在第一轮就赢,分配方案 C n − 1 n 2 − 1 C_{n-1}^{\frac n 2-1} Cn12n1

    否则 Bob 有最大牌 n:

    • Bob 有次大牌 n-1,Bob 必赢。Alice无法在第一轮用次大牌把最大牌引出来,第二局Bob 打出最大牌,Alice 必输;
    • Alice 有次大牌 n-1:
      那么 Alice 能挺过第一轮,然后到第二轮 Bob 先手。
      1.如果 Bob 有 n-2,Bob 必赢。此时剩余牌中最大的为 n-2,Alice 无牌可出;
      2.如果 Alice 有 n-2,就要看 Bob 能不能有次大的 n-3 把这个最大的 n-2 引出来。
       在这种情况下:
       如果 Alice 又有 n-3 的话,n-2 就用不到,留到下一局打出来 Alice 必赢;
       如果 Bob 有 n-3 的话,Alice 就要打出 n-2,此时这两局平局。然后发现刚好用掉了最大的 4 张牌,就可以递推到 n-4 的情况下,同样这样考虑。

    然后根据样例发现,平局的情况只有一种,两个人轮流分牌的情况,所以可以把 Alice 赢的所有方案求出来,用总方案数减去平局和Alice赢的方案数就是Bob赢的方案数。

    如果定义 i 个卡牌时,Alice赢的方案数一共 f[i],那么对于 n 个卡牌时,Alice 赢的方案数就是: C n − 1 n 2 − 1 + C n − 4 n 2 − 3 + f [ n − 4 ] C_{n-1}^{\frac n 2-1} + C_{n-4}^{\frac n 2-3} + f[n-4] Cn12n1+Cn42n3+f[n4]

    从小到大遍历所有 i,用前面的答案更新当前答案。
    初始化 f[2] = 1。

    Code

    #include
    using namespace std;
    
    #define Ios ios::sync_with_stdio(false),cin.tie(0)
    
    const int N = 200010, mod = 998244353;
    int T, n, m;
    int C[70][70];
    int f[N];
    
    signed main(){
    	Ios;
    	
    	for(int i=0;i<=60;i++)
    		for(int j=0;j<=60;j++)
    		{
    			if(!j) C[i][j] = 1;
    			else C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;
    		}
    	
    	f[2] = 1;
    	for(int i=2;i<=60;i++)
    	{
    		if(i % 2) continue;
    		f[i] = (C[i-1][i/2 - 1] + C[i-4][i/2 - 3] + f[i - 4]) % mod;
    	}
    	
    	cin >> T;
    	while(T--)
    	{
    		cin >> n;
    		cout << f[n] << " " << (C[n][n/2] - f[n] - 1 + mod) % mod << " " << 1 << endl;
    	}
    	
    	return 0;
    } 
    

    场上没有把所有情况都考虑清楚,只想到次大值就开始求方案,想把方案数一次性求出来,然后发现求不出来。。
    完全没有想到递推。。

  • 相关阅读:
    通过1688APP分享商品链接淘口令获取商品详情接口,淘口令返利接口,1688淘口令API接口,淘口令解析接口演示案例
    Node.js如何处理多个请求?
    Ranger (四) --------- 安装 Ranger Hive-plugin
    RK3568开发笔记(十一):开发版buildroot固件移植一个ffmpeg播放rtsp的播放器Demo
    rabbitmq载在.net中批量消费的问题记录
    [附源码]计算机毕业设计springboot基于SpringBoot的演唱会购票系统论文2022
    如何解决小程序异步请求问题
    MILP(混合整数线性规划)
    4. xaml Button按钮
    MYSQL的锁
  • 原文地址:https://blog.csdn.net/Mr_dimple/article/details/127126436