NOIP2016 Day1 天天爱跑步 题解

第一次出题好激动啊,这题是我在军训时候开脑洞想起来出的,其实一开始题目比这个难,但是我发现我做不出来了。最后经过多次迭代题目变成了这个样子。这个解法是某次ddl干不完于是去厕所冷静一发想出来的。

首先是求出来每条路径的LCA,倍增或者Tarjan都行。接下来路径变成向下和向上的路径。

先考虑向上的路径。对于节点$j$的$W_j$,只有起点距离$j$为$W_j$的路径可以被观察到。所以对于起点$S_i$,只有$deep[S_i] = deep[j] + W_j$的时候才能被$j$观察到,这样对于每个询问问题就成了:子树中有多少路径起点的深度值为$deep[j] + W_j$,且这个路径经过自己。这是个经典的离线问题,首先可以DFS一遍求出DFS序,之后一颗子树在序列上是连续的,所以相当于问一个区间有多少值为$deep[j] + W_j$,从左往右扫描一遍即可。记$pre_i$为DFS时初次访问节点$i$的dfs序,$suf_i$为退出节点$i$时的dfs序,再记录一个数组$a$,那么离线起来有这些事件:

  • 对于一个$W_j$,在扫描到$pre_j$时候记录下$a[deep[j] + W_j]$的值;扫描到$suf_j$的时候再记录下$a[deep[j]+W_j]$的值,两次做差就是$j$观察到人数
  • 对于一个向上的路径,起点为$S_i$,终点为$T_i$(这里的$T_i$是LCA不是原题的$T_i$),在扫描到$pre_{T_i}$时, 给$a[deep[S_i]]$加上1;扫描到$suf_{T_i}$时,给$a[deep[S_i]]$减去1。
    类似的,对于向下的路径,有$W_j - deep[j] = total_len - deep[T_i]$,其中$total_len$为路径的长度。之后可以用类似的算法做出来。

 

比赛的时候有个小插曲,当时我们班组织在圆明园玩,突然微信群上看到说我题目样例描述有问题…

ymy

还有天天小朋友长这样:

tt

以及我阿甘快刷不完了

冬天的圆明园还不错

noi2015-杭州游记

noi之前

我们提前来了几天跟着学军的大爷们一起集训,每天都处于被虐的状态。

报到日

因为之前一直住在学军附近宾馆,所以我们并不怎么着急,就是搬了个地方。下午的时候遇到了外语的小伙伴们,和安一的那个妹子。

到了寝室发现被分到了女寝,然后被寝室的画风吓傻了,乡下人没见过世面。还在墙上发现了某个鬼畜的树。之后就是翻一翻柜子看看会不会有妹子留下的什么奇怪的物品,雾

领物品的时候打开包发现真的给我发了粉色衣服,然后激动的拿了出来,被负责迎宾的妹子笑了一番QAQ。然后不知道什么缘故,夹心选的粉色衣服并没有给他,他表示相当气愤。

开幕式、笔试

开幕式上最大的感触就是“别人学校的妹子”。不得不说学军的妹子真的多才多艺。dzd像往常一样继续表示noip取消保送是CCF和教育部斗争的结果,但是大家的热情并不减之类的话。又说noi人数创新高,比去年多一人,似乎去年也是这么说的,CCF真机智啊,这样就可以实现每年NOI人数持续增长。C、D类的人数似乎还感受到了外快也创新高了

下午笔试,发现还是99分,并不知道哪里错了,和去年似乎一样。

下午的时候和rbw一起去操场转悠,遇到了两个妹子,操场上就我们4个人,不太好意思躲开就去要了QQ。发现里面其中一个人是mjy,看了她的成绩后被吓傻了,还是初三,感觉妹子这么厉害还怒虐男选手。

day1

不太明白为什么要在门口排队进,感觉这样还是很挤啊。

翻开题目被吓了一跳,卧槽这画风不对,没有提答,CCF想干嘛。看了第一题画风更不对了,似乎是个真·普及难度?我又读了几遍题还是不敢动键盘。第二题看了后感觉又不对了,树剖裸题?要干嘛?第三题看完之后觉得不会,可以玩4个小时第三题。为了吸取数次比赛跪的教训,最后再写数据结构题。不过中间剩3个小时的时候觉得保险还是去给前两题写了。此时t3并没有什么进展。最后YY了一个70分的算法,感觉自己代码能力有些坑,剩40分钟才搞完。测了一下给的样例对了,又跑了一下200\300的点,都能跑出来,最后试了一下500,发现卧槽0.4s就可以出解,是我常数压的小的缘故吗?

成绩出来后梦迪300分,我也是300分,感觉不错,真·暴力出奇迹。

下午讲题的时候第二题出题人被婊的好惨,第二题有200+人AC,出题人表示如果去看一眼BZOJ就不会发生今天这个情况…

社会活动日

先去阿里听报告,在路上导游介绍的时候我一直在玩马云不会写代码和支付裱这个梗…报告其实是从其他地方贴来的PPT换了封面,感觉应付一批一批的来听报告的人也是蛮辛苦的。

