[ABC369C]CountArithmeticSubarrays 题意： 判断有多少个区间是等差数列（不能重排）。 \(1\len\times10^5\)。 思路： 赛时看错题了，以为这个区间可以重排，卡了8min，小丑了。 首先容易注意到，对于一个区间\([l,r]\)，若其是等差数列，则这个区间的子区间\([l',r']\)肯定也是子序列，造成的贡献是\(\frac{(r-l+1)(r-l+2)}{2}\)。 那么考虑求出所有极长等差区间，设\(d_i=a_{i+1}a_i\)，若\(i\)能加入\(i-1\)的等差区间，当且仅当\(d_i=d_{i-1}\)；否则就要新开一个等差子区间...

题意： 给定\(n,m\)，一个区间序列\(\{[L_1,R_1],[L_2,R_2],\cdots,[L_n,R_n]\}\)被称为好的当且仅当： \(\foralli\in[1,n],1\leL_i\leR_i\lem\)。 \(\foralli\in[1,n-1],[L_i,R_i]\cup[L_{i+1},R_{i+1}]\ne\emptyset\)。 输出好的序列个数对给定质数\(p\)取模的结果 \(nm\le10^7\)。 思路： 考虑动态规划算法，定义\(dp_{i,l,r}\)表示第\(i\)次为\([l,r]\)，则状态转移方程为： \[dp_{i,l,r}=\su...

思路： 注意到答案应该是链加上一串贡献相同的树的贡献，因为若\(a\tou\)的贡献比\(b\tou\)的贡献小，那么可以连\(b\toa\)，答案会更优。 那么有一个贪心思路，对于每个根，找到连向这个根的最短边，然后对于这条边的另一个端点，也找到连向这个端点的最短边，以此类推；很显然，这个假了。 设\(T\)为当前根，考虑找到全局最短边\((u,v,w)\)，考虑令\(u\toT\)，然后其它所有点都连\(v\)，这样其它点到\(T\)的贡献必然是最小的，但是若\(u\toT\)的贡献非常大，那这样也是不优的。 则考虑组成一个\(u\toT\)的一条链，使得这条链的贡献加上其它所有点的贡献最...

思路： 考虑按照dfn序将关键点的集合排序后为\(a_0,a_1,\cdots,a_k\)，则答案为： \[\frac{\sum\limits_{i=0}^k\operatorname{dis}(a_i,a_{(i+1)\bmodk})}{2}\] 简单证明一下： 需要找出包含一些关键点的最小联通导出子图。 则随便以一个关键点为根，对于子树内没有关键点的子树直接丢掉，就形成了新树；新树的叶子节点绝对都是关键点。 我们要找出新树的边集数量，即在dfs搜索的时候，每条边会在搜入子树时经过一次，出子树的时候经过一次，总计每条边会经过两次。 这个dfs搜索的过程等价于按照叶子节点dfn序的相...

思路： 我们可以对于每个\(i\)找到它能跳到的最远的点和最近的点，倍增求一下\(k\)级祖先即可，令\([l_i,r_i]\)新表示\(i\)能跳到其祖先中深度在\([l_i,r_i]\)内的点；同时令\(lim_i=d_ih_i-1\)表示\(i\)至少要跳到\(lim_i\)的深度。 考虑动态规划算法，令\(dp_i\)表示从\(i\)出发到山顶的合法登山序列个数。 那么相当于先从\(i\)滑落到\(j\)，然后再从\(j\)冲刺到\(k\)，再加上\(dp_k\)的方案数。 则状态转移方程为： \[dp_i=\sum_{j在i子树内}\sum_{k为i的祖先}(d_k\in[l_j...

思路： 先考虑Sub1的部分分，暴力算法： 暴力询问所有\(i<j\)的数对\((i,j)\)。则一个\(i\)为最大值当且仅当\((i,j)\)的返回值都是\(i\)且在\(i\)之前没有满足此条件的位置。 则设\(\operatorname{F}(n)=\frac{n(n-1)}{2}\)表示暴力找出\(n\)个数中的最大值需要的询问次数，注意到\(\operatorname{F}(1000)=499500\)，故可以通过Sub1。 对于Sub2，直接暴力肯定是不行的，但是注意到\(t\)的值开大了，故我们没必要一步到位，可以逐步缩小范围。 定义\(\operatorname{W...

noi模拟赛t1，所以打了些部分分，不介意吧…… 思路： 仿照平面最近点对思路，先按照横坐标排序，考虑分治。 对于分割线\(y=X\)，考虑求跨过这条线的贡献，设\(d\)为左边和右边分治结果的最小值，则这三点中最长边的长度必须\(\le\frac{d}{2}\)，不然不会比\(d\)更优。 则我们只需要考虑横坐标到分割线的距离\(\le\frac{d}{2}\)的贡献，将这些点找出来，再按照纵坐标进排序，这里使用归并排序的话可以降一个\(\log\)，但是没必要。 然后暴力枚举这\(3\)个点，使得三个点的\(y\)坐标的极差\(\le\frac{d}{2}\)，然后计算贡献即可。 时间复杂...

本文中的机器人同炸弹，主要是题目描述不同，两道题目做法是本质相同的。 思路： 先说一下没有墙怎么办，那么当一个位置放了机器人之后，这个机器人所在的行和列是不能继续放置的。 那么发现行和列几乎是独立的，考虑建二分图，若\((i,j)\)能放一个机器人，那么给\(i\toj\)建一条边。 那么答案就是这个二分图的最大匹配，这样每个匹配的就代表着一个机器人所放的位置。 现在再考虑有墙的情况，有墙时，机器人所放的激光无法穿透过去，则在墙另外一边依旧可能可以放置机器人。 发现墙就是把行或列分为了几个部分，每个部分互不干扰，则考虑每遇到墙，就新起一行表示当前位置到下一个墙或者这一行的末尾的放块；列同理。 ...

思路： 容易发现，区间\([l,r]\)中\(A\)与\(B\)等价的充分必要条为： 两个序列中所有元素对于在区间\([l,r]\)内的出现集合组成的集合相等。 这样才可以使得存在一种对应的映射方案使得等价。 考虑哈希判定。 设\(S_i\)表示\(i\)出现的位置的集合，则设\(\operatorname{Hash}(S_x)=\sum\limits_{i\inS_x}base^i\)，\(\operatorname{Hash}(A/B)=\sum\limits_{i=1}^m\operatorname{Hash}(S_i)\)。 固定左端点\(l\)时，容易发现\(r\)具有单调性，考...

题意： 给定一个长度为\(n\)的排列\(a\)，判断其中是否有长度\(\ge3\)的等差数列。 \(1\len\le5\times10^5\)。 思路： 首先若存在长度\(>3\)的等差数列，则其中的一部分肯定由长度为\(3\)的等差数列组成；即我们现在只需要判断是否存在长度为\(3\)的等差数列即可。 考虑枚举中间的数\(a_i\)，则问题转化为\(a_i-k\)与\(a_i+k\)是否同时出现在\(i\)的两侧。 注意到\(a\)是一个排列，则是没有重复数字的。 那么我们可以记作若\(i\)左边的\(a_j\)出现过，则将标记数组中第\(a_j\)个位置为\(0\)。 若不可以构成...

[ABC368F]DividingGame 双倍经验。 题意： 有\(n\)堆石子，第\(i\)堆有\(a_i\)颗石子，每次可以拿走任意一堆石子数量任何数量的棋子，但是要保证拿走之后该堆的石子数量为原来的约数（不能不拿）。 问是先手必胜还是后手必胜。 \(n,a_i\le10^5\)。 思路： 发现与Nim游戏类似，且全局信息公开，状态有限，故为公平组合游戏。 考虑构造必胜状态，设\(\operatorname{F}(a)=\operatorname{xor}\limits_{i=1}^n\operatorname{f}(a_i)\)，若\(a_i=\prod\limits_{i=1}^kp...

思路： 定义\(F(l,r)\)表示若已经确定了\([1,l-1]\)的数，且\([l,r]\)没有限制的贡献数。 设\(n\)的长度为\(len\)，考虑先求出\([1,i](i\lelen-1)\)的贡献（是没有限制的），那么每次枚举第\(1\)位数字\(a_1\in[1,9]\)，算上\(F(2,i)\)的贡献即可。 则该情况贡献和为： \[\sum_{i=1}^{len-1}\sum_{j=1}^9F(2,i)\] 现在来考虑长度为\(len\)的数的贡献的和，也考虑枚举第\(i\)位的数字\(j\)，那么若想要使得\([i+1,len]\)没有限制，则至少要满足\(i\in[...

思路： 考虑函数\(\operatorname{F}(v_0)_i\)表示风速为\(v_0\)时，\(i\)到达原点的时间，易得： \[\operatorname{F}(v_0)_i=\frac{x_i}{v_i+v_0}\] 则若\((i,j)\)满足条件，需要满足\(\operatorname{F}(v_0)_i\)与\(\operatorname{F}(v_0)_j\)的交点的横坐标在\([-m,m]\)间，那么若\(\operatorname{F}(v_0)_i=\operatorname{F}(v_0)_j\)，即\(\operatorname{F}(v_0)_i-\oper...

这篇题解相对于其它题解对小白要友好一些。 模拟赛题，赛时sb了，\(n^2\)都不会。 思路： 考虑什么情况下深度最大，容易发现(((...)))是肯定不劣的。 那么考虑枚举中心点的位置，设左边有\(a\)个左括号和\(x\)个问号，右边有\(b\)个右括号和\(y\)个问号，然后我们来枚举深度\(i\)，求\(i\)的贡献次数。 要使得深度为\(i\)，则要左边新添\(i-a\)个左括号，右边新添\(i-b\)个右括号，直接组合数计算贡献： \[\sum_{i=\min(a,b)}^{\min(a+x,b+y)}\binom{x}{i-a}\binom{y}{i-b}i\] 这样直接...

思路： 首先可以先考虑没有换根的情况。 先将树拍到dfn序上，那么一个子树\(u\)的所有点的dfn序区间为\([dfn_u,dfn_u+siz_u-1]\)。 那么询问变为： 每次给定两个区间\([l_1,r_1],[l_2,r_2]\)，对于在第一个区间内的点\(x\)和在第二个区间的点\(y\)，若\((x,y)\)有贡献，当且仅当\(w_x=w_y\)。 询问有贡献的点对数量。 即P5268[SNOI2017]一个简单的询问。 设\(F(l_1,r_1,l_2,r_2)\)表示\([l_1,r_1]\)与\([l_2,r_2]\)的贡献，那么： \[F(l_1,r_1,l_2,...

思路： 首先随意钦定一个不是叶子节点的节点为根节点。 然后考虑对于一个不是根节点的点\(u\)，肯定需要至少一个叶子去与\(u\)子树之外的叶子节点配对。 考虑\(u\)到\(fa_u\)的这条边，首先至少有一个叶子节点穿过，然后设\(p_u\)表示\(u\)中的叶子节点个数： 若\(p_u\)为偶，在一个叶子节点往外传后还剩奇数个，两两配对后还剩一个叶子节点，也需要往外传经过\(u\tofa_u\)的这条边。 否则\(p_u\)为奇时，在一个叶子节点往外传后还剩偶数个，可以完美两两配对。 那么对于\(u\tofa_u\)的这条边，经过这条边的叶子节点个数为\(1+[p_u\bmod2=0...

思路： 考虑往直径方向想，设直径的长度为\(d\)。 首先可以注意到一个性质： 每次操作最多只会覆盖住直径的\(2\)个点，那么答案的下界即为\(\lceil\frac{d}{2}\rceil\)。 分类讨论一下。 若\(d\)为奇数，则存在唯一的一个直径中心\(u\)： 那么答案为\((u,0),(u,1),\cdots,(u,\lceil\frac{d-1}{2}\rceil)\)。 最优次数是\(\lceil\frac{d}{2}\rceil\)次。 若\(d\)为偶数，则存在两个直径中心\(u,v\)： 若\(d\bmod4=0\)时： 那么答案为\((u,1),(v,1)...

思路： 注意到答案有单调性，考虑二分答案。 现在由最优性问题转换为判定性问题。 我们很容易注意到一个性质： 一个军队不停的往上跳是更优的。 因为可以覆盖住更多的叶子节点。 那么对于二分答案的\(mid\)，我们只需要求出每一个军队在\(mid\)时间内能跳到的最高的那个点，然后判定一下是否覆盖了所有叶子节点即可。 但是这样会存在一个问题，即若当前这个点为\(1\)的儿子，且有多个军队跳到，则可能可以支援一下\(1\)号点的其它儿子（因为检查点不能放在\(1\)上，则可能还有空余的时间经过\(1\)走到\(1\)的其它儿子）。 先来考虑一个简单的问题： 若已知每个检查点的位置，如何判断是否...

思路： 首先考虑离线。 设\(Min-nxt_i\)表示下一个小于\(a_i\)处的位置，\(Max-nxt_i\)表示下一个大于\(a_i\)处的位置。 那么\([l,r]\)是魔法区间当且仅当： \(r\)是\([l,r]\)的最大值，且\(r<Minnxt_l\)。 \(r\)是\([l,r]\)的最小值，且\(r<Maxnxt_l\)。 再令\(Min-pre_i\)表示上一个小于\(a_i\)处的位置，\(Max-pre_i\)表示上一个大于\(a_i\)处的位置。 那么我们可以对于每个\(r\)，求出对应的\(l\)的氛围： 若\(r\)是\([l,r]\)的最大...

思路： 考虑先求出经过\((x_1,y_1),(x_2,y_2)\)的抛物线解析式 我们有： \[\begin{cases}ax_1^2+bx_1=y_1\\ax_2^2+bx_2=y_2\end{cases}\] 考虑将\(b\)消掉，求出\(a\)。 那么考虑令\(1\)式减去\(2\)式的\(\frac{x_1}{x_2}\)倍： \[ax_1^2+bx_1ax_1x_2bx_1=y_1\frac{x_1}{x_2}y_2\] \[a(x_1^2-x_1x_2)=y_1\frac{x_1}{x_2}y_2\] \[a=\frac{y_1\frac{x_1}{x...