搞颓记录

6-2

难得一次能AK,以后这种比较简单的考试也要多想正解/高分部分分

100 + 100 + 100 = 300

T1

先考虑枚举gcd,把限制缩紧,有(a,b)=1(a', b')=1,然后再化式子

一个比较有用的结论:

满足{a+b=n(a,b)=1\begin{cases}a+b=n\\ (a, b)=1\end{cases}a,ba, b的对数就是φ(n)\varphi(n)

(a,b)=1(a,a+b)=1(a,n)=1 \begin{aligned} &(a, b) = 1\\ \Rightarrow &(a, a+b)=1\\ \Rightarrow &(a, n)=1 \end{aligned}

T2

最长上升子序列计数

用线段树/树状数组求LIS的时候顺便记一下方案数即可

T3

分情况讨论,前缀和优化dp

Solution 很容易得到一个O(n3)O(n^3)的做法(枚举lca深度, 分别枚举左右两侧链长)。写出这个暴力后可以发现,在枚举两侧链长之后,lca深度范围就确定了,于是可以用前缀和直接算

6-6

花了很长时间在想T1正解,结果部分分都没写完。T2比较简单,之前做过)。T3想了一会儿,离正解已经很近了,但是最后一步没有想清楚:中间某一部分的机器人是一定能被选出来的

40 + 100 + 60 = 200

T1

考虑题目式子的具体意义,然后转化成一个概率模型(虽然正向推几乎不可能想到。。。

要大胆猜结论。。。

T2

比较巧妙的构造,主要难在四联通条件的处理

Solution 19-6-6-1

T3

通过一些特殊的状态进行dp

Solution 因为所有机器人是一起移动,相对位置不变,那么可以看成只移动出口,并且存活的机器人的范围跟着出口在一起变化
任意时刻存活的机器人的范围一定是一个矩形,于是可以以这个矩形作为状态进行dp
要发现一个性质:当前状态下有一部分区域是一定能获救的(即救这个区域内的机器人不会改变存活的机器人的范围)
需要注意的是,已经获救的机器人\ne当前状态下一定能获救的机器人\ne当前状态下存活的机器人

6-16

题目比较迷,尤其是T3。T2挂了分

100 + 80 + 100 = 280

T1

方案对应无根树形态,根据prufer序,答案为nn2(n1)!n^{n-2}*(n-1)!

T2

答案为φ(n)\varphi(n),根据这里的知识)直接计算即可, 需要Pollard Rho大数质因数分解

T3

没有奇环没有欧环的连通图就是树。。。

6-17

题面垃圾,题解垃圾,自己太菜了

60 + 50 + 30 = 140

T1

数学题,没看懂

T2

傻逼题不会做

Solution 很容易想到一个做法:从左往右移动长度为LL的区间,预处理右边部分的dp数组,左边的动态处理,动态更新答案
需要注意到一个性质:假设当前删除区间为[x,x+L][x, x + L],那么只需要看ax+L+1a_{x+L+1}是否对答案产生贡献,因为再后面的数显然此时不会更优

T3

狗屎分块,std有300L

6-20

Process

T1

点分治?

对于每种被不同的深度,它们对答案贡献的增量不同,如何解决这个问题?

必须要支持把深度数组平移的操作

T2

dp[i][j]dp[i][j]表示长度为ii的排列中,有jj个逆序对的方案。枚举下一个数填什么转移,O(n3)O(n^3)

优化一下可以到O(nk)O(nk),常数是22,好像能跑过。。。

容斥?

不会。。。

T1无限接近正解,还是差了点

然后T1暴力也挂了。。。

39 + 57 + 33 = 129

T1

不必考虑增量,显然把深度数组平移这个操作可以用FFT来实现。。。

考试的时候还忽略了一个问题,这个点分治并不能像平时一样,必须先算分治中心整棵子树的答案,再分别对应减去各个儿子对应子树的答案

T2

kk拆分成在每一位对答案的贡献,然后容斥dp

因为第ii位对逆序对总数的贡献范围在[0,i)[0, i)间,于是可以转化为,选出nn个数aia_i,满足

