2017-C10-team8

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

=== A ===
题意：给定整数序列a，数字互不相同。称三元组(i,j,k)为tricky当且仅当a_i<a_j<a_k。三元组(i,j,k)的长度定义为(j-i+n)%n+(k-j+n)%n。求长度最小的tricky三元组。
~~显然应该对每个a_j选取最近的a_i和a_k，对元素排序后从大到小删除，用双向循环链表维护。O(n)。~~
直接找最大值。O(n)。
=== B ===
题意：有一块大小为l的缓冲区，有两个线程分别写和读，每次写w字节，读l字节。可写字节数不足w时写线程等待，可读字节数不足r时读线程等待。问是否会发生死锁。
缓冲区中可读字节可能的大小为 kw % r，因此发生死锁当且仅当存在 kw % r > l - w。而 kw % r <= r - gcd(w, r)，因此有 r - gcd(w, r) > l - w。O(logn)。
=== C ===
@JTJL
=== D ===
题意：给定两个字符串AB，有m个递增的询问x_i，每次删去A中第i个字符（改变串），问B在所有m+1个串中作为子串出现了多少次，同样的下标集合视为一次。
首先计算原串中的答案，然后对于每个非边界的消除位置，计算两侧可以相连接的模式串前后缀数。可以用正反串kmp在原串上的匹配长度L[i]和R[i]来表示。反串是普通的匹配结果，正串则要跳过被消除的位置（因为消除顺序从左到右，只需简单地跳过即可）。匹配数的计算考虑正反模式串的fail[]构成的树T1和T2。一对L[i]和R[i]对应T1上一条到根的路径和T2上一条到根的路径。可以对T1做DFS，每次进入一个结点u，就对T2中以(m-u)为根的子树做区间+1，这样进入L[i]时对R[i]进行查询就能获得R[i]到根的路径上与L[i]路径中点的匹配数。O(nlogn)。
=== E ===
题意：打印序列表示，支持单页、连续页、连续奇数页和连续偶数页
排序。dp(i,j,k)表示前i个数，i-1和i不同状态（独立、连续、2连续）的最小长度。九种状态中有一些是不合法的，可以优化。O(nlogn)。
=== F ===
题意：给定一个字符串，要求给出能匹配它的非空字符集。首先最小化该字符集匹配的字符串，其次最小化长度，最后最小化字典序。
首先枚举是否取补。显然出现字符越少越好，因此未出现的可用字符都不可选。它们将字符集分为数个连续段，对每个连续段，如果字符数<=2应该枚举，否则用区间形式。注意non-empty。O(sigma)。
=== G ===
题意：有n个盘子，第i个盘子上有n块第i种披萨，现在希望每个盘子上都有n种不同披萨。一次操作可以将一块披萨从一个盘子放到另一个盘子，但每个盘子最多只能放n块披萨；也可以将一块披萨移动到小盘子里或者从小盘子移动到盘子里。给出最少操作数和操作方法。
将物品传递视为有向边，则得到一个有向完全图，直接做欧拉回路。其中一条边需要用small plate完成。O(n^2^)。
也可以考虑增量，n=2时方案显然。n>2时可以先做n-1，保留最后一步。此时2号还缺一块，则先做2->u，再进行n<->i的交互，最后u->n。O(n^2^)。
=== H ===
题意：给了一个比赛规则和排名规则，四队小组赛进行六场，问俄罗斯队必胜、必败或不确定。
枚举比分。100分应该能遍历后两个关键字。O(100^2^*16)。
=== I ===
题意：交互题，确定x0和m，给出m的上限n。每次询问a_i，交互程序计算x_{i}=(x_{i-1}+a_{i})%m，然后输出x_{i}和x_{i-1}的大小关系。在2016次询问内确定x0和m的值。
首先做两次倍增确定小于m的最大的2的幂次，然后二分。若有x<2^k^，同时当前对m的下界估计l有(m-l)<=c*2^k^（c为一较小的常数，在迭代过程中似乎是3），那么在可以在常数次内得到k-1对应的x和同数量级的估计。缩小到一定范围后就可以直接暴力。
=== J ===
题意：给定n种果汁，要求将其分为尽可能少的组，每组体积之和相同，种类不超过两种。果汁可以实数划分。n<=20。
n=1时答案为1。其他情况下，答案范围[(n+1)/2,n-1]。容易证明n种果汁总存在n-1组的解，先不考虑最大的一种果汁u，对其他果汁，用大于均值的最小的一种填充小于均值的任意一种，重复直到所有剩余果汁都小于均值，此时用u填充。因此只考虑<=n-1的解。枚举答案，用状压DP判定。设答案为k，将每个数变换为c_i*k-sum，这样和为-sum的数的集合就对应了n个数n-1组。O(n^2^*2^n^)。
剩余证明部分：对于任意解，将一种果汁视为点，混合为一组为连边，可能会有重边和自环。如果某个解中存在重边，可以对组成这些重边的两侧值取模，模数组成一条边，其他转化为两侧自环。因为总点数是n，所以组数可以用每个联通块边数和点数的差值来确定。每棵树的贡献是-1，其他类型联通块的贡献则>=0。设总贡献为-x，则必定可以将所有联通块分为x组，每组的总贡献为-1，因此状压DP总能获得最优解。
=== K ===
题意：给定图G，占领点u需要a_u个单位，占领边e需要两侧城市兵力之和至少c_e个单位，在u处投放一个单位需要代价b_u，问占领所有点的最小代价。
假设占领边(u,v)时，端点两侧均有单位，那么将u侧全部单位在v侧单位来源中某一个城市w产生，因为w的初始兵力增加，必定同样能到达v。(u,v)两侧总兵力不变，同样能占领。然后沿原方案中u的汇聚过程反向占领，能达到和原方案一样的效果。因此在占领边构成的连通块中，所有单位都在代价最小的城市产生，数量为城市最大值和边最大值中较大者。因此若最终方案中有(u,v)，则(u,v)所处连通块与其他连通块的边的权值应大于(u,v)的权值，否则加入这条边后不会增加代价，不如合并。因此用类似Kruscal的方式加边，动态维护每个连通块最小解即可。O(mlogm)。
=== L ===
题意：有2n个操作，每个操作都有执行时间。一类操作将一个球放入池中，二类操作从池中随机取一个球。问每个球的期望存在时间。保证二类操作执行时池非空。
从后往前计算期望。对第i个操作计算此时加入的球的期望存在时间f_{i}。如果是一类操作则直接累加时间。如果是二类操作，容易知道现在池中球的数量m，因此其对应的增加时间是(t_{i+1}-t{i}+f_{i+1})*(m-1)/m。O(n)。