之后去西溪湿地,在车上的时候勾搭到了负责河南和贵州的妹子,她们原来是新高一的,随身还带着王后雄,感觉好厉害,感觉这预示着我NOI药丸,要回去高考。

在西溪湿地有个寻宝活动,但是可能我们走的比较慢的缘故,只发现了一张谢谢参与。不过这个似乎比河北他们拿到10张谢谢参与要强233333333。感觉西溪湿地的景色挺不错的,志愿者妹子也不错:)。玩到下午突然下起了雨,把我们都打散,学军也决定不去湿地博物馆了。在返回出口的电瓶车上和mjy坐到了一起,被吓得到处在爬。我们返回的时候发现车队停在了钉子路口,三个岔口路边都是车,并不知道哪辆是返回的车,3个方向都找了一遍才找到车,好感人。

回去之后跑去宾馆,洗澡的时候累的站不稳了,差点晕倒,感觉我的体质也是药丸。

day2

早上4点就醒了,床上翻滚了一个小时后去上个厕所就彻底睡不着了,

恩,直接让我们进了,没有排队,可能因为去的比较早的缘故并没有感觉挤。

翻开题目,没有提答,但是两题都有部分分,感觉不对劲。发现t1似乎K=2的时候把高度作为第二个键值建哈夫曼树做就行了。敲了以后发现对于其他情况似乎只要根节点儿子满了之后也是正确的,一直在想存在不存在一种调整方案,但是并没有想到。

t2似乎没有部分分,应该是作为送分题出的吧,想了想感觉把串反过来变成后缀,之后利用后缀自动机每个节点的性质做是裸题?其实后缀自动机我仅仅停留在看懂证明的状态,其他性质全是背下来的TAT,但是发现这些性质正好够用。后缀自动机的每个节点表示一类最后一个位置集合相同,suflink还构成了一棵树,得到这个集合大小后,可以直接搞出计数。对于最大值可以维护最大,次大一类的不断上传就行,大概是个树形DP。不过似乎用全是a的数据就会卡爆栈,改成非递归的才放心。

最后一题,感觉前两问可以dp做,最后一个似乎是网络流模型。但是我比较傻逼前两问并没有敲出来…而且那个网络流我似乎也不知道怎么写,感觉并不可惜。

萌帝230,我60+100+12(卧槽还对了一些点),感觉au要悬。

讲题时出题人怒婊全场,表示昨天出t2被骂很不爽。我当时觉得考跪,就没有心情上去正面刚。t1似乎直接补0就可以解决不满的问题了,t3那个网络流是有下界最小流。

最后知道分数线整个人都跳起来了,竟然这也能au。之后梦迪去了pku,我去thu了。

鬼畜运动会、闭幕式

运动会的时候大家表示都不太想来,最后我、萌帝、ztx、nh组了一队,玩的比较欢脱。那个毛毛虫竞技我们配合不好,之后我和萌帝就轧马步跑了过去,感觉规则并没有说必须要跳。反正最后很开心就对了。

闭幕式的时候wh说道这次比赛考查了并查集…的时候,大家一阵鼓掌,感觉NOI要变成noip普及组+数据结构专场。

吐槽一下,那个牌子的做工并没有去年深外的做工好。

不管怎样,高中生活就在最后一次NOI中结束了,感觉自己突然获得了一年自由的时间并没有什么想象的那么激动。我还没想好要怎么规划好这一年,毕竟真的玩一年不是特别好的样子。

Codeforces Round 310 (Div. 2)

我脑子里全是草泥马…

A. Case of the Zeros and Ones

题意:给你一串01串,每次可以选择一个”0”和一个”1”消掉,问最后长度最短是多少。

串的长度减去0或1最小的数量的2倍就行了。

B. Case of Fake Numbers

题意:有n个数$a_0, a_1, …, a_{n-1}$,问是否存在一个$k$,使得满足对于所有的$i$,有$a_i + (-1)^{i}*k mod n = i$。

显然求出来对于$a_0$的$k$,之后判定一下是否全部满足就就可以了。

C. Case of Matryoshkas

题意:有n个套娃,之后有一些已经放在桌子上嵌套在一起了。问把n个全部套在一起需要几次操作。(对于几个套在一起的如果分开只能从上方拿掉一个!差不多类似放在桌子上然后只能一个手操作。)

模拟吧,对于1开始有序的那部分不用拆开,其他都要拆。这个题意我看了好长时间才看懂TAT

D. Case of Fugitive

题意:每个小岛在轴上是一个区间,然后有一些距离确定的桥,问是否存在一种桥使用方案使得相邻的岛之间有桥。

把相邻的岛可以接受的桥的长度搞出来,之后相等于一群区间是否有方案使得每个区间覆盖一个不同的点。区间左端点和桥一起排下序,贪心匹配一下就行了。

E. Case of Chocolate

