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\) 体积。