UOJ Logo jiry_2的博客

博客

UOJ Test Round #2 题解

2017-01-08 20:13:52 By jiry_2

直播看着看着发现题解还没写,反正题目比较简单,我就随便写一下题解然后就接着去浪吧。

P.S. 写好一句话题解被吕老师叫回来重写了,伤心到变形。

感觉这一套题虽然总体难度不大,但是细节比较多,套上捆绑还是比较恶心的..而且验题的时候感觉样例比较弱(造题的不是我我不背锅)

看了一下榜感觉这个难度挺兹瓷的?以后就按照这个出吧。

题目排列顺序

from jiry_2,数据 from cy

算法一

聪明的你肯定发现了把所有位置按照权值第一关键字升序,下标第二关键字降序排序,依次分配 $1$ 到 $n$ 这 $n$ 个数就直接 work 了。

咦我好像不会排序那怎么办办呢?只好写个冒泡排序了。

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

算法二

哇我好像知道一个叫做 std::sort 的东西耶,赶紧来试一试吧。

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

题目交流通道

from jiry_2,数据 from SkyDec

算法一

先来考虑 $d_{u,v}>0$ 的情况。

对于边 $(u,v)$,我们先来看是否存在一个点 $k$ 满足 $d_{u,v}=d_{u,k}+d_{k,v}$,如果不存在这样的 $k$,那么这条边的权值就只能是 $d_{u,v}$,否则这条边只要大于等于 $d_{u,v}$ 就可以了,即有 $K-d_{u,v}+1$ 种方案。把所有边的方案乘起来就可以了。

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

算法二

考虑边可以等于 $0$ 的情况,这时 $d_{u,v}=0$ 的边肯定在图中连成了若干个团。我们把每一个团给缩起来。

两个团之间的点对距离一定是相等的,考虑团与团之间的边,此时相当于有重边的 $d_{u,v}>0$ 的情况。假设这是一条 $a$ 重边,如果存在 $k$ 有 $d_{u,v}=d_{u,k}+d_{k,v}$,那么所有边只要大于等于 $d_{u,v}$ 就可以了,即有 $(K-d_{u,v}+1)^a$ 种方案。如果不存在,那么至少要有一条边等于 $d_{u,v}$,其他边都要大于它,即有 $(K-d_{u,v}+1)^a-(K-d_{u,v})^a$ 种方案。

考虑团内部的边,每个团肯定由 $0$ 的边连成了一个联通块,这是一个经典的容斥,令 $f_i$ 为 $n$ 个点的距离为 $0$ 的团的方案数,$g_i$ 为 $n$ 个点的图的方案数。则有 $g_n=(K+1)^{\binom{n}{2}}$,$f_n=g_n-\sum_{i=1}^{n-1} f_i \times g_{n-i} \times \binom{n-1}{i-1} \times K^{i(n-i)}$。

把所有部分的答案乘起来就好了。时间复杂度 $O(n^3)$,期望得分 $100$ 分。

当然最重要的是要判对无解的情况,大致有四种,分别是 $d_{i,j} >K$,$d_{i,i} \neq 0$,$d_{i,j} \neq d_{j,i}$,$d_{i,j} > d_{i,k}+d_{k,j}$,大力 check 一下就可以了。

题目难度提升

from jiry_2,数据 from cy

这道题还是挺简单的,本来是出给 hiho 的 A 题,后来感觉有点难了(其实是最开始想简单了)就出 UR 了,感觉主要难度在于细节稍微多了点。

算法一

按位枚举,判断合法性只需要把后面所有的数升序排序然后检查一下就可以了。

直接裸写时间复杂度 $O(n^4)$ 已经够了,期望得分 $20$ 分。

算法二

考虑没有相同的数的情况。那么这个时候假设中位数是 $m$,新加入的数是 $a$。如果 $a < m$,那么中位数减少;如果 $a > m$,那么中位数增大;否则中位数不变。

按位枚举,一个前缀有解当且仅当前缀的中位数 $m$ 小于等于所有还没有放的数。

最开始先放最小的数,每一阶段放两个数进去。阶段开始时因为有奇数个数,所以中位数一定落在某个数上。

假设开始时中位数是 $m$,大于 $m$ 的第一个还没有放的数是 $K$,如果 $(m,K)$ 中已经有数放了,那么这个数不管放什么都可以,直接放最大的数就可以了。否则新放入的数 $a$ 一定要满足 $a+m \leq 2K$,即 $a \leq 2K-m$,令 $R=2K-m$。如果 $(m,R]$ 中已经有数放了,直接放最大的数就可以了,否则找到 $(m,R]$ 中最大的数放进去即可。

假设此时中位数是 $M$,大于等于 $M$ 的第一个还没有放的数是 $L$,如果 $(m,L)$ 中已经有数放了,那么直接放最大的数,否则就只能放 $L$ 了。

可通过第 4 个子任务,结合算法一可获得 $50$ 分。

算法三

有相同的数其实也不难。令所有数的中位数是 $m$,如果小于等于中位数的数中没有重复出现的数字,那么算法一仍然适用,否则令 $R$ 为第一个小于等于 $m$ 的重复出现的数字。

那最开始两个数最大字典序的情况一定是两个 $R$。因为如果更大的话中位数就没机会落在重复数上了,这时就满足算法一的性质,然而最大的数还没有放,所以无解。

放了两个 $R$ 后接下来就可以贪心了,每次放一个最大的数和一个小于等于 $R$ 最大的数,这个时候中位数在两个 $R$ 中左右横跳,一直没有变化,直到小于等于 $R$ 的数都用完了。这时就回到了算法一的情况,接着用算法一就可以了。

如果暴力实现的时间复杂度 $O(n^2)$,期望得分 $40$ 分。

可以发现所有的操作都是可以用 set 方便的做到。时间复杂度 $O(n \log n)$,期望得分 $100$ 分。

后半部分直接按位枚举也是可以的,稍微优化一下可以做到 $O(n \log^2 n)$ 或者 $O(n \log n)$,细节会稍微少一点。因为要降难度,所以也没去卡 $O(n log^2 n)$ 的做法,感觉还是比较良心的。

暂别

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

jiry_2 Avatar