UOJ Logo jiry_2的博客

博客

标签
暂无

暂别

2016-07-27 21:55:56 By jiry_2

众所周知智障少女九条可怜一夜之间就要变成大学生了。

虽然名字写的和 vfk 一样但是感觉自己并写不出来那样的文章,那就只好试试老干部流啦。

我大概是在两年前的这个时候第一次听到 uoj 的,应该算是第二批用户吧,那个时候 uoj 群里也只有不到 100 人,大家每天热衷于交个 A+B 然后自己 hack 自己;后来因为评测机压力太大,vfk 把这项娱乐活动给禁止了,大家就开始水群;再后来因为 uoj 群太水了,vfk 就搞了个叫三连击的东西出来,大家就开始专注举报三连击。

然后最开始的时候,uoj 首页除了 rating 排名,还有一个叫做通过题数排名的东西,然而没过两天,就有一大堆小号贴着别人的代码愉快到了榜首,然后这个功能就被 ban 了。

那个时候自己刚刚被 NOI 类别杀,心灰意冷,每天除了睡觉吃饭就想着出偏题报复社会。憋了一个暑假出出来三套垃圾题,DZY Loves Graph就是其中一道(其中还有一道放出来的题目是 DZY Loves Math VIII),当时出的时候标算是可持久化并查集什么的。后来听说 UOJ 要出 UER,然后自己就投了这道题,vfk 一眼艹了标算然后就把这题收了[捂脸]。而且后来好像还把标程写错了,如果没记错的话这题应该是 UOJ 上第一个被 Hack 的标程,在这之后这种事情好像就渐渐的多了起来2333。

我第一次给 UOJ 出题的幕后故事差不多就是这样的,那个时候自己出题的口味也是非常不正常,之前还出了一大堆奇形怪状的高斯消元题。后来跟着集训队爸爸们做了一百多道 CF 题之后渐渐知道了怎么出题,也渐渐的有了正常的评价题目好坏的观念,之后的两年也算是断断续续的给 UOJ 出了挺多题吧:

DZY Loves Graph怎样更有力气智商锁懒癌信息的交换决战圆锥曲线开学前的涂鸦量子态的棋盘元旦老人与汉诺塔元旦老人与数列最强跳蚤思考熊票数统计合唱队形奇怪的线段树

列出来发现居然有 15 道题,惊了,好多呀..然而翻了一下好像并没有人同时 A 了这些题 QAQ。

在这么多题里面我自己最喜欢的就是 懒癌 啦,简直就是出题生涯的巅峰。之后就是 元旦老人与数列思考熊 了,虽然后面那题出了出题事故有点小遗憾,但就出这些题的 idea 来说,感觉还是挺自豪的。最后就是 奇怪的线段树 啦,这道题应该是我出了这么久题第一道网络流题,感觉意外的不错 2333 考场上被稳爷爷直接碾过去吓得我瓜子都掉了。

有点小遗憾的就是 开学前的涂鸦思考熊 这两题了,它们都或多或少出了点出题事故。仔细一看好像到现在都还没有真正的勇士写前面这题的标算 QAQ 有没有老司机愿意来写一波大 DP 呀,要不第一个用标算 A 这题的人来找我我请他吃一顿饭吧 2333

再来讲讲自己出比赛的经历吧。泥萌问我 UOJ 管理员辛不辛苦,当然是辛苦的啊。感觉当了这么久管理员,学会的一个道理就是:没有什么 ddl 是通一次宵解决不了的!

在当管理员之前就为了调 开学前的涂鸦 熬到凌晨,这瘠薄题真的是怎么调都有错,当时真是意识模糊。后来造万圣节那场 UER 也是,数据各种有错,各种弱,万圣节的南瓜灯 的数据我造到了凌晨三点,最后好像还是太弱了,嗨呀这是最气的。然后就是 UNR 了,因为比赛时间正好和毕业旅行冲突,出发前一天晚上索性通了一波宵看了一波日出,把坑填了大半,后来实在来不及就随手丢到乐滋滋脸上拔腿跑啦。

还有一场不得不说的就是 UR#10 啦,在出这场之前我和乐滋滋突击学习了半个多月的抽代(为了看懂七爷的题解),然后在去清华集训的火车上我强忍着翔意写完了 Pascal 的交互库(咦好像大部分的时间是在看琅琊榜哎),直到比赛开始前10分钟才把所有东西做好。后来到了比赛结束前10分钟突然发现标程错了,还好数据造的机智大样例什么的都没什么问题,之后匆匆忙忙又是改标程又是改数据,等到题解发出来的时候已经十二点多了,意识模糊。

感觉造 UR 的故事实在太多了,一打开话题根本写不完啊..篇幅问题这儿就不写了,以后群里有讲故事活动的时候再说吧2333。

虽然造 UR 挺辛苦的,不过在看到大家愉快做(爆)题(零)的时候,感觉还是非常开心的!特别是在最后大家愉快讨(骂)论(我)题(毒)目(瘤)的时候,感觉一切付出都是值得的!

智慧的凝视

后来等到我 CTSC 身败名裂退役之后,因为自己沉迷守望先锋,所以投入在 UOJ 上的时间也少了很多,当时我和 vfk 的日常差不多就是:

vfk:jryjry 快来造 UR!jryjry 快去找题!

jry:好!我这就去问问!

啊守望先锋真 tm 好玩。

学习

所以实在是对不起大家了 QAQ 这段时间 UOJ 的比赛连续跳票的锅的确应该是我背。我印象当中有好几位想给 UOJ 投题的人,特别是有一道出题答题的小哥,真的是特别热心,题目改了一版又一版,但是那个时候自己处理的可能也是比较敷衍,草草了事,渐渐的就没了下文,实在是对不起了[鞠躬]。如果你们看到了这篇文章,如果还愿意的话,可以把题目发给下一代管理员们!我相信他们会认真处理的!(三句话不离甩锅)

说了这么多,也该说到正题啦!智障少女九条可怜已经成为了退役老人,也该淡出 UOJ 的出题圈了,之后也应该让现役选手们出一些有趣的题给大家了。当然如果有好的 idea 我自然也是会出题的,毕竟还是不想这么轻易的就让出出题数最多的 UR 出题人这个位置 2333。

接着就是大家期待已久的念 UOJ 下一代管理员名单的环节了!感谢这些勇士们义无反顾的接下了 UOJ 管理员的 debuff!他们是(之后可能会有补充):

matthew99, C_SUNSHINE, SkyDec, NanoApe, cy

最后就用 vfk 去年的话结尾吧。虽说博客题目是暂别,但是也不是暂别吧,因为UOJ 的团队一直在这里。我们会忙活 UOJ 的事,只是花的时间比以前少多了。

我很喜欢 UOJ,即使从 OI 退役了也如此,高三折腾 UOJ 的日子是最难忘的回忆,愿 UOJ 有更加美好的未来。

(话说是不是现在可以以“出比 noi 更像 noi 的比赛”为目标啦2333)

UOJ NOI Round #1

2016-07-13 19:03:19 By jiry_2

UOJ NOI Round #1 将于 7 月 16 日至 7 月 18 日举行。这是 UOJ 第一场 UOJ NOI Round。

Q:教练我只听说过 UER,UR 和打酱油的 UTR,这 UNR 又是什么呀。

A:因为马上就要 NOI 啦,既然大家都觉得 UER 太难了做 NOI 模拟一点都不清真,那么我们就彻底地来一次 NOI 全真模拟吧!

比赛时间

笔试模拟将于 7 月 16 日晚 19 点开始,将进行半个小时。

Day 1 的比赛将于 7 月 17 日上午 8 点半开始,将进行五个小时,共三道题。

Day 2 的比赛将于 7 月 18 日上午 8 点半开始,将进行五个小时,共三道题。

出题阵容

这次比赛的大部分题目来自于 IOI2016 国家候选队的队员,出题人有:

jiry_2xllend3, SkyDecmatthew99qmqmqmYJMWOI

这场比赛除笔试外将计入rating

比赛难度

比赛的难度将与 NOI2013 相近,相信对绝大部分选手来说题目是具有一定的挑战性的。

同时我们尽力确保了较多的部分分、较好的区分度以及考察内容的全面性,题目中还有着一道提交答案题,大家可以放心食用。

比赛奖励

这次比赛将会根据三次比赛的总分进行排序(如果存在同分将以两天的罚时总和作为第二关键字),其中比赛的前五名将成为这次训练的金牌得主,第六名到第十五名将获得银牌,第十六名到第三十名将获得铜牌。(得奖人数将根据参赛人数进行调整)

总分前三名将获得 UOJ 萌萌哒的撕烤熊抱枕一只。

UPD:比赛已经结束。

颁奖环节

经过管理员们的讨论,决定发放15枚金牌,25枚银牌,50枚铜牌,同时总分前三名将获得 UOJ 萌萌哒的撕烤熊抱枕一只。

恭喜获得抱枕的选手:

  1. WuHongxun
  2. xumingkuan
  3. WrongAnswer

获奖名单见排行榜