A

题意：给定整数序列a，数字互不相同。称三元组(i,j,k)为tricky当且仅当a_i

显然应该对每个a_j选取最近的a_i和a_k，对元素排序后从大到小删除，用双向循环链表维护。O(n)。

直接找最大值。O(n)。

B

题意：有一块大小为l的缓冲区，有两个线程分别写和读，每次写w字节，读l字节。可写字节数不足w时写线程等待，可读字节数不足r时读线程等待。问是否会发生死锁。

缓冲区中可读字节可能的大小为 kw % r，因此发生死锁当且仅当存在 kw % r > l - w。而 kw % r <= r - gcd(w, r)，因此有 r - gcd(w, r) > l - w。O(logn)。

C

@JTJL

D

题意：给定两个字符串AB，有m个递增的询问x_i，每次删去A中第i个字符（改变串），问B在所有m+1个串中作为子串出现了多少次，同样的下标集合视为一次。

首先计算原串中的答案，然后对于每个非边界的消除位置，计算两侧可以相连接的模式串前后缀数。可以用正反串kmp在原串上的匹配长度L[i]和R[i]来表示。反串是普通的匹配结果，正串则要跳过被消除的位置（因为消除顺序从左到右，只需简单地跳过即可）。匹配数的计算考虑正反模式串的fail[]构成的树T1和T2。一对L[i]和R[i]对应T1上一条到根的路径和T2上一条到根的路径。可以对T1做DFS，每次进入一个结点u，就对T2中以(m-u)为根的子树做区间+1，这样进入L[i]时对R[i]进行查询就能获得R[i]到根的路径上与L[i]路径中点的匹配数。O(nlogn)。

E

题意：打印序列表示，支持单页、连续页、连续奇数页和连续偶数页

排序。dp(i,j,k)表示前i个数，i-1和i不同状态（独立、连续、2连续）的最小长度。九种状态中有一些是不合法的，可以优化。O(nlogn)。

F

题意：给定一个字符串，要求给出能匹配它的非空字符集。首先最小化该字符集匹配的字符串，其次最小化长度，最后最小化字典序。