{ai=ki,0ai<i \begin{cases} \sum{a_i} = k\\ \forall i, 0\le a_i < i \end{cases}

先不考虑下面的限制,如果只有上面的限制的话显然答案就是插板法(n+k1n1)\binom{n + k -1}{n-1}

下面的限制可以通过容斥来满足,暴力容斥的话是枚举至少有多少个数不满足条件

i=0k(1)iS,S=i(n1+kSn1)\sum_{i=0}^{k}(-1)^{i}\sum_{S, |S| = i}\binom{n-1+k-\sum{S}}{n-1}

显然只关心S|S|S\sum{S}

S(1)S(n1+kSn1)\sum_{S}(-1)^{|S|}*\binom{n -1 + k - \sum{S}}{n - 1}

再变换一下,考虑对于相同的S\sum{S},统计出(1)S\sum{(-1)^{|S|}}

fi,,jf_{i,, j}表示S=i,S=j|S| = i, \sum{S} = j的方案(方案即为(1)S\sum{(-1)^{S}}的系数,这里考不考虑符号都无所谓,如果考虑的话最后统计答案的时候就不需要考虑了)

这个dp很巧妙,首先因为每个数互不相等,那么可以强制状态中每个数是按照从大到小严格单调的来保证。

fi,j=fi,ji+fi1,jifi1,jn1 f_{i, j} = f_{i, j - i} + f_{i - 1, j - i} - f_{i - 1, j - n - 1}

考虑要么把当前所有的数全部+1,要么在这个基础上在后面新加一个1

但是这样第一个数可能会等于n+1n+1,所以要把第一个数为n+1n+1的情况减掉

发现S|S|O(k)O(\sqrt k)级别的,所以dp是O(kk)O(k\sqrt k)

总复杂度O(n+kk)O(n + k\sqrt k)

6-22

Process

T1

作差分?

倍增?

显然,只有某一段的差分均为dd的倍数,才有可能有值

离线?

maxmindr+l \frac{\max - \min}{d} - r + l

假设从llrr的所有差分均为dd的倍数,那么这一段的答案为

maxmindr+l \frac{\sum{\max} - \sum{\min}}{d} - \sum{r} + \sum{l}

差分不为dd的部分把原序列划分成了若干个连续段,预处理出这些连续段的答案,然后在每次端点处单独讨论一下即可

能快速求出max,min\sum\max,\sum\min吗?

单调栈?离线?

HNOI2016 序列。。。

一整场考试在T1,开场30mins左右想到了一个似乎是正解的做法,写到考试结束前1个多小时才发现是假的,区间内数不能重复这个条件没想到,于是光荣爆炸,后面两题看都没看

35 + 16 + 0 = 51

T1

只有满足以下条件的区间[l,r][l, r]才合法:

  • 没有重复元素
  • 所有元素模dd同余

其贡献为

maxmind(rl) \frac{\max - \min}{d} - (r - l)

于是需要维护所有可行区间的 ,并且求和

转化成一个经典套路:扫描线 + 单调栈 + 线段树维护历史版本和

具体来说,按右端点排序,对于所有左端点,用一棵线段树维护以当前扫到的位置为右端点的答案

对于 ,需要用单调栈维护,在线段树上区间加减

同时,因为右端点在移动的过程中,会有一段连续的左端点变成不合法,于是需要支持线段树上置0操作

最后,因为对于每个左端点,要维护扫过的所有右端点的答案和,所以需要线段树维护历史版本和

形象理解一下:

19-6-25-1

一开始答案是蓝色矩形的面积,即C(T1)C * (T-1)

假设在TT时刻该点权值变为KK,那么答案就是蓝色和红色矩形的面积并,也就是TK+(CK)(T1)T*K + (C-K)*(T-1)

因为权值变化量Δ=KC\Delta = K-C,那么化简一下,对于之后的某个时间ii,其答案即为iKΔ(T1)i*K - \Delta(T-1)

维护KKΔ(T1)\sum{\Delta(T-1)}即可

T2

神题。。。不想写sol了。。。

看谁写了直接蒯过来吧

UPD gc写了sol,已经放在文件目录下了

T3

题解写得很清楚,观察性质一个个部分分往上做就行

6-23

Process

T1一开始想打表,发现最多才只能卡到68K左右,懒得搞了,观察了一下,发现当n>log(m)n > \log(m)时答案就是log(m)\log(m)(仔细想想发现也是),剩下的跑暴力就能过了

T3写了好久暴力,最后情况还是没考虑全,爆零

100 + 40 + 0 = 140

T1

随便搞

T2

这里链的情况保证了根为链的端点。。。直接stable_sort

二叉树的情况:

先随便找个点,遍历每个点,如果有祖先就跳到过去,这样就能O(n)O(n)求出根了。同理,用这个方法就能求出根的两个儿子,递归处理即可

T3

树剖 + 扫描线 + 计算几何

尝试了用解析几何的方法写计算几何,感觉还行,这道题也就调了一上午

6-24

Process

T1想了好久,T3考过原题,T2没时间看了

100 + 44 + 100 = 244

T1

类似于长剖的过程,贪心地把树划分成若干条链,取前kk大的链即可

T2

权值75\le 75

线段树暴力维护信息

T3

差分,转化成求2k2k个起点,nmnm条边的最短路,最后状压dp