Contest Info

date: 2018.08.04 12:00-17:00

practice link

Solutions

A. Ability Draft

签到题，搜就完事儿了。

B. Short Random Problem

题目大意：给你一棵树，每条边的边权服从 \(U[0,1]\)，且相互独立，求树直径的期望。

题解：std 四百多行，不想写了。做法大概是这样的。

考虑枚举每一条边，计算中心在该条边上的期望。首先我们需要预处理每个点到它子树距离最大值的期望，我们需要支持两种操作：

一是给一个随机变量加上一个 \(U[0,1]\)。设 \(X,Y\) 是连续型随机变量且相互独立，且 \(Y\sim U[0,1]\)，那么 \(Z=X+Y\) 的概率密度函数为 \[ \begin{aligned} h(z)&=\int_{-\infty}^{+\infty}f(x)g(z-x)\mathbb{d}x\\ &=\int_{z-1}^{z}f(x)\mathbb{d}x \end{aligned} \] 二是取两个随机变量的最大值。设 \(X,Y\) 是连续型随机变量且相互独立，那么 \(Z=\max\{X,Y\}\) 的概率密度函数为 \[ \begin{aligned} h(z)&=\frac{\mathbb{d}\left(\int_{-\infty}^{z}f(x)\mathbb{d}x\int_{-\infty}^{z}g(y)\mathbb{d}y\right)}{\mathbb{d}z}\\ &=\frac{\mathbb{d}\left(\int_{0}^{z}f(x)\mathbb{d}x\int_{0}^{z}g(y)\mathbb{d}y\right)}{\mathbb{d}z} \end{aligned} \] 从操作的性质可以看出，这些概率密度函数都是以 \(1\) 为单位的分段多项式函数。

枚举每一条边时，它的子树的最大距离我们已经预处理了，而它上面的部分也容易在 \(dfs\) 时顺便求出。下面分几种情况讨论：

• 若两个部分都是单点，显然答案是 \(\frac{1}{2}\)。

• 若一个部分是单点，设另一部分的最大距离服从随机变量 \(X\)，这条边服从随机变量 \(Y\sim U[0,1]\)，那么我们的期望为 \(E(u(X,Y))\)，其中 \[ u(X,Y)=\begin{cases} &0&(X<Y)\\ &\frac{X+Y}{2}&(X\ge Y) \end{cases} \] 那么它的答案为 \[ \begin{aligned} E(u(X,Y))&=\int_{-\infty}^{+\infty}\int_{-\infty}^{+\infty}u(x,y)f(x)g(y)\mathbb{d}x\mathbb{d}y\\ &=\int_{-\infty}^{+\infty}\int_{-\infty}^{x}\frac{x+y}{2}f(x)g(y)\mathbb{d}y\mathbb{d}x\\ &=\int_{0}^{1}\int_{0}^{x}\frac{x+y}{2}f(x)\mathbb{d}y\mathbb{d}x+\int_{1}^{+\infty}\int_{0}^{1}\frac{x+y}{2}f(x)\mathbb{d}y\mathbb{d}x\\ &=\int_{0}^{1}\frac{3}{4}x^{2}f(x)\mathbb{d}x+\int_{1}^{+\infty}\frac{1}{2}xf(x)+\frac{1}{4}f(x)\mathbb{d}x \end{aligned} \]

• 若两个部分都不是单点，设两个部分的最大距离分别服从随机变量 \(X,Y\)，枚举的边服从随机变量 \(Z\sim U[0,1]\)，那么我们的期望为 \(E(u(X,Y,Z))\)，其中 \[ u(X,Y,Z)=\begin{cases} &\frac{X+Y+Z}{2}&(Z\ge|X-Y|)\\ &0&(Z<|X-Y|) \end{cases} \] 那么它的答案为 \[ \begin{aligned} E(u(X,Y,Z))&=\int_{-\infty}^{+\infty}\int_{-\infty}^{+\infty}\int_{-\infty}^{+\infty}u(x,y,z)f(x)g(y)h(z)\mathbb{d}x\mathbb{d}y\mathbb{d}z\\ &=\int_{-\infty}^{+\infty}\left(\int_{-\infty}^{x}\int_{-\infty}^{x-y}\frac{x+y+z}{2}f(x)g(y)h(z)\mathbb{d}z\mathbb{d}y+\int_{x}^{+\infty}\int_{-\infty}^{y-x}\frac{x+y+z}{2}f(x)g(y)h(z)\mathbb{d}z\mathbb{d}y\right)\mathbb{d}x\\ &=\int_{-\infty}^{+\infty}\left(\int_{-\infty}^{x-1}\int_{0}^{1}\frac{x+y+z}{2}f(x)g(y)\mathbb{d}z\mathbb{d}y+\int_{x+1}^{+\infty}\int_{0}^{1}\frac{x+y+z}{2}f(x)g(y)\mathbb{d}z\mathbb{d}y+\int_{x-1}^{x}\int_{0}^{x-y}\frac{x+y+z}{2}f(x)g(y)\mathbb{d}z\mathbb{d}y+\int_{x}^{x+1}\int_{0}^{x-y}\frac{x+y+z}{2}f(x)g(y)\mathbb{d}z\mathbb{d}y\right)\mathbb{d}x\\ &=\int_{-\infty}^{+\infty}\left(\int_{-\infty}^{x-1}\frac{2x+2y+1}{4}f(x)g(y)\mathbb{d}y+\int_{x+1}^{+\infty}\frac{2x+2y+1}{4}f(x)g(y)\mathbb{d}y+\int_{x-1}^{x}\frac{3x^{2}-2xy-y^{2}}{4}f(x)g(y)\mathbb{d}y+\int_{x}^{x+1}\frac{3y^{2}-2xy-x^{2}}{4}f(x)g(y)\mathbb{d}y\right)\mathbb{d}x \end{aligned} \]

