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

UOJ Test Round #3 题解

2017-11-19 22:25:53 By WuHongxun

其实写题面的时候埋了不少彩蛋啊?大家可以试一试能找出几个?

几何冲刺

出题人 ftiasch

数据和题解 WrongAnswer

验题人 matthew99

算法一

对于每对红点 $P_i,P_j$,暴力枚举蓝点 $Q_k$ 判断其是否在三角形 $OP_iP_j$ 内。

如何判断 $Q_k$ 是否在三角形 $OP_iP_j$ 内?只需判断三角形 $OP_iQ_k$、三角形 $OP_jQ_k$、三角形 $P_iP_jQ_k$ 的面积之和是否等于三角形 $OP_iP_j$ 的面积即可。以 $(x_1,y_1),(x_2,y_2),(x_3,y_3)$ 为顶点的三角形面积为 $${1\over 2}|x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)|$$ 这样就能每次 $O(1)$ 完成判断了。时间复杂度 $O(n^2m)$,期望得分 32 分。

算法二

考虑将问题进行转化。

注意到点 $Q_k$ 在三角形 $OP_iP_j$ 内的条件是点 $P_j,Q_k$ 在直线 $OP_i$ 同侧,且 $\angle Q_kOP_i < \angle P_jOP_i$ 且 $\angle Q_kP_iO < \angle P_jP_iO$。于是可以枚举 $P_i$,枚举直线 $OP_i$ 的一侧,然后把每个红点和蓝点 $X$ 当成一个二元组 $(a,b)$,其中 $a=\angle XOP_i$,$b=\angle XP_iO$。然后枚举点 $P_j$,就只需找出 $a,b$ 两维均比 $P_j$ 小的蓝点了。

按其中一维排序,用数据结构(如树状数组或set)维护另一维即可。具体实现方式是按其中一维从小到大顺序扫描每个点,如果是蓝点则插入数据结构,如果是红点则在数据结构中查询另一维比该点小的蓝点。时间复杂度 $O(n(n+m)\log m)$,期望得分 78 分。

算法三

算法二还可以进一步优化。

我们可以一开始以原点 $O$ 为中心,将所有点(包括红点和蓝点)进行极角排序。

之后枚举点 $P_i$ 时,每个点的 $a$ 这一维已经有序。由于对非空三角形只要找出任意一个内部的蓝点,因此在按 $a$ 从小到大枚举 $P_j$ 时不需要要数据结构维护蓝点,只需用一个变量维护扫描到的蓝点中 $b$ 最小的点即可。

这样时间复杂度为 $O(n^2+nm)$,期望得分 100 分。

去月球

出题人 WuHongxun

数据和题解 Scape

验题人 worse

算法 1

首先我们先来证明一个结论 即最终答案和消除顺序无关。

如果在某个时刻删掉了$..xx..$会使答案变差,那么说明更优解应该是其中的某个$x$和一个另外的$x$配对了,不失一般性地,我们设是左边这个$x$。

那么在删左边这个$x$之前,序列的样子应该是$..xxx..$,这时候我们注意到删左边这对$xx$和删右边这对$xx$之后结果的是一样的,所以答案并不会变大。

对于这个结论也有一个wiki

那对于每个询问,我们都拿一个栈暴力跑一遍就可以知道答案了

时间复杂度$O(nq)$,期望得分$20$分

算法 2

我们考虑Subtask 2

我们显然只要考虑出现了两次的括号

对于某个出现了两次的权值$i$,设第一次出现在$l_i$,第二次出现在$r_i$

那么对于某个询问$L,R$,这对括号被消除当且仅当$\left [l_i+1,r_i-1\right ]$是可消除的并且$l_i\geq L$,$r_i\leq R$

判断是否可消除可以直接建一棵树来判断。

而第二个约束是显然可以通过二维数点来实现的。于是这个Subtask就被解决了。

算法 3

Subtask 3是给离线做法的,我们先来考虑离线。

我们进行分治,对于当前分治区间$\left [L,R\right ]$,我们只处理过中点的询问。

我们设中点是$mid$,那么对于$\left [L,mid\right ]$的每个后缀区间和$\left [mid+1,R\right ]的每个前缀区间$,我们都用一个栈维护出他们消除后的答案。

考虑把两个区间合并,新发生的消除显然只会是前面区间的某个后缀和后面区间的某个长度相同的前缀翻转过来完全相同。我们接下来就是要求一个lcp。

考虑怎么求lcp,$\left [mid+1,R\right ]$的长度为$i+1$的前缀消除后的结果要么是长度为$i$的前缀删掉最后一个字符或者是在最后面加上一个新的字符。那么我们用trie来保存这个结果。求lcp就是求两个对应节点的LCA。

而在线就显然只需要把每个区间的trie和结果都存下来,对于每个询问都去对应的分治区间查询。

那么我们如果用倍增/树剖去求LCA,我们可以做到$O(n\log ^2n+q\log n)$,基本上可以得到$100$分。

如果我们用RMQ去求LCA,我们可以做到$O(n\log ^2n+q)$

如果更丧病一点用$O(n)-O(1)$LCA,我们可以做到$O(n\log n+q)$

