Contest Info

date: 2018.12.07 16:30-21:30

practice link

Solutions

B. Point Pairs

题目大意：

二维平面上有\(2n+1\)个两两不同的整点，两个点可以配对当且仅当它们的\(x\)坐标或者\(y\)坐标相同。

对于每一个点，问如果删掉它，剩下的\(2n\)个点是否可以有完备匹配。

题解：

建图，点\((x,y)\)转化为图中横坐标\(x\)到纵坐标\(y\)的一条无向边，则存在完备匹配当且仅当每个连通块中的边数为偶数。

求一下桥边，根据是否为桥边处理一下即可。

E. Eel and Grid

题目大意：一个循环的 \(n\times m\) 的网格，一开始在左上角格子的中心 \((0,0)\)，每次向右或向下走一步，如果穿过边界就走到对侧。问不重不漏地走完所有点后回到 \((0,0)\) 的方案有多少种。

题解：注意到，每个 \((x,y)\) 和 \((x+1,y-1)\) 的方向必须相同。设 \(\gcd=\gcd(n,m)\)，那么所有 \(x+y\equiv x'+y'\pmod{\gcd}\) 的 \((x,y)\) 和 \((x',y')\) 的方向都应该相同。

容易发现，最开始 \(\gcd\) 步的 \(x+y\) 恰好膜 \(\gcd\) 互不相同，因此这 \(\gcd\) 步就决定了是否有解。之后很简单，不再赘述。

G. Rectangle-free Grid

题目大意：要求你构造一个 \(n\times n\) 的方阵，满足：

• \(2\le n\le150\)
• 每个位置是 . 或 O
• 至少有 \(1700\) 个 O
• 不存在一个长宽至少为 \(2\) 的子矩阵的四个角均为 O

题解：这里直接给出构造方法：

首先我们填充一个 \(169\times169\) 的矩阵，之后截取其中 \(150\times150\) 的一个子矩阵即可。对全部 \(i,j,k\in[0,12]\)，将 \(\text{mat}[13i+j][13k+(ik+j)\mod{13}]\) 填入 O，其它位置填入 .

显然第 \(4\) 个条件等价于任意两行至多有一列同为 O。首先注意到第二维相等的必要条件是 \(k=k'\)，对于一对固定的 \((i,j)\) 和 \((i',j')\)，同余方程 \((i-i')k+(j-j')\equiv0\pmod{13}\) 在 \([0,12]\) 上至多只有一个解。因此该构造满足第 \(4\) 个条件。

H. Cups and Beans

题目大意：

有\(n\le10^5\)个杯子，第\(i\)个杯子中有\(A_i\)个豆子。

两个人玩游戏，轮流操作，每一轮操作的人首先选择一个不为空的杯子，从中拿出一颗豆子，将其放入\([i-C_i,i-1]\)中任意一个杯子中，不能操作的人输。

问最优策略下先手后手谁获胜。

题解：

每棵豆子独立，分别计算sg值再异或起来。

对于第\(i\)个杯子，\(sg_i=mex(sg_{i-C_i},\cdots,sg_{i-1})\).

考虑用线段树维护二分结构来求解区间mex，令线段树叶子节点为\(sg\)值等于该叶子编号的最大位置，非叶子节点为两个儿子的最小值。

则询问\([L,R]\)的mex时，维护了前缀\(R\)的sg信息，在线段树上二分，如果左儿子的值小于\(L\)，说明存在权值在左儿子区间的sg值没有出现过，进入左儿子递归，否则进入右儿子，直到到达叶子，叶子的编号就是答案。

每次更新只需要单点修改，时间复杂度\(O(n\log{n})\).

J. Travel in Sugar Country

题目大意：

有\(n\le100\)个城市排成一排，第\(i\)个城市到第\(i+1\)个城市的距离为\(D_i\)。

现在要从中\(k\le10\)个不同的城市，并选择一个顺序\(s_1,\cdots,s_k\)遍历它们，代价为\(\sum\limits_{i=1}^{k-1} Dis(s_i, s_{i+1})\)。

求有多少种不同的方案，代价是\(M\le30\)的倍数，取模\(10^9+7\)。

题解：

令\(dp[i][s][r]\)表示决策到前缀\(i\)，填了排列中\(s\)这些位置，代价\(\mod{m}\)的余数为\(r\)的方案数。

转移时只需要数一下\(s\)中有多少个相邻的位置填与未填的状态不同，乘以\(D_i\)即可算出新的代价。

时间复杂度\(O(2^k\cdot nk)\).