A 机器人 By Dafeng (代码点此)
经过若干推(W)理(A), 可以得到一个漂亮的结论。先分别求出要经过的A类点和B类点横跨的区间,[MinA, MaxA]
和[MinB, MaxB]
. 然后再将这两个区间往左右两边扩展,扩展到第一个特殊点,得到新的区间[LA, RA]
和[LB, RB]
。(注意对于A,点s也是特殊点)。答案就是区间[min(LA, LB), max(RA, RB)]
的长度*2,如果要走到B的点,则加上2k.
(根据这个结论,是不是可以出道丧心病狂的动态题呢嘿嘿嘿~)
B 吃豆豆 By Dafeng (代码点此)
其实是常规的DP+倍增套路。首先不要被C的范围(1e18)吓到了。当C很小时,我们可以直接dp.
dp[t][i][j]
表示第0秒从位置i出发,t秒时到达j时获得的糖水数。
考虑到数组T取值为1..10, 那么取1..10的lcm: 2520, 一定是所有格子的公共周期。知道了这点,就可以搞事情了。
我们可以对所有t<=2520
的t求出dp[t][i][j]
, 接着以2520为最小单位,依次倍增求出dp[2520*2^k][i][j]
.
假设答案具有A*2520+B
的形式,那么我们可以用求出来的dp[2520*2^k][i][j]
的值逐位确定A,接着使用dp[t][i][j], t<=2520
的值确定B,得到答案。
PS:样例的答案应该是1464!!! 太过分了!!
此类问题是一种新套路。
定义f(n)=[1,n]中满足性质P的数字个数占[1,n]的比例,求解f(n)>=p的最小的n。
这类问题的解法是先找一个初始解b,并定义a为[1,b]中满足性质P的数字个数,然后根据a和b来调整。
怎么调整呢?因为现在的比例是a/b,找到最小的c满足(a+c)/(b+c)>=p,即假设b后面的数字全部满足性质。
这是最优的情况,所以无论如何都要调整c这么多,更新b+=c,然后重新计算a,继续迭代直到找到答案。
可(bu)以(hui)证明最多调整O(log)次便能找到答案。
回到这题,按照上面的套路做即可,但为什么还未AC呢?
因为假设p=0.99999,那么答案可能非常大。。。要实现高精度整数和小数。。。弃疗了。。。
(经检验unsigned LL范围内p最大是0.9)
--------后更---------
实际上并不用实现高精度小数,因为p最多是5位,所以转成p=q/100000的形式,交叉相乘就可以避免使用小数。
但依然还是要使用高精度整数(加法,单精乘法,单精除法)。
看了一下所有AC的,他们估计是真的写了高精度小数,因为我只有69ms,他们最少是699ms。。。。
H 割葱 By Zayin(代码点此)
令dp[l][r][h][k]表示[l,r]这个区间之前在高度h被割过,还剩k刀可以用的最大值。注意到[l,r]的有效区间只有O(n)个即可。
这种类型的题是利用了状态较少的性质————笛卡尔树的节点只有O(n)个。
听说类似的题还有ICPC 2016 Hong Kong G. Scaffolding
BTW,其实可以不写背包。
I 起起落落 By Zayin(代码点此)
对除自己外所有人按拥有宝物数降序排序,每个人拥有的宝物按升序排序。
假设拥有宝物最多的人有c个宝物。枚举除自己外所有人拥有宝物的最大数量h,从大到小枚举,即从c枚举到0.
这样每次枚举一个h时,将所有拥有宝物超过h个的人多出的宝物买过来(当然先买便宜的,所以每个人宝物按升序排序),这是第一部分的花费。然后统计下买过来的宝物数量够不够h+1,如果还差k,就从剩下没被取的宝物中买k个最便宜的宝物,这是第二部分的花费。
第一部分的花费可以直接对每个人维护一个队列,按需pop即可。第二部分的花费可以在这些队列的基础上,加一个权值线段树维护。(Zayin写了主席树,做法也差不多吧……)
K 星球大战 By Zayin(代码点此)
首先建立1号点的bfs树,邪恶点的入侵一定是按照bfs树的深度入侵的。
bfs树以外的边包含的点可视为关键点。
然后就可以枚举光明点,预处理所有关键点到此光明点的距离,可以轻松计算出关键点被谁占领,关键点的多少级祖先是邪恶光明的分界线。
A Erase Nodes By Zayin(代码点此)
千言万语汇成一句话:OJ不规范,做题两行泪。。。
B Erase Numbers III By Zayin(代码点此)
易知删除i个数字一定是从删掉i-1个数字后的答案再删掉一个得到的,所以只要知道删除一个怎么做这题就搞完了。
最暴力的方法肯定是建个后缀数组暴力匹配,但(理论上?)会被出题人卡掉,因为n*len已经上亿了,还要乘个后缀数组的常数,卡掉很正常
所以要寻求更优的解法。
首先比较两个数的大小,可以认为是先比较数字串的长度再比较字典序大小,所以删数字一定是删长度最小的数字。
那么字符串比较的偏移量就已经知道了,所以从后往前扫一下就可以知道哪个更优了。
D Honeycomb By Zayin(代码点此)
题目里藏着两句很深的话。。。
一:所有测试数据的特别格子的数量之和不超过3000。
二:保证每个不特别的格子没有可以穿行的边界。
所以上面的加起来就是说总有效格子(都是特别格子)是3000,因为不特别格子没有边向外连,可以忽略。
又因为这个图点的度数不超过6,所以跑一次最小割是O(n)的。。。
所以暴力建个最小割树就做完了。。。
E Power of Function By Zayin(代码点此)
易知f^m(n)=1当且仅当n在k进制下各个数位的和加上位长=m+1。
所以这是一道很简单的数位DP
不要偷懒写成O(log^2n)就没什么大问题了~
G Routes By Zayin(代码点此)
观察一:任意两点的最短路不超过2k-1.
首先从一个城市到另外一个城市只有两种本质不同路径,一种是不用热气球,一种是用热气球。
所以基本想法就是把任意两个点的min(不用热气球,用热气球)加起来。
不用热气球相当于只能在铁路上走,所以距离就等于|i-j|,暴力枚举某个点左右O(k)个点即可(因为|i-j|要不超过2k-1),这个很容易。
下面讨论怎么计算用热气球的路径总和。
先规定符号:
col[i]表示i号点的颜色;
f[i][c]表示i号点到颜色c的最短距离;
g[a][b]表示颜色a到颜色b的最短距离。
那么i到j用了热气球的最短路为min(f[i][c]+f[j][c]+1),+1表示在c这里用了一次热气球。
暴力枚举是O(n^2·k)的。
观察二:g[col[i]][c]<=f[i][c]<=g[col[i]][c]+1,即点到团的距离至多是团到团的距离加一。
推论:g[col[i]][col[j]]<=dis(i,j)<=g[col[i]][col[j]]+2。
那么可令一个二进制串sta[i]表示i这个点f和g的差,换言之,如果g[col[i]][c]==f[i][c],则sta[i]的第c位是0,否则为1.
如果枚举起点i,终点的颜色b,中转热气球是a,那么用预处理的sta[]可以做到O(nk^2),这里不做过多阐述。
考虑枚举起点i的颜色a,终点j的颜色b。
那么a到b的路径大概可以分成一下几类:
1、dis(i,j)==g[a][b]且i->j用过热气球。
2、dis(i,j)==g[a][b]但i->j没用过热气球。
3、dis(i,j)==g[a][b]+1且i->j用过热气球。
4、dis(i,j)==g[a][b]+1但i->j没用过热气球。
5、dis(i,j)==g[a][b]+2.
5是最容易的,因为如果dis(i,j)==g[a][b]+2的话,中间一定用过热气球。
1、3也很容易,因为走过去的时候就用过热气球了。
考虑2和4,因为走过去的时候没用过热气球,所以要在a或b那里额外再用一次,答案额外+1。
那么只要利用预处理的sta[]还有另外一些东西就可以统计出以上五种路径的数量,那么就做完了。
复杂度是O(nk+k^3+k^2·2^k):
O(nk)是算f[][]和暴力枚举不走热气球的复杂度,O(k^3)是算g[][]还有一些奇奇怪怪的预处理,
O(k^2·2^k)是O(k^2)枚举起点终点O(2^k)统计路径条数 以及 一些二进制卷积之类的。
这不仅是一道思维题,还是一道考验编程能力的题。。。
首先把i转成二进制就已经很神奇了,更神奇还在后面预处理中转点和统计路径,是我没见过的船新二进制技巧,orztls
另外有一些写预处理的方法,就算理论复杂度是对的,但也有可能会T,所以要更深的琢磨怎么预处理,反正这题就是太神仙了。
强烈建议把这题补了!!!
还有一道类似但非常简单的二进制处理题HDU5823
I Square Subsequences By Zayin(代码点此)
枚举分段点然后左右两边做最长公共子序列即可,但这样是O(n^3)的。
使用位运算加速dp,可做到O(n^3/w),w取120(__int128)。
但是这样依然是卡不过去的...可能是我常数太大,所以要使用一些奇奇怪怪的卡常姿势,鬼知道我卡了多久。
还有就是__builtin_popcount只能算int的1个数,因为这个也WA了很久。。。
位运算加速dp提交请戳这
J Square Substrings By Zayin(代码点此)
其实我看得不太懂题解ppt在说啥。。。下面是我YY的做法。
对于一个平方字串s[l..r],如果我们把(l,r)画在二维平面上,那么询问(L,R)就是问一个矩形(实际上是一个三角形,因为l<r,L<R)内点的个数。
那么其实做法就很显然了,先把所有平方串抠出来转成二维点,再询问矩形(三角形)内点的个数。
如果平方串的个数很少的话,那么这是一个经典的数据结构题。
但我们可以构造出类似aaaaaa形式的串,这样的话平方串个数是O(n^2)的。
回忆我们用后缀数组找平方串的过程,其实我们找的是平方字串组(开始下标连续且长度相同),那么最多有O(nlogn)个平方组。
所以这题其实就是给出不超过O(nlogn)段斜率为1的离散点,询问一个矩形(三角形)内点的个数,这个随便用一些数据结构瞎搞就可以了。
复杂度为O(p(n)logn+qlogn),p(n)是平方组的个数。
而事实上,根据runs theorem,一个串的runs(极大平方字串组)个数是O(n)级别的。
所以真正的复杂度是O(nlogn+mlogn)。
平方串的个数是O(n)级别。
这句话可以有两种解释。
一:一个串的极大平方字串组的个数是O(n)级别的,这个是这题要用到的结论(其实也没啥用,证明复杂度而已。。。)
二:一个串本质不同的(本原)平方字串个数是O(n)级别的,证明详见2019集训队作业Round11串串的题解。
L Pyramid By Zayin(代码点此)
一个任意放置的三角形总能恰好被一个正立的三角形套住,剩下的都是推公式了。。。
B 集合 By Zayin(代码点此)
镜面反射点。
(计算几何算反三角函数时要特别注意精度误差造成的影响,最好对-1和1取个max,min)
C 小游戏 By Zayin(代码点此)
dp好题!!!非常好!!!
重新回顾了姿势:缺什么状态就补上什么状态,直到可以完美表示为止。
记dp[i][a][1/2]为以i结尾且该类型的能量是a,当前序列末尾有1/2个。
其实往后更新的dp是很容易写的,但会TLE,所以一定要写成从前贡献的dp,用前缀和优化即可。
不懂可以直接看代码,挺短的2333.
F 小清新数论 By Zayin(代码点此)
经典杜教筛。
sigma (f·g)(i) [1<=i<=n]= sigma (f·g·1)(i) [1<=i<=n] - sigma (f·g)(n/i) [2<=i<=n]
H 涂鸦 By Zayin(代码点此)
标记永久化其实还挺好写的...
I 石头剪刀布 By Zayin(代码点此)
小清新并查集。
J 子序列 By Zayin(代码点此)
我们先考虑一个普通字符串怎么统计子序列个数。
记f[i]为以i结尾的子序列个数,sum为当前总子序列个数,初始时sum=1(空串)。
每遇到一个字符c,则有f'[c]=sum,sum'=2*sum-f[c],那么每个字符都可以写成一个转移矩阵。
回到这题,字符串的变化是 S <- SaS,那么矩阵对应乘起来即可。
类似的题还有Loj6074
E 黄金矿工 By Zayin(代码点此)
记dp[s]为取完s中金块的最短时间,转移相当于是给定若干个凸包,问碰到某个凸包的最小时间。
按照计算几何的套路,将极角切分,使得每一份里面都只有线段,那么剩下的就是在这些线段中三分出最小值或直接手算最小值。
H 命命命运 By Dafeng (代码点此)
我们需要求出对于i号玩家,第j轮,获得第k块地的概率,然后把所有j,k取值下的概率累加起来,就是每个人获得地的块数的期望。i号玩家,获得第j块地等价于1..(i-1)
号玩家前j轮不曾走到k,i号玩家第j轮第一次走到k,(i+1)..6
号玩家前(j-1)轮未曾走到k.
于是我们要求出两个概率来,never[i][j][k]
表示i号玩家前j轮未曾走到k的概率,first[i][j][k]
表示i号玩家第j轮第一次走到k的概率。
为了求出这两个东西,我们还需要一维状态,即玩家当前所处的位置。所以pos[i][j][k][m]
表示i号玩家前j轮未曾走到k,走完第i轮后位于m的概率。
转移式很好写出来。于是我们得到了一个个复杂度O(6*6*500*n^2)
的优秀算法, n为500, 爆了。
那么怎么优化这个东西呢?
突破口在于,pos数组的k只需要求前7块地就可以了。这样由pos的结果得到前7块地的first和never值,而后面8..n块地的first,never值可以直接由前面7块地的first,never值分别递推出来。因为每一轮掷骰子的概率是独立的,跟所处位置无关,j轮移动可以看成1+(j-1)轮,即走完第一轮再走j-1轮。例如,我们求first[i][j][k]
, 可以枚举第一轮移动的步数t,贡献就是p[i][t]*first[i][j-1][k-t]
. never同理。
于是我们得到了正解。
J 跑跑跑路 By Zayin(代码点此)
显然的一点是x,y贡献独立,那么只需考虑一维的情况。
假设第一轮第i个集合点的坐标是x1[i],第二轮第i个集合点的坐标是x2[i],那么对答案的贡献就是sigma (x[i]-x1[f[i]])^2+(x1[f[i]]-x2[s[i]])^2.
所以相当于是对有着1000个变量的函数求最小值,数分告诉我们这时候随便求个导就能求极值了
对函数求完偏导后是一次方程组,令偏导=0解出各个变量的取值即可。
1000个变量做高斯消元会T?
有个trick就是第二轮集合点的坐标是完全由第一轮的集合点所决定的,所以独立的变量其实只有500个。
K 两条路径 By Zayin(代码点此)
主席树实现二进制高精度,支持单位加减法,高精加法,还行.
我感觉我写的高精可以拿去当板子
(Comment By Dafeng: 你太强了)
(Reply to Dafeng By Zayin: fAKE!)
A Cactus Draw By Zayin(代码点此)
仿照树的版本,只要把环拉平就可以了。
(比赛时一直想着斜着拉,感觉要讨论好久,其实拉平什么情况都没有。。。还是太菜了【叹气】)
B Diameter By Zayin(代码点此)
其实真的是可以做到O( (nlogn)^2 )的。。。因为转移是个卷积的形式,所以理论上套个分治FFT就可以做到一轮转移O(nlog^2n)。。。
但从实际效果来看。。。emmmmmmm。。。FFT常数太大。。。任意模数导致常数又要乘个4。。。CDQ。。。感觉常数乘起来比n还大了。。。
专心优化常数吧
最后我成功地把O(n^3)卡在700ms以内。。。也算不错?
D Doppelblock By Zayin(代码点此)
可能是因为太久没有碰到过大搜索的题,所以在赛场上没有想到爆搜。。。
其实知道是搜索后还挺好写的,毕竟有太多可以剪枝的地方了。
但最后也只是33ms,并没有做到dls的0ms,是我太菜了,想不到怎么剪下去。。。
C Division By Zayin(代码点此)
F Kropki By Zayin(代码点此)
考虑容斥,首先肯定是规定哪些位置一定要满足两倍关系,其他任意,然后统计这种规定下的方案数,暴力算至少是O(2^n)的。
可以观察到,根据上述规定,一条长度为n的数链被划分为若干条不相干的短链,实际上就是对n进行整数拆分,所以状态数是P(n)=20W,不至于O(2^n)。
统计方案数其实是一个相同的过程,所以这题就轻易解决了,时间复杂度为O(P(n)*n).
类似的题还有今年青岛的某道容斥题,还有某场opentrain的压缩状态数的题(忘记哪场了)。。。
G Least Common Multiple(代码点此)
首先转化原问题,可证(cai)明(ce)答案就是max PI(x+ai)/LCM(x+ai),因为x^n与 PI(x+ai)其实是同阶无穷大。
观察上式,等价于求 算LCM(x+ai) 时最多可以除掉多大的数。
那么根据中国剩余定理,每个素数贡献独立(可以根据x mod p^e的取值还原出x)。
对于一个素数p,假设LCM中p的指数是e,那么一定存在一个i使得p^e|x+ai(LCM的性质),所以对于其他的j,x+aj中p的指数就被除掉了。
枚举e和i,统计剩下的j对指数的贡献即可。
H Nested Tree By Zayin(代码点此)
其实思路和普通的树上计数没什么区别。。。
赛场上想到的是虚树,所以觉得很难打,其实可以直接写树剖,超级容易写。。。
PS:我已深深地爱上了标记永久化的线段树【呲嘴笑】.
B 重新定义字典序 By Zayin(代码点此)
枚举B中是第p[k]小的数小于A,然后就相当于给出两个大小分别为x,y的数集,问在这两个集合中选出t个数,并且x中选的数的个数不少于p的方案数。
直接暴力枚举x或y中选的个数是O(n^2)的,但如果是枚举x和y的最小集合中选的数个数,复杂度就降到了O(nlogn),因为一个位置最多被枚举O(logn)次。
I 集合 By Zayin (代码点此)
题解PPT说的已经很完全了。。。其实是个大水题
J 强壮的排列 By Zayin (代码点此)
神仙题。。。真的神仙题。。。我对生成函数计数一无所知【喷血】。。。
后更:除了题解的做法,还有一种基于容斥的cdq分治,O(nlog^2n)
再更:假的,再进一步化简得到的就和敦爷的方程一模一样。。。
H 二人的白皇 By Zayin(代码点此)
考虑点分治。
但如果每次分治都重新计算距离分治点的个数,最坏情况是O(路径长度)的。
不难发现其实很多计算都是重复的,比如分治点与分治点之间的子树,其实可以预处理出来,不必每次都直接算。(这是属于点分的一类小技巧?)
考虑预处理的时间复杂度,每个分治点的子树不会超过子树的一半,所以每次分治下去和它相邻的子树大小减半,所以和他相邻的子树总大小是O(sz[i])的。
由点分树的结构可知,O(sigma sz[i])=O(nlogn)。
所以总复杂度是O(mlogn+nlogn)。
I 岸边露伴的人生经验 By Zayin(代码点此)
首先做出如下转变 0->00,1->01,2->11,则|x-y|-> (sx^sy)中1的个数。FWT后再统计一下即可。
J 去音乐会 By Zayin(代码点此)
(看懂了题解的做法,但感觉有点复杂,下面是我自己想的更简单做法)
考虑这题的几何意义,即有一条长度为n的线段,每隔d个单位把d-c个单位染成黑色,然后再每隔b个单位用一个长度为b-a的括号框住线段,问框起来的总黑色线段长度。
括号问题考虑差分,对于一个括号来说,计算线段从头直到这个括号的总黑色长度即可。
如果该括号的距离为bx+a,即要计算[(bx+a)/d]*(d-c)+max((bx+a)%d-c)。
把max拆开,用拓展欧几里得加速即可。