标算用的是RMQ求LCA。

但是还有一个小细节是如果我们想要做到每个询问回答是$O(1)$,我们还要做到快速定位到询问区间

我们有两个做法,第一个做法是分治实际上就是一棵线段树,那么某个询问对应的分治区间实际上就是他们的$LCA$,我们用$O(1)$回答的LCA就可以做到。

或者我们也可以用一个更简单的方法,我们把分治这棵线段树开到$2^{17}-1$,这样对于询问$L,R$,他们会在$L\ xor\ R$的highbit上分开。

这题$80$分的Subtask大概是给一些分块做法和询问需要$log^2$的做法的(比如二分hash)。

算法4

from matthew99

考虑我们像算法二那样建一棵操作树,保证对于这棵树的每个子树都是可以完美消除的。

我们直接类似算法三分治后建trie的做法,我们从左往右扫,如果当前字符和栈顶匹配就回到父亲,不然就把当前字符压到栈内并且走到对应的儿子。

对于这棵树,我们从任意一个节点出发,经历一个可完美消除的序列后,它都一定会回到这个节点本身。

所以对于某个询问$\left [L,R\right ]$,答案就是$R-L+1$再减去他们在这棵树上的距离。

正常的写法是$O((n+q)\log n)$

如果用hash_map和$O(n)-O(1)$LCA的话,可以做到$O(n+q)$

具体实现细节可以参考这个submission

量子破碎

出题人 WuHongxun

数据和题解 WuHongxun

验题人 fateice

算法0

我们用操作4,暴力$O(2^n)$的问出来每个$a[i]$就好啦。

算法1

我们考虑怎么优化这个暴力。

我们可以注意到我们大部分的时间都在查空的$a[i]$,如果我们只关注一位,不妨把别的位都变成0,然后查一查这一位上xor是0还是1。

注意$AA^t = I$意味着,$A^t = A^{-1}$,从而$A$一定是可逆的。

而把所有别的位都改成0不是一个可逆的操作,所以肯定是无法用2实现的。

我们只好用操作3来做到把除了第$i$位之外每一位强制为0,作用上矩阵$\begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix}\\$

然后用操作4查一下$a[0]$和$a[2^i]$即可。

因为要对每个$i$做一次,复杂度$O(n^2)$。

算法2

我们考虑如何丢掉算法1里的最后一步用操作4查$a[0]$和$a[2^i]$?

如果直接随机,那么无论xor是0还是1,都会随机返回0或1(每次x会重新随机)。

为了区分出来我们做变换$a[0] := a[0] + a[2 ^ i]$,$a[2^i] := a[0] - a[2 ^ i]$, 也就是应用矩阵$\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\\$

这样如果xor是0,那么一定会返回0,否则会随机返回0或1。

随机多次判断即可,复杂度$O(n^2)$有较大的常数。

算法3

fateice 在验题时提出一个hack。注意题面里有提到交互库的实现,会在概率平方和为0的时候返回0。

如果平方和不为0,返回0的概率很小。

那么只要每次把一位做变换$a[0] := a[0], a[1] := a[0]$,如果返回了0,那么说明xor为0,否则说明xor为1。

$\begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix}\\$

复杂度$O(n)$但同样是概率算法。

算法4

我们考虑对每一位$i$都做算法2中的变换$a[0] := a[0] + a[2 ^ i]$,$a[1] := a[1] - a[2 ^ i]$,这样$a[0]$就会变成所有$a$的和。

如果我们在变换前枚举第$i$位,把它的$a[0] := a[0], a[1] := -a[1]$,也就是作用矩阵$\begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}\\$。

那么变换后如果这位xor为0,那么$a[0]$会变为$0$,否则一定不是$0$。

最后一步用操作4查一下$a[0]$就好啦。

询问复杂度$O(n^2)$

算法5

@fateice 在算法1上稍微修改一下,丢掉操作3的玄学做法。

我们可以对旋转矩阵,$\begin{pmatrix} cos(x) & sin(x) \\ -sin(x) & cos(x) \end{pmatrix}\\$随机取几个$x$。

然后对除了第$i$位之外的每一位做这个变换,然后随意找一个位置$x$用操作4查出$a[x], a[x ^ (1 << i)]$。如果同时有值就说明了xor为1。

算法6

我们思考一下算法4,不难发现这其实是一个fwt!算法2中我们用它得到了一些non-trivial的信息,算法4中我们用$a[0]$的信息得到了一个部分分做法,$a[t]$的信息丢掉非常可惜,我们不妨思考一下它能告诉我们什么?

考虑fwt中$x$对$y$的贡献,显然绝对值肯定是$1$,由于fwt的矩阵只有 $A[1][1] = -1$。所以贡献的权值等于 $(-1)^{x \& y}$。

fwt之后位置$t$的值等于 $(-1)^{x \& t} + (-1)^{ y \& t }$。

为 $0$ 当且仅当 $x \& t = y \& t$,根据$F_2$下的乘法分配律也就是 $(x \oplus y) \& t = 0$。

所以我们 $a[t] \not= 0$ 当且仅当$t$和答案的and有偶数个1!