UOJ Easy Round #6 题解

2016-07-01 16:26:54 By jiry_2

票数统计

By jiry_2

这题数据是瞎随的,所以好像出现了一些奥妙重重的得分分布QAQ

算法一

爆枚所有可能的情况,检验每一个限制是否合法。

时间复杂度 $O(T2^nm)$,期望得分 $30$ 分。

算法二

不难发现当 $x > y$ 时后 $y_i$ 位用户中,恰好有 $x_i$ 位投了通过肯定是不成立的,当 $x < y$ 时后 $x_i$ 位用户中,恰好有 $y_i$ 位投了通过也肯定不成立。

所以只有当 $x \neq y$ 时限制是唯一确定的。

因此如果有解,本质不同的限制最多只有 $O(n)$ 个,可以先把不同的限制去重掉,然后再爆枚所有情况判断。

时间复杂度 $O(T2^nn)$,期望得分 $50$ 分。

算法三

对于第六个点,所有限制都是针对前缀的。

不难发现这时限制把整个序列分成了 $O(m)$ 段并对每一段限制了 $1$ 的个数,因此每一段的方案数都是组合数,直接把它们都乘起来就好了。

时间复杂度 $O(Tn+n^2)$,结合算法二期望得分 $60$ 分。

算法四

先考虑 $x \neq y$ 的情况,这时考虑把对后缀的限制转化成对前缀的限制。

枚举所有人中投通过的人数,这样后缀的限制就变成了前缀的限制,直接用算法三求解就好了。

存在 $x=y$ 时,不难发现所有 $x=y$ 的限制中只需要考虑 $x$ 最大限制就行了,因为这个限制满足了剩下的 $x=y$ 的限制一定也满足了。

枚举限制 $x=y$ 被哪一边满足,答案就是前缀满足的方案数加上后缀满足的方案数减去两端都满足的方案数,这样就把 $x=y$ 转化成了只对前缀或者只对后缀的限制。

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

寻找罪犯

By sevenkplus,题解By C_SUNSHINE

算法一

暴力枚举每个人是否是罪犯,然后扫描所有证言判断是否为真,并判断是否满足条件,时间复杂度$O(2^m m)$。

算法二

对于每个人,建立一个$01$变量表示他是否是罪犯,对每一条证言,建立一个$01$变量表示它是否为真,那么就可以把要求转化为一些条件。

对于一条供词$i$,建立条件:“若此供词为真,则某个人是/不是罪犯”。

接着对于每个人,建立条件:“若此人不是罪犯,则其说的每一条证言都为真”。

由于一个人最多说一句假的供词,则对于同一个人说的任意两条供词,建立条件:“若供词A为假,则供词B为真”。

条件都可以写成“若$x_i=a$则$x_j=b$”的形式,这是一个2-SAT问题,可以使用经典的强连通分量算法求解。

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

算法三

对于完全图的情况,可以先特判所有人都是罪犯的情况,否则必有一个人不是罪犯,枚举任意一个人不是罪犯,则通过他的供词可以得知其他所有人是否为罪犯。

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

算法四

考虑推广算法二,对一个有$k$条供词的人,建立$3k$个$01$变量,分别表示第$i$条供词是否为真,前$i$条供词是否都为真,后$k-i+1$条证词是否都为真。

那么若前$i$条供词为真,则前$i-1$条供词也为真,且第$i$条证词也为真,对于后缀也是一样,这部分边数是$O(m)$的。

那么可以建立条件的时候就可以使用前缀后缀来优化,若一个人为真,只要长度为$k$的前缀都为真即可。

对于一个人最多说一条假的供词这个限制,若一个人的第$i$条供词为假,则前$i-1$条和后$n-i$条证词都为真,这部分的条件数就变成$O(m)$的了。

于是变量数和条件数都是$O(n+m)$的,总复杂度就是$O(n+m)$。

逃跑

By SkyDec

算法一

考虑化简方差,设d为每次经过的点的个数。

$$E=\sum (d-avg)^{2}=\sum d^2-2*d*avg+avg^2=(\sum d^2)-avg*2*(\sum d)+avg^2*all$$

根据平均数的定义,有

$$avg=\frac{\sum d}{all}$$

所以有

$$E*all=(\sum d^2)*all-(\sum d)^2$$

$all$可以很简单地计算,于是问题就变成了:求$\sum d^2$和$\sum d$,即经过的点的个数的平方之和,经过的点的个数之和。

我们可以$O(4^n)$枚举每次往哪个方向走,统计一下经过了几个点,就可以直接计算了。

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

算法二

考虑部分分$w_3=w_4=0$

即不可能往左右走,也就是说行走的区域只有一维了。

一维区域经过的点显然是一个区间,经过的点就是这个区间里整点的个数。

令$f[i][j][k][x]$表示走了$i$步,当前经过的区间为$[j,k]$,当前的位置是$x$的方案数,直接模拟下一步往哪儿走转移即可。

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

算法三

考虑如何快速地计算$\sum d$。

考虑计算$\sum (n+1-d)$,也就是经过一个点时上次早已经过这个点的点的个数。

显然$\sum d=(n+1)*all-\sum(n+1-d)$。

考虑一段长度为$n$的序列$L$,每个元素是$(0,1),(0,-1),(1,0),(-1,0)$中的一种。

那么如果对于坐标$(x,y)$,设序列$c_1..c_k$为满足$(\sum_{i=1}^{t}L[i])=(x,y)$的所有$t$按顺序排列的序列

那么对应的,对于$1\leq i\leq k-1$,有($\sum_{j=c_i+1}^{c_{i+1}}L[j])=(0,0)$

可以发现,一个出现了$k$次的点产生了$k-1$段没有前缀$(0,0)$的和为$(0,0)$的序列。

而显然出现了$k$次的点对我们要求的答案的贡献是$k-1$。

所以根据期望的线性性,我们只要计算有多少段连续子序列满足和为$(0,0)$且没有前缀$(0,0)$即可。

设$f[i]$表示长度为$i$的答案。

设$g[i]$表示长度为$i$的和为$(0,0)$的序列有几种。显然$i$是奇数时,$g[i]=0$。

$$g[i]=\sum_{j=0}^{i/2}\frac{i!}{j!j!\frac{i-j*2}{2}!\frac{i-j*2}{2}!}*w_1^jw_2^jw_3^{\frac{i-j*2}{2}}w_4^{\frac{i-j*2}{2}}$$

相当于枚举每种向量的个数,排列组合了一下。

然后$f$的计算就很显然了。

$$f[i]=g[i]-\sum_{j=0}^{i-1}f[j]*g[i-j]$$

统计答案时只要算$\sum_{i=1}^{n}f[i]*all^{n-i}$就行了

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

算法四

在上个算法里,我们通过比较直观的转换将题目转化成了求无前缀$(0,0)$的和为$(0,0)$的段数。

然而当我们求$\sum d^2$时,就无法直接用期望的线性性计算了。

设$p=(n+1-d)$,即上个算法里的重复计算次数。有:

$$\sum d^2=\sum (n+1-p)^2=all*(n+1)^2-2*(n+1)*\sum p+\sum p^2$$

$\sum p$我们已经可以轻易地计算了,现在就考虑计算$\sum p^2$了。

设布尔数组a[l][r]表示$[l,r]$是否满足条件。

那一个数列的贡献就是$(\sum_{l\leq r}a[l][r])^2$

即$$\sum_{l\leq r}\sum_{x \leq y}a[l][r]*a[x][y]$$

然后现在就有期望的线性性了,我们只要对于每对$(l,r)$,$(x,y)$计算他们同时满足条件的方案数即可。

当区间不相交时,他们互相几乎不影响,直接计算即可。

当只有一段时我们可以简单地记录坐标$dp$,并保证中途不经过为$(0,0)$的点即可。

那么当有两个区间时,我们可以先$DP$第一个区间,然后中途加入一个区间,当一个区间和变为$(0,0)$时就意味着他终止了。

当区间相交时,考虑$f[i][x1][y1][x2][y2][2]$表示当前长度为$i$,第一段的和为$(x1,y1)$,第二段的和为$(x2,y2)$。当前有几个区间。每次转移考虑下一步走哪个方向,要不要加入区间即可。

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

算法五

考虑第七个点,他的$w_1=w_2=w_3=w_4$,显然$w$之间是一种比例关系,全部相等就等价于全为$1$,我们用上个算法的程序打个表即可。

期望得分10分

算法六

区间的相交分为两种情况:包含和不包含。

我们先考虑不包含的情况,这样肯定分成了三段:只属于第一段的,重合的,只属于第二段的,我们设他们分别为$A$,$B$,$C$。

考虑$A$,我们枚举$A$的和,设为$(Ax,Ay)$,那么我们可以轻易地推导出:B的和为$(-Ax,-Ay)$,C的和为$(Ax,Ay)$。

考虑$A$需要满足什么条件,由于只属于第一段,所以只需要满足没有前缀$(0,0)$即可。

