南京市网站建设_网站建设公司_会员系统_seo优化

F. Guards In The Storehouse

轮廓线dp 状压

不太懂为什么叫轮廓线，总之就是多行，有一定规则，求和方的涂色方案数，一般会用一个m a s k maskmask记录上面已经d p dpdp过的行的状态，据此判断转移是否合法

对于本题，就是可以用一个m a s k maskmask维护有视野的列，扫过每一行，在用一个变量维护当前行到这目前有无向右的视野，如果当前位置有视野，则放不放哨兵都可以，否则必须放哨兵，如果是障碍则不能放哨兵，且会阻断视野。

至多一个位置没有视野，用一个布尔记录有无没有视野的位置，最多允许一个没有视野的位置可以不放哨兵。

状态维度有点多，考虑压成l o n g l o n g long longlonglong用哈希表记忆化，理论上也可以用一个一维数组，并用状态的多个维度手动寻址，但那需要精细的寻址过程，让生成的地址范围不超过申请的数组大小，相比之下哈希表更方便

G. Rudolf and CodeVid-23

状压 最短路

无法dp，因为这个转移不具有无后效性，已经治好的并可能因为新的药物的副作用有复发，但依然存在转移，考虑建图跑最短路。每个患病状态，用上每一种药都能产生一个转移，建有向边，从初始患病状态开始，求到达不患病的最短路

D. Same Count One

构造 转换维度

考虑行的构造不好构，注意到每次换的都是同一列的两个，列之间是不会互相影响的，于是可以考虑逐列交换。最终每一行都应该有t o t / n tot/ntot/n个1 11，因此每一列，我们显然都可以把1 11个数超过这个值的行的1，和个数小于这个值的行的0交换，假设这两种的行分别x , y x,yx,y个，那么这一列能进行的交换次数就是min ⁡ ( x , y ) \min(x,y)min(x,y)，方案就是每次从这两个类里各选一个配对。同时，需要更新每一行的1 11个数

如果t o t / n tot/ntot/n是整数，这个方案一定能构造到每一行都相等，并且操作次数是最优的，因为我们每次交换都没有走回头路，也就是没有无效操作。

P10723 [GESP202406 七级] 黑白翻转

拓扑排序 树

相当于把一颗树断开成多个连通块，现在要修复回一个连通块，问最少恢复多少个点？那显然目前已有的连通块之间的点都要修复，最外侧的点，不和另一个连通块相连的点不用恢复。

所以计算这样的点有多少个即可，实际上就是从叶子开始拓扑排序，只有白色的才入队，统计入队/出队一共多少个点，就是外部无影响的点数