我们是不是随机线性无关的 $n$ 个 $t$ 就可以解出答案了呢?

很可惜,这些$t$并不是满秩的!比如说当答案是二进制$11$的时候,$t$只能是$00$和$11$,$00$没有用,也就是说最大秩为$n - 1$。

因为每一维选不选定为$c_i$的话,我们其实有一个限制若干个$c_i$(ans为1的那些$c_i$)异或起来为0,所以秩只有$n - 1$。

不过这只是偶数的情况,如果我们把它变成and有奇数个1,那么我们可以用$10$和$01$构成一组满的基!

考虑怎么变成奇数个1,只要在一个xor为1的位,应用算法4中的变换 $\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\\$ 即可。

我们每次枚举一位,然后应用变换 $\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\\$ 之后,用fwt随机$O(n)$个t,然后高斯消元判断一下秩是$n$还是$n - 1$即可知道这一维是不是1。(考虑答案中只有一位是1的情况,就算在满秩情况接出了所有位,最差情况总是要枚举每一位)

询问复杂度$O(n^3)$。

算法7

我们用另外一个方向理解一下为什么秩只能有$n - 1$,因为所有$x \oplus y = 0$始终都会是xor方程的解。

xor方程组始终都有两个解$x \oplus y$和$0$,所以秩为$n - 1$。

但是我们知道答案不可能是$0$,所以把它丢掉取$x \oplus y$输出即可。

期望要随机$O(n)$个随机向量会满秩,实际上更接近$n + 1$。

询问复杂度$O(n^2)$,期望得分100分。

算法8

matthew99在验题的时候,猜想是fwt,于是,fwt之后暴力枚举$2^n$直到方程只有一个解。

询问复杂度$O(n^2)$,算法复杂度$O(n 2^n)$。期望得分100分。

由于交互库很慢,所以只能让这种做法通过了。不过思考到fwt,可以说已经解决了这道题的一半了。

题目背景

其实这道题目相当于给出$n$个纠缠的量子比特,你每次可以旋转翻转(正交变换)其中一个量子或者是做一次观测(然后会坍缩到一个态)。

如果把题目中$2 \times 2$的矩阵换成一个$2^3 \times 2^3$的矩阵作用在三位上,并且允许振幅是复数,就是量子计算的理论模型了。

这个算法其实正是量子计算机上寻找循环节的Simon算法,正是这个算法启发了著名的Shor算法。

FWT和高斯消元从入门到精通

UOJ Test Round #3

2017-11-17 16:38:03 By WuHongxun

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

NOIp刚刚结束,不知道大家都觉得题目如何呢?不如来做做UTR换换口味吧!

Q & A

Q: 为什么是Test Round呢?

A: 因为我们要测试新的三个AI管理员有没有bug!(雾)其实一方面是因为UR和UER的题目珠玉在前,大家每每讨论如何出题总是受到之前的UR和UER影响,干脆办成自由一些的UTR。另一方面是这场比赛的题目会全部选择交互题的形式。

Q: uoj怎么好久没有比赛了?

A: uoj没有凉凉!欢迎大家给uoj投题,帮uoj +1题!

比赛信息

本场比赛将以大家喜闻乐见的Steam游戏为主题。

出题人 : ftiaschWrongAnswerScape, WuHongxun

感谢验题人:fateicematthew99worse

本场成绩将计入Rating。

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

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

恭喜前5的同学:

  1. laofu

2.YMDragon

3.fjzzq2002

4.whzzt

5.hzt1

抱枕条件是

echo -n 比赛中倒数第二个CE的提交 | md5
a7141f001a0eb13ebeab553e37168c5e

恭喜zx2003 获得uoj抱枕!

whx的新博客

2017-11-16 15:46:46 By WuHongxun

杜教的Dzy loves Chinese证明

2017-10-09 11:40:11 By WuHongxun

因为杜教当年的blog已经不复存在了,所以向杜教重新请教了一边这个证明,把正确的证法在uoj重放一边,方便有兴趣的同学。

要证明的做法就是先随便选一个生成树,然后给每条非树边在2^64范围内随机一个权值(等于是映射到(F_2)^64),然后每条树边的权值等于跨越他的非树边权值的xor,对于每次询问,不连通 iff 删掉的边权的集合线性相关。

这篇blog主要证明给每个非树边分配一位的情况下,有不连通 iff 删掉的边权的集合线性相关。

考虑每次树边等于非树边的xor,其实就是每次一个环上xor了一个值,等于每个点相连的所有边的xor = 0。

每个点的xor =0 iff 树边等于非树边 xor(考虑一个个加入非树边)

考虑一个割,等于若干点的xor起来,所以一个割一定xor = 0。

证完一个方向,另外一个方向如下。

同时xor = 0的时候如果没有割,直接取一个生成树,然后新取的生成树里xor还是为0,所以新的非树边是一组base并且和原来的base大小相同。

所以新的非树边线性无关和存在xor = 0矛盾,证完。

WuHongxun生日快乐

2017-09-11 18:54:20 By WuHongxun

虽然今天不是我的生日,但是我今天也不快乐呀,

共 10 篇博客