设$g[i][x][y]$表示和为(x,y),长度为$i$,没有前缀$(0,0)$的方案数,这个可以用简单的$O(n^3)$dp得到。

考虑$C$需要满足什么条件,由于只属于第二段,所以只需要满足没有前缀$(Ax,Ay)$即可,即没有后缀$(0,0)$。

没后缀$(0,0)$跟没前缀$(0,0)$显然是等价的问题。

考虑$B$需要满足的条件,这个就比较复杂了,毕竟是重合的部分,他要满足第一段,所以他需要没有前缀$(-Ax,-Ay)$,即没有后缀$(0,0)$

他也需要满足第二段,即没有前缀$(0,0)$。

设$o[i][x][y]$表示和为$(x,y)$,长度为$i$,没有前缀$(0,0)$和后缀$(0,0)$的方案。

考虑容斥计算$o$。我们可以用$g[i][x][y]$作为总方案,那么考虑枚举最短的长度为$j$的后缀和为$(0,0)$。

那么前$(i-j)$的和就是$(x,y)$,他们只需要满足没有前缀$(0,0)$,也就是$g[i-j][x][y]$。

考虑长度为$j$的部分,他们的和为$(0,0)$,由于要求最短,所以他们也不能有后缀$(0,0)$,并且由于整段里不能有前缀$(0,0)$,所以他也不能有哪个前缀和前面的$(i-j)$构成$(0,0)$,即没有前缀$(-x,-y)$。

于是设$v[i][x][y]$表示长度为$i$,和为$(0,0)$,不能有前缀$(0,0)$和前缀$(x,y)$的方案数。

考虑容斥,设$f[i][x][y]$表示长为$i$,和为$(x,y)$的段数,那么可以以$f[i][0][0]$作为$v[i][x][y]$的初值。

考虑枚举第一次违反,设长度为$j$。

$(1)$当违反的是不能有前缀$(0,0)$时,相当于要求长度为$j$,和为$(0,0)$,不能有前缀$(0,0)$和前缀$(x,y)$的序列个数,可以由$v[j][x][y]*f[i-j][x][y]$转移过来。

$(2)$当违反的是不能有前缀$(x,y)$时,相当于要求长度为$j$,和为$(x,y)$,没前缀$(0,0)$和前缀$(x,y)$的序列个数,即前后缀都不为$(0,0)$的序列个数。可以由$o[j][x][y]*f[i-j][0][0]$转移过来。

而上面的$o$是从$v$转移过来的,并且每次转移长度都会变大,我们可以枚举长度从小到大后一起计算$v$和$o$。

考虑计算答案:

$$\sum_{l<=r}\sum_{(x,y)}\sum_{i=1}^{l-1}\sum_{j=1}^{n-r}g[i][x][y]*o[r-l+1][-x][-y]*g[j][x][y]*all^{n-(r-l+1)-i-j}$$

设$sum1[i][x][y]=\sum_{j=1}^{i}g[j][x][y]*all^{-j}$

那么答案就是

$$\sum_{l<=r}\sum_{(x,y)}o[r-l+1][-x][-y]*all^{n-(r-l+1)}*sum1[l-1][x][y]*sum1[n-r][x][y]$$

以上大多数$dp$状态数都是$O(n^3)$,转移都是$O(n)$容斥,所以复杂度是$O(n^4)$。

考虑包含的情况,类似的,我们把他分成三段$A,B,C$,并枚举$A$的坐标为$(Ax,Ay)$。

那么$B$的坐标和为$(0,0)$,$C$的坐标和为$(-Ax,-Ay)$。

$A$只要满足没有前缀$(0,0)$,$C$只要满足没有后缀$(0,0)$。

$B$要满足没有前缀$(0,0)$且没有前缀$(-Ax,-Ay)$,即$v[j][-Ax][-Ay]$。

考虑计算答案:

$$\sum_{l<=r}\sum_{(x,y)}\sum_{i=1}^{l-1}\sum_{j=1}^{n-r}g[i][x][y]*v[r-l+1][-x][-y]*g[j][-x][-y]*all^{n-(r-l+1)-i-j}$$

我们可以类似上面地优化一下即可。

时间复杂度$O(n^4)$,由于很多状态其实是没用的,可以在$1s$内通过

期望得分$100$分

UOJ Easy Round #6

2016-06-26 23:24:38 By jiry_2

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

这是UOJ第六场UOJ Easy Round。咦为啥在这个节骨眼上搞 Easy Round 呢?因为我们出不出来题了NOI即将到来,是时候来一场小清新的 UER 来给大家实战演练一波了!

Q:真的是 NOI 难度吗,看了前几场的 UER 感觉不像啊。

A:难度会略高于去年 NOI 的难度,和几年前的 NOI 较为相似。具体来说,A题是一道难度低于 UR A 的题,B题和C题都是 UR B 的难度或更低。

2016年6月24日6点,连夜进行的英国脱欧公投计票工作接近尾声。英国广播公司报道称,根据初步统计结果,约52%的英国选民投票支持英国脱离欧盟,英国脱欧已成定局。当日,英国首相卡梅伦发表声明,将辞去英国首相的职务。一时间,有关英国脱欧的话题,成为全球的焦点。

最近,由于 UOJ 管理员集体划水,UR 长期跳票,引发了 UOJ 广大用户的不满。于是,大家决定在2016年7月1日晚举行全民公投,废除 UOJ。

因此,本次 UER 将以全民公投为主题。

出题人:jiry_2sevenkplus, SkyDec

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

这场成绩将计入rating。

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

UPD:比赛已经结束!

echo -n 罚时最接近6小时6分钟6秒的选手,如有多个,取排名最高的 | md5sum
08c79db829dda067511bbfba48e04997

恭喜获得前 5 名的选手!

  1. lbn187
  2. maijing
  3. bright_sun
  4. bzoj
  5. cy

恭喜 zxozxo 获得 UOJ 抱枕一个!

UOJ Round #14 题解

2016-04-22 21:12:19 By jiry_2

最强跳蚤

By jiry_2,题解By C_SUNSHINE

算法一

显然直接把边权乘起来是不现实的(当然你想写高精度开根我也是兹瓷的),我们考虑每一个质因子$p$,它的次数必须是偶数。

那么我们就有了简单粗暴的算法1:从每个点开始dfs,维护每个质因数的出现次数,预处理每个数的质因数分解即可,复杂度是$O(n^2 \log n)$,空间复杂度$O(w)$。 如果使用map存次数的话,可以做到$O(n \log^2 n)-O(n)$的时空复杂度,期望得分30分。

算法二

我们把$w$质因数分解,每个出现过的质数离散化一下,可以发现至多出现$O(n \log n)$个不同的质数(事实上当$w/n$不是很大的时候这个数目是$O(n)$的)。

那么使用bitset维护每个质数的出现次数,再dfs就可以做到$O(\frac {n^3} {32})$了,但是这样并不能跑出$n=3000$,事实上我们直接对离散化之后的质数开桶统计就能做到$O(n^2 \log n)$了,期望得分50分。

算法三

对于$w \leq 80$的数据,由于80以内的质数不超过32个,我们可以对第$i$个质数分配一个权值$2^{i-1}$,一条边的权值就是$w$所有质因子的权值的异或,一条路径的权值就是每条边权值的异或,从根开始dfs求出根到每个节点的权值,那么$u \rightarrow v$是可行的当且仅当根到$u$的权值等于根到$v$的权值,把根到所有节点的权值排序统计一下即可。

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

算法四

考虑推广算法三,其实我们可以对于每个质数,给它分配一个$[0,2^{64})$内的随机数,于是一条合法路径权值一定是$0$,而不合法路径只有$\frac{1}{2^{64}}$是$0$,这个概率可以忽略不计。剩下的按照算法4将根到每个节点的权值排序统计即可。

至于质因数分解,可以预处理$10^4$以内的质数表,然后每次暴力分解,复杂度是$O(\sqrt{w} + n \pi (\sqrt{w}))$,可以通过全部测试点。

人类补完计划

By matthew99,题解By C_SUNSHINE

算法一

对于$m \leq 20$的情况,我们可以暴力枚举每条边在不在$S_v$里,并判断是否符合题目要求,把合法的方案的权值加入答案中。

时间复杂度$O\left(m2^m\right)$,期望得分5分。

注意到不同的连通块之间的贡献独立,对每个连通块分别处理,可以通过第二个测试点得到10分。

算法二

观察题意其实就是枚举所有的基环外向树,$w$是非叶节点个数,把$2^w$加入答案。

那么我们首先考虑基环外向树的计数,第一步是环的计数。 环的计数可以非常容易的通过状态压缩DP来实现设$cir_{i,S}$表示集合$S$组成一条以$j$开头$i$结尾的链的方案数(令$j$为$S$中编号最小的元素), 转移时枚举$i$的下一个元素即可,要求和$i$直接有边且编号$>j$,最后对于每对$i,S$,若$i,j$之间由有边,则将$cir_{i,S}$加入集合$S$的答案$f_S$中。 注意一个环从$j$开始有两种不同的顺序遍历,所以最后答案要除以$2$。

