House_of_Fan

AT_abc444_c[ABC444C] AtCoder Riko 思路 这道题细节比较多，导致很多人赛时没切掉。 一步一步来： 首先我们知道每根饼干最多分裂一次，也就是说对于每一种初始长度，若分裂出的其中一根饼干的长度确定，则也可以得出另一根的长度就是总长减第一根。 由此我们就可以得出计算一种初始长度是否可行的方法。 只要遍历一遍每种存在的长度，判断一下与其对应的长度存在的饼干数量是否和它相等即可。 而对于长度恰好为初始长度一半的，判断其数量 $x$ 是否 $\equiv 0\pmod 2$，因为它对应的是自己，一定要两两一组。 对于长度等于初始长度的，直接跳过，它不需要和长度为 $0$ 的饼干拼接。 在发现验证某初始长度是否成立的方法后，易得到一个结论：成立的初始长度只有可能是最长的长度或者最长的长度加上最短的长度。 我们设长度为 $len$，最长为 $mx$，最短为 $mi$，分类讨论一下： $len<mx$：无法得到长度最大的，一定不行； $mx<len<mx+mi$：最大的就算加上最小的仍然大于初始长度，无法得到，一定不行； $mx+mi<le...

CF2194B Offshores 思路 很简单的题，没想明白为什么有人切了 CD 没切。 问了一下 @WBJ0429 为什么做那么慢，得知他以为可以进行多次转移，把某个银行中剩余的钱作为“补给”，在最后 $10$ 分钟才发现。 实则这是错的。 ▶ [证伪] 设有银行 $A,B,C$，我们的最终目标是 $C$。 有两种方法（从 $A$ 到 $B$ 和从 $B$ 到 $A$ 只是交换编号，不多赘述），分别是 $A\to B\to C$ 和 $A\to C,B\to C$。 显然 $C$ 中有多少钱不影响最终的结果相对大小。 则第一种转移情况会使得在 $B\to C$ 这一步时转移的钱数变少，因为 $A\to B$ 的一部分再转移一次显然不到 $cnt_a\times y$，而 $B$ 中的剩余部分又不足以再转移一次。 故从每个银行出发只转移一次一定优于转移多次。 我们知道若要使得某银行中的存款数达到最大，则需要把其他银行中所有能转...

CF2194D Table Cut 思路 假设一共有 $tot$ 个 $1$ 块。 第一部分很简单： 注意到任何分配均可以成立，故最大值一定为 $\lfloor\frac{tot}{2}\rfloor\times\lceil\frac{tot}{2}\rceil$ 这样的构造。 考虑第二部分如何构造： 我们假设上半部分分 $tar=\lfloor\frac{tot}{2}\rfloor$ 个 $1$，考虑如何构造。 预处理第 $i$ 行的总和为 $cnt_i$，现在已经加入了 $now$ 个，若 $cnt_i+now<tar$，则直接加这一行。 若 $cnt_i+now\ge tar$，则从后往前枚举，若能加则加，不能加就说明现在已经够了。 这样的构造要如何转化为题目要求的输出呢？ 首先若要加一整行，则直接输出 D，若要加上行末的 $k$ 格，则输出 $m-k$ 个 R，然后输出一个 D，再补上该行剩余的 R 即可。 最后输出剩下的 D。 代码 12345678910111213141516171819202122232425262728293031323334353637...

CF2194C Secret message 思路 先找所有可能的长度（总长的因子），从小到大排序。 枚举长度，枚举总字符串的每一位对应到子字符串的哪一位。 用状压的思想枚举子字符串的每一位所有可能值，从全集开始，每次都或上当前位所有存在的字母并集，若最后状态还不等于 $0$，则此位可以成立，若为 $0$ 直接 break。 若全部遍历完后则输出每一个状态最低位的对应字母（题目要求任意子字符串皆可）。 笑点解析：没初始化调了 $10$ 发都 TLE，结果用第一发代码加个初始化就过了。 代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980#include<bits/stdc++.h>#define fir first#define sec second #define int long long#define pii ...

AT_abc444_e [ABC444E] Sparse Range 思路 题目要求求出满足对于所有的 $1\le l\le r\le n$ 所构成的区间，能使得区间中所有数之间的差值都大于 $D$ 的 $(l,r)$ 对数总和。 注意到对于每个区间，这个要求都比它的子区间更难达到。 所以对于每一个 $r$，若 $l_1<l_2\le r$，则若 $(l_1,r)$ 满足要求，它的子区间 $(l_2,r)$ 显然一定也满足要求。 而若要从 $l_2$ 推到 $l_1$，则需要所有 $l_1$ 和 $l_2$ 中间的数之间满足要求，且这些数都与 $l_2$ 到 $r$ 中间的数满足要求。 考虑使用双指针。 从大到小枚举 $l$，全局变量 $r$，每当有一个新的 $l$，就二分找现在小于等于它的最大的数和大于等于它的最小的数，如果差值小于 $D$，就将 $r$ 减一，然后再判断，直到满足为止，然后从 $l$ 到现在的新 $r$ 之间的所有区间全都满足，不从 $l$ 出发的前面统计过了，所以直接加上 $r-l+1$ 就行了。 由于每个 $r$ 都只会被枚举一次，所以可以通过。 代...

