明明应该想出来却因为自己傻逼而没想出来了的题目集合

## $[HNOI2018]$转盘 ### 总结： 这题我居然没想出来？？？？？ 我觉得我要退役了。 最擅长的方面就是数据结构和简单数论函数。 居然前面那个就不会。 滚粗了啊。 这题我的**结论猜错**了，并且导致了之后的式子也无法推出来，整个石乐志。 ### 题解： 首先我们能猜到一个结论：选定一个起点之后，一定是等一段时间之后只走一轮也就是$n-1$步就能够结束。我之前猜的结论是最优答案一定是选定一个起点然后不等直接走，这样其实也没错，但非常不方便维护,主要是这样找不到算答案的量。 让我们抛弃错误结论，考虑在正确结论下怎么做。那我们一定是要找到这个等待时间的最大值，而决定这个等待时间最大值的就是各个物品的出现时间和起点到它们的距离。为了方便，我们倍长数组，破环为链。然后我们只要在相应的时间提前出发就可以了。 $$\begin{aligned}ans&=\min(\max(T_i-(i-S))+n-1)(i\in[S,S+n-1])\\&=n-1+\min(S+\max(T_i-i))\end{aligned}$$ 然后只要用线段树/数组维护那个$\max$，就可以做到$30/40pts$。 考虑怎么维护$\min$。注意到，如果我们把$i$的右边界设为$n+n-1$，答案仍然不会变，因为后面$i$更大，显然不会被取到最大值。 这个式子的答案取的位置肯定是有关$T_i-i$的一个从右到左的单调递增序列（其实我觉得这不叫单调栈，因为它不弹栈顶，只是让劣数不入栈），答案只会在每个相同数的最左边那个可能取到。 ~~我又琢磨了一会儿如何维护单调栈，还瞄了几下网友们的做法。然后下面的题解写完了准备开始打，想细节的时候看了下网友的代码，发现口胡根本就是假的，完全无法维护$\sout{Ans}$，于是删掉重来。~~ 我们考虑每次更新先进行修改，然后在$pushup$的时候，我们考虑如何更新当前区间答案。~~我一开始以为是自上而下更新，然后就没想出来~~ 首先，$Max$可以直接更新。 然后，如果$Max[L[root]]<=Max[R[root]]$，那么答案一定是$l+Max[R[root]]$，因为只有这样才最优秀； 如果不是，那么可能变更的答案只有$L[root]$的子树里那些$Max<Max[R[root]]$的区间的$Ans$。 那我们可以在$L[root]$的子树上二分，如果某个$x$的$Max[R[x]]>Max[R[root]]$就往右边走，因为考虑左区间内答案的变动是没有意义的，最终算答案时一定会取$Max[R[x]]$，因此$x$的答案不会受到影响；否则右边的答案肯定全部变化，而最优肯定是在$mid+1$这个位置，那么右区间的答案直接取$mid+1+Max[R[x]]$就可以了，我们就继续遍历左子树，考虑它答案的变化。注意此时$Max[L[x]]$一定$>Max[R[root]]$ ，因为我们能遍历到的区间一定是满足$Max[x]>Max[R[root]]$的，而$Max[x]$是上推而来。 注意遍历右子树和遍历到$l==r$时答案要与当前区间答案取$\min$，遍历左子树时不能这么做，因为当前区间的答案可能取不到，没有意义。 这样的话最坏时间复杂度是$\log^2$的，因为我们最多$pushup\log$次，然后每次的二分复杂度是$O(\log)$的。 注意不能与右边比较，因为右边还不能跑完一圈，因此单调序列没有意义。实现可以精细一点。 那么我们就在$O((m+n)\log^2 n)$的复杂度下解决了这个问题。 ## $[HAOI2018]$奇怪的背包 ### 总结： 这题不知道为啥也没想出来，而且没一点想法。$80pts$都不会。不过也是因为没看到数据范围，想到$n=1$的$exBSGS$随后放弃了。 如果自己能想到$exBSGS$判无解的话或许能想到裴蜀定理。 ### 题解： 显然就是求个同余方程有解方案数，注意$P$的系数一定$\neq 0$。 那么也就是说有解当且仅当$gcd([x_1\neq 0]v_1,[]v_2,\cdots,[]v_n,P)\vert w_i$，那么我们可以设$dp[i][j]$表示前$i$个数，$gcd$为$j$的方案数，又因为$P$系数一定$\neq 0$那么我们干脆直接把所有$gcd$都与$P$做一次，也就是$gcd$与$P$再做$gcd$为$j$的方案数。这样就可以直接枚举$P$的约数$DP$，$DP$随便做就可以了。最后算一下为$gcd$倍数的方案数就可以了。时间复杂度为$O(nd(P)\log P+q)$，可以拿到$80pts$。 优化也很简单，注意到与$P$的所有约数$gcd$相同的数，也就是与$P$的$gcd$相同的数的贡献一样，并在一起就可以了。时间复杂度降为$O(d(P)^2\log P+q)$，$d(P)\le 1500$，就做完了。 ## $[HAOI2018]$染色 ### 总结： 其实我想的是对的，也可以转化成正解$\cdots\cdots$但我中途计不清所以弃疗了。 总结就是，**看到容斥不能只想容斥系数，核心还是思考如何去掉非法的方案**。比如这题我想到了容斥系数是组合数的形式，但实际上根本不需要$(-1)^i\cdots\cdots$因为你每个数量都要算，不需要一次用$(-1)^i$算出合法答案，这样反而计不清。 ### 题解： 首先一眼容斥，然后可以想到枚举至少有几种颜色满足的方案数。 发现如果直接构造容斥系数不太好算，因为一个排列可能会被算多次，于是就不太方便归纳成统一的容斥系数。 比如当前我们枚举至少有两种颜色，那么因为其它随便填，就有可能有三种颜色满足，那么实际上你枚举这两种颜色的时候，就会把一个满足三种颜色的同一排列算$\binom32$次。 那么就简单了，设$f_i$表示至少$i$种颜色满足，$g_i$表示恰好$i$种颜色满足，那么 $$g_i=f_i-\sum_{j=i+1}^m\binom jig_j$$ $$\begin{aligned}f_i&=[is\le n]\binom{m}{i}\binom ns\binom{n-s}s\cdots\binom{n-(i-1)s}s(m-i)^{n-is}\\&=[is\le n]\binom{m}{i}\frac{n!}{(s!)^i(n-is)!}(m-i)^{n-is}\end{aligned}$$ 此时获得了$50pts$。 $g$与$f$的关系式可以分治$FFT$或者卷。 $$\begin{aligned}f_i&=\sum_{j=i}^m\binom jig_j\\g_i&=\sum_{j=i}^m(-1)^{j-i}\binom jif_j\\&=\frac1{i!}\sum_{m-j=0}^{m-i}f_jj!\times\frac{(-1)^{j-i}}{(j-i)!}\\&=\frac1{i!}\sum_{j=0}^{m-i}h_jr_{m-i-j}\end{aligned}$$ $h_i=f_{m-i}(m-i)!,r_i=\frac{(-1)^i}{i!}$，就做完了。 ## $[JSOI2018]$潜入行动 ### 总结： $DP$复杂度想错了，而且还设错状态了$\cdots\cdots$虽然我觉得考场上发现错了应该可以改出来，但是首先要觉得自己的复杂度是对的$\cdots\cdots$ ### 题解： 设$dp[i][j][0/1][0/1]$表示第$i$个点，子树内用了$j$个监听设备，这个点有没有放装置，有没有被监听的方案数。之所以多设一个有没有被监听是因为有可能让父亲监听这个点，方便转移。然后直接做就可以了。这样的复杂度实际上是$O(nk)$而不是$O(nk^2)$的，可以去看大聚聚歪歪比的博客。 ## $[JXOI2018]$守卫 ### 总结： 其实事我觉得我的做法太奇怪了，可能是假做法，然后参考了一下别人的。 话说这个$JXOI$咋两道签到题啊$\cdots\cdots$这题$70pts$可能也不太难。 但好像大家得分都不太高啊，$DOFY$只有$150pts$，有点惨。~~虽然好像这可以当队长了~~ ### 题解： 考虑设$dp[l][r]$表示$[l,r]$里最少需要的保镖数。我们正着枚举$r$，**再**倒着枚举$l$，然后记录一下当前区间内$r$处能够看到的最左边的点$pos$，然后可以进行转移： $$dp[l][r]=dp[pos][r]+\min(dp[l][pos],dp[l][pos-1])$$ 为什么只有这两项呢？因为$pos$这个点没有必要再放保镖，但因为它肯定比$pos-1$高，那么这个点的答案有可能更优秀；而$pos+1$及之后的没有，是因为那些肯定比它矮，所以答案也没有$dp[l][pos]$优。而将$pos$定为其它$r$能看到的点时，似乎答案与这个相同，反正不会比这个优吧。 当然在$l$能被看到时，$dp[l][r]=dp[l+1][r]$，这个正确性显然。同时要更新$pos$。 感觉这个题$idea$怪怪的$\cdots\cdots$ ## $[PKUWC2018]Minimax$ ### 总结： 一开始毫无办法，看了题解第一眼发现我**又**看漏题了$\cdots\cdots$没看到这是二叉树。 加上看了题解一眼很快想出了做法，但是第一次写这种类型的线段树合并有很多细节想不清。 ### 题解： 首先一个很显然的递推就是求$dp[u][i]$表示$u$号点权值是$i$（离散化）的概率。 $$dp[u][i]=dp[lson][i]\times\sum(p\times dp[rson][j<i]+(1-p)dp[rson][j>i])$$ 直接按有效状态$DP$复杂度应该是$O(\sum size)=O(n^2)$的。 这个$DP$显然可以用线段树合并优化，但我没想到可以用个乘法标记去维护。 我们在线段树合并的时候可以考虑$[l,mid],[mid+1,r]$之间的贡献，注意要考虑左儿子对右儿子的贡献，也要考虑右儿子对左儿子的贡献。 为了方便，当当前左右只有一个儿子时我们把乘法标记打上来，实现上可以把贡献递归下去，记录一下区间和就可以了。 最后遍历一整棵线段树就做完了。