接下来考虑集合$V$组成的基环外向树计数$cnt_V$,我们可以枚举环的集合$S$,然后把环缩成点,直接套用Matrix-Tree定理即可,这样处理所有$V$的总复杂度是$O\left(3^n n^3\right)$的。

我们考虑给权值一个意义,假设每个节点可以染成黑白两种颜色,叶子节点只能染成白色,那么只要计算染色的总方案数,一个$S_e$就会被恰好计算$2^w$次。

对于染色方案数的计算,我们可以考虑容斥原理,用总方案数减去存在黑色叶子节点的方案数,注意到基环外向树删去叶子之后仍然是基环外向树。

令$val_V = 2^{|V|}cnt_V$,枚举叶子节点集合$T$,则方案数

$$g_V = \sum_{T \subset V,T \neq \emptyset} \ (-1)^{|T|} \times val_{V-T} \times ways(T,V-T)$$

其中$ways(T,S)$表示$T$向$S$连边的方案数,为$T$中所有节点在$S$中邻接点个数之积,容斥时暴力计算就好,这部分时间复杂度是$O\left(3^n n\right)$的。

于是这个算法总的复杂度就是$O\left(3^n n^3 \right)$,期望得分30分。

算法三

算法2的时间复杂度瓶颈在与求$cnt_V$上,我们考虑换一种计数方式,把$cnt_V$的计算和答案的计算放在一起。

首先考虑$V$集合的权值和计算,对于$V$的每一个子集$T$,我们都计算出叶子节点集合为$T$的基环外向树个数$g_T$,那么权值和就可以直接计算了。

依旧使用容斥原理,令$h_T = cnt_{V-T} ways(T,V-T)$,即$T$为叶子节点集合的子集的方案数,然后对$h$做子集反演得到$g$:

$$ g_S =h_S + \sum_{S \subset T} (-1)^{|T|-|S|} \times h_T $$

那么显然$V$集合对答案的贡献就是$2^{|V|}f_V+\sum_{S \subset V,S \neq \emptyset}\ \ 2^{|V|-|S|} \times g_S$。

接下来考虑$cnt_V$如何计算,对于每个$V$首先把单独为一个环的情况$f_V$加入答案, 然后既然我们已经求出了以任意集合$S$为叶子的基环外向树方案数$g_S$,直接把$cnt_V$加上所有$g_S$的和即可。

计算$h_T$的总复杂度是$O\left(3^n n\right)$的,子集反演可以使用$O\left(2^n n\right)$的快速算法,总复杂度也是$O\left(3^n n\right)$,期望得分70分。

算法四

我们采用一种新的思考方式,考虑树的prufer编码,每次选取最小的一个叶子删去并将其邻接点加入prufer序列。

具体令$dp_{V,S}$表示$V$集合组成的$S$不能为叶子的基环外向树数目。

转移时我们令$k$为$V-S$中编号最小的节点,我们有两种转移方式:

1.令$k$为叶子,并将$k$删去,那么我们在$k$的邻接点中选取一个节点$l$,将$l$设置为可以为叶子。

2.将$k$设置为不可为叶子。

当$V=S$时可以发现答案一定为一个环,即$dp_{V,S}=f_V$。

