骰子游戏-Dice
题面
构造 $n$ 个骰子 , 每个骰子内的数互不相同 , 每个骰子随机取一个数 , 使得异或和为 $d$ 的倍数 .
解题思路
离谱的构造题 QwQ .
因为 $d$ 的范围较小 ( $0 \le d \le 60$ ) , 可以用 6 位二进制表示 , 64 进制构造 .
即 $0d$ , $1d$ , $64d$ , $65d$ , $4096d$ , $4097d$ . 值域不到上限 $3 \times 10^5$ , 能过 .
彩带裁剪-Cut
题面
给定一个长为 $n$ 的序列 , 将其分为若干区间 , 每个区间的贡献为最小的这个区间没有出现过的非负整数 $\operatorname{mex}$. 最大化 $\sum mex$ .
解题思路
显然的动态规划 .
设 $f_i$ 表示前 $i$ 个位置分开后的最大贡献 , 枚举上一个位置并计算 $\operatorname{mex}$ . 复杂度 $O(n^2)$
整体值域很小 , 因此每个区间的 $\operatorname{mex}$ 不会超过 $21$ . 并且 $dp_i$ 单调不降 , 转移时枚举最后一段的 $\operatorname{mex}$ , 求能取到该值的最右端 ( 可以预处理 ) . 复杂度 $O(nV)$
挑战NPC Hamilton
题面
给定一个 $n$ 个点 $m$ 条边的有向图 , 选出一些边 , 使得每个点的入度和出度都为 $1$ .
解题思路
拆点网络流 .
对于原图的点 $i$ , 建立边 $S \rightarrow i$ , $i + n \rightarrow T$ ( 流量为 1 ) , 对于原图的边 $u \rightarrow v$ , 建边 $u \rightarrow v + n$ .
跑 $S$ 到 $T$ 的最大流 $flow$ , 如果 $flow < n$ 则无解 , 否则将原图中所有所选的边 $u \rightarrow v$ 连成若干个环即可 .