UOJ Logo WuHongxun的博客

博客

UOJ Round #17 题解

2018-03-18 22:58:56 By WuHongxun

滑稽树上滑稽果

By jiry_2,数据、题解By WuHongxun

写题解之前,我们先来回顾一下上次比赛的A题题解:

这道题可能并没有那么有趣..本来有一道很棒的 A,但是比赛前突然被发现是个假题..然后就临时出了这么个题..感觉送送分还是不错的。

emm 懂我意思吧?

如果看到题面里大大的滑稽还没有察觉事情不太对...请允悲...

子任务一

既然 $n$ 那么小,我们直接枚举每个点的父亲!

时间复杂度 $O(n^n)$。

子任务二

保证是一条链了,我们就只要枚举排列了!

冷静一下马上就会意识到,答案一定是一条链。这个部分分肯定是出题人用来提示大家冷静一下的!

时间复杂度 $O(n!)$。

子任务三

保证滑稽值的字典序最小?那就等于是每次枚举一个和当前的滑稽值and起来最小的值,然后把他加到后面。

时间复杂度 $O(n^2)$。

子任务四

把相同的位拿出来,这些位要么一定是每次没贡献,要么一定是每次有贡献。

那么剩下的位,每次一定会减去一位,从而最多只会用$O(log a)$次就减到0了,每次暴力找最小的就好了。

时间复杂度 $O(n log a)$。

子任务五

chat

出题人给了一个部分分是这个贪心的过程,我们睿(ruo)智(zhi)的分析一下,这个做法一定是错的!

事实上的确是希望考验大家独立思考、小心求证的能力。

我们一样先把每个数都一样的那些位拿出来,剩下的位我们等于是希望尽快把他们变成$0$。

这可以用一个dp来实现,$f[S]$表示$S$集合内的位为1的时候,想要变成$0$还需要多少代价。

dp转移就是每次枚举一个$a[i]$,$f[S] = min(f[S], f[S \& a[i]] + (S \& a[i]))$。

时间复杂度 $O(na)$。

子任务六

我们可以每次不枚举一个$a[i]$,而是枚举一个子集$T$,强制把这个子集$T$变成$0$。

现在的问题就是,判断有没有一个数他和$T$,and起来是0。

这非常好做,只需要每次$cnt[i] |= cnt[i | (2^j)]$,从每个比$i$多一个$0$的位置转移就好了。

事实上dp的时候,我们可以用贪心得到的解来进行剪枝,所以是不卡常数的。

时间复杂度 $O(a^{log_2 3}) = O(a^{1.58})$

滑稽树下你和我

By picks,数据、题解By Scape

算法一

直接输出两起始点距离即可。

期望得分$5$分。

算法二

考虑"保证存在最优方案,在任意时刻至少有一端点位于树的某结点上"这个性质。

我们先考虑二分答案,显然可以设计一个dp即为$f[i][j]$表示是否存在某种方案使得最终一个点在点$i$,一个点在点$j$。直接按照定义转移即可,时间复杂度$O(n^2logn)$

期望得分$15$分。结合算法一可获得$20$分。

算法三

同样我们先考虑二分答案,看答案是否能$\le v$。

我们考虑一条这样的性质。对于两个状态,两个点所在的边都相同,并且两个状态的两点间距离是$\le v$的,那么这两个状态是两两可达的。因为我们考虑是把其中某一条直线摆平,那么另外一条直线肯定是单调的。

那么我们就可以依此设计状态,令$f[i][j]$表示是否存在某种方案使得一个点在点$i$上,一个点在边$j$上距离点$i$最近的那个点上。那么$f[i][j]$为$1$当且仅当点$i$到边$j$的最短距离$\le v$且存在某个$f[k][x]$为$1$,其中$k$是$j$的某个端点,$x$是某个以$i$为端点的边,或存在某个$f[t][j]$为$1$,其中$t$与$i$有边相连。直接BFS转移就可以了。

