首页 > 其他分享 >ABC354 E - Remove Pairs 做题笔记

ABC354 E - Remove Pairs 做题笔记

时间:2024-05-20 11:18:17浏览次数:25  
标签:局面 nxt Pairs 游戏 int Remove 必输 ABC354 dp

ABC354 E - Remove Pairs 做题笔记

题目链接

对于这种带有博弈论的 dp,考虑这样设计状态:令 \(f_s \in \{1, 0\}\) 表示“游戏局面”为 \(s\) 时,先手必胜还是必败。本题中,“游戏局面”可以表示为剩余卡牌的编号集合。又因为本题中 \(N\)​ 很小,通过状压,可以直接用一个 int 表示游戏局面。

下面讨论 dp 的三要素:答案统计、初始化、转移。

  1. 答案统计:因为游戏开始时所有卡牌都没有被拿走,所以初始状态为 \(\{1, 2, \cdots, N\}\),答案为 \(f_{\{1, 2, \cdots, N\}}\)。(代码实现上可以把初始状态写成 (1 << n) - 1)。

  2. 初始化:对于所有不能继续进行游戏的状态(也就是不存在数字相同的牌可以选了),设为 \(0\),表示先手必输。但代码实现上不用特别去初始化,因为全局变量初值本就为 0。

  3. 转移:转移方程为 \(f_s = \operatorname{OR}_{t \in nxt(s)} \lnot f(t)\),其中 \(nxt(s)\) 表示从 \(s\) 可以一步到达的游戏局面的集合,“\(\lnot\)” 表示逻辑非。

    可以这么理解:因为玩家会最优地选择策略,所以在他所有能到达的下一步游戏局面中,如果存在一个先手必输的情况,他必然会选择到达这个情况。这样等到下一个回合时,他的对手就面临了一个先手必输的局面,因此对手必败,也就是他必胜。否则,若不存在这样的下一步局面,就说明他无论怎么走都会到达一个先手必胜的局面,他就必输了。

代码实现上,可以用记忆化搜索和 dp。

记忆化搜索:

bool dfs(int s)
{
	if(vis[s]) return f[s];
	for(int i = 0; i < n-1; i++)
	{
		if(!(s & (1 << i))) continue;
		for(int j = i+1; j < n; j++)
		{
			if(!(s & (1 << j))) continue;
			if(p[i].a != p[j].a && p[i].b != p[j].b) continue;
			int nxt = s ^ (1 << i) ^ (1 << j);
			f[s] |= (!dfs(nxt));
		}
	}
	vis[s] = true;
	return f[s];
}

AC 记录

dp:

for(int s = 0; s < S; s++) // 从小到大枚举状态
{
    for(int i = 0; (1 << i) <= s; i++)
    {
        if(!(s & (1 << i))) continue;
        for(int j = i+1; (1 << j) <= s; j++)
        {
            if(!(s & (1 << j))) continue;
            if(p[i].a != p[j].a && p[i].b != p[j].b) continue;
            int nxt = s ^ (1 << i) ^ (1 << j);
            f[s] |= !f[nxt];
        }
    }
}

AC 记录

需要注意的是,这样从小到大枚举状态是可行的,也就是可以保证 \(\forall t \in nxt(s), t < s\)。证明很简单:\(nxt(s)\) 中的元素都是把 \(s\) 的两个二进制位从 1 变成 0 得到的,因此一定小于 \(s\)。

闲话

这场 ABC 的 D 题非常恶心,没有做出来;一怒之下去做 E,但是对这类题不太熟,乱搞了一个记搜,而且脑子进水了没想到状压,用了一个 map<vector<int>, bool> 来存状态,最后 5 分钟交上去 AC * 28,TLE * 2。因为 T 的点也只有 2208ms,我怀疑 T 了只是因为常数比较大,稍微改了一下交上去还是 TLE * 2,彻底绷不住了。最终达成了 ABC 只做出 ABC 的惨剧(

标签:局面,nxt,Pairs,游戏,int,Remove,必输,ABC354,dp
From: https://www.cnblogs.com/dengstar/p/18201484

相关文章

  • AtCoder abc354E
    原题链接ProblemStatementTakahashiandAokiareplayingagameusing\(N\)cards.Thefrontsideofthe\(i\)-thcardhas\(A_i\)writtenonit,andthebacksidehas\(B_i\)writtenonit.Initially,the\(N\)cardsarelaidoutonthetable.Wit......
  • 「杂题乱刷」AT_abc354_f
    大家一起来做下这个典题。链接(at)链接(luogu)我们很容易可以想到处理前后缀的最长上升子序列的长度,然后容易\(O(n\log_2n)\)预处理。做完了。点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出来,是不是该考虑换题?打cf不要......
  • [ABC354D]
    https://www.luogu.com.cn/problem/AT_abc354_dhttps://atcoder.jp/contests/abc354/tasks/abc354_d由图片可知,很显然每个\(4\times2\)​网格(称为单位网格)都是全等的。为了方便,将\(A,B,C,D\)都增加\(10^9\),因为\(10^9\bmod4=10^9\bmod2=0\),所以图形没有变化。(很重要,这......
  • ABC354
    A.ExponentialPlant模拟代码实现h=int(input())now,day=0,0whilenow<=h:now+=1<<dayday+=1print(day)B.AtCoderJanken2模拟代码实现#include<bits/stdc++.h>#definerep(i,n)for(inti=0;i<(n);++i)usingname......
  • 多线程下使用List中的subList和remove方法产生的 java.util.ConcurrentModificationEx
    在说多线程操作List之前,我们先看下单线程下产生的问题:单线程List<Integer>listA=newArrayList<>();listA.add(1);listA.add(2);listA.add(3);listA.add(4);listA.add(5);listA.add(6);for(Integera:listA){......
  • [shell:bash] ubuntu_remove_old_kernel_test
    [shell:bash]  ubuntu_remove_old_kernel_test    一、基本信息 1、os:Linuxubuntu6.5.0-35-generic#35-UbuntuSMPPREEMPT_DYNAMICFriApr2611:23:57UTC2024x86_64x86_64x86_64GNU/Linux 2、bash:GNUbash,version5.2.......
  • openGauss 开启RemoveIPC引起的core问题
    开启RemoveIPC引起的core问题问题现象操作系统配置中RemoveIPC参数设置为yes,数据库运行过程中出现宕机,并显示如下日志消息。FATAL:semctl(1463124609,3,SETVAL,0)failed:Invalidargument原因分析当RemoveIPC参数设置为yes时,操作系统会在对应用户退出时删除IPC资源(共......
  • [Unit testing - React] Use the waitForElementToBeRemoved Async Util to Await Unt
    Sometimes,youmightneedtowaitforanelementtodisappearfromyourUIbeforeproceedingwithyourtestsetupormakingyourassertion.Inthislesson,wewilllearnaboutawrapperaroundthewaitForthatallowsyoutowaituntilanelementisremove......
  • [LeetCode] 2487. Remove Nodes From Linked List
    Youaregiventheheadofalinkedlist.Removeeverynodewhichhasanodewithagreatervalueanywheretotherightsideofit.Returntheheadofthemodifiedlinkedlist.Example1:Input:head=[5,2,13,3,8]Output:[13,8]Explanation:Thenodesth......
  • [992] Remove holes within polygons in a shapefile
    Toremoveholeswithinpolygonsinashapefile,youcanusethegeopandaslibraryinPython.Here'showyoucandoit:importgeopandasasgpd#Readtheshapefilegdf=gpd.read_file('path_to_shapefile.shp')#Removeholeswithinpolygon......