注意到这样的统计会有重复计数,因为对于一个基环外向树,令其点集为$V'$,非叶节点集合为$S'$,那么对于所有$V=V',S \subseteq S'$都会被$dp_{V,S}$计数一次, 共会被计数$2^{|S'|}$次,我们发现这恰好就是这个基环外向树的权值,那么对所有的$dp_{V,S}$求和即可。

时间复杂度也是$O\left(3^n n\right)$,期望得分70分。

算法五

考虑对算法2进行优化,算法2的瓶颈在于计算集合$V$构成的环套树的方案数,而这个方案数在算法3中我们可以枚举叶子节点的集合进行容斥,而算法3的瓶颈在于莫比乌斯反演。

我们考虑把算法2和算法3结合起来,我们直接枚举非叶节点集合$S$,在枚举$S$的超集$V$,枚举$V$可以使用dfs,在dfs的过程中计算$ways(V-S,S)$,使用如下容斥式子计算答案:

$$g_V = \sum_{S \subset V} (-1)^{|V|-|S|} \times val_S \times ways(V-S,S)$$

dfs之后统计$S$对于$V$的贡献即可,复杂度是$2^{n-|S|}$的,总复杂度就是$O\left(3^n\right)$了,期望得分100分。

matthew99的计数小课堂

大家好这里是matthew99,我来说一些更好的求每个子集组成的基环外向树的方法:

我们注意到算法二有一个很不优美的地方,为了求出每个子集的基环外向树个数,我们不得不使用了一个$O(3 ^ n n ^ 3)$的算法。后面的算法中给出了更好的求这个的办法,但我这里要扯一些其他的办法。

注意到我们如果求出每个点集中恰有$0, 1, 2, \cdots n$条边的连通图个数,那么我们就能求出每个子集的基环外向树个数,这个很容易用容斥得到。考虑记录每个点集边数为每一个值的任意图个数和连通图个数,我们用经典的思路,枚举$1$号点所在连通块是哪些点,然后再枚举这个连通块内的边数然后直接容斥即可,这样复杂度是$O(3 ^ n n ^ 2)$,期望得分50分。我们如果用二维集合占位多项式并实现对一个二元函数求$\ln$,我们可以将这一部分做到$O(2 ^ n n ^ 4)$,但其实际效率甚至不如直接容斥。

还有一个思路就是我们考虑有向图中的基环外向树可以看成就是每一个点恰好连出去一条边,无向图我们可以定向之后达到同样的效果。考虑记录每个子集,每个点恰好指定一条边连出去的图的个数,答案似乎是度数的乘积,这样我们似乎考虑直接套用前面所述的容斥算法就可以做到$O(3 ^ n)$了,但其实不然,由于是无向图我们可能会出现重边,但是我们注意到如果有重边,相当于一棵树上随便找一条边让它再被选一次,所以我们用Matrix-Tree定理$O(2 ^ n n ^ 3)$求出每个子集的生成树个数,然后在此基础上很容易实现$O(3 ^ n)$的容斥算法求每一个子集的基环外向树个数。

思考熊

By jiry_2

QAQ 这题的来源是我在做乐滋滋胡策的时候 YY 出的一个 idea,那个时候觉得这个 idea 还是挺厉害的,于是就接了这么一个 C 题的坑。

但是用 idea 造题这种事情毕竟不靠谱,在造题的过程中发生了各种各样的偏差..在经过了各种各样的挣扎之后,出出来这么一个题,有很多的不足之处 QAQ 求轻喷。

算法一

在询问时暴力枚举每一个可以使用的接应点,算出路径的权值和并更新答案。在计算路径的权值的过程中,需要计算两个点之间的 LCA。

如果直接使用倍增或者树剖计算,那么时间复杂度是 $O(nm \log n)$,期望得分 $7$ 分。

可以发现两个节点的 LCA,就是在欧拉序中,它们第一次出现的位置之间深度最小的节点。于是就可以用 ST 表来询问两个点之间的 LCA 。这样时间复杂度是 $O(nm)$,期望得分 $20$ 分。

算法二

如果只有插入的话,我们可以直接分块。在插入的过程中,一旦插满一块,我们就对每一个树节点预处理出到这个块中所有节点的距离的最大值,这是一个经典的树形 DP 的问题,我们可以在 $O(n)$ 的时间内求出答案。

在询问的时候,对于询问区间内完整的块,可以直接得到答案;对于块外的块,使用算法一中单次 $O(1)$ 的算法计算权值。这样的时间复杂度和空间复杂度都是 $O(n \sqrt n)$ 的。

那么现在问题来了,有删除的时候怎么办呢..有一种非常简单的方法就是不管..这样可以通过第三个 subtask,期望得分 $40$ 分。

肛道理

可能到这儿有人会说,出题人你会不会造数据,又偏题出出暴力放放..那么我们来肛道理..

如果知道了块的大小,卡这个做法是非常轻易的——只要在刚好插满一个块的时候反复重复插入和删除,这样时间复杂度就边 $O(n^2)$ 了。

但是问题来了..作为出题人,我根本不知道泥萌的块大小是多少 QAQ

在比赛的时候对着程序卡是一种可行的方案,但是我对着程序卡同样会被婊 QAQ 再加上如果写程序的时候加点奇技淫巧,比如拿输入数据 srand 一波然后随一个块大小出来,这样我即使是对着程序也卡不掉了..

所以最后想想索性都不卡了,因为如果我对着固定块长的卡了,却放了随机块长的过了,大家都不高兴是吧..反正只是暴力分嘛是吧..放过去了就放过去了..

难道就没有什么不存在被卡可能性的算法吗?难道就没有什么能卡这个的方法吗?当然都是有的..在后面会讲..

算法三

考虑 $w \geq 0$ 的部分分,我们来考虑一下如何快速求一个点到一个点集 $S$ 的距离的最大值。

我们可以发现,假设 $S$ 中距离最远的一对点是 $u$ 和 $v$,那么任意一个点 $x$ 到点集 $S$ 中的点的距离的最大值一定是 $x$ 到 $u$ 的距离或 $x$ 到 $v$ 的距离,证明还是很显然的。所以我们就可以使用两个点来代替一个点集。

我们可以使用线段树,对线段树的每一个节点来维护这个区间中的点集的信息。合并两个点集的信息时候,我们可以把这两个最远点对一共四个点放到一起,那么它们两两之间距离最远的一对点就是合并后点集中距离最远的两个点。可以合并信息,那么插入和删除操作就可以轻易地完成。

在询问答案的时候,只需要对定位出来的每一个子区间统计计算答案并更新就好了。

时间复杂度 $O(n \log n)$,可以通过第五个 subtask。

算法四

当 $w$ 可以小于 $0$ 时,维护直径的方法就不行了。

如果点集 $S$ 给定,我们可以先求出点集 $S$ 在树上的虚树,然后求出虚树上每一个点到它的子树中的关键点的最远距离 $d_i$ 和到子树外的关键点的最远距离 $u_i$ ,这个可以用两遍 DFS 预处理来解决。

现在要询问点 $x$ 到点集 $S$ 中的点的最远距离,我们可以先找到 $x$ 深度最大的祖先 $f$,使得 $f$ 在虚树的某一条边上,接着我们找到 $f$ 所在边的深度较深的端点 $v$,那么答案就是 $\max(dis(x,v)+d_v, w_x-w_v+u_v)$,其中 $dis(x,v)$ 表示两点之间的距离,$w_v$ 表示 $v$ 到根路径上所有边的权值和。

那么如何找到 $f$ 呢,我们可以在虚树中找到 DFS 序小于等于 $x$ 的最后一个节点 $l$ 以及大于 $x$ 的第一个节点 $r$(这个可以通过一次二分解决),那么 $f$ 就是 $x$ 和 $l,r$ 的最近公共祖先中深度较深的那个(这个可以通过脑补虚树的构建过程得到)。在找到 $f$ 后,我们二分出虚树中 DFS 序大于等于 $f$ 的第一个节点,那个就是 $v$ 了。

这个做法需要两次二分和两次 LCA,如果大家有更好的定位方法欢迎来和我讨论。

至于修改,我们先来考虑插入:在只有插入的时候我们可以使用二进制分组来解决。

我们可以对最普通的二进制分组算法进行一点拓展来支持区间查询操作:在把两个块合并成一个新块的时候,保留原来两个块,并把新块作为原来两个块的父亲,这样我们就得到了一个线段树结构。这样在查询的时候,就可以和线段树一样,先找到完整组成询问区间的 $O(\log n)$ 个块,然后分别在块中查询。

这样我们就把一个动态插入的问题转化成了静态的问题,时间复杂度 $O(n \log^2 n)$,空间复杂度 $O(n \log n)$,可以通过第四个 subtask。

算法五

最后我们来考虑删除操作,出这题的时候,核心在于一种将二进制分组拓展使得它可以在时间空间复杂度不变的情况下支持删除,这个虚树的背景只是我们为了找一道“只能用二进制分组做的题”的时候,硬套上去的。

普通的二进制分组之所以不能支持删除,是因为它的复杂度是均摊的,我们在它重建的时候,可以通过不停的删除和插入,使得它不停地合并一些非常大的块。

我们观察拓展后的二进制分组结构,它有 $t$ 层,从下到上第 $i$ 层的每一个块中有 $2^i$ 个节点。在原来的二进制分组中,我们相当于在每一个块插满后,立即重建这个块。

现在我们来考虑这个一个做法,在删除的时候,我们给所有涉及到的块(最右边一列)打上狗带标记,表示这个块的信息目前不对。在查询的时候,如果我们当前查询的块是狗带的,那么就递归对它的两个孩子进行求解。

当我们插满一个块的时候,我们不立即重建这个块,我们访问它的前驱块(同一层中相邻的前面那个块),如果它的前驱块是狗带的,就重建前驱块,否则就什么都不干。

接着我们来分析这个算法的复杂度。在这个算法中,我们相当于每时每刻都保证了每一层至多有一个块是狗带的,因此在查询的过程中,我们只会对 $O(\log n)$ 个块进行递归,因此需要查询的块的个数还是 $O(\log n)$ 的,于是查询复杂度还是 $O(\log^2 n)$。

接着我们对第 $i$ 层计算重建的代价,考虑这样两个事件:

  1. 给一个块打上标记,这个事件复杂度是 $O(1)$ 的。
  2. 重建一个块,这个事件的复杂度是 $O(i 2^i)$ 的。

令 $n$ 为序列长度,$len_i$ 为第 $i$ 层没有被打标记的块的总长度,令势能函数 $\phi (i)=|n-len_i-2^i|$。一次插入或者删除至多让势能函数增加 $1$,而一次事件会让势能函数减少 $2^i$,于是可以得到第 $i$ 层的均摊复杂度是 $O(ni)$。

让 $i$ 在 $1$ 到 $O(\log n)$ 范围内求和,那么就可以得到它的时间复杂度是 $O(n \log^2 n)$ 的。

因此这个算法的总时间复杂度是 $O(n \log^2 n)$,空间复杂度是 $O(n \log n)$。

算法二中,我们也可以一样,在分块的时候延迟重构,保证至多有一个块的信息是狗带的,这样时间复杂度就对了。

这就是这个算法的全貌了,当初在脑补出这题的时候感觉还是非常厉害的,但是在造数据的时候发现:根本没法卡暴力。

实际上面临的问题和算法二一样,如果选手在二进制分组的时候随机扰动一下,让出题人不知道你的代码的重构的位置,那么就没法卡了,实际上在期望情况下随机分组的复杂度的确是对的。

在这题的数据中,我对一些比较正常的重构位置附近卡了一下,而如果你在非常奇怪的地方分组的话,算法的常数会变得非常大,感觉随机分组的方法还是比较难通过的。

当然,硬要卡的话,这种随机分块和随机分组的方法还是可以卡的。我们可以用交互的形式,你的代码边运行,我的交互库边生成数据,发现你这几个操作特别慢,就赶紧删除回去再来一遍。

然而交互题实在是太麻烦了..要改成交互的话,我必须在交互库里内嵌标程,而交互库又必须要写 C 和 Pascal 的...

QAQ

于是只能选择狗带了QAAAAAQ

算法六

当然..上面这些算法基本没有最开始那棵树什么事..实际上在出题的时候我们也没怎么考虑那棵树..

本来想用凸包做这题的内容的,但是乐滋滋的胡策里已经有凸包了,后来又想用半平面交,但是半平面交和凸包又没有什么区别。再后来想用 mex,但是 mex 的题实在太多了,又不是很好。于是最后想了想发现虚树这玩意不是很好合并,决定就是它了。

然而在考前 10min 我突然发现好像可以在那棵树上直接做 QAQ 根本不关二进制分组什么事.. 感觉成功身败名裂了。

我们可以直接对最开始的树点分治,对每一层分治维护分治中心的的子树中的最远点(要维护最远点和扣除最远点所在子树后的最远点),这可以用线段树或者平衡树随便搞..

然后..就做完了..

QAQ

当然实际上要过这题也没有这么轻易..平衡树常数太大估计会 T,而最裸的线段树因为我们不知道值域,需要动态开节点,所以空间是 $O(n \log^2 n )$ 的,这肯定是过不了的。

但是我们可以用一些鬼畜技巧来优化掉空间的一个 $\log n$:对每一个节点,我们先规定它的线段树的值域为 $2^0$,然后在插满的时候,把值域修改为 $2^1$,然后暴力重构线段树并分配空间,再插满就修改成 $2^2$...

脑补一下就发现空间 duang 的一下变成 $O(n \log n)$ 了。

当然这样空间的常数比较大,具体能不能过这道题我不知道,这一块里的算法我也没有真正写过,都是我瞎 BB 的..(但是这样也已经掩盖不了这是一道垃圾题的事实了)

感觉出数据结构题实在太难了 QAQ 还是小清新计数题好..

这道题就当做是对一些奇技淫巧的推广吧..对我这种写不动数据结构的老年人来说这种方法还是挺 work 的,都是一些公式化的东西,也挺好写..

不过现在的科技这么发达,真正想要出又要新颖,又要只能用这种方法做的题目真的是太难了 QAQ

惨啊..

QAQ

UOJ Round #14

2016-04-19 15:46:13 By jiry_2

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

这是UOJ第十四场UOJ Round。UOJ Round还是一如既往的省选及以上难度,欢迎大家来玩owo

公元前1184年4月24日,希腊联军巧施木马计攻破了特洛伊城,结束了持续10年之久的特洛伊战争。

在遥远的异世界,有一片跳蚤大陆,在跳蚤大陆上生活着人族与跳蚤族。经过了漫长的发展,跳蚤族在伏特跳蚤国王的带领下建立了自己的国家,而人族则以一个被称为pion吧的城市为中心,建立了城市联邦。千年来,人族与跳蚤族一直和睦相处,而且就在几年前,人族甚至还邀请了伏特跳蚤国王到pion吧中担任吧主的职位。

然而,就在人们都以为和平将永远持续下去的时候,灾难悄悄地降临了:一名叫做_叫我猪猪侠的人类,在pion吧中策划了兵变,将伏特跳蚤国王赶出了人族的领地并取而代之。很快,受到侮辱的跳蚤国王率领着百万跳蚤大军包围了pion吧——人族和跳蚤族的战争一触即发。

因此,这一场比赛将围绕着这场战争展开。

出题人:jiry_2matthew99, jiry_2

这场成绩将计入rating。

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

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

UPD:比赛已经结束!

echo -n 所有通过A题的人中A题提交次数最多的 | md5sum
805d8caf8307b6e26f0bc9e1e17cb84f

恭喜获得前 5 名的选手!

  1. r_64
  2. cy
  3. zhangzj
  4. YMDragon
  5. faebdc

恭喜 YMDragon 获得 UOJ 抱枕一个!

UOJ Round #13 题解

2016-04-10 20:19:58 By jiry_2

大家好这里是写题面的JRY。

最近因为种种原因,UR 跳票了半个多月的时间,不过终于,新的一场 UOJ Round 还是和大家见面啦。(在某学堂的提醒下,管理员们终于想起来还有UR这回事了...

因为写题面的人比较懒,所以这一次的标题就用了杜老师的格式:)

希望大家能够喜欢这一次的题目owo

Yist

By matthew99

算法一

直接状压每一种可能的子序列,时间复杂度$O(2 ^ npoly(n) + q)$,期望得分30分。

算法二

二分之后贪心每次删除最小的数,判断是否可行。由于删除一个数会让更大的数“更容易”被删,所以这个算法显然是正确的。

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

算法三

使用平衡树等数据结构优化算法二,时间复杂度$O(qn \log ^ 2n)$,由于常数大可能较难通过90分的数据。

算法四

我们考虑到对于一个数,删除它最小需要的区间长度是多少,如果我们在序列左右都加上一个无穷小且没有被删除,考虑找到它左边没有被删除的第一个比它小的位置$u$,右边没有被删除的第一个比它小的位置$v$,那么需要的区间长度就是$(u, v)$这个开区间的长度减去这个区间中所有比它小且需要删除的数的个数。答案就是所有数对于的区间长度的最小值。

从左往右扫一遍,并用set或者什么其他数据结构维护一下,可以求出所有的$u$和$v$,然后从小到大加入,用树状数组或者什么其他数据结构维护一下即可求出区间中所有比它小且需要删除的数的个数。时间复杂度$O(qn \log n)$,期望得分90分。

算法五

算法四中提到,需要的区间长度就是$(u, v)$这个开区间的长度减去这个区间中所有比它小且需要删除的数的个数,实际上,我们只需要用开区间的长度减去这个区间中所有需要删除的数的个数即可。

考虑一个数,假设区间中有一个数需要删除且比它大,那么显然这个比它大的数所对应的区间长度比原数短,所以这样显然不会影响答案(因为我们要求的只是最小值)。

所以我们只要求出$u$和$v$即可。

这样很多劣于线性的算法都能AC,这里列举几个:

维护A的单调栈,并在上面二分,由于常数小可以AC。

用ST表加上二分,然后加上一些优化$O(1)$去除一些显然不能更新答案的位置,也可以AC。

从大到小加数,所有被删除的和已经被加入的未被删除的位置记为1,其他位置记为0,则显然$u$和$v$分别就是左边和右边的第一个0,用并查集很好维护,如果不计读入的话时间复杂度为$O(qn \log n)$或者$O(qn \alpha(n))$。

算法六:

为了避免成为辣鸡卡常出题人,接下来我来讲讲线性做法,我的程序可以在时限的大约三分之一内出解。

其实很简单,对于所有被删除的位置,从大到小,每次暴力找$u$和$v$,并把所有访问过的地方标记,如果暴力的时候遇到了标记过的地方,那么可以发现原来访问到这个地方的数显然对应的区间更短,所以这个时候可以不用继续找$u$和$v$,直接考虑下一个位置即可,这样每个位置只会访问一次,若不考虑读入,则时间复杂度$O(qn)$,期望得分100分。

题外话:

我看到开场就有几个人交了正解的第一步:只找最大的一个数暴力找$u$和$v$更新答案,首先我样例是随机的所以你们很容易通过,其次我第一个点也是随机的所以你们也能过第一个点的十分,其他点应该都是过不了的,我想说的是你们就不会认真分析一下问题再提交么,实际上如果你们只找最大的几个更新答案也是很难有很多分的。考虑一下有两个阶梯,一个阶梯就是左右两边都是很小的未被删除的数,中间是比两边大的被删除的数和比被中间所有所有被删除的数都要大的未删除的数,那么如果第一个阶梯的数比第二个阶梯的数大而且第一个区间更短,那么更新答案的应该是第二个阶梯中的最大值,这样前面很多很多个数对应的区间都不是答案。

Ernd

By PoPoQQQ

因为A题和C题难度偏高所以出了道简单题平衡一下难度

ctb上瘾的出题人

算法一

对于subtask1,$n\leq20$。

暴力枚举接哪些水果,线性统计得分,时间复杂度 $O(n\times2^n)$。

用DFS的方式可以将复杂度降低至 $O(2^n)$。

期望得分 $10$ 分。

并没有什么卵用的算法。

算法二

对于subtask2,$n\leq1000$

我们定义“段”为满足对于其中任意相邻元素 $i$ 和 $i+1$ ,满足接到第 $i$ 个水果后可以接到第 $i+1$ 个水果的极长子区间。

考虑暴力dp,定义 $f_i$ 为以第 $i$ 个水果结尾的接水果序列的最大总得分,那么有:

$f_i=\max(f_i,f_j+1|\text{ 接到第 }j\text{ 个水果后可以接到第 }i\text{ 个水果})$

$f_i=\max(f_i,f_j-1+(i-j+1)^2|\text{ 第 }i\text{ 个水果和第 }j\text{ 个水果属于同一段})$

枚举 $j$ 进行转移,时间复杂度 $O(n^2)$,期望得分 $20$ 分。

算法三

我们考虑如何优化第一部分转移。

我们将水果都放在二维平面上,第 $i$ 个水果变成一个坐标为 $(a_i,b_i)$ 的点,那么容易发现,接到一个果子后,能接到的其他果子都在这个点的 $[45^\circ,135^\circ]$ 范围的方向上。

旋转坐标系,将每个点变为 $(b_i-a_i,b_i+a_i)$,那么接到一个果子后,能接到的其他果子都在这个点的右上方。

问题变成了一个二维偏序问题,用树状数组维护上升子序列即可。

观察subtask4,$n\leq5\times10^5$,答案不超过$10^4$,这意味着任意一段的长度都不会超过 $\sqrt{10^4}=100$。

第一部分转移使用算法三,第二部分转移暴力,时间复杂度 $O(n\log n+100\times n)$ ,期望得分 $40$ 分。

算法四

现在开始考虑如何优化第二部分转移。

注意到一段内的元素在按照 $b_i-a_i$ 排序后可能不连续,但相对顺序不会改变,因此我们不用担心转移顺序的问题。

这部分转移每段之间彼此独立,因此我们考虑对于每段内部分别计算。

观察转移方程 $f_i=\max\{f_j-1+(i-j+1)^2\}$,设 $P=f_j-1+(i-j+1)^2$ ,那么有:

$(f_j+j^2-2j)=2i\times j+(P-i^2-2i)$

我们发现这个式子可以斜率优化,将每个决策点 $j$ 化为平面上的点 $(j,f_j+j^2-2j)$ ,维护一个上凸包即可。

注意到我们维护的是上凸包而查询斜率 $2i$ 随 $i$ 单调递增,因此我们需要用一个栈而不是队列来维护这个凸包。

当然你要二分斜率也是完全可以的。

时间复杂度 $O(n\log n)$,期望可以通过全部测试点拿到 $100$ 分。

算法五

考虑用另一种方法优化第二部分转移。

观察到对于决策点 $j< k$,随着 $i$ 的增大,$(i-j+1)^2$ 的增长速率永远大于 $(i-k+1)^2$ 的增长速率,这意味着一旦某一时刻 $f_j-1+(i-j+1)^2 > f_k-1+(i-k+1)^2$,那么决策点 $k$ 将会永远不可能成为最优决策点,决策点 $k$ 可以删除。

由此我们发现了决策单调性,利用单调栈+二分的方法维护有效决策点,时间复杂度 $O(n\log n)$,期望可以通过全部测试点拿到 $100$ 分。

什么你问我subtask3是干嘛的?

照顾常数写残党/数据结构爆搞党/乱搞党。

以上。

Sanrd

By Stilwell

算法一

容易发现我们需要求的是$l\sim r$这段数的次大质因子之和,其中次大质因子定义为可重集的次大。

一个最简单的方法是将每个数都质因子分解,对于前50\%的数据,$r-l\leq 10^7$,这一段数的质因子总个数是$O((r-l)\log r)$的。

预处理出$\sqrt{r}$范围内的质数,考虑使用埃氏筛法进行分解,设当前质数为$p$,那么范围内第一个被$p$整除的数为$\lceil\frac{l}{p}\rceil p$,筛法消耗的时间和质因子总个数是相同的。

时间复杂度$O(\sqrt{r}+(r-l)\log r)$,期望得分50分。

算法二

原问题等价于求$1\sim n$的次大质因子之和。

考虑用$[1,n]$范围内的所有数做一个乘积背包,设$f[i]$表示现在乘积为$i$的数的最大质因子之和,升序枚举质因子可以保证当前质因子是转移后的最大质因子,转移前的最大质因子就是需要求的次大质因子,背包生成的每个数都是不重复的,所以可以直接计入答案。

容易发现$f[i]$的可能取值只有两种,0或$i$的最大质因子,取决于当前枚举的质数能不能组成$i$。这样表示状态明显非常浪费,可以尝试优化。

对于一个数$x(x\leq n)$,$x$的次大质因子一定$\leq \sqrt{n}$,所以$>\sqrt{n}$的质数我们可以考虑批量转移。

对于一个状态$i$,在背包时还能转移的质数需要$\leq\lfloor\frac{n}{i}\rfloor$,不妨直接用$\left\lfloor\frac{n}{i}\right\rfloor$来表示状态。

设$g[j]$表示$\lfloor\frac{n}{i}\rfloor=j$的数的最大质因子之和,由于$\lfloor\frac{n}{i}\rfloor$的取值只有$O(\sqrt{n})$种,所以状态数缩减为$O(\sqrt{n})$,原先$i\rightarrow ip$的转移变化为$j\rightarrow \lfloor\frac{j}{p}\rfloor$。

那么现在问题就转化为这样两部分:

  1. 求$\leq\lfloor\frac{n}{i}\rfloor$且$>\sqrt{n}$的质数个数。
  2. 用$\leq\sqrt{n}$的质数完成$g[j]$的背包。

先来解决第一部分,设$p_1\sim p_m$为$\leq\sqrt{n}$的质数,且$p_i < p_{i+1}$。

设$P[i][j]$为$[1,j]$ 范围内与前$i$个质数互质的数的个数,需要求的即为 $P[m][j]$。

设$l=\lfloor\frac{j}{p_i}\rfloor$,容易得到以下递推式 $$P[i][j]=P[i-1][j]-P[i-1][l]$$

递推时只需要计算$\lfloor\frac{n}{i}\rfloor$这$O(\sqrt{n})$个状态就能完成转移。

设质数密度为$O(\frac{1}{\log n})$,那么暴力递推的计算量可以估计为 $$\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}O\left(\frac{i}{\log i}\right)+\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}O\left(\frac{\sqrt{n}}{\log\sqrt{n}}\right)\thickapprox O\left(\frac{n}{\log n}\right)$$

