题解 | 2013 Asia Chengdu Regional Contest
题解 | 2013 Asia Chengdu Regional Contest
A
题意
构造一张 n 个点 m 条边的有向图，每条边的边权分别为 1,2,...,m，使得
- 两点之间最多只有一条有向边，没有自环
- 从每个点出发可以到达任何点（包括自身）
- 任意一个有向环的权值和为 3 的倍数。
题解
先让所有点在一个环上，以满足条件 2。对于 i\in \{1,2,...,n-1\}，在 i 和 i+1 间连一条边权为 i 的边。n 和 1 间的边在 \{n,n+1,...,m\} 中选一个权值，使得这个环的权值和为 3 的倍数。
剩下 m-n 条边，n^2 枚举间距 \ge 2 的点对 (i,j)，把权值和 i\rightarrow j 距离对 3 同余的边安排到 i,j 之间。
B
题意
写一个简单的 HTML 代码格式化工具。
tag（尖括号<>包着的内容）内部不用动text（没被尖括号包着的内容）过滤掉多余的空白字符（ASCII 32空格、ASCII 9Tab 和ASCII 10换行符），使得两个单词之间仅由一个空格分隔。- 根据深度加空格缩进
题解
大模拟，细节比较多，调了一个下午。
C
题意
有一个 1\sim n 的排列，小 P 想要将其从小到大排序。
题解
D
题意
给出一张 n 个点 m 条边的有向图，小 P 想要在 T 分钟内从 1 号点走到 n 号点。
经过每条边时，要花费一些时间和金钱。小 P 一开始有 R 元，他希望到达 n 号点时手头的钱尽可能多。
小 P 在路上交易盐。除了 1 号点和 n 号点，每个点都有盐，并且给定价格。小 P 每次到一个点，都可以
- 卖出一包盐
- 买入一包盐
- 什么都不干
但是小 P 最多只能携带 B 包盐（他出发时没有带盐）。交易盐不需要时间。
小 P 还有一个设备，可以在 k 个标号为 0\sim k-1 的平行宇宙中穿梭。小 P 一开始在 0 号宇宙。每次使用设备，可以花费 1 分钟从 i 号宇宙穿越到 (i+1)\bmod k 号宇宙中编号相同的点。
平行宇宙中编号相同的点的盐价可能不一样，但是经过相同的边时花费的时间和金钱是相同的。小 P 不能访问 1\sim k-1 号宇宙的 1 号点和 n 号点。
注意：一旦他到达 n 号点旅途就结束。他必须要在 T 分钟内到达 n 号点，并且在旅途中他手头的钱不能是负数。
问他到达 n 号点时手头的钱最多为多少。
题解
可以搞个 DP。f_{t,k,u,b} 表示时间为 t，在 k 号宇宙的 u 号节点，手头有 b 包盐，最多有多少钱。
转移要么是在当前宇宙走一条边，要么是到下一个宇宙，然后分买盐 / 卖盐 / 什么都不干三类讨论。
E
F
题意
给出一张 n 个点 m 条边的无向图，所有边都有权值 \in\{0,1\}。问在图上能否找到一棵生成树，使得树边的权值之和是斐波那契数。
题解
跑最小生成树和最大生成树，记权值之和分别为 l,r。如果 l\sim r 有斐波那契数，答案即为 Yes。
证明起来比较困难，但是可以感性理解，在最小生成树的基础上通过不断删除一条权值为 0 的边，增加一条权值为 1 的边，并保持生成树的性质，过渡到最大生成树。
G
题意
维护一个单词表，支持两种操作
- 增加一个模式串
- 询问一个文本串中模式串的出现总数
字符集为 \{0,1\}，强制在线。如果一个模式串出现多次，可以假设每次出现都算作一个新串。
题解
首先想到 AC 自动机。但是 AC 自动机没法修改。考虑开两个 AC 自动机 S,B。令 \text{threshold}\approx\sqrt{n}，使得 S 的节点数保持 \le\text{threshold}，并且每次加新串时重构；当 S 的节点数 \gt\text{threshold} 时，把 S 中的串移到 B 中，然后重构 B。实现中直接钦定了 \text{threshold}=1000。
H
题意
操作系统和制造商对于硬盘空间的计算方法不同。操作系统认为 1\text{KB}=1024\text{B},1\text{MB}=1024\text{KB},...，而制造商认为 1\text{KB}=1000\text{B},1\text{MB}=1000\text{KB},...。给出一个形如 100[MB] 的字符串，问制造商的计算方法比操作系统的计算方法少了百分之几，四舍五入保留两位小数。
题解
签到题，直接按照题意模拟即可。注意使用 printf 输出 % 时，要写 %%。
I
题意
模拟一场 ACM 比赛。
评测结果有 3 种
ERROR评测机炸了，参赛队伍没有 A 掉这题，但是不会罚时NO代码假了，参赛队伍没有 A 掉这题，会罚时YES参赛队伍 A 掉这题
为了使得比赛更加紧张刺激，有封榜机制。
- 如果一个队伍在封榜前没有切掉某道题，并且在封榜这一瞬间或者之后提交了这题，对于这支队伍来说，这道题就
冻住了 - 不同的队伍
冻住的题可能是不同的 - 对于
冻住的题，榜上只会显示这支队伍提交了几次，而不会显示评测结果
排名由以下因素决定（忽略冻住的题，优先级从高到低）
Solved切掉的题目数量，题数越多越靠前Penalty设在第一次YES之前返回NO的次数为 x，第一次YES的时刻为 T，罚时为 T+20\cdot xLast Solved最后一道切掉的题切题时间较早的排在前面，如果相同的话，比较倒数第二道切掉的题，以此类推Name按照队伍名字的字典序从大到小排，字典序靠后的排名靠前
比赛结束时会揭榜。
- 在榜单上选择排名最低的有
冻住的题的队伍 - 从这支队伍
冻住的题目中解冻一道题（如果有多道题，解冻题目名称字典序最小的题）。公开这题的评测结果，重新计算排名，更改榜单。 - 重复上述过程，直到所有队伍
冻住的题都被解冻。 - 得到最终的榜单。
输出揭榜前的榜单，最终的榜单，以及揭榜的过程。
题解
首先要解决队伍排序的问题，根据题意，对每支队伍维护以下信息
每道题的（实际）状态
unordered_map<char, bool>
其中状态只有 unsolved 和 solved。
当前（公开）切掉的题
榜单按照此信息排序
- 切掉的题的总罚时
penalty
set<int>
- 切掉的题的总数
size() - 切掉的题的首次 AC 时间（注意到由于揭榜的特殊操作，时间没有单调性）
每道题的罚时
unordered_map<char, int>
如果一道题已经切掉，就不再有罚时了。
冻住的题的集合
set<char>
要按照题号字典序揭榜。
队伍名字
最后的排序依据。
J
题意
给出两个区间 [a,b],[c,d]，在 [a,b] 间随机取一个整数 x，[c,d] 间随机取一个整数 y，问 x+y\equiv m\pmod p 的概率。
题解
为了写起来方便，我们先解决 [0,a],[0,b] 这样的情况，对于 [a,b],[c,d] 这样的情况简单容斥一下。
[0,a] 中有 a+1 个整数，我们可以把这些整数分成 \lfloor\frac{a+1}{p}\rfloor 个长度为 p 的大段，和一个长度为 (a+1)\bmod p 的小段。对 [0,b] 同样操作。
大段和大段的贡献是 \lfloor\frac{a+1}{p}\rfloor\cdot p\cdot\lfloor\frac{b+1}{p}\rfloor（对于 [0,a] 大段的每一个数，[0,b] 大段都有 \lfloor\frac{b+1}{p}\rfloor 个数和它匹配）。
大段和小段的贡献是 (a+1)\bmod p\cdot\lfloor\frac{b+1}{p}\rfloor+(b+1)\bmod p\cdot\lfloor\frac{a+1}{p}\rfloor（[0,a] 小段的每一个数都可以在 [0,b] 大段找到 \lfloor\frac{b+1}{p}\rfloor 个匹配，[0,b] 小段同理）。
小段和小段的贡献可以算和为 m+i\cdot p（从 i=0 开始枚举） 的数对的数量。
