ARC不会做选讲

## $061F$ 题意： 给定$n,m,k$，代表每个人有$n/m/k$张卡牌，$Alice$先手。 每张卡牌有一个字母$a,b,c$，表示接下来由$Alice/Bob/Charlie$出牌。 在$3^{n+m+k}$种卡牌顺序中，有多少种是$Alice$一定会赢的？ $n+m+k\le 300000$。 题解： 这题好骚啊。 不妨直接考虑最终的出牌序列有多少种是符合条件的。显然可以发现当序列的前$i$位满足$sum_a=n,sum_b<m,sum_c<k$时，$Alice$能获得胜利。 考虑直接计数，显然我们可以在前$n$个$a$前乱填$b,c$。我们枚举这里放了$x$个$b,y$个$c$，注意第$n+x+y$个数一定填$a$所以不能枚举。 $$ans=\sum_{i=0}^{m+k}3^{m+k-i}\binom{n-1+i}{n-1}\sum_{x=0}^{min(i,k)}[i-x\le m]\binom{i}{x}$$ $i$表示$x+y$，这样你就可以拿到$500pts$。 考虑怎么优化式子的计算，这就是很神奇的地方。 为了方便，我们设$m\ge k$。 我们考虑后面的式子是组合数求行的和，然后我们就可以手玩一会儿杨辉三角。 $UPD:$好像有简单的$O(n)DP$，是我沙雕了。 ## $078F$ 题意： 给定无向带权连通图，删去边权和尽量小的边使得$1\to n$路径唯一。 心路历程： 没有思路，就是我菜。 题解： 考虑这个东西删边很麻烦，不如直接换成加边，设$dp[S][i]$表示当前枚举的点集为$S$，$1\to i$的路径只有一条的方案数。 考虑一次可以加一个桥，也就是$dp[S|(1<<j-1)][j]=\max(dp[S|(1<<j-1)][j],dp[S][i]+w_{i\to j})$；或者也可以挂一个点集上去，这个点集不能与之前的点集有连边，也就是$dp[S|T][i]=\max(dp[S|T][i],dp[S][i]+val[T])(S\cap T=\varnothing,T\cup i=T)$，$val[T]$表示点集$T$内所有边都连上的权值，这个可以直接预处理$DP$得到，从$T-lowbit$转移，每次添加新点连接点集内所有边即可。 观察到这样转移得出的到$n$的路径一定是唯一且最优的。时间复杂度$O(n3^n)$。 ## $081E$ 题意： 给定一个小写字母字符串，找一个最短的串使得它不是原串的子序列，在最短的前提下字典序最小。 心路历程： 想到了必须组成$len$组$a\to z$才能保证当前长度为$len$的串全部出现。然后觉得细节特别多放弃了，去$orz$了题解。 题解： 这个转移好神啊$\cdots\cdots$ 首先不难发现上面那个性质，并且我们知道匹配的过程就是从头开始，在母串中不断地找下一个位置再哪里。 那么考虑某个位置$i$，如果它后面没有$a\to z$中的某一个，就可以直接让它作为结尾（最后跟一个那个字母）。如果都有，我们可以直接选择最短的那个。 设$dp[i]$表示匹配到母串的第$i$个位置，子序列的最大长度，设$nex[i][j]$表示$i$这个位置后面的$j$号字母在哪，没有就是$n+1$，并令$dp[n+1]=0$。转移就直接$dp[i]=\min\{dp[nex[i][j]]+1\}$。 输出答案的话，就从前往后直接枚举$a\to z$从小到大贪心，每次往$dp[nex[i][j]]==dp[i]+1$的地方走。 感觉细节还没有想清楚啊$\rm qwq$ ## $083F$ 题意： 给定$n\times n$方格和$2n$个球，在$(1,0),\cdots,(n,0),(0,1),\cdots(0,n)$各有一个机械臂，机械臂可以抓它上面或者右边的球，只会抓最近的那一个，抓走就挂机。如果路径上没有球，它伸展完了也会挂机。 求$(2n)!$种机械臂伸展顺序中，能够抓完所有球的方案数。 心路历程： 完全没有半点想法。~~连行列建点都忘了~~ 题解： 原来的模型太鬼畜了，先考虑行列建点，一个点对应一个机械臂，然后一个球坐标是$(x,y)$的话就让$x$行与$y$列连边。 显然我们可以发现，如果局面合法，那么每一个连通块都必须是基环树，否则一定会出现一个点无法对应一条边的情况。 考虑怎么计数。首先对于不在环上的结点，我们没法选择，因此它们就选了对应的那条边。而环上的任意一点只要确定了选择哪条边，其它点也会选定，因此可以直接枚举任意一个点的选择。 然后开始计算顺序。注意到因为某些边如果要选择顺序是要在某些边之后的，因此我们可以让点$x\to y$连边表示$x$这个点（选的边）一定要在$y$之前选，~~问题便转化为求合法拓扑序数量也就是$\sout{PKUWC2019D1T1}$。~~可以发现连的这些边一定还在原来的基环树上（此时可脑补一下机械臂的抓取过程）。 进一步我们可以发现，环上权值和最大的两个点之间的边是不用连的，因为对于这条边对应的球来说，它的上面和右边都不可能有球，那么这两个机械臂是各自不需要另一个机械臂帮自己处理掉这个球来抓更上/右边的球的。因此我们得到了一个森林，并且这个森林的有向边从儿子指向父亲（只能感性理解不会证）。 对于每一棵这样的树来说，它的合法拓扑序方案是$\displaystyle\frac{n!}{\prod_{i=1}^n siz_i}$，因为对于每一棵子树来说，在全排列中只有$\frac1{siz_i}$是合法的，并且每棵子树互不影响，可以直接算方案。实际上可以发现对于森林的算法是一模一样的，但因为每棵基环树有选择并且选择间独立，因此我们可以先运用加法原理，把每棵基环树的两种选择分别构造的分母加起来，然后直接乘起来，分子再填$(2n)!$就可以了。 ## $084D$ 我连$D$都不会做了$qwq$ 题意： 求出是$x$倍数的集合中的数位和最小值。 心路历程： 心态崩了。 题解： 考虑每个数可以花费$1$的代价$+1$，或者花费$0$的代价$\times 10$。注意到模意义下相等的数是等价的，且我们只会去选择数位和最小的那一个，因为它们到达$x$的倍数的距离是一样的。 然后就这样建边，$1\to 0$跑一下最短路就可以了。注意$9\to 10$这样的边是不合法的，但由于一定不会出现在最短路上所以建了也无所谓。实现上可以用$01BFS$，注意$dis[1]=1$。 ## $084F$ 题意： 心路历程： 惊闻此题是多项式$\rm gcd$，深感震惊。遂弃疗。 ## $086F$ 题意： 心路历程： 被众人提醒是$514flowey$以前出的神仙题，只有$zhou888$一个人改了，遂直接弃疗。 题解： 咕咕咕。 ## $087E$ 题意： 定义两个串$A,B$“前缀~~免费~~自由”当且仅当这两个串各自不是各自的前缀。 给定一个字符串集合$S$，这个集合里的所有串长度不超过$L$，并且两两都是前缀自由的。 现在$Alice$和$Bob$要打隔膜，两人轮流加一个串进$S$，要求加进去之后$S$仍然满足上面的性质。谁不能再添加谁就输了。 $Alice$先手，请问谁必胜。 $L\le 10^{18},\vert S\vert\le 10^5,s_1+\cdots+s_n\le 10^5,s_i$表示初始第$i$个串长度。 心路历程： 以前看过，一直不会，没有**疾风狂猎犬**的帮助我连题解都看不懂。 题解： 首先可以转化一下模型，我们把所有串插到一个$\rm 01trie$里，那么可以发现，每个**有且仅有**一个儿子的结点都可以插入一条链当作自己的另一个儿子。 我们如果将每个这样的结点到$L$的距离当做状态，那么总游戏状态可以由多个状态异或而来，并且每个状态的后继也很好表示了： $$sg(x)=\mathrm{mex}(0,sg(x-1),sg(x-1)\oplus sg(x-2),\cdots,sg(x-1)\oplus\cdots sg(1))$$ 其中$0$代表只加一个点，最后一个代表一加到底。 然后可以打表发现$sg(x)=lowbit(x)$，直接异或起来就可以了。 ## $088D$ 题意： 给定一个$01$串，操作是选定一个长度不短于$K$的区间$01$转换。求能通过操作使得最终序列变为全$0$串的最大的$K$。$n\le 10^5$。 心路历程： 想了好久结论都不会。看了题解发现这个结论我又不会证，我发现我对于这种必要性结论都不大会猜。 题解： 发现如果对于任意一个$a[i]\neq a[i+1]$的$i$，我们至少需要进行一次操作，这个操作不能同时包含$i,i+1$。 于是我们就循环一遍然后令$ans=\min(\max(i,n-i))$就可以了。 ## $088F$ 我$TM$连$NOIp$原题都不会做$\cdots\cdots$~~而且考前还做了这一场但因为$\sout E$当时不会做就没看$\sout{F\cdots\cdots NMDWSM}$啊~~ 题意： 你有一种两个联通块合并的方式，这个方式即为，从每个联通块中各选出一个点，然后将这两个点合并为一个点，即将所有连向这两个点的边连向这个新点，并将原来的两个点以及那些边删去。问你需要通过这样的方式，将$A$条长度不超过$B$的链合并成一棵给定的树。求在满足$A$最小的情况下，最小的$B$的值。 心路历程： 没看出来最大值最小，一直在想有奇数儿子的点怎么合并，然后就凉了。好像我$NOIp$也是这么凉的，怎么重蹈覆辙啊。 题解： 其实$A=\frac O2$，$O$是奇度数点个数。显然每个这样的点都会拉伸出一条链。但不知道这个也没问题，可以直接用贪心解决。 至于求$B$，二分答案即可，每次把所有儿子传上来的链放到$set$，从大的开始匹配，要求链长$\le mid$，如果有两个不能匹配的直接$\rm return\ 0$，否则就把最大的不能匹配的传上去，时间复杂度$O(n\log ^2n)$，注意要从最长的开始匹配，因为我们要保证传上去的也尽量小。 ## $089D$ 首先这题是一道很简单的题，我现在应该很不冷静。 题意： 有一个无限面积的矩形，给定$n$个点的坐标和对应的颜色要求，选定一个原点，求能满足的最多要求个数。 心路历程： 思路混乱，于是没想出来 题解： 同余（$2k$，可以看下图）一下，枚举原点位置，直接用两个二维前缀和计算即可。 ## $090F$ 题意： 有$n$堆石子，每堆$a_i$个，有一个数$k_i$，$Alice\& Bob$轮流取，每回合取一个堆里的石子每堆只能取$1\to\lfloor \frac{a_i}{k_i}\rfloor$个（以当前石子个数为准），无法取者输。求谁必胜。 心路历程： 我承认我找规律确实很菜，这个规律我的确没找出来。 题解： 打表，从$0\to a_i$每$k$个一行，发现每行第一个都是$i-1$，然后发现有些数是相同的。 ~~通过查阅百度~~可以发现$sg(x,k)=sg(x-\lfloor\frac xk\rfloor-1,k)$，然后可以发现~~那确~~确实~~实~~是这样~~子~~的~~啦~~。 考虑有了这个规律后怎么算。 我一开始想的时候觉得“这玩意儿不是可以直接算么”，然后发现$k$可以特别大然后就根本算不了$orz$。 可以用一下整除分块的思想。注意到有很多$\lfloor\frac xk\rfloor$是相同的，可以一次把它们跳完。跳到一个$x\equiv 0\pmod k$就可以直接返回答案了。 注意和整除分块不同的是它是上面在变，实现上就是找到当前块的第一个数来决定跳多少次，也就是$(x-x/k*k)/k=(x\%k)/k$，$(x/k*k)$就是当前块的第一个数。那么跳的距离就再乘$k$就可以了。时间复杂度$beginend$说是$O(n\sqrt{k\log k})$。 ## $092F$ 题意： 有一个有向图，求把某一条边翻转之后，$SCC$是否发生变化。 图无重边无自环。$n\le 1000,m\le 2\times 10^5$。 心路历程： 猜到了不少结论，但无法将结论对应到解法上。 题解： 首先如果一条$a\to b$的边翻转后$SCC$变化，意味着它们之间的连通性发生变化，要么多构成一个环，要么多拆掉一个环。如果原来$b$能到达$a$且$a$能通过其它方式到达$b$，那么换边肯定是没有影响的，它们所处的$SCC$岿然不动。如果原来$b$到不了$a$，$a$也只能这样到达$b$，这种情况$a,b$一开始不会在一个$SCC$里，它们翻转也一定不会形成一个环。可以发现不会出现一拆一增的情况，那样其实会形成一个大的$SCC$。这个可以脑补一下双环。 然后可以枚举每个点搜一下找到这个点能到的点，注意一开始不标记能直接到达的点。最后枚举每条边看其是不是上述情况就可以了。时间复杂度$O(nm)$。 ## $093E$ 题意： 有一个$n$个点$m$条边的有向图，给每条边染黑白，要求原图必须存在一个由黑边和白边组成的生成树，且在所有由黑边与白边构成的生成树中，最小生成树的边权为$x$，求染色方案数。 $n\le 10^3,m\le 2\times 10^3$。 心路历程： 根本没认真想，根本没想出来。状态有问题。 还没看到$m\le 2\times 10^3$。 题解： 先求出$MST$。 然后枚举每条边，再枚举这条边一定要被选的情况下$MST$大小。这个就是暴力维护就可以了，就是找到路径上边权最大值然后替换。我们设这个$MST$的权值为$val$。 如果$val>x$，这条边不会在上面，任意涂色。 $val=x$，那么这条边可以任意涂，除了所有这种情况的边的生成树的颜色都是一样的情况。 $val<x$，这条边一定得和其它这种情况的边是同一种颜色，并且得和这些生成树上的边是同一种颜色。那么它们的颜色是被绑定的，不算就可以了。 也就是说，$ans=2^{c_1}\times(2^{c_2}-1)\times 2$，最后那个$2$就是$case2,3$全部一样的两种颜色情况。 ## $094F$ [看肖大佬博客。](https://www.cnblogs.com/ShichengXiao/p/9775499.html) ## $096D$ 这场好没面子啊，$DEF$都不会。主要是这题我考场上没做出来有心理阴影。 题意： 不想写。 题解： 考虑实际上只会掉头一次，否则一定不优。于是记录前缀后缀最大值，枚举一开始按$clockwise/counter$走，再枚举掉头位置就可以了。 ## $096E$ 题意： 一个拉面餐厅有$n$种配料，一碗拉面可以任意添加任意的配料，也就是说，一碗拉面可以添加$2^n$种不同的配料组合。一个人要来拉面餐厅买若干碗拉面。求他有多少种不同的方式，满足所有购买的拉面的配料各不相同，且每种配料在所有购买的拉面中至少出现两次。 $600pts:n\le 50$ $900pts:n\le 3000$ 心路历程： 一开始我觉得只要用一些盘子满足条件，剩下的盘子可以随便拿。这些盘子的数量不会超过$2n$，然后我就在想如何$DP$。然后想到了通过枚举出现次数$0$的和$1$的进行$DP$，但是就不会做了。而且这个方法有个问题，就是因为要保证不算重，前面这些盘子要保证每种物品的出现次数正好为$2$。然而有时候某些方案不会出现这样类型的盘子，然后就凉了。 题解： 首先这个$600pts$是个$AGC\ B$难度的容斥，考虑不合法的方案就是有出现次数为$0,1$的配料，我们就分别枚举。但是发现出现次数为$1$的还要安排，要把它们安排到$k$个相同的非空盒子里。 $$ans=\sum_{i=0}^{n}(-1)^i2^{2^{n-i}}\binom{n}{i}\sum_{j=0}^{i}\binom{ i}{j}\sum_{k=1}^{j}\begin{Bmatrix}j\\k\end{Bmatrix}(2^{n-i})^k$$ 前面那$2^{2^{n-i}}$表示$2^{n-i}$种选项，每种都有可能出现或否。 ## $097E$ 题意： 给定$n$黑$n$白球，每种颜色的球各有编号$1-n$。 每次操作可以交换相邻两个球，要求最终序列黑白都要有序，求最小操作次数。 $n\le2000$。 心路历程： 我记得我好像之前想了个贪心还是啥做法，不知道对不对，但应该是假的。 题解： 考虑一个序列排序的最小交换次数是逆序对个数，这个就是你考虑每个数至少要与哪些数交换，贡献和加起来除以$2$（因为每个交换算了两次）就是逆序对个数。 但是这个序列，因为我们并不知道终态是什么，因此我们不知道逆序对个数是什么。当然我们要把逆序对的定义扩展一下，就是始态$i<j$，终态$i>j$的点对。 于是这个东西我们可以$DP$，设$dp[i][j]$表示为**编号**前$i$个黑球，前$j$个白球，对于两种颜色的球都要排成顺序的最小逆序对数。 我们考虑每次新填一个黑球，状态变为$dp[i+1][j]$。那么这个球的**位置**前面，编号比$i$大的黑球，编号比$j$大的白球都是要交换的，不然填不到这个位置来。而那些编号小的已经确定好顺序了，这个球移动不会产生影响。白球则同理。 那么现在就要求每个位置前面，编号小于某个数的白/黑球个数。这个可以直接求个二维前缀和得到，其实本质就是个递推。总时间复杂度$O(n^2)$。 ## $097F$ ~~出题人$\sout{\rm immortalCO}$。~~ 题意： 有一棵$n$个节点的树，~~黑白~~猫要上树。 猫可以走一步并把目标点反色，也可以停留并把当前点染色。都需要花费$1s$。 求把树染成黑色的时间。$n\le 10^5$。 心路历程： 猜到了一个确定起点，并让终点为起点时答案就固定了，只要删掉黑子树就可以了。然后一直以为取不同白点为起点黑子树不一样，我他妈是个傻逼。 题解： 首先上面的黑子树是一样的，那么先这样跑出一个答案。这样的路径是一个“环”~~，具体形状可以参考$\sout{popcart}$城镇手指~~。那么这样的答案就是路径上边数量的两倍加上**完全**路过所有点后白点的个数。 然后我们的目标是找到一条对答案贡献最大的路径，然后把它删掉，就得出了真正答案。 注意到一个没调整的点的入度减少$1$，会让它变色，那么我们即使少经过一次这个点，也需要花费$1s$来反色，代价没有变化；如果一个调整了的点入度减少$1$，我们既不需要多遍历也不需要调整，代价减少了$2s$。那么就可以直接找一个这样的直径就可以了。 ## $099E$ 题意： 把一个图划分成两个部分，使得两个部分都是完全图。 最小化划分得到的两个图的边数。$n\le 700,m\le\frac{n(n-1)}2$。 心路历程： 石乐志，连二分图都没发现。 题解： 首先可以发现两个完全图的补图是二分图。 于是我们对补图的所有连通块进行二分图染色，如果有一个不能就是无解。 那么现在二分图染色完了，我们发现同一个连通块里的异色点只能分开，这个证明的话你就考虑一条链，你随便把一个跟一号点不相邻的点拿过来，然后发现最后与一号点相邻的那个点总会和一号点分到一边，这就显然不行。 当然，不同连通块的异色点是可以放在一起的，因此我们可以用个背包随便统计一下，最后枚举某一边的点个数就可以了。 ## $099F$ 惊闻此题是哈希，然而我却是直接判的，不知道为啥。 故此暂时留坑。 ## $100D$ 题意： 把一个序列划分成$4$段，使得最大权值和减最小权值和最小。 $n\le 2\times 10^5,a_i\le 10^9$。 心路历程： 我是傻逼。 题解： 其实是个暴力，就是我们枚举中间的那个断点，然后再枚举左边，然后再枚举右边。 发现中间的断点往右移的时候，左边断点一定单调不递减，右边也是这样。并且显然当前枚举到的位置没有上次优下次显然不会更优。 因此可以直接暴力了。时间复杂度$O(n)$。 ## $102E$ ## $103F$ 题意： 给定每个点到其它所有点的距离，构造这样一棵树。 心路历程： 没啥历程，被三道构造做吐了无心再想。 题解： 考虑最大的点一定是叶子，那么我们可以确定它的父亲。 设$v$为叶子$u$为其父，显然$dis[v]=dis[u]-(n-1)+1$（$+1$是到叶子的距离）。 我们推广这个结论，对于两个有边相连的点$u,v,dis[v]=dis[u]-siz[v]+siz[u]$。，这里的$siz$指的是它那一边的子树大小。 然后我们其实已经可以按距离排序倒序确定父亲了。如果没有满足条件的父亲就是无解的。这样的过程一定是自底向上的，那么我们当前遍历到的结点的儿子肯定被遍历完了，所以$siz$一定是正确的。