在这里必须吐槽一下组题人和出题人的语文水平……愣是把这场打成了语文场……
「CEOI2019」Cubeword (D1T3)
居然这个题是完全机翻的……怪不得难以理解……
题意简述
给定 $n$ 个互不相同的有意义的单词( $1\le n\le 10^5$ ),每个单词都是一个长度在 $[3,10]$ 间的字符串,单词中包含小写的a
到z
,大写的A
到Z
,数字0
到9
。
然后,你选定正方体的棱长 $a$ ,建立一个有 $a^3$ 单位的立方体。你要在这个大正方体的 $12$ 条边上的所有单位正方体上填上一个字母(这里字母的定义是小写的a
到z
,大写的A
到Z
,数字0
到9
)。边上的所有单位立方体填上字母后,每条边都必须是一个有意义的长度为 $a$ 的单词。每条边可以双向阅读,即只要从一个方向读起来是有意义的单词即可。
例如上图就是 $a=6$ 时,只填了 $3$ 条边时的情况。此时已填的三条边分别可以看出单词SUBMIT
(或TIMBUS
)、ACCEPT
(或TPECCA
)、TURING
(或GNIRUT
)。
如果一个立方体可以通过旋转或镜像变成另一个立方体,则认为这两个立方体是不同的。
主要思路
以 $S$ 表示字符集。考虑如何处理长度为 $len$ 的单词。
当一个顶点所在的三条棱的另一端的顶点都已经确定填什么字母时,显然这三条棱的填法种类是固定的。这里使用 $f(i_1,i_2,i_3)$ 来描述。显然处理单个 $f(i_1,i_2,i_3)$ 的复杂度是 $O(|S|)$ 。
枚举正方体四个互不相邻的顶点该位置填什么字母。设这四个顶点分别填 $i_1,i_2,i_3,i_4$ ,则此时整个正方体满足要求的方案数是 $f(i_1,i_2,i_3)\times f(i_2,i_3,i_4) \times f(i_3,i_4,i_1) \times f(i_4,i_1,i_2)$ 。则最终的答案就是
$$\sum\limits_{i_1\in S}\sum\limits_{i_2\in S}\sum\limits_{i_3\in S}\sum\limits_{i_4\in S} f(i_1,i_2,i_3)\times f(i_2,i_3,i_4) \times f(i_3,i_4,i_1) \times f(i_4,i_1,i_2)$$
此时总时间复杂度是 $O(8 \times |S|^4)$ ,据说会被卡常。
考虑处理答案时可以钦定 $i_1\le i_2\le i_3\le i_4$ ,处理 $f(i_1,i_2,i_3)$ 时可以钦定 $i_1\le i_2\le i_3$ 。如此常数减小,完全可过。
注意最后求答案时需要处理 $i_1,i_2,i_3,i_4$ 的出现次数。
参考代码
1 |
|
「LOJ 6364」烂柯
居然是原创题,然而还是很难懂……
题意简述
给定一棵 $n$ 个节点的树,其中 $m$ 个节点上有柿子。在这棵树上进行博弈。双方轮流操作,每次选择一个有柿子的节点,将上面至少一个柿子移动到相邻节点,或如果这个节点是叶子节点且与开始给定的一个节点 $k$ 的距离是奇数,将上面至少一个柿子删除。每个柿子都不能移动到该柿子曾经位于的节点上。最后不能操作的人就输了。
给出树的形态和开始 $m$ 个节点上柿子的位置及个数,求双方最优策略下先手胜负。
有 $case$ 组数据, $case \le 10,\ n,a_i \le 100,\ m\le 18$ 。
主要思路
数据出得如此小,简直考验选手心理。
考虑以 $k$ 为根,能删除柿子的节点是深度为奇数的叶子(深度从 $0$ 开始)。这样,在节点上删柿子可以看作在该节点下挂了一个虚节点,将柿子移动到了该节点。所以当不能移动柿子时,柿子深度均为偶数。
发现每个柿子会被移动次数的奇偶性与深度的奇偶性相同,而游戏显然不能无限进行,因此该游戏和普通阶梯博弈等价。只需将所有距离 $k$ 为奇数的节点的柿子数量异或起来(记为 $cnt$ ), $cnt > 0$ 就是先手必胜, $cnt = 0$ 就是后手必胜。
代码难度小,不放代码了。
「CF 567F」Mausoleum
Zory说这是签到题,然而本人场上没想出来……
题意简述
一个长为 $2n$ 的数列,其中 $1,2,\dots,n$ 各出现两次,并且是单峰的(先一段不降再一段不升,长度可以为 $0$ )。并且给出了 $k$ 个限制,要求第 $x_i$ 个位置的数必须 $\mathtt{sign_i}$ 第 $y_i$ 个位置上的数,其中 $\mathtt{sign_i}$ 是等于、大于、小于、大于等于、小于等于中的一种。
求该数列的可能种数。 $n \le 35, k\le 100$ 。
主要思路
考虑 $f(l,r)$ 表示 $[l,r]$ 中的位置还没有填数并且峰顶在 $[l,r]$ 中时的方案总数,初始时 $f(0,2n + 1) = 0$ ,我们要求的答案是 $\sum\limits_{i=1}^{2n-1}f(i,i + 1)$ (因为剩下两个 $n$ 只能填在空缺的两个位置)。
$f(l,r)$ 可以转移到 $f(l+1,r+1),f(l+2,r),f(l,r-2)$ ,注意限制,具体实现见代码,大概就是每个位置开一个 $\text{vector}$ 存一下这个位置要等于哪些位置、小于等于哪些位置、小于哪些位置,然后转移时暴力判断。
参考代码
1 |
|
「HDU 5181」numbers
实在是搞不懂为什么一个意义简明的题面可以被解释得如此难懂,导致本人在考试结束前 1h 才看懂题面。
题意简述
你手上有个栈,你要将 $1,2,\dots,n$ 依次入栈,然后有 $m$ 个限制,限制 $A_i$ 必须早于 $B_i$ 出栈,其余出栈顺序不限。求有多少种合法的进出栈序列。 $case$ 组数据, $case \le 5,n \le 300,m \le 90000$ 。
主要思路
我们添加一个数 $0$ ,让 $0$ 在所有数进栈之前进栈,所有数出栈之后出栈。这样进出栈序列可以写成一棵以 $0$ 为根的树,dfs 序为 $0,1,2,\dots,n$ ,每个元素 $x$ 将在自己子树内(除自己)的所有元素进栈前进栈,出栈后出栈。
如果没有限制,显然我们可以设 $dp(x,k)$ 为考虑 $[x,n]$ 的进出栈顺序, $x$ 的子树大小为 $k$ 的种数。枚举 $x$ 除最右子树外其他子树大小和 $t$,则有 $dp(x,k) = \sum\limits_{t=1}^{k-1}dp(x,t)\times dp(x+t,k-t)$ 。
考虑限制 $(A_i,B_i)$ 在这棵数上的意义。
- 如果 $A_i=B_i$ ,显然直接无解。
- 如果 $A_i<B_i$ , $A_i$ 的子树内不能包含 $B_i$ ,即 $A_i$ 的子树大小最大是 $\operatorname{Maxsiz}(A_i)=B_i - A_i$ 。
- 如果 $A_i>B_i$ , $B_i$ 的子树内必须包含 $A_i$ ,即 $B_i$ 的子树大小最小是 $\operatorname{Minsiz}(B_i)=A_i - B_i + 1$ 。
仍设 $dp(x,k)$ ,此时 $k\in [\operatorname{Minsiz}(x),\operatorname{Maxsiz}(x)]$ 时才有意义。
由于某个点在挂到别的点上时,子树大小并不改变,所以可以仍如上述方法做 dp ,在处理完 $dp(x,k)$ 后再把无意义的位置设为 $0$ 即可。
复杂度 $O(n^3)$ ,完全可过。
参考代码
1 | //#include<bits/stdc++.h> |