ARC计划2

ARC090~ARC081
difficult数据来自kenkoooo

只有代码没有解析不代表看不起这题什么的,而是表示只看代码就能看出writer的转化

ARC090到ARC086平均数=2719.6

ARC085到ARC081平均数=2686

(其实perf这东西好像和打出来的总分和有关,所以题目难的时候会偏低,参考价值不高)

ARC090 rk33 perf=3035

ARC090C - Candies:会做

code

ARC090D - People on a Line:会做

code

ARC090E - Avoiding Collision:会做,dif=2282

题意:n点m边带权无向连通图,给定st和ed,统计多少对两点间最短路径$(S,T)$,满足同时正走S和倒走T的两人不会相遇,$n \le 1e5,m \le 2e5$

请先思考后再展开

注意到相遇时一定在L/2处,对于每个S在这个位置唯一计数,分类讨论在点或边上,得到合法的T个数。具体而言,在点上答案为$f_xg_x*(f_{ed}-f_xg_x)$,在边上答案为$f_xg_y*(f_{ed}-f_xg_y)$

code

ARC090F - Number of Digits:会做,dif=2841

题意:给定常数$S \le 1e8$,求$(l \le r)满足\sum_{i=l}^r i的十进制位数=S$

请先思考后再展开

绝杀成功美滋滋,这类细节题做得很小心很慢,而且写得太奔放re、mle好一会

很自然地按开头和结尾的位数考虑,$a*i+\sum_{t={i+1}}^{j-1} t*9*10^{t-1}+b*j=S$

$i=j$的情况只需考虑S的约数,$O(\sqrt Slog)$;$i+1<j$的情况$i,j \le 8$即可,很明显枚举+适当剪枝就能过;

$i+1=j$的情况就是手动拓展欧几里得,$ai+b(i+1)=S,a_0=-S,b_0=S,a’=a+(i+1),b’=b-i$,复杂度为$\sum \frac{S}{i^2}$,肯定能跑,实际写出来跑极限数据本机为0.8s,code

ARC089 rk74 perf=2526

ARC089C - Traveling:会做

code

ARC089D - Checker:会做

code

ARC089E - GraphXY:不会做,dif=2889

题意:构造一张不超过300个点的有向图并指定S、T,边权$\in {[0,100]、’X’、’Y’}$,要求$mindis_{带入’X’=x,’Y’=y} (S \to T)=d_{x,y}$

请先思考后再展开

容易想到用三元组$(a,b,c)$表示经过了a条X边b条Y边且常数边长和为c的一条路径

然后我当时的思路是先考虑只有一种字母,想了个做法,然后感觉没法拓展就自闭睡觉了,现在才发现做法的证明是假的

正解的话,首先考虑下输入的合法性判断,枚举每种路径是否合法(要求$ax+by+c \ge d_{x,y}$)且每种$d_{x,y}$都有能覆盖它的合法路径

发现现在我们无需担心满足这个d会影响其他的d了,只要能把所有路径塞到图里,可以构造两条链(官方题解有图),如二分图一样连边,$O(val^4)$

ARC089F - ColoringBalls:不会做,dif=4221

题意:初始有n个白球排成一排,做m次操作,按时间顺序给出每次操作时手上的颜色是蓝还是红,每次选择一段区间染色或者跳过此操作,并且不能直接把白色染成蓝色,问能得到多少种结果序列,$n,m \le 70$

一开始漏想了蓝色会变成红色的情况,写了个正确率奇高的code

请先思考后再展开

我只想到了$O(n^4m^3log)$的做法,常数不大能勉强跑n=m=50,总之atc上跑过了106/112:code

很容易想到如何判断一个结果序列可达:将白色区域删除得到$t \le R$ 块,记每个块中连续蓝色段数为bi,对于bi=0的块要一个r,其他块需要先rb,再然后$b_i-1$次任意颜色(思考一下发现怎样都能构造出方案)。

