2014-2015 Petrozavodsk Winter Training Camp, Contest.58 (Makoto rng_58 Soejima contest)

2014-2015 Petrozavodsk Winter Training Camp, Contest.58 (Makoto rng_58 Soejima contest)

Problem A. Manhattan

solved by RDC 32 min 1Y

题意 给一网格图，找出欧几里得距离为 d 的两点，最大化最短路。

第一回合

三分搜索，第一个点的坐标 $(x,0)(0\leq x<1)$，确定第一个点后，对第二个点的横坐标或者纵坐标进行枚举计算答案。

第二回合

设最优解两点之间，横坐标差绝对值为 $dx$ 纵坐标差绝对值为 $dy$，分类讨论。

• 当 $dx$ 为整数时，枚举 $dx$，有 $dy=\sqrt{d^2-dx^2}$。
• 当 $dy$ 为整数时，枚举 $dy$。
• 否则，猜测答案为 $\sqrt{2}d$，两点斜率绝对值为 1。（距离为 $d$ 的两点曼哈顿距离最大值为 $\sqrt{2}d$）

第三回合

• 注意到，若 $min(dx,dy)\geq 1$ 或者 $dx,dy$ 皆不为整数，两点间最短路即曼哈顿距离。
• 当两点间最短距离不是曼哈顿距离时，$0 \leq min(dx,dy)<1$，且 $dx,dy$ 中存在正整数。

---

Problem C. Clique Coloring

solved by RDC 112 min 1Y

题意 求极小的 m，使得可以选出大小分别为 $a_1,a_2,...,a_n$ 的子集，使得两两交大小小于等于 1.

做法

• 注意到任意两个集合的交，小于等于 1.
• 元素按，是否归属于 $1,2,...,n$ 号集合，可以划分成 $2^n$ 个等价类，编号分别为 $0$~$2^n-1$
• DFS 枚举编号 $bitcount()$ 大于 1 的等价类中是否有元素，剪掉一些 invalid 的枚举（若 $bitcount(x\&y) \geq 2$，那么第 x 个等价类，第 y 个等价类，不可同时有元素）。
• 合法的枚举方案很少 $(<1e5)$，对每种方案统计答案即可。

---

Problem B. Dictionary

upsolved by RDC,sdcgvhgj,F0_0H

题意 给 n 个串，字符集为小写字母，替换 '?'，使字典序单增。

做法1 考虑 DP

• $f[l][r][p][c]$ 表示考虑第 l 个串到第 r 个串的 p ~ 20 位， 使得它们字典序单增，且 $s[x] [p]=c(l \leq x \leq r)$ 的方案数。
• $g[l][r][p][c]$ 表示考虑第 l 个串到第 r 个串的 p ~ 20 位， 使得它们字典序单增，且 $s[l] [p]=c$ 的方案数。
• $g[21][i][i]['\0']=f[21][i][i]['\0']=1(1\leq i\leq n)$
• $f[l][r][p][c]=\sum_{ch}g[l][r][p+1][c]*[condition]$，其中 $[condition]$ 表示 $s[x][p](l\leq x\leq r)$ 能否全为字符 $c$.
• $g[l][r][p][c]=\sum_{ch>c}\sum_{mid}f[l][mid][p][c]*((mid+1<=r)?g[mid+1][r][p][ch]:1)$
• 对 $g[l][r][p][]$ 做后缀和，优化。
  code

做法2 对上述状态转移的简化

• $f[l][r][p][c]$表示考虑第 l 个串到第 r 个串的 p ~ 20 位， 使得它们字典序单增，且 $s[x] [p]\leq c(l \leq x \leq r)$ 的方案数。
• $f[l][r][p][c]=\sum_{ch<c}\sum_{mid}f[l][mid][p][ch]*f[mid+1][r][p+1]['z']*[condition]$，其中$[condition]$表示$s[x][p](mid+1\leq x\leq r)$能否全为字符$c+1$
  code

---

Problem D. Dense Amidakuji

upsolved by F0_0H

题意 排骨龙沿着竹竿往下爬，输出会从哪个竹竿落下。

做法

考虑两个如下事实：

• 对于每条横边，定会被经过两次，一次从左往右，一次从右往左
• 每删除一条横边，相当于交换该横边左右两次经过的状态

所以只需要考虑每条横边原始被经过的标号，交换一下即可（从上到下考虑）
code

---

Problem G. Snake

upsolved by sdcgvhgj

题意 给一条折线段$P_1P_2,.....P_n$，问能否穿过一个洞。

口胡 by rdc

• 能穿过洞，等价于折线段在任意位置都能被直线划分成两段。
• 若在位置 $Q$ 能被划分成两段，那么必存在 $1\leq i \leq n$，使得 $QP_i$ 能把折线段划分成两段。
• 枚举点 $P_i$，更新点集 $\{Q|P_iQ 能划分折线段\}$。
• 有解，等价于，$\cup_{i=1}^{n} \{Q|P_iQ 能划分折线段\} = 折线段上点组成点集$。

---

Problem J. Hyperrectangle

题意 输入 $d$ 维长方体，求 $x_1+x_2+..+x_d\leq s$ 体积。