当$p_{i+1}>j$时,一定满足$P[i][j]=1$。

所以,当${p_i}^2>j\geq p_i$时 $$P[i][j]=P[i-1][j]-1$$

因此,不必重新计算${p_i}^2>j$的情况,记录$j$最近一次被更新时的$i$的值,设为$pre_j$,在调用$P[i][j]$时,将编号$pre_j+1\sim i$间的质数计入。

考虑对于每个$\lfloor\frac{n}{i}\rfloor$计算有多少质数需要转移,计算量可估计为 $$\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}O\left(\frac{\sqrt{i}}{\log i}\right)+\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}O\left(\frac{\sqrt{\frac{n}{i}}}{\log\sqrt{\frac{n}{i}}}\right)$$

后半部分一定大于前半部分,故复杂度可以估计为 $$\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}O\left(\frac{\sqrt{\frac{n}{i}}}{\log\sqrt{\frac{n}{i}}}\right)\approx O\left(\frac{\int_0^{\sqrt{n}}\sqrt{\frac{n}{x}}\mathrm{d}x}{\log n}\right)=O\left(\frac{n^{\frac{3}{4}}}{\log n}\right)$$

完成了质数部分的计算,考虑$g[j]$部分的计算,暴力转移需要枚举每个质数再枚举每个状态,复杂度同样为$O\left(\frac{n}{\log n}\right)$。