枚举A=[bi>0]的块数,B=[bi=0]的块数,然后预处理出此时的括号序分配方案(显然是用掉左边的A个r并且每个往右找最近的一个b,另外尽可能前地找B个r,共计预分配了2A+B个操作)
$$
贪心地按照bi降序处理,pi为第i个r对应的b的位置,p_{A+1}=m
\\
i=1 \sim A,cnt=max(0,cnt+(b_i-1)-[操作序列p_i \sim p_{i+1}没有被预分配中的个数]),最后非负
$$
可以做一个dp,降序考虑蓝色段数=ln的块有j个(因此块数是调和级数),先把j个看做相同的,即多重集排列数
$$
最后ans=\sum dp(0,S,t,cnt \ge 0)*t!*C_{(n-S)+2-1}^{(t-1)+2-1}
\\
dp(ln-1,S+i,t+j,go(cnt,ln,t,j))+=dp(ln,S,t,cnt)*g(ln,i,j)*\frac{1}{j!}
\\
g(ln,i,j)=总体积为i的j个连续蓝色段为ln的块,
g(cc,i+i’,j+1)+=g(cc,i,j)*( C_{i’-1}^{2cc-2}+ 2C_{i’-1}^{2cc-1}+ C_{i’-1}^{2cc} )
\\
go(cnt,ln,st,0)就是cnt被st+1到st+j依次处理后的结果
$$


更好的做法是$O(m^5log)$的(官方题解的整数分拆做法随便把n放到300就gg了):

换一种判断合法性的方法,还是上面说的bi递减的一个序列,每次减掉中间的blu(区间中未预分配的操作数),再加个bi-1,这个过程其实可以转化成,$\forall 后缀i,\sum_{t=i}^A b_t \le up_i$。这个up可以倒推求($up_i=up_{i+1}+blu(pos_i \sim pos_{i+1})+1$),也就是说把cnt换成这个和也是可以的(因此升序考虑ln做dp)

当然此时复杂度还没有优化,但注意到之前记录的总长度S和这个b的和,这两个信息只需要一个就能计算出方案数了(具体地,枚举实际段数=2b-1的块数i,实际段数=2b+1的块数j,剩下的实际块数=2b,但这种块第一个可以是b或r连续段,即$\sum_{i,j} C_A^iC_{A-i}^j 2^{A-i-j} (C_{n-1}^{(2(\sum b)-i+j)+(A+2B-1)-1}+2C_{n-1}^{(2(\sum b)-i+j)+(A+2B)-1}+C_{n-1}^{(2(\sum b)-i+j)+(A+2B+1)-1})$),因此成功省掉了卷积S的那两次循环(不过因为不再是倒着考虑,块数那里常数会变大些,当然,这划得来),code


总结:

做法一并不能因此也得到优化,因为就算不记录S,也还要记录bi的和

可见做法二优越的关键在于它需要的信息,和原本就需要的东西,有一定的重叠

本质关系是「某个变量在变化过程中处处受某个范围的限制」与「$a’=max(a+X-Y,0)$」

感觉第二种更优越的情况应该也是有的,虽然一时举不出来


另外这题好像恰好是2020集训队作业里面的

下面三位都是dp,我是跟myh学习的,有幸比三位都快,另两位做法不太清楚xyxmyhzyy

ARC088 rk18 perf=3001

ARC088C - Multiple Gift:会做

code

ARC088D - Wide Flip:会做

code

ARC088E - Papple Sort:不会做,dif=2303

题意:给定长度为$n \le 2e5$的小写字母串,交换相邻字母,求形成回文串的最小步数

请先思考后再展开

一般位置交换的题目,都是考虑一对点,考虑相对位置发生变化的那次交换,然而这里稍微变形了下我就懵了……


首先,显然对于同种字符,一定是最左边和最右边的配成一对,因此我们分析一对数的交换

[…A…A…B…B…]:无论目标是B还是A在外,都是交换两次,不用管

[…A…B…A…B…]:无论目标是B还是A在外,都是交换一次,不用管

