2013 Asia Chengdu Regional Contest

A

Assignment For Princess

题意

构造一张 n 个点 m 条边的有向图，每条边的边权分别为 1,2,...,m，使得

1. 两点之间最多只有一条有向边，没有自环
2. 从每个点出发可以到达任何点（包括自身）
3. 任意一个有向环的权值和为 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

Beautiful Soup

题意

写一个简单的 HTML 代码格式化工具。

• tag（尖括号 <> 包着的内容）内部不用动
• text（没被尖括号包着的内容）过滤掉多余的空白字符（ASCII 32 空格、ASCII 9 Tab 和 ASCII 10 换行符），使得两个单词之间仅由一个空格分隔。
• 根据深度加空格缩进

题解

大模拟，细节比较多，调了一个下午。

代码

C

Clumsy Algorithm

题意

有一个 1\sim n 的排列，小 P 想要将其从小到大排序。

题解

代码

D

Dinner Coming Soon

题意

给出一张 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

Exhausted Robot

F

Fibonacci Tree

题意

给出一张 n 个点 m 条边的无向图，所有边都有权值 \in\{0,1\}。问在图上能否找到一棵生成树，使得树边的权值之和是斐波那契数。

题解

跑最小生成树和最大生成树，记权值之和分别为 l,r。如果 l\sim r 有斐波那契数，答案即为 Yes。

证明起来比较困难，但是可以感性理解，在最小生成树的基础上通过不断删除一条权值为 0 的边，增加一条权值为 1 的边，并保持生成树的性质，过渡到最大生成树。

代码

G

GRE Words Revenge

题意

维护一个单词表，支持两种操作

• 增加一个模式串
• 询问一个文本串中模式串的出现总数

字符集为 \{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

Hard Disk Drive

题意

操作系统和制造商对于硬盘空间的计算方法不同。操作系统认为 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

ICPC Ranking

题意

模拟一场 ACM 比赛。

评测结果有 3 种

• ERROR 评测机炸了，参赛队伍没有 A 掉这题，但是不会罚时
• NO 代码假了，参赛队伍没有 A 掉这题，会罚时
• YES 参赛队伍 A 掉这题

为了使得比赛更加紧张刺激，有封榜机制。

• 如果一个队伍在封榜前没有切掉某道题，并且在封榜这一瞬间或者之后提交了这题，对于这支队伍来说，这道题就冻住了
• 不同的队伍冻住的题可能是不同的
• 对于冻住的题，榜上只会显示这支队伍提交了几次，而不会显示评测结果

排名由以下因素决定（忽略冻住的题，优先级从高到低）

1. Solved 切掉的题目数量，题数越多越靠前
2. Penalty 设在第一次 YES 之前返回 NO 的次数为 x，第一次 YES 的时刻为 T，罚时为 T+20\cdot x
3. Last Solved 最后一道切掉的题切题时间较早的排在前面，如果相同的话，比较倒数第二道切掉的题，以此类推
4. Name 按照队伍名字的字典序从大到小排，字典序靠后的排名靠前

比赛结束时会揭榜。

1. 在榜单上选择排名最低的有冻住的题的队伍
2. 从这支队伍冻住的题目中解冻一道题（如果有多道题，解冻题目名称字典序最小的题）。公开这题的评测结果，重新计算排名，更改榜单。
3. 重复上述过程，直到所有队伍冻住的题都被解冻。
4. 得到最终的榜单。

输出揭榜前的榜单，最终的榜单，以及揭榜的过程。

题解

首先要解决队伍排序的问题，根据题意，对每支队伍维护以下信息

每道题的（实际）状态

unordered_map<char, bool>

其中状态只有 unsolved 和 solved。

当前（公开）切掉的题

榜单按照此信息排序

• 切掉的题的总罚时 penalty

set<int>

• 切掉的题的总数 size()
• 切掉的题的首次 AC 时间（注意到由于揭榜的特殊操作，时间没有单调性）

每道题的罚时

unordered_map<char, int>

如果一道题已经切掉，就不再有罚时了。

冻住的题的集合

set<char>

要按照题号字典序揭榜。

队伍名字

最后的排序依据。

J

Just Random

题意

给出两个区间 [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 开始枚举） 的数对的数量。

代码