C. Block, Stock and Two Smoking Galaxy Notes

题目大意：\(n\) 个人，有 \(m\) 对关系 \((u_i,v_i)\)，表示这两个人能相互交流。让你从 \(n\) 个人中选出一个 leader，并且把剩下的 \(n-1\) 个人分成若干组。每个组要么 \(1\) 个人，要么 \(2\) 个人。如果是 \(1\) 个人的小组，这个人要能与 leader 交流；如果是 \(2\) 个人的小组，这两人要能相互交流，且存在一个人能与 leader 交流。

题解：枚举 leader，将能与他交流的人各自分为一组，然后剩下的人对这些人连边，求二分图匹配。

D. Lunch Queue

题目大意：\(n\) 个人陆续前来排队，每个人有一个颜色 \(c_i\) 和一个权值 \(a_i\)。第 \(i\) 人到达的时候，他会选一个最前的位置插队，位置满足：插入之后与跟他同色的人相邻，且因为他插队而向后移动的人数不超过 \(a_i\)。若不存在可以插入的位置，则排在队尾。

输出最后的队伍序列。

题解：

std solution:

如果知道第 \(i\) 个人插入队列之后的排名 \(\text{rk}_i\)（只考虑前 \(i\) 个人时的排名），那么就可以倒着还原出最终队列。

那么我们将队列按照颜色分成若干段，给它们按出现顺序重标号，用树状数组维护每段人数。那么第 \(i\) 个人可以插入到排名不小于 \(i-a_i-1\) 的人后。