因为我写完这个东西已经是早上凌晨三点了,所以我当时就认为这个算法是$O(n^3logn)$的,这就是$n\le 200$这个Subtask的由来。(笑

我们仔细分析一下,$f[i][j]$的转移复杂度显然是$O(i的度数)$的。那么加起来的转移复杂度总和显然是$O(n^2)$的,所以整个算法复杂度是$O(n^2logn)$的,你也可以选择不二分答案而是类似最短路那样去做,但还是要sort或者用堆维护,复杂度不变。

期望得分$100$分。

滑稽树前做游戏

By jiry_2

算法一

如果你做过 这个题,你就肯定知道菊花树的情况下答案就是 $\frac{1}{2} + \frac{n-1}{n}$。用快速幂求个逆元就可以了。

期望得分 $10$ 分。

算法二

$n = 4$ 的本质不同的图只有 $11$ 种,如果你有高超的手算水平,相信你可以算出所有 $n \leq 4$ 的图的答案,然后打表。

结合算法一期望得分 $30$ 分。

算法三

这题据我所知有很多种复杂度较高的 DP 算法可以通过 $n \leq 10$ 的数据,但是都没有标算简洁优美,这儿就不进行介绍了。

和大部分期望题一样,令 $g(t) = Pr[f(x) \leq t]$,那么答案显然就是 $2 - \int_{0}^2 g(t) \text{d}t$,因此我们只需要求出函数 $g(t)$,并做一次积分即可。

我们把题目的输入看做一张 $n$ 个点 $m$ 条边的无向图 $G$,那么 $g(t)$ 是一个关于 $G$ 的函数。

定义函数 $h(G,y,t)$,表示在无向图 $G$ 中,所有顶点权值的最大值小于等于 $y$,答案小于等于 $t$ 的概率,并且我们限制这个函数的定义域为 $\frac{t}{2} \leq y \leq \min(1,t)$。现在我们来考虑如何计算得到 $h(G,y,t)$:

  1. 如果所有点的权值都小于等于 $\frac{t}{2}$,那么必定满足顶点权值最大值小于等于 $y$,因此此时的概率为 $(\frac{t}{2})^n$(令 $G$ 的顶点个数为 $n$)。

  2. 如果至少有一个点的权值大于 $\frac{t}{2}$,我们枚举权值最大的点 $i$,设它的权值为 $w$。考虑所有与 $i$ 相邻的点 $j$,所有 $j$ 的出边中,权值最大的就是边 $(i,j)$ 了,因此 $j$ 的权值应当小于等于 $t-w$(又 $w>\frac{t}{2}$,因此不会和其他限制导出矛盾)。我们删去第 $i$ 个点和所有相邻点,得到了图 $G_i$,那么 $G_i$ 中的点应当满足点权小于等于 $w$ 且答案不超过 $t$,即概率为 $h(G_i,w,t)$。

因此,我们得到了关于函数 $h(G,y,t)$ 的递推式:

$$ h(G,y,t) = (\frac{t}{2})^n + \sum_{i=1}^n \int_{\frac{t}{2}}^{y}h(G_i,w,t)\text{d}w $$

显然有 $h(G,y,t)$ 是关于 $y$ 和 $t$ 的 $n$ 次其次多项式,于是我们对 $G$ 进行状压,可以在 $O(2^nn^3)$ 得到 $h(G_0,y,t)$,其中 $G_0$ 为输入的图。那么这时 $g(t) = h(G_0,\min(1,t),t)$,直接积分就可得到答案。

时间复杂度 $O(2^n \times n^3)$,结合算法一可以得到 $70$ 分。

算法四

怎么在算法三种作优化呢,我们发现算法三的复杂度的一个上界是子图个数,但是很多时候又不慢,比如在图是一个团的时候,$G_i$ 均为空,会计算的子图只有 $O(n)$ 个。

那是不是算法三可以直接跑过 $25$ 呢,遗憾的是并不是。不难发现在输入是一棵菊花的时候,算法三就会跑慢 $2^n \times n^3$。但是其中大部分的子图都是不连通的。

不难发现对于一张不连通的图 $G$,它的联通块分别为 $G_1,...,G_m$,那么 $h(G,y,t) = \prod_{i=1}^m h(G_i,y,t)$,因此对于不连通的图,我们可以直接拆分成更小的子问题,而不是和算法三一样递归的搜索。

时间复杂度未知,可以得到满分。

虽然我不会分析复杂度,但是实际上对于所有我能构造的 $n=30$ 的图,这个算法都可以在 $0.2s$ 内出解。于是冷静了一下就把 $n$ 开到 $25$ 出了出来。

这一题目前一共有 $157$ 个测试数据,std 一共只需要跑 $160ms$,所以应该是不存在卡常数的可能性的。

UOJ Round #17

2018-03-17 22:15:32 By WuHongxun

非常抱歉由于这次准备比较仓促,现在才发公告,希望大家帮忙互相转告,谢谢

UOJ Round #17 将于 3 月 18 日星期日晚上 19:00 举行!比赛将进行 3 个小时,共三道题。

Q & A

Q: 为什么之前咕了呢?

A: 因为之前一直没有B题,直到Picks贡献了一个idea拯救世界!

Q: 为什么现在才发公告呢?

A: 因为发了公告就不能咕咕咕了。因为之前大家还在努力出题,idea验证是否合理也需要时间。

Q: 为什么这场UR办的这么滑稽呢?

A: emm这次题目简单,风格清新,是您涨Rating的最佳选择!

比赛信息

本场比赛将以

滑稽

作为主题。

出题人 : jiry_2Picksjiry_2

本场成绩将计入Rating。

参加本场比赛有机会获得uoj抱枕!49850781c2939981efaa3d3dd5202cc7是获奖条件的md5码。

再次提醒大家比赛中途只测样例,最后会进行最终测试,把所有提交记录重测。

比赛结束啦,恭喜前5名的选手:

  1. wangxiuhan

  2. yfzcsc

  3. dreamoon

  4. djq_cpp

  5. F_Darcy

 echo "三道题都得分,并且三题得分倒数的平均数和平均数的倒数的差最大的选手"| md5
49850781c2939981efaa3d3dd5202cc7

恭喜dreamoondjq_cpp获得uoj抱枕!(开销 x2...555)

非常抱歉,我们鸽了

2018-03-10 11:06:46 By WuHongxun

非常抱歉,这次的ur需要推迟了。

事情要从在上一场Goodbye Round结束之后说起。我们惊讶的发现,手里有了两道没有选在Goodbye里的题目,这样一来,只要再出一道题,就可以办出一场ur啦!

于是大家就抱着飞龙骑脸的自信,加了一场半个月之后的比赛。

我首先需要承认,这半个月里,我因为种种个人的私事,没有把精力投入到出题上来。虽然现役管理员Scape这半个月一来一直在努力的思考,想要出一道好题,但是结果也完全不够理想。

结果到了比赛前的最后几天,这道题目的空缺还是没有办法填上,无奈之下只好延迟ur了。

很对不起腾出时间来参加ur,信任我们的同学,这次的ur只能推迟到有合适的题目为止了。

当然如果大家有好的idea,也请多多投题。

Goodbye Dingyou题解

2018-02-18 18:10:43 By WuHongxun

祝大家新年快乐,场场ak!

新年的XOR

出题人 jiry_2

数据和题解 jiry_2

这道题可能并没有那么有趣..本来有一道很棒的 A,但是比赛前突然被发现是个假题..然后就临时出了这么个题..感觉送送分还是不错的。

算法一

既然 $n$ 那么小,相信 $L$ 和 $R$ 肯定也不是很大,直接枚举 $L$ 和 $R$ 然后暴力算异或和!

时间复杂度 $O(n^3)$,期望得分 $20$ 分。

算法二

暴力算异或和太蠢了,直接预处理个前缀异或和 $w_n$ 然后 $O(1)$ 用 $w_{l-1} \oplus w_{r}$ 算,岂不美哉。

时间复杂度 $O(n^2)$,期望得分 $40$ 分。

算法三

好像预处理完前缀异或和之后左端点都不用枚举了,直接枚举右端点然后查表看看有没有能用的左端点就好了。

时间复杂度 $O(n)$,期望得分 $60$ 分。

算法四

好像所有合法的区间左端点都很小。那么就在 $[n-100,n+100]$ 枚举右端点,然后在 $[1,100]$ 枚举左端点试试。

怎么算前缀异或和呢?不难发现 $2i \oplus (2i+1) = 1$,所以如果 $n$ 为奇数,那么 $w_n$ 就是 $\frac{n+1}{2} \mod 2$,如果 $n$ 为偶数,那么 $w_n$ 就是 $n + (\frac{n+1}{2} \mod 2)$。

时间复杂度 $O(1)$,期望得分 $100$ 分。

算法五

诶好像算法四直接 A 掉了。不难发现 $w_n \oplus n \in [0,1]$,而 $w_0=0,w_1=1$,所以只要取 $l \in [1,2]$ 来微调一下个位就可以啦。

因为要求区间的两端都是正数以及区间长度大于 $1$,所以对于 $n=0,1,2$ 要特判一下。

时间复杂度 $O(1)$,期望得分 $100$ 分。

新年的叶子

出题人 liu_runda

数据和题解 Scape

算法一

我们先来考虑一下有关直径的一些性质。

我们这里定义直径的长度是直径上边的条数。

显然一棵树可能会有多条直径,但是这些直径的中点显然应该是重合(对于直径长度是偶数)或者相邻(对于直径长度是奇数)。

否则的话我们可以从直径的一个端点出发,走到直径的中点,再走到另一条直径的中点后走到另直径的一个端点,这样可以得到一个更长的直径。

所以我们可以找到任意一条直径的中点,然后把所有叶子按照它位于这个中点的哪个儿子的子树中分成若干个集合,并且以该中点为根计算出每个叶子的深度。

令叶子的深度最大值是$Max$。

对于直径长度为偶数的情况,直径会变小 当且仅当 所有没有被染黑的且深度为$Max$的叶子 都在同一个集合里。

对于直径长度为奇数的情况,直径会变小 当且仅当 深度为$Max$的叶子都被染黑 或者 深度为$Max-1$的叶子都被染黑。那么我们把深度为$Max-1$的叶子全部放在同一个集合里,奇数的情况就变成了和偶数一样。我们可以一起解决。

接下来我们就要考虑这样一个问题,我们有若干个集合,每个集合里都有若干个叶子。我们每次会随机染黑一个叶子,问期望多久后只剩下一个集合里的叶子不是全黑。

令叶子总数是$m$。

我们可以先转化一下,把“每次随机染黑一个叶子(可能会重复染黑)”改成“每次随机染黑一个还没有被染黑的叶子”。这样转化后,假设还剩下$k$个叶子没有被染黑,那么要染黑一个还没有被染黑的叶子的代价就是$\frac{m}{k}$。

接下来我们只要暴力枚举删除叶子的顺序,就可以计算了。

时间复杂度$O(n!)$。期望得到$12$分。

算法二

我们考虑枚举哪个集合最终剩下了。

令$f[i][j]$表示当且集合还剩下$i$个,其他集合还剩下$j$个时期望的删除时间。直接按照定义转移就可以了。

时间复杂度$O(n^2)$。期望得到$30$分。

算法三

我们考虑枚举哪个集合最终剩下了,设当前集合大小为$k$。

设所有集合大小的和为$n$。

我们枚举当其他所有集合都染黑时,当前集合还剩下$i$个没有被染黑,那么这样的情况对答案的贡献为

$$\frac{\binom{k}{i}\times \binom{n-i-1}{n-k-1}\times \binom{n-k}{1}\times(k-i)!\times(n-k-1)!\times (i)!}{n!}\times (\sum_{j=i+1}^{n}\frac{m}{j})$$

线性预处理阶乘,阶乘逆元与逆元的前缀和就可以做到$O(n)$的时间复杂度。

算法四

from WuHongxun

什么,那么上面复杂的贡献你不知道怎么回事?不要急,这个题之所以在B题而不是C题,就是因为有算法四。

心里有数

考虑我们每次枚举一个集合$x$,然后不管它,计算剩下的集合被全部染黑所需要的期望时间,然后把这些时间加起来。

这个期望时间当然非常好算,如果一共有$n$个叶子,我们关心的有$m$个叶子,那么我们第一步需要期望$\frac{n}{m}$步染黑一个关心的叶子,显然答案就是$\sum_{i=1}^m \frac{n}{i}$,只要预处理$h_n = \sum_i \frac{1}{i}$就可以$O(1)$计算了。

算出来这个有什么用呢?

考虑任何一个方案里我们染黑到所有集合都变黑了为止,它对答案的贡献是多少呢?如果$x$是这个方案里最后被染黑的集合,那么是倒数第二个被染黑的时间,反之则是最后一个集合被染黑的时间,假设有$L$个集合,那么全部染黑被算了恰好$L - 1$次。

所以只要每次枚举一个集合,算剩下集合全部染黑的期望时间加到答案中,最后在答案里扣掉$L - 1$倍把所有集合全部染黑的期望时间,就可以啦!

是不是非常简单呢?

新年的五维几何

出题人 ftiasch

数据和题解 WrongAnswer

算法一

当 $n=1$ 时,满足约束的条件是 $x_1-x_1\ge a_{1,1}$ 即 $a_{1,1}\le 0$,因此当 $a_{1,1}\le 0$ 时输出 $1$,当 $a_{1,1} > 0$ 时输出 $0$。

可以通过子任务1,期望得分5分。

算法二

注意到如果有一个 $a_{i,i} > 0$,答案一定是 $0$,否则不用考虑 $a_{i,i}$ 的约束。以下算法均假设所有 $a_{i,i}\le 0$。

当 $n=2$ 且 $l_1=r_1$ 时,恒有 $x_1=l_1$,实际上只有 $x_2$ 一个变量。

若 $l_2=r_2$,仿照算法一判断四个约束是否同时满足即可,同时满足则输出 $1$,否则输出 $0$。

若 $l_2 < r_2$,则约束 $x_1-x_2\ge a_{1,2}$ 等价于 $x_2\le l_1-a_{1,2}$,约束 $x_2-x_1\ge a_{2,1}$ 等价于 $x_2\ge l_1+a_{2,1}$,求出两个约束和 $l_2\le x_2\le r_2$ 的交集长度,除以 $r_2-l_2$ 就是答案。

结合上述算法,可以通过子任务1,2,期望得分15分。

算法三

当 $n=2$ 时,如果 $l_2=r_2$,交换两个变量即可用算法二解决,故以下假设 $l_1 < r_1$ 且 $l_2 < r_2$。

用 $x,y$ 表示变量 $x_1,x_2$,则在平面直角坐标系 $xOy$ 中,变量的定义域是一个矩形 $l_1\le x\le r_1$,$l_2\le y\le r_2$,而约束的区域是该矩形和半平面 $x-y\ge a_{1,2}$ 及 $y-x\ge a_{2,1}$ 的交集。

考虑只有一个约束 $x-y\ge a_{1,2}$,则约束对应的区域为矩形位于直线 $y=x-a_{1,2}$ 下方的部分。当直线不穿过矩形时,答案为 $0$ 或 $1$,否则该区域可能是直角三角形、直角梯形或者矩形去掉一个直角三角形,根据点 $(l_1,r_1),(l_2,r_2)$ 在直线的上、下方分四类情况讨论计算区域面积即可,答案为该区域面积除以矩形面积 $(r_1-l_1)(r_2-l_2)$。

当有两个约束 $x-y\ge a_{1,2}$ 和 $y-x\ge a_{2,1}$ 时,将 $y-x\ge a_{2,1}$ 变形为 $x-y\le-a_{2,1}$,可得答案为约束 $x-y\ge a_{1,2}$ 的答案与约束 $x-y\ge-a_{2,1}$ 的答案之差(如果差为负数,答案为 $0$)。

结合上述算法,可以通过子任务1,2,3,4,期望得分50分。如果你只考虑了 $a_{1,2}$ 一个约束,则只能得到35分。

算法四

对于当 $j\ne i+1$ 时 $a_{i,j}=-10$ 的子任务,只需考虑相邻变量的约束。

设 $f_i(x)$ 为变量 $x_i,x_{i+1},\cdots,x_n$ 满足约束且 $x_i\le x$ 的概率,显然 $f_{n+1}(x)=1$。

当 $x < l_i$ 时,有 $f_i(x)=0$;当 $x > r_i$ 时,有 $f_i(x)=f_i(r_i)$。

否则,因为 $x_i-x_{i+1}\ge a_{i,i+1}$ 等价于 $x_{i+1}\le x_i-a_{i,i+1}$,所以当 $x_i=x$($x\in[l_i,r_i]$)时,$x_i,x_{i+1},\cdots,x_n$ 满足约束的概率为 $f_{i+1}(x-a_{i,i+1})$,于是,当 $l_i=r_i$ 时,有$$f_i(x)=f_{i+1}(l_i-a_{i,i+1})$$

当 $l_i < r_i$ 时,有$$f_i(x)={1\over r_i-l_i}\int_{l_i}^xf_{i+1}(y-a_{i,i+1})\mathrm{d}y$$

注意到 $f_i(x)$ 是一个段数 $O(n)$ 的分段多项式,维护每个分段多项式,用定积分进行转移即可。

结合上述算法,可以通过子任务1,2,3,4,7,期望得分70分。

算法五

注意到 $l_i,r_i,a_{i,j}$ 都是整数且 $l_i,r_i$ 范围很小,不妨枚举每个 $x_i$ 的整数部分。

当 $l_i=r_i$ 时,$x_i$ 是确定的,无需枚举;否则,记 $x_i=p_i+q_i$,其中 $p_i$ 在 $[l_i,r_i)$ 的整数中均匀随机,$q_i$ 在 $[0,1)$ 的实数中均匀随机,我们枚举每个 $p_i$,计算随机生成 $q_i$ 有多少的概率满足所有约束,每组 $p_i$ 下概率的平均值就是答案。

因为 $x_i-x_j\ge a_{i,j}$ 等价于 $q_i-q_j\ge a_{i,j}+p_j-p_i$:

  1. 当 $a_{i,j}+p_j-p_i\le -1$ 时,约束总能满足,不考虑该约束;
  2. 当 $a_{i,j}+p_j-p_i\ge 1$ 时,约束不可能满足,该情况的概率直接返回 $0$;
  3. 当 $a_{i,j}+p_j-p_i=0$ 时,约束等价于 $q_i\ge q_j$。

现在只要考虑若干个形如 $q_i\ge q_j$ 的约束同时被满足的条件。

注意到如果所有的 $q_i$ 均匀随机生成,那么有两个 $q_i$ 相等的概率为 $0$,$q_i$ 可能出现的 $n!$ 大小顺序是等概率的,每种的概率均为 ${1\over n!}$。因此对每个 $l_i < r_i$ 的变量建一个点 $i$,每个约束 $q_i\ge q_j$ 连一条边 $j\rightarrow i$,设该图的拓扑序有 $T$ 个,则满足所有约束的概率为 ${T\over n!}$。

直接枚举排列或者状压DP均可计算拓扑序个数。

时间复杂度 $O((r_i-l_i)^nn!\cdot n)$ 或 $O([2(r_i-l_i)]^nn)$,期望得分100分。

新年的代码

出题人 Glaceon08, worse

数据 worse

题解 WuHongxun

算法一

$n \leq 10$?

当然是$O(3^n)$状压爆搜啦!

算法二

我们大力猜结论!

evil

每个位置只会不连续的变化两段!

dp就只需要$f_{i,j,k}$表示前$i$位处理完了,第$i$位先变成$j$让我们来继续操作后面的位,然后操作完后面的位之后我们把第$i$位从$S_i$变成了$k$,我们再回来用前面的位把它变成$T_i$的最小步数。

交一发,100分。 bomb

其实是有道理的啦...

myy(matthew99)丢给了我一个他猜完结论后的这题代码,虽然我没看懂https://paste.ubuntu.com/p/6P7XZ6zT2W/

算法三

我们任意给$R,G,B$编号$0, 1, 2$,考虑我们每次操作,其实每次都是给相邻两位在模$3$意义下,一个$+1$,一个$-1$。(当然反过来不是每个$+1$,$-1$都能对应到我们的操作)

我们定义$sa_i = sa_{i - 1} + a_i, sb_i = sb_{i - 1} + b_i$,然后按照$sa_i = sb_i$的每个位置分段,那么每段在$mod 3$意义下相等。

首先长度为$n$的每个段,至少需要$n - 1$步操作才能完成,因为每个中间位置我们都需要把它左边和右边移成一样。

事实上我们可以构造出一个只需要$n$步的方案。考虑每次都至少复原一个字母,如果$S$开头两个是$GG$,那么无论$T$开头是$G$(第一个字母直接一样了),还是开头是$R,B$(一步操作之后可以复原第一个字母),显然都可以递归下去。

否则不妨假设$S$开头是$RG$,那么如果$T$第一个字母是$B$,那么一步操作即可。如果$T$的第一个字母是$R$可以直接递归下去。

于是剩下的唯一问题就是$T$的第一个字母是$G$的情况了,如果是$GR$,那么两步复原两个字母递归下去即可。

如果是$GG$,我们考虑处理剩下的位的时候把第二位变成$B$,然后前两位就是$RB$,最后一步变成$GG$

如果是$GB$,我们处理剩下的位的时候把第二位变成$R$,前两位就是$RR$,最后一步变成$GB$

这样我们就构造出了一段只需要$n$步的方案。

excite

我们还需要证明两端之间是独立的,在上一个结论的基础上,这也不难。我们考虑每次在两端之间操作一下,相当于合并了两端。

假如本来两端长度是$a, b$,需要的次数在$[a + b - 2, a + b]$之中,那么现在长度是$a + b$,至少需要$1 + a + b - 1 = a + b$次,不会变成更优。

合并多段的情况一样可以这么证明。

接下来只需要检查$n - 1$步是否合法了,因为这里每个位置都不会被操作超过两次,我们可以这么dp:

$f_{i,a,b}$表示dp完了前$i$个位置,在操作$i..n$位的过程中,需要第$i$个位置从$a$变成$b$的最小步数。

对于长度为$n$的段,如果这么dp之后存在一个答案为$n - 1$的解,那么就加上$n - 1$,否则加上$n$即可。

这样就可以有理有据的获得100分啦。

good

新年的投票

出题人 WuHongxun

数据和题解 WuHongxun

算法一

老师,我会爆搜!

先假设所有人不带标号,然后所有决策一共有$O(2^n)$种,爆搜每种情况,暴力取最好的情况,就会发现自己得了22分!

这是什么道理呢,如果所有人不带标号,那么我们可以这么构造:

如果多数掌握在$1$的人手里,所有人都应该投看到的奇偶性取反。

如果多数掌握在$0$的人手里,所有人都应该投看到的奇偶性。

唯一的问题是如果看到的$0$和$1$一样多怎么投,这时候可以按照多数是0投。

这样一来只有$\frac{n+1}{2}$的时候会导致错误,由斯特林公式易得总的正确率是$1 - O(\frac{1}{\sqrt{n}})$

这样就可以过任务一啦!

此时得分$22$分。

算法二

如果不带编号的爆搜少女已经gg了...

伤心地吃着咸鱼

那么我们就一定要利用上标号才行,任务二太难不会,任务三分数最低肯定最简单,我们先来看看任务三吧。

第$i$个人看看自己前面如果有人头上是$1$那么就投$0$票,否则就假设自己头上是$1$,然后投$2^i$票。

既然前面加起来只有$2^i - 1$票,显然只有最后一个投的人有效。

这样就有$1 - O(2^{-n})$的正确率了。

任务三就轻易解决了,果然是个送分提答呀

此时得分$40$分。

算法三

我们再回头看看任务二。

我们把它所有人分成$1, 2, 4, ... , 2^{k - 1}$的k组

从第一组开始,如果他之前没有$xor = 1$的组,就按照自己$xor = 1$来投。

如果前面有$xor = 1$的组,就一半投0一半投1,把自己抵消掉。

这样只有全部xor = 1的时候会gg,这样的概率是$2^{-logn} = O(\frac{1}{n})$

所以做到了$1 - O(\frac{1}{n})$的正确率。棒

此时得分$64$分。

算法四

现在就只剩下任务四了,看起来应该是需要一个对于任意的$k$都成立的做法。

每个人可以看到一个$(x_1, x_2, ..., x_k)$的向量,那么他投票方案可以写成一个$k$次多项式,他在$(1-y_1, 1-y_2, ... ,1-y_k)$的投票方案是$a_i$。那么这一项就是$(-1)^{\sum y_i}a_i(x_1 - y_1)(x_2 - y_2)...(x_k - y_k)$。

所有人的策略加起来也是一个k次多项式,最后的结果就是这个多项式带$x$进去之后值的符号。

反过来如果有一个k次多项式,那么我们把它的每一项分配给对应的人作为他们的投票策略,也是可行的策略。所以这两个问题完全等价。

我们如何找到一个这样的$k$次多项式呢?如果有$s$个1,由于$s$符合二项分布,我们可以试着把$[\frac{n - k}{2}, \frac{n + k}{2}]$这个区间做对。(方便起见假设$n$和$k$同奇偶)

设$sgn(x) = -1 / 0 / 1$表示$x$的符号,$sgn(x + 1/2 - s) = (-1)^{[s > x]}$,所以用总的多项式取$p(s) = (-1)^{\frac{n - k}{2}} \prod_{i=0}^{k-1} (\frac{n - k}{2} + i + \frac{1}{2} - s)$即可

显然把$\sum x_i$带入$s$之后是一个$k$次多项式。这个策略在$[\frac{n - k}{2}, \frac{n + k}{2}]$的区间内完全正确,在区间外也有一半的正确率。

此时得分$100$分。

Goodbye Dingyou

2018-02-13 20:53:01 By WuHongxun

再见,丁酉!

刚刚过去2017年,如同白驹过隙一般短暂,又像夏日烟火一般绚烂。在这一年里AlphaGo战胜了围棋,Trump宣誓就职美国总统,xumingkuan斩获IOI第二。

而在即将到来的一年里,狗群里的alpha male——AlphaGo的地位却面临挑战!原来狗群里的众多SingleDog不满狗群的公母比,要大战AlphaGo。这场大战究竟会如何,他们在呼唤你,一只忠诚的跳蚤朋友的帮助!

新的一年即将来临,在2月14号情人节之际,祝各位单身狗新年快乐,希望大家都能在OI中忘却一切现实的烦恼和忧虑,享受思考的乐趣,为SingleDog阵营夺取胜利的旗帜,rua!

这场大战将会在大年初三的下午 13:00 到 18:00 拉开序幕!

即2月18日下午 13:00 到 18:00 会举办Goodbye Dingyou比赛,比赛时间5个小时,一共五题,祝大家GL & HF!

赛制采取OI赛制,题目简单,会有萌萌哒送分提答,无论你是NOIp选手还是IOI大佬,都一定不要错过哦!

出题人:jiry_2, ftiasch, liu_runda, Glaceon08worse, WuHongxun

这场成绩将计入rating。

参加本次比赛将有机会获得 UOJ 抱枕!获奖条件的md5是9d9a36de3665fbaac830a6125102d838 。比赛结束后将公布条件。

UPD:比赛结束

恭喜比赛的前五名:

1.FizzyDavid

2.fateice

3.lastans7

4.whzzt

5.JOHNKRAM

抱枕条件是

echo -n "最后提交的有效代码中d、o、g个数除以代码中的26个字母的个数,对每个得分>0的题求和之后最大的,如果有多个取排名最高的。" | md5
9d9a36de3665fbaac830a6125102d838

恭喜tqyaaaaang

抱枕的统计代码见 https://gist.github.com/fjzzq2002/a59ed353befbd1063a9f6ab1fae774a2

WuHongxun Avatar