ARC口胡集

$079$前的内容失踪。在 ## $080$ ### $D$ 瞎构造，似乎随便按顺序填就可以了。 ### $E$ 观察到一个结论：一个数能作为一个$pair$的$first$当且仅当它要离它当前的右边界距离为奇数；能作为$second$，当且仅当它离它当前的右边界与它的$first$距离都为偶数。 然后我们可以考虑使用线段树模拟这个过程，每次找到当前存在的距离它右边界距离为奇数的最小点作为$first$，在它的右边找一个为偶数的点作为$second$，将它们两个点同时去掉，这需要修改两个部分的右边界。 为了模拟这个过程，我们需要维护每个点的右边界，及它离右边界奇偶分开的$\min$，然后如果修改右边界就需要区间赋值，并且可能需要奇偶交换。不用管出现不同右边界点的区间，反正你只要上推$\min$就没有问题。~~我觉得这个做法很蠢，但好像真的是这么做的~~ 网友的做法好像还用了堆，我可能需要实现才能找出问题。 ### $F$ $LSTete$的考试题。 先差分，然后每次操作只会改$l,r+1$两个位置的值。 观察到对于任意两个位置，差为奇质数则需要$1$次操作，偶数则需要两次，奇合数需要$3$次。证明的话，偶数就是哥德巴赫~~定理~~猜想，奇**非质数**需要分解成偶数和奇质数的和或差。 那么也就是说我们尽量使用第一种配对，其次是第二种，实在不行才用第三种。 我们按奇偶拆分二分图，然后把差为奇质数的连边跑最大匹配。剩下的先在二分图的每一边各自配对，如果最后两边剩下各一个，那就用第三种。 ## $081$ ### $D$ ~~直接容斥。需要预处理相邻个数，感觉有点小细节。~~ 好像可以直接扫一遍，由左边确定右边。 ### $F$ 这是一道看过三次的题，第二次和第三次分别在$TUOJ$和$NOIp$考前三天的模拟题中。 有一个结论，就是如果一个矩阵所有的$2\times 2$矩阵中的黑格个数均为偶数的话，那么这个矩阵一定可以变为全黑。证明可以感性，（必要性）就是你无论怎么翻格子也改变不了这个$2\times2$的奇偶性，（充分性）而如果是偶数的话，我们可以通过有限次操作来达到变为全黑的结果。 因此题目要求变为求满足条件的最大子矩形，这个就枚举行，然后找到每个点这一列的极上满足条件子矩形（就是找到最上面那个位置），然后就从左到右从右到左各用单调栈扫一遍得到当前行每个点满足自己这个极上子矩形的左右边界就可以了。时间复杂度$O(n^2)$。 ## $082$ ### $D$ 感觉就是直接贪$\cdots\cdots$如果有两个相邻的满足$p_i=i$的就直接换，如果是单独的，左右至少有一个换过来满足$\neq$的，直接换那个就可以了。 ### $E$ 可以发现问题的贡献非常奇怪~~，明示转模~~，那个所谓的$2^{n-\vert S\vert}$的意思就是凸包内的点可以任意选。 于是发现问题变为求从点集内任意选点，可以构成凸包的方案数。因为在上面的问题中，一个凸包只有它的凸壳上点是必须要选的，这就与当前问题的贡献相同。 容斥一下变成$2^n-$空集$-$连成直线的方案数，空集方案数就是$1$，然后我们再$O(n^3)$枚举直线及每条直线能串上的点。对于构成每条直线的方案数，我们再容斥一下，变成$2^{\vert S\vert}-1-\vert S\vert$，表示这条直线除了都不选和只选一个点都可以构成。于是就做完了。 ### $F$ 怎么这场$ARC$这么奇形怪状啊$\cdots\cdots$ 这题直接离线，按时间排序，然后对每个询问开个结点进行线段树啊$\cdots\cdots$就每次修改的时候将值与$0$取$\max$就可以了。 网友好像有$O(n)$做法，好强啊。 ## $083$ ### $D$ 一开始想复杂了$\cdots\cdots$ 感觉要保留的边应该就是$floyd$中任何一个$k$都不能更新答案的$(i,j)$。那么应该判一下就好了。 如果存在一个$k$比它的最短路要小那就无解了。 ### $E$ 看错题了，以为是分配颜色，子树和要等于子树那个顶点的权值$\cdots\cdots$ ~~如果看成那样就是生成函数板子题了，直接算$\sout{\prod(x^{\sum w_{son_{son_u}}-w_{son_u}}+x^{2w_{son_u}})}$中$\sout{x^{w_u}}$的系数是不是$\sout 0$就好了。甚至可以做到$\sout{O(n\log n)}$啊~~ 正解有个结论比较巧妙，就是因为点权可以随便安排，那么显然尽量安排空间越多越好，因此对于一个点和它的某个儿子，如果他们不同色，那么与那个儿子异色（也就是与这个点同色）的所有点权和加起来要尽量小。 这是个背包，设$dp[u][i]$表示$u$号点当前子树内同色点权值为$i$，异色点的最小权值，设$g[u]$为$u$号点异色点最小权值。不难发现$dp[u][i-g[son[u]]$可以转移到$dp[u][i]$并且贡献为$val[u]$，$dp[u][i-val[son[u]]$同理转移。最后我们让$g[u]=\min(dp[u][i])$。 实际转移的时候第一维可以直接去掉，每一个结点直接重新用这个数组就可以了，注意一下$dfs$的时机就行。 ## $084$ ### $E$ 如果$K$是偶数，那么答案就是$\frac K2\ K\ K\ K \cdots K$，一共$n-1$个$K$。 如果是奇数，那么我们就要一直找到最中间的那个位置，因此我们先忽略各个后面有空串的序列（譬如$3\ 3,3\ 3\ 1$的前面那个我们不管），那么此时答案就是$\frac{(K+1)}2\ \frac{(K+1)}2\ \frac{(K+1)}2\cdots\frac{(K+1)}2$。 然后观察样例就可以发现要往前推$\frac n2$个了，我也不知道为啥，我以为要往前推$n$个$\cdots\cdots$ ## $085$ ### $D$ 想了一下没什么思路，本来想写个$\alpha-\beta$搜索找找规律，后来发现如果记忆化之后好像就是个$DP$，接着又发现好像答案与取的方式没有关系，好像直接枚举最后的两个数分别是什么就可以了$\cdots\cdots$我是傻逼。 ### $E$ 我怎么觉得好像就是直接贪啊$\cdots\cdots$就每次选最优解之后更新某些选法的贡献放到堆里就可以了啊。 听说正解是最大权闭合子图啊$\cdots\cdots$根本没往这方面想，努比。 ### $F$ 我怎么觉得还是贪心啊$\cdots\cdots$ 考虑先算出每个选法的答案，然后可以发现如果一种选法被选择，那么所有包含它的选法都可以直接去掉，因为它们的贡献显然为负。 因此每次在堆里贪心，然后取出当前最优解之后更新有交部分的贡献即可（并让那些部分的管辖范围减少），似乎这样更新次数最多是$O(n)$次的。 好像实现有细节。 正解好像是线段树优化$DP\cdots\cdots$ ## $086$ ### $D$ 看下最小最大数是否异号，如果是绝对值哪个更大，就先把序列变成全正或全负。这里花$n-1$次。 然后直接累前缀和或后缀和。 ### $E$ 这是一道$slide$题。 发现不同层之间无关，于是两个点在$LCA$出合并之后的概率就等价了。于是可以每一层建个虚树，设$dp[u][0/1]$表示一个点有无石子，然后初始有石子的点$dp[u][0]=dp[u][1]=\frac12$，然后可以先转移$dp[u][1]$，$dp[u][0]=1-dp[u][1]$就可以了。 ## $087$ ### $D$ 发现相隔一个的$T$前/后的$F$所代表的方向在一条轴上。 于是就看一下能不能调整出最终状态，多的可以抵掉，就做完了。 ## $088$ ### $E$ 这题我以为自己是假做法因为细节太多了$\cdots\cdots$结果一到网上看是对的$\cdots\cdots$为什么出得这么恶心$\cdots\cdots$~~结果就还是去网上看了下题解怎么实现~~ 就是首先考虑是相同字符配对显然是外-外，内-内，然后又可以发现两个互不包含的配对如果要变成$abba$这种形式的话，怎么移动对答案没有影响。 然后为了避免很多恐怖的细节，我们可以用$BIT$巧妙地解决计算距离问题（我失了智才没想到这个？？）。我们可以从左往右枚举，假设每次都移动右边那个字符，然后移动到某个串外面就当作移动到整个串的外面（因为当前移动字符一定不会跨过之前移动的字符，要维持回文）。这个就用$BIT$查一下剩下的字符个数就可以了。 ## $089$ ### $E$ 这个构造挺厉害的，主要是没啥提示$\cdots\cdots$ 首先我们可以发现$d$一定从左上到右下单调不递减，否则一定不合法；然后还有不合法的情况就是每一行一定不会出现先加再不加再加这种情况，每一列应该也是如此。 我们构造一条主链，这条主链由若干个连续的$X$与若干个连续的$Y$组成，其个数取决于两个连续的点之间最大的增长量是多少，横竖分别决定了$X,Y$。 接下来的过程我们以$Y$来举例。 如果$d_{x,i-1},d_{x,i},d_{x,i+1}$相邻的两个增长量发生了变化，说明我们需要有一条距离为常数的边来代替某个$Y$（无论是在之前还是之后），在$d_{x,i+1}$的时候，那条常数边就会失去效用（或者开始效用），来盖住某个主链上的边。 $X$的过程是类似的。于是我们可以使用增量构造的方式，如果无法增量了就说明无解。 ## $090$ ### $D$ 好像随便乱做就可以了$\cdots\cdots$我想了好久的做法是先用最短路判定是否有不同长度路径，然后再判定所有点的相对位置关系是否正确。 ### $E$ 一开始看错题了$\cdots\cdots$ 首先建出最短路图， ### $F$ 这题我居然蒙对了$\cdots\cdots$ 就是你发现$n\le 7$时可以跑暴力（$n$表示左端点$f$），暴力就一个个挪左端点就可以了。$\ge 8$时由于一个$f$的函数值就一定可以填满，所以不会出现很多奇怪的一次跳很长的$f$的情况；可以发现区间长度不大于$\frac S8$，于是直接枚举长度就可以了。长度如果整除$S$就会在某些$f$一致的区间算答案，否则能且仅能找到一个合法区间，因为我们能构造出一个$f$交界来满足它的要求。 ## $091$ ### $D$ 题意不想写，题解傻逼题。 枚举一下$b$算一下前缀和一下就完事儿了。 ### $E$ 考虑其实你把一组数放到哪些位置是没有关系的，那干脆就直接放在一起。 每次放一组长度为$A-x\vert B-x$的数，按这样的顺序放：最左边递增放最大的$A$个，最右边递减放次大的$B-1$个；最左边的右边递增放接下来的$A-1$个，最右边的左边递减放接下来的$B-2$个，依次类推。当$A+B>n+1$或无法放时无解，因为$A+B$太大根本无法满足。 ## $092$ ### $D$ ### $E$ 因为奇偶性不同的数根本不可能组合到一起，所以一开始就选择奇数或着偶数项的数，其它的全部作为合成原料~~狗式讲题法~~。 至于怎么选，就是正数全部要，负数如果选了不亏就选，也就是选负数当且仅当将其左边/右边的所有数选了会更优。 那么对于每个负数，我们算出它左或者右各自能拼出来的最大值，如果其比一个绝对值大就和那边一起抛弃。只要从一个方向贪心，答案一定不会更劣。 然后比较一下两个的最大值就可以了。构造就随便做一下。 ## $093$ ### $D$ 一种比原来的劣质好一点的方法。 先尽量满足一种，就是黑白交错一行，下一行全部黑。然后如果白这一行**还差一**就满了剩下的就填黑，下一行再填黑，再下一行填白。然后就开始继续交错，并且每个交错的下一行填白。类似地黑色差一剩下的白色补完再填一行白就做完了。 ### $F$ 这是一道$slide$题，可以去看我的计数与期望笔记。 ## $094$ ### $D$ 首先两个都小显然可以。 如果一个大一些的话就利用整除分块来枚举另一个能取啥，各枚举一次就可以了，这样时间复杂度是$O(q\sqrt{val})$的。 ### $E$ 先把$A_i\le B_i$的所有回合用了。 发现剩下的位置无论怎么做，答案只与最后剩下的那个位置的$B_i$有关，因为这个位置原来的$A_i$多多少，你选数的过程中所有数的总和就会少多少，并且因为总会有一个新位置变成$A_i\le B_i$，那一定可以把所有的$A_i$取完。找到$B_i$的最小值就做完了。 这个贪心在$A_i\le B_i$的部分是不能用的，因为如果你不先把小的弄完，那么对方完全可以让$B_i=A_i$，从而在你动大的时候提前结束。 当然网友提醒我了最终答案其实就是$\sum A/B-\min\{B_i\}$。 ## $095$ ### $D$ 这什么沙雕玩意儿啊$\cdots\cdots$ 直接找最大的，再找一个中间的，随便找。 ### $E$ 这什么沙雕玩意儿啊$\cdots\cdots$ 发现每行的总字符不会改变，就统计每行字符个数就可以了，只要能匹配就是对的，反正能转成对称。 ### $F$ 这什么沙雕玩意儿啊$\cdots\cdots$~~我居然还想错了~~ 发现度数为$1$的点一定是连向其它点的，不会有其它点连向自己（也就是不会作为$p_j<p_i$的$p_j$）。因此这些点会连到一个关键点上，而且它们的编号连续且恰好大于那个关键点。按顺序应该是$45673$这样。 然后我们会发现关键点之间会连起来，那么最后形成的结构是一个链串菊花。我本来以为是按度数排序贪心，结果发现连起来就凉凉了。 实际上直接从链的两端分别开始贪心就可以了，取最优那个就完事儿了。 ## $096$ 因为某些可以告人的原因你在这里找不到它。 ## $097$ ### $D$ 发现可以把每个数对看成边，每一个连通块可以任意换。 枚举每个位置，如果这个位置初始值和它的下标在同一个连通块就$++ans$。 ## $098$ ### $D$ 发现如果有进位就不会满足，也就是区间的每一个位的出现次数都是唯一的，而且如果$[l,r]$不满足，$[l,r+1]\cdots[l,n]$一定也不会满足。 根据抽屉原理，满足条件的区间长不会超过$20$。 枚举起点暴力算就可以了。 ### $E$ 可以想到如果你知道答案是两个点$x<y$，那么意味着，满足$\min\ge x,\min\le y$的区间必须$\ge K$个。 那么枚举$x$，假设$x$作为最小值，那么比它小的所有点会把整个序列分割成多个部分，每个部分的长度决定了它的选取次数。这个显然可以$O(n^2)$随便统计一下。 我们发现如果再枚举最大值，然后通过枚举两个点的方式统计答案是不太好求区间并的（可以做到$O(\frac{n^4}\omega)$），于是我们考虑直接在划分的区间上统计答案，问题转为统计我们能取到的次小值。这个很好统计，直接看能取的区间里的最小值是哪个就可以了。 ## $099$ ### $D$ 找找规律可以发现，答案就是$19,29,\cdots,199,299,\cdots,1999,2999,\cdots$依此类推。这些数答案递增，也就是比下段位的人要菜，同时又比同段位的人要菜，比如$\frac{109}{10}>\frac{199}{19}$。 $UPD:$这个规律到后面出现了问题，好像后面有$21999,22999$这种神奇的数。那就[看$ylsoi$博客](https://blog.csdn.net/ylsoi/article/details/80793472)。 ## $100$ ### $E$ 一开始看错题，以为要求$=k$的$\cdots\cdots$然后想了半天。 $\le k$的很好求，直接枚举超集往上更新答案就可以了。 不过应该有$O(2^nn)$的做法吧。 吧？ ## $101$ ### $D$ 完全失智，每次总想着二分$01$，明显$1,-1$更方便。 首先我们显然二分答案，然后把$\ge$的设为$1$，$<$的设为$-1$。 接下来我们要求中位数为$1$，也就是区间和$\ge 0$的区间个数，如果总个数$\ge \frac{n(n-1)}4$就说明中位数$\ge mid$。 这个就从左往右扫，然后每次往$BIT$里插入**上一个**前缀和，每次我们要求的就是$sum_r-sum_{l-1}\ge 0$的个数（枚举的$r$）。 因此$sum_{l-1}\le sum_r$，这个就直接查就可以了。 ## $102$ ### $D$ 发现这个题给的点和边非常少。于是我们要用乘法原理弄出尽量多的路径。最好的情况就是$2^{20}$，可以发现正好能满足。 拿$mspaint$画一下就可以发现大概就是$a\to T$连$0,1$两条边，$b\to a$连$1,2$两条边，$S\to las$连$2^x,2^{x+1}$。 ## $103$ ### $E$ 首先第$n$位必须要是$0$，第$1$位必须是$1$。 其次$1/n-1,2/n-2,\cdots$必须要满足对称。 接下来考虑如何构造。 如果一个位置$i$是$0$就意味着不能出现长度为$i$（边数量为$i$）的链。 随便拿几个菊花套在一起就可以了。 具体来说，我在网友那看到了一个很不错的构造方法。 就是从$1\to n-1$，若$s[i]=1$就让$i+1$变成根，否则在根上挂一个儿子$i+1$。可以发现这样就正好能构造出来。