题意:有一个n*n的巧克力,之后从左下方到右上有一条对角线,对角下方已经被吃完了。现在有一些询问,每个询问给一个对角线上的点和一个方向(上或者左),从这个点开始朝着给定方向吃,吃到空格子结束。问每次可以吃多少个格子。

考虑向上吃对向左吃的影响,反之一样。可以发现每次向上吃完之后,可能影响的是吃的这个区间的点。而每次求向左的方案就相当于求最近的上。离散化一下用线段树实现区间更新最大值,单点求值即可。


我脑子里全是草泥马…不要问我为什么E没有过…

然后大家似乎FST的很欢脱….我下一场就可以打div1了好开心…

考前划水系列

好长时间没有写记录…感觉没有压迫感。

6.15

BZOJ 2069: [POI2004]ZAW PoPoQQQ大爷的题解 非常神奇的一道题。问题相当于从1号节点走到一个相邻节点,之后再不经过这条边走回1号节点。把这样一条路径的第一个不是1的节点记为$s$,最后一个不是1的节点记为$t$。这样就成了找一对$s,t$使得$len(1, s) + cost(s, t) + len(t, 1)$最小。去除1号节点,把点集分成两部分$A$和$B$,对于在$A$的节点$i$,其起始值为$len(1, i)$,之后做一遍dijkstra,所有$B$集合内的点$i$,可以更新答案$ans = min(ans, d[i]+len(i,1)$。这样如果每对点都不属于一个集合中做过一次最短路,就可以求得答案。对于$i$和$j$,$i \ne j$,则一定有一个二进制位不同,所以枚举二进制位,每次把这一位为1的分为一个集合,0的分为另一个集合,做一遍最短路。
查看代码

BZOJ 2525: [Poi2011]Dynamite 膜PoPoQQQ大爷的。首先肯定二分时间$T$,之后计算最小需要的点燃点的数量,验证之。处理出每每个点$i$儿子中,距离最远且有炸弹的点的距离$deepest_i$,以及从$i$点出发最远可以点燃的距离$down_i$。然后就比较显然了,看代码

BZOJ 1117: [POI2009]救火站Gas 之前做过一次,之后WA某个点弃疗了。树形dp,和上题区别是这个每个点有数量限制。维护救火站到达点$u$以后,还可以救火最大距离为$i$时,能救的点数量$have_{u,i}$。维点$u$距离为$i$的点,还没有被覆盖的点$need_{u,i}$。对于当前维护的点$u$,$i \ge j$,$have_{u,i}$和$need_{u,j}$可以抵消掉,即选择一部分救火站去覆盖点。当$i = j$的时候,一定要抵消掉,否则向上传递后,需要救火的的距离变远,而覆盖的范围变小,变的不合法,如果此时从其兄弟或祖先来救自己的话一定不会更优。对于其他的即使向上传递后也合法,那么暂时不考虑,让传递上去。当然对于$have_{u,i}$和$need_{u,i-1}$向上传递也会变得不合法,不过要等所有$have_{u,i}$和$need_{u,i}$抵消完之后才可以抵消这个(YY证一下这个吧,对着数据调出来的结论)。之后就是各种细节了,看代码


6.16

BZOJ 3203: [Sdoi2013]保护出题人 可以发现对于每个僵尸$i$都要满足$y_n \ge \frac{\sum_i^n A_i}{x_n + (n-i)_d}$。相当于求后面那个东西的最大值。把每个僵尸转化成一个点,$x$坐标为为$\sum_i^n A_i$,$y$坐标为$x_n + (n-i)_d$。这样可以发现,答案是过原点与某个点的斜率最大值。一定在上凸包上,而且往前面新加入点相对位置不会变,这样维护凸包就比较方便了。之后三分求答案。不过注意这个输出的时候,直接printf保留0位小数即可,转化成long long再输出来会崩。
查看代码


6.17

BZOJ 1122: [POI2008]账本BBB 先考虑不进行移动操作时方案,如果需要把“-”变成“+”,那么一定把序列前面一部分“-”变成“+”,这样后面所有可能为负的地方值都会加2。如果需要变成“-”,则一定在最后变。之后前缀和最小的地方如果非负后,那么一定整个序列一定合法了。对于有移动的时候,快速找到最小值可以用单调队列来做。查看代码

BZOJ 1127: [POI2008]KUP 构造题。先处理每行,看看是不是有符合条件的一段(矩形的宽为1)。之后如果没有的话,把大于2_K的点设置为障碍点,再找一个矩形的和大于K的。这个矩形和如果大于2_K,就减去一行,一直减到符合条件位置。因为处理过每行了,所以每次减的一定小于K,所以正确。查看代码


6.20

端午节快乐

BZOJ 2081: [Poi2010]Beads

枚举$k$,之后hash判重就可以了。从hzwer那里看到一个优化,对于反向的串不必插两次,而是把正向和反向的值乘起来。(其实我一开始不仅插两次而且怕冲突双hash了)

BZOJ 2082: [Poi2010]Divine divisor

题太神了。第一问其实是求质因数分解的最大指数$k$。第二问有$cnt$个$p_i^{k_i}$的$k_i$与$k$相同,答案是$2^{cnt}-1$。

可以把每个数小于$10^6$的质因子搞出来,剩下的要么是一个质数,要么是一个质数的平方,要么是两个质数相乘。判断质数可以用miller-rabin做,两个质数相乘可以互相求gcd来找。如果还没有找到那么肯定是两个质数相乘且没有再其他数里面出现过(注意要判读两个数是否一样)。

附上Matrix67的miller-rabin算法介绍,(我整篇文章其实在关注的是Matrix67的素妹子,原来早在很久以前就存在虐狗行为了。我的miller-rabin的a只取了2和3,结果没有卡。这题感觉细节特别恶心,而且最后还需要高精度!

感觉给main函数炸掉了TAT。查看代码


6.22

BZOJ 2083: [Poi2010]Intelligence test

一开始用的方法是利用st表的方法,记录后面$2^k$个和自己一样的数字的位置,再倍增找。BZOJ上莫名T掉,交到main上爆内存。看hzwer的题解觉得自己傻逼了,可以为每个数字开一个数组,记录这个数字出现的位置,之后二分即可。

BZOJ 2084: [Poi2010]Antisymmetry

manacher改变一下即可。不过注意这个需要对于不是’*‘(分隔符)的位置直接跳过不处理。因为如果某个不是分割符号为中心作为“可以覆盖到最远回文串”,则会导致复制过来的len出错,中心字符是无法“对称”的。

BZOJ 2085: [Poi2010]Hamsters

看到数据后突然有些似成相识,我是不是在哪里做过这题@cstdio。

可以预处理出来一张图,对于$i->j$的长度为$len(str_j) - i,j重合的长度$。之后$f_{i,j,k}$表示$i$到$j$走$k$条边的最短路,直接dp显然不行,可以发现这个是“符合结合律”的dp,直接倍增。

**BZOJ 2086: [Poi2010]Blocks

数据范围显然要求做到一次询问在$O(n)$完成。对于每个询问,处理一个sum数组,其中sum[i] = sum[i-1] + a[i] - K。接着对sum数组处理一个单调递减序列。之后从后往前,尝试求每个位置作为子序列结尾的最长长度。显然满足一段序列$[l,r]$符合条件的要求是$sum_r - sum_l \ge 0$。如果处理的过程中某个位置的sum值比之前(后面)某个值还要小,那么显然不可能成为答案。这样选择作为左端点的点在单调队列中的位置是只会向左移动的,用个指针维护左端点在单调队列中的位置即可。

查看代码


6.25

BZOJ 2087: [Poi2010]Sheep

对着别人代码抄的,不过比想象中简单。预处理出每条边是否可行,即是否把分成两部分都是偶数。只关心是不是偶数就行了,这样一定是合法的。之后是一个dp,用$f_{i,j}$表示从第$i$个点到第$j$个点连线时构成的方案数,答案为$f_{1,n}$,转移方程如果$i$到$j$的连边合法,那么$f_{i,j} = sum_k f_{i,k}*f_{k,j}$,否则为0。

查看代码


6.26

BZOJ 2088: [Poi2010]Teleportation

1到2的距离必须大于等于5,那么先假设最后求出来正确答案了,之后再做出来分层图,而且可以得结论:

  1. 如果最后答案1和2号点不连通,那么结果一定是1属于一个完全图中,2属于一个完全图中。
  2. 如果连通的话,那么层数一定等于6,更少的话不符合题意,更多的话可以合并一些层获得更优解。
  3. 如果连通的话,第一层和第六层一定只有一个点,分别是1和2,否则的话可以把第一层和第六层的点分到二、五层,解不会更差。
  4. 如果连通的话,那么第二层和第五层只会存在“在初始图中与1,2相邻的点”,否则可以把他们分给第三、四层,解不会更差。(1或2不存在邻接点时候显然直接按第1中情况算不会更差)
  5. 如果连通的话,继续按照结论3、4的思路,其实可以发现距离1为0,1,2的点一定在一、二、三层;距离2位0,1,2的点一定在六、五、四层中。剩下的点一定可以构造选在三、四层中,而且解不会更差。那么剩下如果二层点比五层的点多,那么放三层更优,反之放在五层最优。

之后统计答案就行,然后我讨论了这么多,代码似乎比别人长一些。不过1A,爽!

查看代码

BZOJ 2091: [Poi2010]The Minima Game

先排序,之后记$f_i$表示第$i$个数以及之前的一个子局面的最优值。可以发现一个人如果选择的话一定选择后一段。可以反正其正确性:如果有空隙的话,后手可以补上,而且获得的分一定不低于先手,此时先手可以还获得剩余局面的最优分,但其实一开始可以直接选择获得剩余局面最优分的方案,再给后面一段带上去,这样一定不会更差。

之后dp方程为$f_i = max(f_{i-1}, a_i - f_{i-1})$,相当于枚举这个点属于新的一段或者归上一段。

查看代码

感觉poi2010剩下的题要不然不想做要不然就是太神,不太想玩了,弃坑弃坑,以后有机会慢慢玩。

CF Round 309 Div2

趁fst前先更blog

A. Kyoya and Photobooks

题意:给你一个字符串,长度小于等于20。问在字符串中任意一个位置插入一个字母,有多少种字符串。

随便搞一下就行。

B. Ohana Cleans Up

题意:给一个01矩阵,每次可以把一整列取反,可以操作任意次,问有最多几行完全为0。

显然操作影响所有行,如果一行变为全0那么只有和这行一样的才可以全0。

C. Kyoya and Colored Balls

题意:有$k$个数字,数字$i$有$num_i$个,一个合法的排列要求最后一个数字$i$的位置一定比最后一个数字$i+1$的位置靠前。

求出来总共和为$n$,可以发现最后一个位置一定是$k$,然后把剩下$num_k - 1$扔到剩余$n-1$个位置,接着求$k-1$的答案填补进去。所以方案数为$f(k,n) = C(n-1, num_k-1) * f(k-1, n-num_k)$。

D. Kyoya and Permutation

题意:给一个1至n的排列,求出其置换表示法,接着去掉括号,如果!@%$@$#&…细节太多自己去看原题。

理解错题意了,不知道是不是div1不发通知只有div2发。可以发现符合条件的序列第$i$个位置为$i$或者与$i+1$交换,最多交换一次。递推式发现是fibonacci数列,可以类似二分的从前往后构造下去就行了。

E. Love Triangles

题意:有$n$个节点的图,任意两点有边,边的颜色可以使红色或者黑色。一些边的颜色已经给定。求满足:任意3个点构成的三角形只有1边是红色或者3条边都是红色。

看上去挺厉害,感觉自己计数题自己有点傻逼,就在那里想啊想,然后发现还是不会统计。剩15分钟的时候突然卧槽,发现自己傻逼了。

可以发现如果已知一个点与剩下所有点之间边的颜色,那么图是确定的,所以不妨记每个点颜色为与1点的边的颜色。

对于一条红边可以确定两个点颜色一定一样,对于一条黑边可以确定两个点颜色一定不一样。先用并查集把第一个连通块缩点,接着对于一条黑边在表示两个连通块之间点连边。记连通块个数为$cnt$。二分图染色,看看是否合法,如果不合法答案为0。合法的的话一个连通块颜色有两种,但是1号点所在连通块颜色固定(其实是没有颜色),所以答案为$2^{cnt-1}$。

我再讲一个有趣的故事,写完代码后发现比赛结束1分钟了→_→。

做题记录4

大概好久没写blog了,这么多天的一下补完吧。

BZOJ3991: [SDOI2015]寻宝游戏 可以发现最短路应该是按照有宝物的点的“轮廓”走,会发现其实dfs序就是按照“轮廓”走的。所以把全部点按照dfs序扔进set,直接维护即可。(我想要强行维护虚树是不是没救了…

BZOJ3990: [SDOI2015]排序 可以发现每种操作方案操作执行的顺序不一样也可以,而且每种顺序操作位置是唯一的,这样如果知道这类方案总步数为$s$,那么这类方案对答案的贡献为$s!$。对于两类不同的方案,是指都按照$1$到$N$顺序操作,存在某个操作两个方案执行的位置不同。既然每类操作顺序无关,可以从第$1$种操作考虑选不选,或者操作位置在哪。选择方式也很显然如果第$i$类操作后,把数组分成$2^i$段,每段是连续的即为合法操作。仔细分析后发现对于当前数组最多有2种操作位置(比如说”1 4 3 2”有两种方式),所以递归时最多有$2^N$种情况,每层递归需要扫描一遍数组。总复杂度$O(2^{2N})$。

BZOJ3992: [SDOI2015]序列统计 神题!最裸的dp显然可用$f_{i,j}$表示选择了$i$个数字模$M$时乘积为$j$的方案数,复杂度$O(nm)$。转移可以用矩阵做,快速幂加速,复杂度$O(m^3\log n)$。自己重新定义矩阵的“乘法”,即直接将两个数组乘起来$ret_k=\sum_{i+j=k}a_ib_j$,复杂度降为$O(m^2logn)$。最厉害的是分别把下标用$G^k \mod M$表示,其中$G$为$M$的原根,$G^k$构成了简化剩余系。这样$ret_{G^k}=\sum_{i+j=k}a_{G^i}b_{G^j}$,直接用指数来替换原来的下标,这个时候是卷积的形式,FFT加速,总复杂度为$O(m\log^2n)$

BZOJ3676: [Apio2014]回文串 嗯,直接用回文树来做吧,回文树讲解。恩…我不太会构造奇偶串的情况,就直接加分隔符,统计的时候注意下是不是分隔符。我不太理解用hash怎么统计出现次数。

BZOJ4003: [JLOI2015]城池攻占 树链剖分然后在线段树上倍增,还是T掉了,本地造数据似乎只慢了2~3倍的样子,也不知道是不是哪里虚掉了。还有一种做法是离线,接着每个节点维护一个可以攻占到这个节点的将军的堆。选取此时战斗力最小的测试是否会被干掉。每个节点的堆可有由儿子节点合并而来,注意每次向上走一步对于堆内全部节点的战斗力影响是一定的,所以可以打lazy标记。学习了左偏树(想起了大叔的话:左偏树应该是最好写的数据结构了吧

BZOJ4002: [JLOI2015]有意义的字符串 欺负我没有上过高二…

2015-6-3 21:53:24 :咦。。。还有好多没补,我要回寝睡觉。。。明天继续补

TJOI2015 day2 题解报告

BZOJ上的题号分别为3999,4000,4001;COGS上的题号为1978,1979,1980

[TJOI2015] 旅游 给定一棵树,询问操作为求两点u->v路径上两点a,b,$V_b-V_a$的最大值,要求a距离u较近,b距离v较近。直接用树链剖分来做,维护每个区间的最大值、最小值、左边点减右边点的最大值,右边点减左边点的最大值。似乎用LCT代码量可以少一些,不过感觉自己LCT可能虚掉就去敲树链剖分了。

[TJOI2015] 棋盘 题面有些坑其实是自己傻逼读错题。可以发现如果两个棋子会产生冲突那么距离不会超过一行,s为二进制位表示一行每个点是否被放棋子,$f_i,s$表示第$i$行状态为$s$的方案数,预处理转移方案,用矩阵乘法优化。

[TJOI2015] 概率论 萌帝说可以找规律,但是我还是没有看出来。以下萌帝的做法:用$g_i$表示$i$个点的二叉树有多少种同构方式,用$f_i$表示$i$个点的二叉树所有不同构的树的叶子数量和。接着发现$g$其实是卡特兰数。继续打表,发现$f_i=i*g_{i-1}$。卡特兰数的通项式为$g_i=\frac{\tbinom{2n}{n}}{n+1}$,所以可以得到答案为$\frac{n^2(n+1)}{2n(2n-1)}$。在网上找到了证明,但是没有看懂QAQ 。

做题记录3

4.20

COGS1941. 超牛冠军赛 想了个显然错误的贪心,显然WA了…最小生成树,然后就$O(n^2)$没了。学了prim,似乎COGS的逆天评测机kruskal也不会跪。

COGS1942. 审查 AC自动机,顺便记录每个字符匹配到自动机上那个点,以便删除后可以直接找到对应点。我忽略了一个致命的问题,因为这个会往回退,所以复杂度好像不是$O(n)$。科学的做法应该是记录last[u][c],作为当节点u到试图匹配字符c错误时到哪里可以匹配上,不科学的做法是cheat掉….

BZOJ3218: a + b Problem 神题…网络流。首先连边$(S,i,w_i)$,$(i,T,b_i)$,假设已经获得选择白色和黑色全部收益,再减去最小割就是实际收益。对于点$i$,连边$(i’,i,p_i)$,所有满足题目条件的$j$连边$(j,i’,inf)$。这时最小割要么使得所有$j$都为黑色,要么使得$i$为黑色且扣除$p_i$或者$i$为白色。但是因为边数量是$O(n^2)$的,会T掉,就有特别神的方法:把边像主席树上的边一样连起来。PoPoQQQ的题解,看了他的图我才看懂,我就不画了。

BZOJ3687: 简单题 bitset好神奇。背包dp,记录每个和的数量,再异或起来。发现是异或所以只关注每个和的奇偶性即可。对于模2意义下的加法,相当与异或,可以用bitset加速转移。

BZOJ3688: 折线统计 dp即可。可以发现转移条件可以用树状数组优化,就没有了。


4.21

BZOJ3689: 异或之 对于每个数字寻找在这个数字前面的数字的第k小值。可以利用可持久化trie来寻找。


4.22

BZOJ3694: 最短路 符合题目条件的最短路一定可以只经过一条非树边,枚举每条边,会影响的点一定是该边在树上的路径除去lca。可以用树链剖分,我用的是枚举每个点相邻的边,暴力更新这个点的父亲,栈优化。还有种神做法我没有看懂QAQ。


4.23

BZOJ3695: 滑行 有个叫最速原理的东西, 我似乎没有上过高二,大概就是这样。接着二分第一个入射角即可。注意二分的时候角度的误差不能太大,否则时间的误差会更大。


4.25 省选日

就这样低速行进了三天,浮躁了两天去省选了。省选我似乎跪傻了,真的一天啥都不会写。写一天暴力。结果机器逗比奇怪的使得某些正解谜之T,但是神犇们依然虐场,跪梦迪和夹心。

接下来因为奇怪的原因没有去学校,继续浮躁QAQ。


谢谢夹心共享的HAOI2015题解包


4.29

COGS1962. [HAOI2015]树上染色 大力出奇迹,直接dp复杂度其实是$O(n^2)$,ydc大爷的题解。(我才不会告诉你考场上我写的是30分暴力)


5.1

1964. [HAOI2015]数组游戏 好神奇,讲不详细,直接看题解吧,题解包在上面。证明跳跃次数一样($N/i$一样)时,sg值一样。接着就乱搞了。最后不知道怎么搞的卡时过了,就没再管那比较玄学的复杂度了。

做题记录2

2015-4-13至2015-4-18

颓废了一个星期,我也不知道为什么。

BZOJ1978: [BeiJing2010]取数游戏 game 记$f_i$表示第$i$个数字选择的时候最多选多少个。可以枚举$a_i$的大于$L$的约数$d$,然后记上一个含有$d$的约数为$last[d]$那么显然$f_i=max(f_i,f_{last[d]}+1)$。因为如果从一个$j < last[d]$且$d | a_j$转移,那么一定也可以选择$a_{last[d]}$使得答案更大。每个数字最多有$2\sqrt{n}$个约数,复杂度为$O(n\sqrt{n})$

BZOJ3563: DZY Loves Chinese 首先扔度娘的文言文翻译,接着我看了好久也没有意识到哪里逗比了,后来找到了这个……由于每行数量可以读出,就可以利用$k$知道$lastans$,最后一个没法推就并查集暴力。

BZOJ3569: DZY Loves Chinese II 求出dfs树,去掉一些边不连通,那么去掉的边中一定有一条树边且覆盖这条边的非树边全部被去掉。可以记录每条树边有多少条非树边覆盖,然后再枚举其他边要去掉的边看是否覆盖。判断一条边是否覆盖另一条边,可以断判断覆盖边的端点是否是被覆盖边的儿子和祖先,可以利用dfs是记录的$pre$和$suf$两个时间戳判断。还看到另一种判断方法是高斯消元,感觉比较神,记下了可能以后有用。


BZOJ3561: DZY Loves Math VI 推出来一个奇怪的公式:$\sum_{T=1}^{n}\sum_{d\mid T}d^{d^{mod-2}}T^{2d}\mu(\frac{T}{d}) \sum_{i}^{n/T}\sum_{j}^{m/T}i^dj^d$,然后枚举$d$,预处理出$i^d$,然后枚举$d$的倍数$T$。似乎复杂度是$O(nlog^{2}n)$计算$T^{2d}$的log去不掉。卡时过了没有再管。


BZOJ2668: [cqoi2012]交换棋子 建立三层节点…刚才编辑的时候remarkable蹦了,什么都没了…那就YY吧


BZOJ3683: Falsita 可以先dp预处理出答案。接着发现对于单点修改操作,可以用树链剖分修改父亲:对于主链上的点,每次修改答案变动$(size[u]-size[son[u]])d$,主链就可以预处理出变动值,每次询问求d的和。树状数组即可。而主链间交接的点直接暴力修改。对于子树修改,对父节点的影响相当与单点$dsize[u]$。对儿子的修改,相当于平均值加上$2*d$,可以在dfs序上用树状数组维护。

莫比乌斯反演-笔记

关于莫比乌斯反演,主要摘自策爷的笔记知乎–如何证明莫比乌斯反演

Dirichlet卷积定义:对于数论函数$f$和$g$,他们的卷积为$f*g$为

$$(f*g)(n)=\sum_{d\mid n}f(d)g(\frac{n}{d})$$


定义以下函数:

衡为1的常函数$1(n)=1$

恒等函数$id(n)=n$

单位函数$\epsilon(n)=[n=1]$


定义莫比乌斯函数:

当$n=1$时,$\mu(1)=1$。

否则将$n$分解成$p_1^{a_1}p_2^{a_2}…p_k^{a_k}$这样的形式,$p_i$为质数,且$a_i$均为$1$时,则$\mu(n)=(-1)^k$。

其余情况$\mu(n)=0$


可以得到:

$$1*\mu=\sum_{d\mid n}\mu(d)=\epsilon(n)$$

由二项式定理可证,这个用途在于当存在类似$ \epsilon(gcd(i,j))$这样的函数的时候,可转换成$\sum_{d\mid n}\mu(d)$的形式,用于进一步变换。

而且证明莫比乌斯反演时,这是一个关键步骤。


莫比乌斯反演:

$$F(n)=\sum_{d\mid n}f(d) \Rightarrow f(n)=\sum_{d\mid n}\mu(d)F(n/d)$$

其实也可以写成Dirichlet卷积的形势:$F=1*f$,这样更好证明。

$$F=1f \Rightarrow \muF=\mu1f \Rightarrow \mu*F=f$$


然后其实莫比乌斯反演还有另外一种形式:

$$F(n)=\sum_{n\mid d}f(d) \Rightarrow f(n)=\sum_{n\mid d}\mu(\frac{d}{n})F(d)$$

证明:

$$\sum_{n\mid d}\mu(\frac{d}{n})F(d) = \sum_{n\mid d}\mu(\frac{d}{n})\sum_{d\mid m}f(m) =\sum_{n\mid m}f(m)\sum_{d\mid \frac{m}{n}}\mu(d)$$

显然当且仅当$m=n$时$\sum_{d\mid \frac{m}{n}}\mu(d)=1$其余为$0$,所以

$$\sum_{n\mid d}\mu(\frac{d}{n})F(d)=f(n)$$


例题:3529: [Sdoi2014]数表

大意:$Q$个询问,每个询问给出$n,m,a$。有一张$nm$的网格,每个格子$(i,j)$的数字为$gcd(i,j)$的约数和。问格子上的数字小于$a$的数字的和,可离线。$ Q \le 210^4 ,1 \le n,m \le 10^5, a\le10^9$

题解(参考PoPoQQQ的题解):

约定$n \le m$,否则交换即可,不影响解。

用$g(k)$表示网格中数字为$k$的数量,记$n’=\lfloor\frac{n}{k}\rfloor$。

$$\begin{split} g(k) =\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=k] =\sum_{i=1}^{n’}\sum_{j=1}^{m’}[gcd(i,j)=1] =\sum_{i=1}^{n’}\sum_{j=1}^{m’}\sum_{d\mid gcd(i,j)}\mu(d)=\sum_{d=1}^{n’}\mu(d)\lfloor\frac{n’}{d}\rfloor\lfloor\frac{m’}{d}\rfloor \end{split} $$

用$f(k)$表示$k$的约数和,枚举每个数的倍数可在$O(nlogn)$时间预处理。

那么显然没有a的限制时

$$ \begin{split} ans=\sum_{k=1}^{n}f(k)g(k)= \sum_{k=1}^{n}f(k)\sum_{d=1}^{n’}\mu(d)\lfloor\frac{n’}{d}\rfloor\lfloor\frac{m’}{d}\rfloor=\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{k\mid T}f(k)\mu(\frac{T}{k}) \ \end{split} $$

对于最后一步变换是把$T$替换成$dk$。因为$\lfloor\frac{n}{T}\rfloor$最多有$2\sqrt{n}$种结果,记$h(T)=\sum_{k\mid T}f(k)\mu(\frac{T}{k})$,那么预处理出$h$的前缀和就可以在$O(\sqrt{n})$的时间完成一次询问。

因为存在a的限制,所以可以先给询问按照a排序,然后离线处理。对于每个询问,我们把$k \le a$的插入$h$中,因为需要插入,所以$h$用树状数组来维护。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int L_N = 1e5 + 10;
int mu[L_N], pr[L_N], pn, not_p[L_N];
struct F
{
int val, id;
bool operator<(const F &f) const
{
return val < f.val;
}
} f[L_N];
struct Query
{
int n, m, a, id;
bool operator<(const Query &q) const
{
return a < q.a;
}
} qs[L_N];
struct TreeArr
{
int a[L_N];
int lowbit(int i) { return i & -i; }
void add(int p, int val)
{
for (; p < L_N; p += lowbit(p))
{
a[p] += val;
}
}
int query(int p)
{
int ret = 0;
for (; p; p -= lowbit(p))
{
ret += a[p];
}
return ret;
}
int query(int l, int r)
{
return query(r) - query(l - 1);
}
} ta;
void pre()
{
mu[1] = 1;
for (int i = 2; i < L_N; i++)
{
if (!not_p[i])
mu[i] = -1, pr[++pn] = i;
for (int j = 1; j <= pn && ipr[j] < L_N; j++)
{
not_p[pr[j] i] = true;
if (i % pr[j] == 0)
{
mu[pr[j] i] = 0;
break;
}
mu[pr[j] i] = -mu[i];
}
}

for (int i = 1; i < L_N; i++)
{
f[i].id = i;
for (int j = i; j < L_N; j += i)
{
f[j].val += i;
}
}
sort(f + 1, f + L_N);
}

void insert(F f)
{
for (int j = f.id; j < L_N; j += f.id)
{
ta.add(j, f.valmu[j / f.id]);
}
}

int sol(int n, int m)
{
if (n > m)
swap(n, m);
int ed = 0, ret = 0;
for (int t = 1; t <= n; t = ed + 1)
{
ed = min(n / (n / t), m / (m / t));
ret += (n / t)(m / t) * ta.query(t, ed);
}
return ret;
}

int ANS[L_N];
int main()
{
//freopen(“in.txt”,”r”,stdin);

pre();

int T;
scanf(“% d”, &T);
for (int i = 1; i <= T; i++)
{
scanf(“% d % d % d”, &qs[i].n, &qs[i].m, &qs[i].a);
qs[i].id = i;
}
sort(qs + 1, qs + 1 + T);

int fn = 1;
for (int i = 1; i <= T; i++)
{
Query &q = qs[i];
while (fn < L_N && f[fn].val <= q.a)
{
insert(f[fn]);
fn++;
}
ANS[q.id] = sol(q.n, q.m);
}

for (int i = 1; i <= T; i++)
{
ANS[i] &= (1 << 31) - 1;
printf(“% d\n“, ANS[i]);
}

return 0;
}