Contest Info

date: 2018.10.01 12:30-17:30

practice link

Solutions

A. Thickest Burger

签到题。

B. Relative atomic mass

签到题。

C. Recursive sequence

签到题。

D. Winning an Auction

题目大意：一共 \(n\) 件物品，Alice 手上有 \(A\) 金钱，Bob 有 \(B\)。每轮各自出价 \(a \in[0, A], b\in [0, B]\)。若 \(a > b\) 则 Alice 花费 \(a\) 获得这件物品，若 \(a < b\) 则 Bob 花费 \(a\) 获得这件物品，若 \(a=b\) 则第奇数件物品的时候 Alice 获得，否则 Bob 获得。两人均采用最优策略（最大化获得的物品数量），且都知道 \(n, a, b\)，问结果。

题解：定义 \(f[p=0/1][i][j][k]\) 表示当前局是第奇数/偶数局，还剩 \(i\) 件物品，Alice 有 \(j\) 金钱，Bob 有 \(k\) 金钱，Alice 能获得的最大物品。那么我们只需要预处理出 \(f\)，然后每次询问我们查询 \(f[1][n][A][B]\) 即可。

当 \(i=1\) 的时候，Alice 和 Bob 的出价都是手上的全部金钱。考虑 \(i\geq 2\)，如果 \(j=k\)，那么 \(f\) 值是 Alice 在后续 \(i\) 件物品中的优势局面个数。

否则，假设当前局面是 Alice 占优势，我们枚举 Alice 的出价 \(x=0,1,2,\dots\)，那么如果 Alice 获胜，收益为 \(\text{va}_x = f[1-p][i-1][j-x][k]+1\) 。如果 Bob 想获胜，则出价 \(x+1\),收益为 \(\text{vb}_{x+1} = f[1-p][i-1][j][k-x-1]\)。如果 \(\text{vb}_{x+1}\geq \text{va}_x\)，那么 Bob 不会浪费钱出 \(x+1\)，此时 \(f[p][i][j][k]=\text{va}_{x}\)。如果 \(\text{va}_{x+1}\leq \text{vb}_{x+1}\)，那么 Alice 不会浪费钱出 \(x+1\)，此时 \(f[p][i][j][k]=\text{vb}_{x+1}\)。否则，我们继续枚举 Alice 出价为 \(x+1\) 的情况。

复杂度是 \(\mathcal{O}(2n^4/(3!))\)，其实 \(j<k\) 和 \(j>k\) 的时候，有 \(f[p][i][j][k]=f[1-p][i][j][k]\)，但是因为体系结构的原因，这个优化实测会变慢。

E. Counting Cliques

题目大意：

给出一个\(n\le100\)个点，\(m\le1000\)条边的简单无向图，保证每个点的度数不超过\(20\).

求图中大小恰好为\(1\le S\le10\)的团的数量。

题解：

枚举一个点作为团上编号最大的点，然后从它的出度中枚举其它的点，可以有很多剪枝。

用bitset来check是否可以加入一个新点进入团，复杂度\(O(n/32)\)，可以当作一个小常数。

如果一个连通块是完全图，那么可以不进行搜索直接统计答案。

时间复杂度\(\displaystyle O(nS\cdot\binom{20}{S-1})\).

G. Do not pour out

题目大意：一个直径和高均为 \(2\) 的圆柱体杯子，里面装入了高度为 \(h\) 的水。现在将杯子倾斜至水刚好不倒出，求水面的面积。

题解：显然二分。水的高度大于 \(1\) 的情况比较简单，这里不赘述。

水的高度小于 \(1\) 时，我们二分水面与杯壁形成的夹角，设为 \(\theta\)。我们用一些与 \(xOy\) 平行的平面来切割这个图形做积分。

设 \(x\) 为平面与圆柱体上顶面的距离，那么截面的面积为 \(\alpha-\sin\alpha\cos\alpha\)，其中 \(\alpha=\arccos(1-x\tan\theta)\)。那么 \(x=\frac{1-\cos\alpha}{\tan\theta}\)。积分式为： \[ \begin{aligned} &\int_{0}^{2}\alpha-\sin\alpha\cos\alpha\mathbb{d}x\\ =&\int_{0}^{2}\alpha-\sin\alpha\cos\alpha\mathbb{d}\frac{1-\cos\alpha}{\tan\theta}\\ =&\frac{1}{\tan\theta}\int_{0}^{\arccos(1-2\tan\theta)}\alpha\sin\alpha-\sin^{2}\alpha\cos\alpha\mathbb{d}\alpha\\ =&\frac{1}{\tan\theta}(-\alpha\cos\alpha+\sin\alpha-\frac{1}{3}\sin^{3}\alpha)\big{|}^{\arccos(1-2\tan\theta)}_{0} \end{aligned} \]

底面沾水的面积和水面的面积成 \(\sin\theta\) 比例。

H. Guessing the Dice Roll

题目大意：给出 \(n\leq 10\) 长度为 \(l\leq 10\) 的序列（只由数字 \(1,2,3,4,5,6\) 组成）。现在投掷一个骰子无限次，第一次出现某个序列作为后缀，那么它获胜。求每个序列的获胜概率。