在树状数组中二分找到可以插入的最小段编号（这一段不一定跟它同色），再去 \(c_i\) 的段集合(可以使用 vector 实现）中二分找到最小的可以插入的同色段 \(p\)，否则新建一段。那么第 \(i\) 个人要去的段已经确定了，但是排名还不清楚。

排名去树状数组中问一下之前段的总人数（插入到段 \(p\) 头部）和 \(i-a_i-1\)（插入到段 \(p\) 中间） 取 max 即可。时间复杂度 \(\mathcal{O}(n\log{n})\)。

E. Oneness

题目大意：定义一个数的 oneness 表示它长度大于等于 \(2\) 且全由数字 \(1\) 组成的约数个数。随机一个大整数 \(n\)，问 \(1\sim n\) 中所有整数的 oneness 之和。

题解：显然答案为 \(\displaystyle{\lfloor\frac{n}{11}\rfloor+\lfloor\frac{n}{111}\rfloor+\cdots=\lfloor\frac{9n}{10^{2}-1}\rfloor+\lfloor\frac{9n}{10^{3}-1}\rfloor+\cdots}\)。

注意到 \(\displaystyle{\lfloor\frac{10^{n}}{(10^{t}-1)}\rfloor=10^{n-t}+10^{n-2t}+\cdots+10^{n\text{ mod }t}}\)，\(10^{n}\text{ mod }(10^{t}-1)=10^{n\text{ mod }t}\)。我们可以对每一位先计算第一部分的答案，容易发现这是一个卷积形式，可以用 NTT 加速。对于第二部分，对于每个 \(t\)，我们相当于要求 \(9n\) 在 \(10^{t}\) 进制下的各位数字之和除以 \(10^{t}-1\)。注意到大整数是随机的，我们只需要取每一个 \(10^{t}\) 进制位的前若干十进制位近似计算即可。

时间复杂度 \(\mathcal{O}(20\cdot n\log n)\)。

F. Shuffle

题目大意：定义对字符串的操作 \(\text{shuffle}(s_1\dots s_n)=s_1s_3\dots s_{n-1}s_2s_4\dots s_n\)，其中 \(n\) 是偶数。给定两个长度相等的字符串 \(s,t\)，求最少的操作次数使得 \(s\) 变成 \(t\)。

题解：我们可以 \(\mathcal{O}(n)\) 求出这个置换的循环节，打表可知这些循环节的 lcm 大概也是 \(\mathcal{O}(n)\) 级别的（并不会证）。因此我们可以对每个循环节列出一个同余方程，解这个同余方程组即可。

对每个循环节我们用 kmp 匹配一下就可以知道需要循环多少次。注意到虽然可能有多个匹配，但是这些位置必然是模 \(s\) 的循环节同余的。因此这里看似有多个方程，实际上可以化简成一个。时间复杂度 \(\mathcal{O}(n\log n)\)。

G. Piecewise Linearity

题目大意：给出平面上 \(x\) 坐标严格递增的 \(n+1\) 个点 \(P_0,P_1,\dots,P_{n-1},P_n\)，它们构成的图形为线段 \(P_iP_{i+1}(1\leq i\leq n-2)\)，以及射线 \(P_1P_0,P_{n-1}P_n\)。问你是否存在实数 \(\lambda_1,\lambda_2,\dots,\lambda_m\) 和 \(a_1,\dots,a_m\) 使得下列函数与其具有相同的图形：

\[ f(x)=\sum_{i=1}^m\lambda_i|x-a_i| \]

题解：注意到 \(f\) 必然有如下的形式：\(\sum_{i=1}^{n-1}\lambda_{i}|x-x_{i}|\)，且满足 \[ \begin{cases} -\lambda_{1}-\lambda_{2}-\cdots-\lambda_{n-1}&=k_{0,1}\\ \lambda_{1}-\lambda_{2}-\cdots-\lambda_{n-1}&=k_{1,2}\\ \vdots\\ \lambda_{1}+\lambda_{2}+\cdots+\lambda_{n-1}&=k_{n-1,n} \end{cases} \] 其中 \(k_{i,i+1}\) 表示点 \(i\) 到点 \(i+1\) 的斜率。容易发现这一方程有解，当且仅当 \(k_{0,1}=k_{n-1,n}\)。

满足这一条件后，就可以解出这个函数的各个系数了。之后还需要代入验证“截距”是否满足要求。

在这道题中，使用浮点数运算会带来一定的精度损失。由于本题只需要判断两个浮点数是否相等，因此我们可以随机选择一个较大的质数，在模该质数的意义下计算，碰巧相等的概率很小。

H. Sketch

题目大意：定义一个序列 \(\{a\}\) 的 \(s_k\) 表示其所有长度为 \(k\) 的不降子序列中最后一个元素的最小值。定义 \(s(a)=s_1,\dots,s_l\) 是序列 \(a\) 的一个速写，其中 \(l\) 是 \(a\) 最长不降子序列的长度。现给出 \(k,n,m\)，以及 \(t_1,\dots,t_k\) ，让你构造一个序列 \(a_1,\dots,a_n\)，满足 \(a_i\in [1,m]\)，且如果 \(t_i\neq -1\)，那么必有 \(t_i=s_i(1\leq i\leq k)\)。同时 \(s(a)\) 的长度等于 \(k\)。

题解：如果 \(k>n\) 那么无解，否则我们把 \(t_1,\dots,t_k\) 依次排列（如果 \(t_i=-1\)，那么我们让 \(t_i=t_i-1,t_0=1\)），这已经满足题目要求了，但是还剩下 \(n-k\) 个数字。注意我们不能让 \(s(a)\) 的长度大于 \(k\)。

我们往上述序列头部依次插入 \(t_1+1,t_1+2,\dots,m\)，直至长度为 \(n\)。每次插入一个数字 \(x\) 的时候，我们找到 \(t_1,\dots,t_k\) 中能续上 \(x\) 的位置，然后将 \(x\) 重复若干次，使得续上之后长度为 \(k\)。

I. \(\leq\) or \(\geq\)

题目大意：交互题。有 \(n=10000\) 个栈，每个栈有 \(k=10\) 个元素。一开始知道每个栈的栈顶，你要每次输出一个 \(x\)，接着 jury 会选择一个 \(\leq\) 或者 \(\geq\) 操作，将栈顶 \(\leq\) 或者 \(\geq x\) 的弹栈。要求你在 \(50\) 次之内把所有栈清空。

题解：如果每次取中位数，那么可以被卡到 \(k\) 次清空一半的栈，那么需要 \(k\log n\) 次。考虑加权中位数，还剩 \(k'\) 个元素的栈权重为 \(2^{k'-1}\)。