AT_abc444_d [ABC444D] Many Repunit Sum 思路 注意到每一步操作 $i$ 都是把 $1$ 到 $a_i$ 的数位的数值加 $1$ 显然类似高精度的实现。 然而直接枚举不行，因为只有一次查询，所以考虑支持区间修改的差分。 最后做一次前缀和，再处理一次进位即可。 代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include<bits/stdc++.h>#define fir first#define sec second #define int long long#define pii pair<int,int>#define fep(i,s,e) for(int i=s;i<e;i++)#define pef(i,s,e) for(int i=s;i>e;i--)#define rep(i,s,e) for(int i=s;i<=e;i++)#define...

CF2190B1 Sub-RBS (Easy Version) 思路 有一个很简单的思路。 先说结论：如果前 $n\div2-1$ 个中存在右括号，答案是 $n-2$，否则答案是 $-1$。 证明 以下三个命题相互等价： 存在长度为 $l-2$ 的更好子序列； 存在任意长度的更好子序列； $s$ 的第一个右括号后至少有 $2$ 个左括号。 等价性简化证明 $1$ 到 $2$（显然成立） 若存在长度为 $l-2$ 的更好子序列，该子序列本身就是“任意长度的更好子序列”，直接得证。 $2$ 到 $3$ 设 $t$ 是更好的子序列，第一个差异位为 $i$，满足 s[i]==')' 和 t[i]=='('； 差异导致 $t$ 前缀 $0$ 到 $i$ 的平衡度（左括号数 - 右括号数）比 $s$ 多 $2$； $t$ 是合法 RBS，需后续右括号抵消该额外平衡度，且这些右括号均来自 $s$； $s$ 是合法 RBS（最终平衡度为 $0$），故 $s_i$（第一个右括号）后必须有至少 $2$ 个左括号，抵消多余平衡度，得证。 $3$ 到 $1$ 定位关键位置：$pos...

CF2191B MEX Reordering 思路 将数组从小到大排序，这样前面一定会出现 $a$ 个 $0$，然后在 $a$ 之后的后缀数组的 MEX 值一定是 $0$，不会与前缀数组相同，而在 $a$ 及 $a$ 之前的前缀数组的 MEX 值一定是 $1$，只要后面有至少一个 $1$ 出现就行了。 而如果没有任何一个 $1$，且存在两个及以上的 $0$，那一定有出现以某点为分界的前缀和后缀 MEX 值都为 $1$，一定不行；若全局没有出现 $0$，则所有前缀和后缀的 MEX 值皆为 $0$，也一定不行。 所以直接按照上面判断就行了。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include<bits/stdc++.h>#define fir first#define sec second #define int long long#define pii pair<int,int>#define fep(i,s,e) for(i...

AT_arc212_a [ARC212A] Four TSP 思路 考虑如何构造出一个经过 $4$ 个点的环。 定义不存在任何端点为同一个点的两条边是一组对边。 画图后，我们发现，只有任意两组对边才可以组成一个符合题目要求的环。 考虑枚举这三组对边分别的长度和。 发现第三组对边的长度和可以由前两组求得，并且必定存在合法的六条边的长度分配。 则枚举两组对边长度和 $a,b$，第三组对边长度和为 $c$。 而具体到每一条边时，已知和为 $p$，则长度分配方法有 $p-1$ 种。 最后将题目转化为这个式子（设 $c=k-a-b$）： $$\sum_{a=1}^{k-2}\sum_{b=1}^{k-1-a}(k-\max(a,b,c))\times(a-1)\times(b-1)\times(c-1)$$ 直接按照这个式子实现即可。 要注意 $a,b,c$ 都是正整数，注意判边界条件。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142#include<bits/stdc++....

AT_arc212_b [ARC212B] Stones on Grid 思路 要使得所有第 $i$ 行和第 $i$ 列的棋子数均相等，则需要使选的所有 $x_j=i$ 和 $y_j=i$ 的数量相等。 那这不就是找环吗？ 形式化题面：如何找到含有给定边 $(x_1,y_1)$ 的最小环。 这就很简单了，跑出 $y_1$ 到所有点的最短路 $dis$，再枚举所有边，若对应的 $y_i=x_1$ ，则答案和 $c_1+dis_{x_i}+c_i$ 取最小值。 对上面的式子的解释：从 $x_1$ 出发先到 $y_1$，然后从 $y_1$ 出发到某个点 $x_i$，最后从 $x_i$ 出发回到 $y_i$，也就是 $x_1$。 没有负边权，可以用 Dijkstra 跑。 代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include<bits/s...