UOJ Logo WuHongxun的博客

博客

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抱枕!

杜教的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

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

共 15 篇博客