题解：建立 trie 图，删掉终止节点的出边，然后把图的邻接矩阵求一个足够大的 \(2\) 的幂的幂。

I. The Elder

题目大意:

有一棵\(n\le10^5\)个节点，以\(1\)为根的树，每条边有个权值。

对于每个节点\(x\)，可以把它到根的路径分成若干段（分割点必须在点上不可以在边中间），代价为每一段的边权和的平方和加上段数减一乘以\(P\)，最小化这个代价。

对于所有节点，求最大的最小代价是多少。

题解：

令\(dp_1=-P\)，显然转移方程为： \[ \begin{aligned} dp_i &= \min_{j\text{是}i\text{祖先}}\{dp_j+(dis_i-dis_j)^2+P\} \\ &= \min_{j\text{是}i\text{祖先}}\{dp_j+dis_j^2-2dis_i\cdot dis_j\} + dis_i^2 + P \end{aligned} \] 是一个斜率优化dp，可以用凸包来维护。

因为可以转移的\(j\)是\(i\)父亲链上的点，我们用一个可持久化栈来维护凸包，每次新加点时倍增弹栈顶即可，三分也可以用二分来代替。

时间复杂度\(O(n\log{n})\).

coldwater’s solution

用可持久化单调队列维护，二分head和tail，然后记录tail改变前的位置和值，回溯的时候撤销。

J. Query on a graph

题目大意：

给出一棵\(n\)个点\(n\)条边的简单无向连通图，\(q\)次操作，每次选择一个点\(u\)，把距离点\(u\)距离不大于\(k\)的所有点的权值都加上一个值，或者询问它们的权值和。

\(1\le n, q\le10^5,0\le k\le2\)

题解：

先建出基环外向树，然后求出bfs序，对于任意点\(x\)，子树中深度比它多一和多二的点的bfs序分别是在一个区间，那么就可以用线段树维护对这些点的修改和询问。

然后，对于不在子树中的点，将\(k\)减少一之后去递归地处理父亲节点，并把自己这里重复的部分逆操作一下。

还有经过环的情况，就再去环上的邻点递归处理一下即可，设定参数只允许第一次考虑环上的情况就不会重复操作。

时间复杂度\(O((n+q)\log{n})\).

K. New Signal Decomposition

题目大意：求 \(\displaystyle{b_{i}=\sum_{j=0}^{p-1}a_{j}2^{\sin^{3}(\frac{2\pi ij}{p})}}\)，其中 \(p\) 为质数，\(a\) 给出。

题解：注意到 \(\sin\) 以 \(2\pi\) 为周期，那么 \(2\pi ij\) 可以替换为 \(2\pi(ij\mod{p})\)。那么把所有下标都对 \(p\) 的某个原根取个 \(\log\) 就变成 FFT 了。

L. A Random Turn Connection Game

题目大意：

在一个\(8\times8\)的棋盘上，每回合随机选择一个没有被占领的格子随机落\(A\)棋子或者\(B\)棋子，同样的棋子\(4\)连通。

如果某回合结束后，\(A\)棋子连通了第一行与最后一行，则\(A\)胜利，游戏结束；

如果某回合结束后，\(B\)棋子连通了第一列与最后一列，则\(B\)胜利，游戏结束；

如果某回合开始时，没有格子可以放了，则游戏结束，没有人获胜。

给定一个初始局面，问\(A\)和\(B\)获胜的概率分别是多少。

题解：

显然\(A\)和\(B\)不可能同时获胜，可以考虑不提前结束游戏而是必须放满棋盘，因为获胜之后发生的事件的总概率为\(1\)，这样计算的获胜概率不变。

每次随机选择位置会使得概率的分母有一个\(k!\)，刚好消掉了落子的顺序，因此我们只需要统计局面数量除以总数量即可。

\(A\)获胜的局面数，插头dp记录轮廓线上的\(8\)个格子所在的连通块，转移时要求与最上方连通的连通块存在且编号为\(1\)。

\(B\)获胜将棋盘转置一下再计算一次即可。

M. Subsequence

题目大意：

有一个长度为\(n\le10^5\)的序列，第\(i\)个位置是三元组\((cost0_i,cost1_i,color_i)\).

定义一个子序列的代价为每个位置取上一个位置的颜色（第一个位置认为上一个颜色为\(0\)）对应的代价的和。

求代价第\(k\le10^5\)大的子序列的代价。

题解：

新增源点\(s\)和汇点\(t\)，每个位置拆成三个点，表示选择这个位置，不选这个位置且末尾颜色为\(0\)，不选这个位置且末尾颜色为\(1\)，连边，则问题转化为这个图的第\(k\)长路。

因为这是个分层图，最长路可以dp求，然后用可持久化左偏树来求第\(k\)长路即可。

时间复杂度\(O(n\log{n}+k\log{k})​\).

Dirt Replay

D: -5 dp 的时候枚举顺序反了；卡常数（体系结构）

I: -2 三分写错了