首先枚举是否取补。显然出现字符越少越好，因此未出现的可用字符都不可选。它们将字符集分为数个连续段，对每个连续段，如果字符数<=2应该枚举，否则用区间形式。注意non-empty。O(sigma)。

G

题意：有n个盘子，第i个盘子上有n块第i种披萨，现在希望每个盘子上都有n种不同披萨。一次操作可以将一块披萨从一个盘子放到另一个盘子，但每个盘子最多只能放n块披萨；也可以将一块披萨移动到小盘子里或者从小盘子移动到盘子里。给出最少操作数和操作方法。

将物品传递视为有向边，则得到一个有向完全图，直接做欧拉回路。其中一条边需要用small plate完成。O(n²)。

也可以考虑增量，n=2时方案显然。n>2时可以先做n-1，保留最后一步。此时2号还缺一块，则先做2->u，再进行n<->i的交互，最后u->n。O(n²)。

H

题意：给了一个比赛规则和排名规则，四队小组赛进行六场，问俄罗斯队必胜、必败或不确定。

枚举比分。100分应该能遍历后两个关键字。O(100²*16)。

I

题意：交互题，确定x0和m，给出m的上限n。每次询问a_i，交互程序计算x_{i}=(x_{i-1}+a_{i})%m，然后输出x_{i}和x_{i-1}的大小关系。在2016次询问内确定x0和m的值。

首先做两次倍增确定小于m的最大的2的幂次，然后二分。若有x<2^k，同时当前对m的下界估计l有(m-l)<=c*2^k（c为一较小的常数，在迭代过程中似乎是3），那么在可以在常数次内得到k-1对应的x和同数量级的估计。缩小到一定范围后就可以直接暴力。

J

题意：给定n种果汁，要求将其分为尽可能少的组，每组体积之和相同，种类不超过两种。果汁可以实数划分。n<=20。

n=1时答案为1。其他情况下，答案范围[(n+1)/2,n-1]。容易证明n种果汁总存在n-1组的解，先不考虑最大的一种果汁u，对其他果汁，用大于均值的最小的一种填充小于均值的任意一种，重复直到所有剩余果汁都小于均值，此时用u填充。因此只考虑<=n-1的解。枚举答案，用状压DP判定。设答案为k，将每个数变换为c_i*k-sum，这样和为-sum的数的集合就对应了n个数n-1组。O(n²*2ⁿ)。

剩余证明部分：对于任意解，将一种果汁视为点，混合为一组为连边，可能会有重边和自环。如果某个解中存在重边，可以对组成这些重边的两侧值取模，模数组成一条边，其他转化为两侧自环。因为总点数是n，所以组数可以用每个联通块边数和点数的差值来确定。每棵树的贡献是-1，其他类型联通块的贡献则>=0。设总贡献为-x，则必定可以将所有联通块分为x组，每组的总贡献为-1，因此状压DP总能获得最优解。

K

题意：给定图G，占领点u需要a_u个单位，占领边e需要两侧城市兵力之和至少c_e个单位，在u处投放一个单位需要代价b_u，问占领所有点的最小代价。

假设占领边(u,v)时，端点两侧均有单位，那么将u侧全部单位在v侧单位来源中某一个城市w产生，因为w的初始兵力增加，必定同样能到达v。(u,v)两侧总兵力不变，同样能占领。然后沿原方案中u的汇聚过程反向占领，能达到和原方案一样的效果。因此在占领边构成的连通块中，所有单位都在代价最小的城市产生，数量为城市最大值和边最大值中较大者。因此若最终方案中有(u,v)，则(u,v)所处连通块与其他连通块的边的权值应大于(u,v)的权值，否则加入这条边后不会增加代价，不如合并。因此用类似Kruscal的方式加边，动态维护每个连通块最小解即可。O(mlogm)。

L

题意：有2n个操作，每个操作都有执行时间。一类操作将一个球放入池中，二类操作从池中随机取一个球。问每个球的期望存在时间。保证二类操作执行时池非空。

从后往前计算期望。对第i个操作计算此时加入的球的期望存在时间f_{i}。如果是一类操作则直接累加时间。如果是二类操作，容易知道现在池中球的数量m，因此其对应的增加时间是(t_{i+1}-t{i}+f_{i+1})*(m-1)/m。O(n)。