[…A…B…B…A…]:最好能A外

因此这个答案的下界就是,每对AA和BB,满足条件三的,都能满足

而这个下界是可以达到的,就是从左往右扫,碰到在i的人,就把和他一对的另一个丢到n-i+1去(这里的i不统计作为中间那个老哥,另外他的统计方式为,剩下人一半在它左边一半右边,而这些人原本都在他右边)

移动要经过多少人可以用树状数组算,code

ARC088F - Christmas Tree:会做,dif=3010

请先思考后再展开

这题和noip2018D1T3很像,所以做个这样的F踩人很不是滋味

因为这其实就是要选出A条路径,每条长度不超过B,而且每条边必须被恰好一个路径覆盖

那直接设mx=INF跑一次得到最小的A,然后二分B(判断是否与第一次相同,因为随着B减小,最小的A不降)。那第一次和中间每一次,其实都是给个上界,然后满足上面说的条件,最小化用的路径数。那么路径数是第一关键字,上传的链长度是第二关键字,做法就是维护multiset然后每次选最大的找里面能找中最大的,连成一条链,做法正确性相关见noip那题相关题解(我应该没写

code

ARC087 rk42 perf=2644

ARC087C - Good Sequence:会做

code

ARC087D - FT Robot:会做,dif=1500

请先思考后再展开

差点不会做

核心观察:唯一要决策的是方向,而转向的时候不关心现在的方向,所以x和y独立

bitset会更好写,$O(n^2/32)$

code

ARC087E - Prefix-free Game:会做,dif=2438

请先思考后再展开

在熟悉SG、nim相关理论的前提下,快速知道建出Trie后,就是要扫只有一个孩子的节点,然后求某个大小的满二叉树的sg值

显然有$sg_1=1,sg_i=mex_{j=1}^{i} ( \oplus_{t=j}^{i-1} sg_t )$,熟练的选手选择打表试试,发现$sg_i=lowbit(i)$,code

ARC087F - Squirrel Migration:会做,dif=3275

请先思考后再展开

真没想到我能AK全场6人ak的场,虽然因为太困没法考虑时间因素

首先想到,我们只关心分配每个人去哪里,那么就不会有地方空着。这虽然看起来是个废话,但因此我们枚举每条边时,总是希望能让子树内尽量多的人出去,而不需要关心别人进来这种事,即$\sum min(siz_x,n-siz_x)$,尝试能否达到这个上界

此时我先是试图讨论了一番$siz_x与n-siz_x$的大小关系,无果,忽然意识到这是无根树,直接选重心为根,根据$siz \le n/2$的性质,所有人都是$siz_x \le n-siz_x$

问题转化成若干组,每组大小为ai,和为n-1,给每个点分配pi,使得pi=G或pi所在组不是这个组

容易发现能用经典容斥$\sum_S (-1)^{|S|}$解决,发现式子就是$(\sum_S (-1)^{|S|} \frac{ (n-S)! }{ \prod left_t! })*\prod_t a_t!$

直接dp即可,$O(n^2)$,code

值得一提的是个人认为没必要讨论重心的数量啊

ARC086 rk80 perf=2392

ARC086C - Not so Diverse:会做

code

ARC086D - Non-decreasing:会做,dif=1571

不是最显然的做法

ARC086E - Smuggling Marbles:不会做,dif=2818

请先思考后再展开

枚举每种深度做dp,设g表示根无人c表示子树内该深度的点数,$g_x=2^{c_x}-( \prod g_y )( \sum \frac{2^{c_y}-g_y}{g_y} ),ans+=(2^{c_0}-g_{0})*2^{n-c_0}$

将深度放到里面,发现对于某个d,只有不超过一个孩子有状态的话直接继承

和hotel很像,长链剖分,因为还要记录和,只需要特殊处理所有轻儿子涉及到的深度,也就是扫两次即可

因为要求逆元,$O(nlogn)$,如果想优化成线性的话可以考虑初衷是恰一个子树贡献出“有人在根”,加入一维0/1即可

反正都带log就写得比较奔放

ARC086F - Shift and Decrement:dif=inf

做个屁

ARC085 rk32 perf=2861

ARC085C - HSI:会做

阅读理解了挺久

ARC085D - ABS:会做

code

ARC085E - MUL:会做,dif=2593

请先思考后再展开

将点权取反,就是个最大权闭合子图去选出不要的点,code

ARC085F - NRE:太尴尬了,dif=3071

请先思考后再展开

直接对答案集合做dp,然后就会了:只考虑「互不包含」的答案集合,不妨以右端点排序

$dp_i=\min_{j<i,r_j<l_i} c0(l_i,r_i)+dp_j+c1(r_j+1,l_i-1),dp_i=\min_{j<i,l_j \le l_i \le r_j} c0(r_j+1,r_i)+dp_j$

前者随便做,后者发现可以每次对覆盖范围做个min更新,然后查询的时候单点查询左端点

这种单点询问不需要吉司机,标记永久化或直接下传都行,$O(nlogn)$,code

ARC084 rk110,perf=2264

教练我想否认我打过这vp

ARC084C - Snuke Festival:会做

混了个只过这题里面的rk3

ARC084D - Small Multiple:不会做,dif=2540

请先思考后再展开

假设x为答案,则$K|x$,它是可以通过x/10转移过来的,于是我们发现一个值能否成为答案我们只关心其模k的结果

特殊的dp可以转化为图论问题用最短路处理,往这方向想想得到做法:K个点,10K条边($x \to (10x+i)\bmod K,i$)

其实不难看出来这个做法还能进一步优化,每个点只建乘十和加一两条边,肯定也是等效的(能进位不进肯定亏),队列实现$O(k)$,code

ARC084E - Finite Encyclopedia of Integer Sequences:看错题,dif=2804

请先思考后再展开

虽然做法一样不过感觉官方题解思路有点怪

按照第一个分k组,每组个数一样,k是偶数时总数为偶数,答案就是这一组最后一个即$k/2,k,k,k,…k$,当然也能打表观察法

k是奇数的话,答案肯定在$\frac{k+1}{2}$那组,显然就是$(k,n-1)$这个子问题的答案或答案的前一个

$ans(k,1)=\frac{k+1}{2},ans(k,n)=[\frac{k+1}{2}][n\&1?ans(k,n-1):left\ of\ ans(k,n-1)]$,code

复杂度虽然很明显还是稍微说明吧,就把空位当做0,几乎就是大整数在–,k=2已经线性,更大的k只会让常数更小

ARC084F - XorShift:不会做,dif=3443

题意补充:线性空间是无限大的,X只是限制了要输出的范围,记$m=4000$

请先思考后再展开

只想到了$O(n*m^3/32)$的做法:直接把nm个数塞线性基里面,二分k,判断就是要求第k大,code


核心观察:位移跟异或这两种操作的组合,可以简洁的记作两个二进制数的乘法(加法指异或),A是B的倍数等价于存在$C*B=A$;而$ax+by$的集合显然是等价于$ax+b(y-x)$的集合的(a和b是形式上的系数),而这很像辗转相减,我们不妨定义它为gcd(名字并不重要,因为不代表满足辗转相除),于是可以$O(n*m^2/32)$求出n个数的gcd,于是把n个数的问题变成了1个数

剩下就很容易了,高位起$z=|mx|-|gcd|+1$个位都是随便填,然后后面的位是根据前面填的情况唯一确定的,因此答案就是$mx的高位起z位组成的数+[前面z位和mx一样时,后面得到的方案是否不超过mx]$,code

ARC083 rk39,perf=2775

赛后才开始码F,过的时候比赛已经结束30min了,码的时候是一直在想怎么写得更简洁(我感觉从过E开始计,且忽略各种与OI无关的杂事,好像比当场过题的所有人还快一丁丁,听起来还是挺振奋人心的)

不过整体来看,我觉得即使我应当做到更快,感觉也很难快30min这么夸张,所以那两个AK的是真的恐怖

ARC083C - Sugar Water:会做

阅读理解了一万年

ARC083D - Restoring Road Network:会做

code

ARC083E - Bichrome Tree:会做,dif=2290

code

ARC083F - Collecting Balls:会做,dif=3678

题意:在$[1,n]\times[1,n]$平面上有2n个不重叠的球,求有多少个2n的排列能把所有球拿完,其中a表示x=a直线上拿走y最小的一个球,n+a表示y=a直线上拿走x最小的一个球,$n \le 1e5$

请先思考后再展开

刷新了“会做”里面的最高dif,撒花,但不可否认的是基环树相关的题挺泛滥的

肯定要转化,第一个想到的是二分图,感觉没有原本的模型那么直观,但想想好像也没有更好的转化模型,所以就深入想了想。每一个球就是一条边,将无向图按照是哪个点取走了它定向,这样每个点恰一个入度,就是一个基环内向树森林。

所以对于每个基环树考虑边的方向的两种情况,对于节点x,所有x指出去的点,如果比指向x的点小,则必须比x先出现。在基环树上,这种边一定是原图的子图且方向相反,即唯一出度,因此一定是树(想想就知道不会是基环树),每个点是子树中最小是个经典模型(见套路集锦)

用了点小技巧,应该真的很简洁了,随便看看网上题解都是臭长

ARC082 rk61,perf=2657

赛后10min过F好评!主要是写法有点问题,纠结了半天,然后即使不考虑E,D也因为想偏了,慢正常人10min+

ARC082C - Together:会做

code

ARC082D - Derangement:会做

code

ARC082E - ConvexScore:会做,dif=2908

题意:给出平面上不重叠的$n \le 200$个点,求$\sum_{点集S是凸多边形} 2^{凸多边形包含的点数(包括边界,但不包括顶点)}$

请先思考后再展开

这道题是一年多前的栋老师出的题,然后当时的mld想了个n四方:
把每个凸包用最下面的点表示(多个则最左),然后极角排序后,跑一个dp,记录内部点的数量(暴力预处理三角形内点的数量)

然后三方怎么做我是完全不记得了,反而对四方的有点印象——凸包相关,然后直接造成这次想了半天……

唯一记得的是当时觉得这三方做法真的是人能想得到的吗,现在想想其实只是当时的我的实力限制了想象力,跳出凸包后很快就 想到了:相当于把每个面积为正数的点集,从其凸包唯一计数了,因此答案就是正面积点集数,$O(n^3)$,code

ARC082F - Sandglass:会做,dif=2512

code

ARC081 rk30,perf=2872

F忘记判一列那种情况(当时是先感觉一行可能有问题,但没有,哦那不管了),浪费了2发罚时+10min=20min=排名可以到13=perf到3123=让后面五场的perf比前五场高,差距极大.jpg

ARC081C - Make a Rectangle:

code

ARC081D - Coloring Dominoes:

code

ARC081E - Don’t Be a Subsequence:

看完题开始写,全场第六个过的,单题速度一眼看去有可能是最快的

不过代码写得还是麻烦了

ARC081F - Flip and Rectangles:

请先思考后再展开

网上都是比较不直接的结论做法,然后也有一两个非结论做法,这里也是一个非结论做法,本质应该也差不多:

枚举每一行作为起点,枚举这行是否翻转可以得到每列如果在答案中是否需要翻转。每列是否翻转确定后,一个矩形作为答案的条件就是每一列经过前面说的唯一翻转后,每一列完全相同。那优化方法很多,我考虑的是预处理出相邻两列在4种翻转情况时,哪些行的那两个是不同的。这样每次踢掉没用的头后,可以把变化时间点按递减排序,然后从下往上用并查集合并,并且用最大集合大小更新答案

通过一些计数排序之类的技巧可以优化到$O(n^2)$,$O(n^2log)$-code

完结撒花!

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/b27dc4f4.html
转载请注明出处,谢谢!