回想前一部分是如何优化的,考虑如何省去$p^2>j=\lfloor\frac{n}{i}\rfloor$时的运算。

有$p^2>j\Rightarrow\lfloor\frac{j}p\rfloor < p\leq \sqrt{n}$,所以这些状态在以后的转移中只能再加入一个$\leq\sqrt{n}$的质数了,可以这样优化:

  1. 这一部分转移不再进行。
  2. 记录最后一次更新$g[j]$时的$p$,最后再计算相应的贡献。
  3. 当转移到这些$g[j]$时,不更新$g[j]$,直接统计剩下还能使用的质数个数,计算相应的贡献。

优化后复杂度和第一部分一样为$O\left(\frac{n^{\frac{3}{4}}}{\log n}\right)$。

时间复杂度$O\left(\frac{n^{\frac{3}{4}}}{\log n}\right)$,期望得分100分。

UOJ Round #13

2016-04-01 16:58:19 By jiry_2

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

这是UOJ第十三场UOJ Round。UOJ Round还是一如既往的省选及以上难度,欢迎大家来玩owo

1984年4月9日,日本建成了世界上第一座无人工厂。在此之后,人们对机器人、人工智能的研究经久不衰,并获得了许多喜人的成果。

就在最近,uoj 公司对外宣称他们已经成功的研发出了一种机器人 betacome,可以在任何方面任何领域战胜人类。在此之后,betacome 在很多领域与人类进行了角逐,并取得了全胜的战绩:它跳的比跳蚤国王高,跑的比香港记者快,填数独比JCVB熟练...

在取得了这样优秀的成果之后,uoj 公司觉得 betacome 已经拥有了挑战站在人类智慧的巅峰的男人——picks 博士的能力,于是他们公开发表了挑战书,并决定在2016年4月10日的晚上,展开这场人类智慧与人工智能之间的巅峰对决。

因此,这一场比赛将以 picks 博士与 betacome 之间的对(jiao)决(yi)为主题。

出题人:matthew99, PoPoQQQ, Stilwell

这场成绩将计入rating。

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

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

UPD:比赛已经结束!

echo -n A题AC代码中跑的最快的,如果有多个取排名最高 | md5sum
089258aecc9c8464b9ec6b6ecd0d5b13

恭喜获得前 5 名的选手!

  1. hzt1
  2. srwudi
  3. cy
  4. Dr_Picks
  5. gao_r_q

恭喜 lostmemory 获得 UOJ 抱枕一个!(赛后rejudge过一次,以final test的结果为准)

关于 《Segment tree Beats!》 的一些问题

2016-03-03 10:46:17 By jiry_2

这几天重新研究了一下冬令营营员交流《Segment tree Beats!》的课件,发现课件里面 $O(n \log n)$ 部分的复杂度证明似乎是伪证。

QAQ

哇

然后这两天挣扎了好久,然而既没有找到 $O(n \log n)$ 的复杂度证明,也没有构造出DFS次数 $n \log^2 n$ 的数据。(目前构造出来的数据在 $n,m = 5 \times 10^5$ 范围内暴力 DFS 次数在 $10^7$ 级别..我已经把它加到 extra test 里面重测了。)

因为感觉我的姿势水平已经无法闷声修掉这个 bug 了,所以想了一想还是把这个事故公开出来,希望对这个问题有兴趣的老司机能够带带我 QAQ。

在这一波重测结束之后我会把这道题目重新公开出来供大家 hack(因为目前还没有找到 $5 \times 10^5$ 范围内跑不出来的数据,所以就暂时不修改数据范围了)。如果因为 Hack 数据的 10M 大小限制而无法提交的话可以直接来找我,我可以直接加到 extra test 里面进行重测。

如果有老司机能构造出 $n \log^2 n$ 级别的数据 hack 或者想出更好的复杂度证明请务必和我联系,不胜感激。

UOJ Round #12 题解

2016-02-28 19:27:08 By jiry_2

这里是写题面的 JRY,这一次的题面是不是很资慈呀 ( •̀∀•́ )。

因为之前在造比赛的时候 VFK 点名要让我来写题面,在感觉受宠若惊的同时为了不辜负 boss 的信任,当然要把题面写的生动有趣啦(笑)。

如果大家喜欢的话以后的题面里还是会继续这样写的 (*•̀ㅂ•́)و 。(当然前提是 VFK 还会再让我写题面)

最后插播一个小花絮,其实原来第三题的标题是长这样的:

嘿嘿嘿

后来因为它实在是太 ydcydc 了,所以就被无情的改掉啦 (╯°Д°)╯︵ ┻━┻。

公告