势能分析，一开始势能为 \(n2^{k-1}\)，每次选择带权中位数，会选到一半的势能，然后一次操作之后被选到的势能减半。所以一次操作相当于乘 \(\frac{3}{4}\)，最后势能为 \(\frac{n}{2}\)。所以需要 \(\log_{\frac{4}{3}}2^k\approx 24\) 次操作。

J. Stairways

题目大意：

给出一个长度为\(n\le10^5\)的数列\(a_n\)（\(1\le a_i\le10^9\)），现在要把它分成两个序列，每个序列的代价是每个位置的前缀最大值之和减去序列中的数之和，最小化这两个序列的代价和。

题解：

因为序列中数的和是一定的，我们只考虑最小化两个序列的前缀最小值之和。

显然将原数列的前缀最小值都放入一个序列最优，为了方便叙述，记这个序列为大的序列，另一个为小的序列。

令dp[i][j]为考虑原数列的前缀\(i\)，小的序列的最大值为\(j\)的最小代价，pre[i]为原数列前缀的最大值。

若a[i] = pre[i]，直接将其加入大的序列，dp[i][j] = dp[i-1][j] + a[i];

否则a[i] < pre[i]，如果将其放入小的序列：

• 可以放在之前最大值不大于a[i]的序列后面，最大值变为a[i]，\(dp[i][a[i]] = \min_{j\le a[i]} dp[i - 1][j] + a[i]\)
• 可以放在之前最大值大于a[i]的序列后面，最大值不变，\(dp[i][j](j>a[i]) = dp[i - 1][j] + j\).

如果将其放入大的序列：\(dp[i][j] = dp[i - 1][j] + pre[i]\)，显然这种转移只有j < a[i]时需要用到。

现在我们需要一种数据结构来加速转移，支持查询前缀最小值，给一个前缀都加上一个相同的值，单点修改一个位置为给定值，以及给一个后缀加上自己的下标。

我们将权值离散化之后分块，每块将dp值表示成kx+y的形式，对于同一块，\(k\)是相同的值，维护一下\((x,y)\)的下凸壳即可，对于整块++k和y+=v的操作维护两个tag即可。

因为k递增，取到最优值的位置在下凸壳上是递减的，暴力移动即可。

时间复杂度\(O(n\sqrt{n})\)，空间复杂度\(O(n)\).

K. Hiding a Tree

题目大意：给出一棵树的输入 \(n\)，和 \((u_i,v_i)(1\leq u_i,v_i\leq n, i\in[1, n))\)，目标是让 \(n\oplus u_1\oplus v_1 \cdots u_{n-1}\oplus v_{n-1}=0\)。你可以对允许的点进行重标号，但是重标号之后标号必须互不相等，标号范围 \([1,10^9]\)。

题解：设度为奇数的允许重标号的点有 \(\text{cnt}\) 个。令 \(\text{ans} = n\oplus u_1\oplus v_1 \cdots u_{n-1}\oplus v_{n-1}\)。

若 \(\text{ans}=0\)，那么满足条件，直接输出。

否则，若 \(\text{cnt}=0\)，那么无解。

若 \(\text{cnt}=1\)，设它为点 \(a\)，那么我们需要它重标号为 \(t = \text{ans}\oplus a\)。若 \(t\neq 0\) 且 \(t\) 未被使用过，那么将点 \(a\) 重标号为 \(t\)。否则若 \(t\) 是个偶数点且允许操作，那么我们把 \(t\) 重标号为 \(2^{17}\)，把 \(a\) 重标号为 \(t\)。否则无解。

若 \(\text{cnt}\geq 2\)，设其中两个为 \(a,b\)，令 \(t=\text{ans}\oplus a\oplus b\)。若 \(t\neq 0\)，那么我们把 \(a\) 重标号为 \(2^{17}\)，把 \(b\) 重标号为 \(t\oplus 2^{17}\) 即可。否则若 \(t=0\)，如果 \(\text{cnt}=2\) 那么无解，否则我们找到点 \(c\)，那么 \(\text{ans}\oplus a\oplus c\) 一定非 \(0\)，我们按上述做法即可。

Dirt Replay

I: -3 解法错误；忘删调试语句；算法里排序关键字错误

K: -5 RE没判断cnt=0；corner case没分析清楚；Z来改的时候elseif漏写else

G：-4 精度问题eps

H：-1 算法错误，构造出来的序列不是最短的，判无解判错了