我们发现 613Chloe_fanxjt 这三位选手的 C 题代码,以及 Chloe_fanxjt 这两位选手的 A 题代码过于相似,经过管理员之间的讨论,我们决定取消他们这次比赛的参赛成绩。如果这几位选手存在异议,请在评论中提出。

希望各位参赛选手能以此为鉴,掌握开黑的正确姿势(雾),诚信比赛。

实验室外的攻防战

By matthew99

题解By C_SUNSHINE

算法一

我们建立 $n!$ 个点表示所有可能的排列,对于每个点次枚举交换哪两个,就能建出转移边,这样进行bfs就可以了判断 $A$ 状态是否能到达 $B$ 状态了。

这个算法能通过Subtask 1得到 $24$ 分。

不会bfs的戳这里

算法二

我们使用冒泡排序进行模拟,在交换时判断一下,如果经过 $n$ 轮之后仍然不能排成 $B$ 的样子,就输出 "NO"。

这个算法能通过Subtask 1~2得到 $56$ 分。

不会冒泡排序的戳这里

为什么这样是对的呢?因为自信!

算法三

我们可以猜一发结论,假设 $A_{a_i}=i,B_{b_i}=i$,一个显而易见的结论就是如果不存在 $1 \leq i < j \leq n$ 满足 $a_i < a_j且b_i > b_j$,则答案为"YES",否则为"NO"。 必要性十分显然,假设在 $A$ 中 $i$ 在 $j$ 前,而在 $B$ 中 $j$ 在 $i$ 前,那么一定有一个时刻 $i$ 和 $j$ 相邻且需要进行交换,而 $i < j$,无法交换,所以不可行。 充分性更加显然,考虑冒泡排序的过程,如果存在某一次交换 $i,j$ ($j$紧邻在$i$后面)两个元素时由于 $i < j$ 而无法交换,则一定出现了违反上述必要性的情况,这个命题的逆否命题就是充分性的证明。

那么我们怎么判断是否存在这样的 $i,j$ 呢?

我们按照编号从小到大枚举 $j$,并统计满足 $a_k < a_j$ 的所有 $k$ 中 $b_k$ 最大的值 $b_i$ ,如果$b_i > b_j$ 则说明这种情况出现了。判断完 $j$ 之后,用 $b_j$ 更新位置 $a_j$ ,用树状数组维护前缀和就好。

这个算法能通过全部Subtask得到 $100$ 分。

不会树状数组的戳这里

密码锁

By matthew99

得分情况

一个字形容——惨

49分——SanSiroWaltzBillXu2000

26分——xuhaike

19分——很多人

0分——很多人

算法一

对于subtask1,我们可以枚举每条边的定向,然后暴力求出强连通分量数。

什么你说你不会求强连通分量数?直接floyd跑一遍求传递闭包,把所有的互相能到达的点都缩起来就可以了。当然你也可以BFS。

如果使用$O(n + m)$的求强连通分量的算法,比如tarjan算法,则时间复杂度为$O(2 ^ m (n + m))$,期望得分19分。

算法二

懂逆元的同学都应该知道模意义下统计一个东西的概率,我们可以先统计出强连通分量数的期望,最后乘上$10000 ^ {n(n - 1)}$的数即可。如果不知道逆元可以参考维基百科。可以算出$10000$在模$998244353$下的逆元为$796898467$。

注意到定向后的图是个有向完全图,即竞赛图,竞赛图的强连通分量缩点之后,一定是一个链状的图,满足每个点和后面的点都有连边。

如何统计答案呢,设这张图为$G(V, E)$,注意到答案即为链的长度,链的长度的统计可以转化为链的前缀的数量减一,这条链的前缀显然就是一个点集$S \subset V$,满足所有的$S$与$V - S$之间的连边都是从$S$中的点连出去的,我们定义这样的点集为割集(只是这篇题解中临时引入的定义),那么我们统计割集数量即可。

暴力枚举所有可能的点集$S$,然后直接计算所有$S$与$V - S$之间连边为$S$连出的概率,最后乘起来。

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

算法三

妈妈我会数学!

对于$m = 0$的情况,大小相同的点集是割集的概率是相同的,对每一种大小的点集很容易计算出该概率以及这种大小的点集的个数,直接统计答案即可。

时间复杂度$O(n)$,期望得分7分,结合前面的算法可以获得49分。

算法四

对于后面的数据,我们发现m比较小,因此最好能想出一个在指数意义上和n无关的算法。

对于一个点集,它是割集的概率无非就是这个点集中的点与点集外的所有点的所有连边都是从这个点集连出去的概率,也就是每条边是连出去的概率乘起来。对于概率非0.5的边我们称其为特殊边,对于大小为$x$的点集,如果其中没有任何特殊边则是割集的概率为$0.5 ^ {x(n - x)}$,如果其中存在一条特殊边,设这条边从$x$连出的概率为$P$,那么这个概率要乘上$2P$,也就是这个特殊边的贡献。我们不妨统计出每个大小的连通块,其中所有特殊边的贡献,最后对每个大小的连通块乘上$0.5 ^ {x(n - x)}$再加起来即可。

一个想法就是枚举有贡献的边的集合,如果一条边有贡献,那么它的两个端点必然有且仅有一个在$S$中,那么我们可以考虑黑白染色,如果染色失败那么一定不存在这种情况,否则我们对于某个连通块,要么黑点在$S$中,要么白点在$S$中,并且每种情况的贡献都容易算出,所以我们通过一个$O(n ^ 2)$的类似背包问题的DP,即可算出每种大小的连通块的贡献总和。

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

算法五

我们发现之前的复杂度在于背包DP上,对什么进行背包DP呢,对每个连通块进行背包DP,等等你说每个连通块?

一个连通块,如果有$m$条边,那么最多有多少个点,$m + 1$个!我们可以对每个连通块直接枚举哪些点在$S$中,然后计算贡献,最后再来一次类似背包的DP。于是这题就被我们愉快的解决了。代码又短又优美,不比19分的暴力要长。

时间复杂度为$O(2 ^ {m + 1}n + n ^ 2)$,期望得分100分。

a^-1 + b problem

By shanquan2

题解By jiry_2

算法一

直接暴力模拟整个过程,逆元可以通过费马小定理用快速幂求,也可以直接用扩展欧几里得求,这两个方法都是单次 $O(\log n)$的。

时间复杂度 $O(nm \log n)$,期望得分 $10$ 分。

算法二

当没有求逆元操作的时候,我们可以直接更新总和:整体加上 $x_i$ 相当于给总和加上了 $n \times x_i$。直接更新就行了。

时间复杂度 $O(n+m)$,结合算法一期望得分 $20$ 分。

算法三

对于集合中的一个数,我们考虑若干次操作之后它会变成什么。显然每一时刻,都存在常数 $a,b,c,d$,使得原来数列中的每一个数 $A[i]$,它都变成了 $\frac{aA[i]+b}{cA[i]+d}$

于是问题就转化成了,每一次给出一个函数 $f(x)=\frac{ax+b}{cx+d}$,求 $\sum_{i=1}^n f(A_i)$。

当 $c=0$ 的时候,我们可以直接求和,因此接下来假设 $c \neq 0$。

首先,我们可以把 $f(x)$ 给表示成 $f(x)=e+f \times \frac{1}{x+g}$,于是我们只需要考虑求原来的所有数加上某一个数 $k$ 后的倒数和就行了。

因为 $\prod_{i=1}^n (A_i+k)$ 我们可以 $O(n)$ 求出,所以我们可以先给答案乘上这个值,于是我们就只需要求 $\sum_{i=1}^n \prod_{j \neq i}\ (A_j+k)$,不难看出这个也是可以 $O(n)$ 求出来的,这样我们就可以避免掉求逆元的 $O(\log n)$ 啦。

当然,这个做法想要拿到 $50$ 分的话需要加一点常数优化,其中一个方法是:我们可以发现本质不同的询问最多只有 $\frac{m}{2}$ 次,所以可以去掉重复的询问。

时间复杂度 $O(nm)$,期望得分 $30$ 至 $50$ 分。

算法四

考虑优化算法三。考虑算法三中 $O(nm)$ 的部分,第一个地方是求 $\prod_{i=1}^n (A_i+k)$,第二个部分是求 $\sum_{i=1}^n \prod_{j \neq i}\ (A_j+k)$。

先考虑第一个地方,我们构造多项式 $g(x)=\prod_{i=1}^n (A_i+x)$,那么第一部分就相当于给出了若干次询问 $k$,求 $g(k)$ 的值。这是一个经典的多项式多点求值问题,可以用多项式除法解决。至于 $g(x)$ 我们可以通过分治 FFT 得到。

第二个地方的处理方法类似,我们构造多项式 $h(x)=\sum_{i=1}^n \prod_{j \neq i}\ (A_j+x)$,那么也就变成多点求值问题啦。不难发现 $h(x)=g'(x)$,所以在求出 $g(x)$ 之后 $O(n)$ 求一下导就能得到 $h(x)$ 啦。

这样我们就得到了一个 $O((n+m) \log^2 n)$ 的算法,期望得分 $70$ 至 $100$ 分。

共 24 篇博客