Misaka16172's Blog

前言 第一次也是最后一次作为高中正式选手参加 CSP-S，玩得很开心！（是不是这个文案到 NOIP 还能用一次/kel） Day -1 下午在机房 rand 了 inf 道题，一道都不会，于是睡大觉。 晚上打了三四个板子，发现 tarjan 全忘了。 睡的不咋好，夜里醒了一次。 Day 0 上午睡大觉。 中午吃完饭跑去买了一车吃的，在店里碰见了 cc，并回家顺了一包纸。 在校门口碰见了 timswn 并恰 v，一块进了考场。 中途随机遇到了若干同学。 省流：100+100+35+0，我是奶龙。 开局挺不错的，花了不到二十分钟调好了 sublime 和 arbiter，拥有了一个极其舒适的调试环境。打开 pdf 发现没有任何一道 mod998244353 和输入俩数输出一个数，这场下限应该是稳的。 十分钟切了 t1，这啥唐龙题？？然后火速莽了 t2 60 性质分 + 暴力和 t3 暴力，感觉还挺良好的。 t2 把车子弄成线段之后就变成了一个看起来很典的问题，但我为啥只会差分约束啊？画了半天图然后终于把边权全转成正的了，可以跑 dij 最短路求最大解，写写写写写，之后的俩小时我也不知 ...

前言 upd on 2024.10.16：发现了针对原思路的 hack，修改了不正确的特判部分 场上写了不用动脑子的 40pts 部分分，挂成 4pts。 比较恶心的分类讨论构造题，但个人觉得比 T2 T4 可做，反正都是我做不出来的题（？） 思路 发现这个题的限制似乎不是特别多，非常多的情况下都可以把不一样的字符两两配对，于是应当尽量使最终的解接近这种形式。 这个题的两个特殊性质极为友好，先从特殊性质入手。 先来看性质 A：考虑一张将每个字符出现次数从小到大排序的柱状图，发现如果每次取出其中出现次数最多的两个字符，这张柱状图将越来越平缓，由于保证每个字符出现次数 ≤n2\leq \frac{n}{2}≤2n​，每个字符最终都能够被配对。于是按照该思路使用大根堆等维护每个字符的出现次数并模拟即可。 将性质 A 的做法推广到串长为奇数的情况：将剩下的最后一个字符随便扔到一个子序列中即可。如果这样不合法，那么所有的 ⌊n2⌋\lfloor \frac{n}{2} \rfloor⌊2n​⌋ 个子序列中一定均含有该字符，加上本身后，与“每个字符出现次数 ≤⌊n2⌋\leq \lfloor ...

√\color{green}√√：vp 时独立做出。 √\color{orange}√√：vp 后独立做出。 √\color{red}√√：经过提示后做出。 −\color{gray}-−：未做出。 ×\color{red}××：尝试提交过，未做出。 A √\color{red}√√，*900。 《开幕雷击》，vp 的时候被这糖题卡了。 考虑到同一种字母构成的子序列带来的贡献无论如何都无法去除，贪心地尽量让同一种字母放在一块即可；同时每种字母的数量应尽量平均，所以直接先将每种字符添加 ⌊n5⌋\lfloor \frac{n}{5}\rfloor⌊5n​⌋ 个，再将剩余的 nmod  5n\mod 5nmod5 个字母添加进来即可。 B1 √\color{green}√√，*1000。 简单版本，n=2n=2n=2。设 min⁡(b0,b1)=l\min(b_0,b_1)=lmin(b0​,b1​)=l，max⁡(b0,b1)=r\max(b_0,b_1)=rmax(b0​,b1​)=r。 分类讨论： 当 a<la<la<l 时，学生会被在 lll 处的老师抓到， ...

前言 感觉是最近做过最有意思的一道容斥计数啊，来补篇笔记。 思路 下文将满足 1≤a<b<c<d≤n1\leq a<b<c<d\leq n1≤a<b<c<d≤n，且 pa,pb,pc,pdp_a,p_b,p_c,p_dpa​,pb​,pc​,pd​ 从小到大的排名在这四个数中依次为 1≤i,j,k,l≤41\leq i,j,k,l\leq 41≤i,j,k,l≤4 的四元组 (a,b,c,d)(a,b,c,d)(a,b,c,d) 简称为 ijkl\text{ijkl}ijkl，若排名不确定则用 x\text xx 代替。例：1423\text{1423}1423，1x2x\text{1x2x}1x2x。 简单概括一下题意：求 111 到 nnn 的排列中 1324\text{1324}1324 的数量减去 1243\text{1243}1243 与 1432\text{1432}1432 数量之和的结果。 看见这几个奇形怪状的东西第一反应是拿什么数据结构科技直接跑去暴力求（毕竟 1234 4321\text{1234}\ \tex ...

前言 笑点解析： 思路 一种很新的建图 trick，看完题解你会发现这题的思想和 [ABC232G] Modulo Shortest Path 一模一样。 先想缩小数据范围怎么做。题意相当于一堆形如 Xi+(Ti−Sj)≤XjX_i+(T_i-S_j)\leq X_jXi​+(Ti​−Sj​)≤Xj​ 的不等式，给定 X1X_1X1​，要求最小的一组解。如果点数 mmm 缩小到 500500500，这就是一个差分约束跑最长路的经典问题，直接暴力从每个 iii 向 jjj 连边建图跑最长路然后输出答案即可，边数为 m2m^2m2 级别，但有一个很好的性质就是题目保证 Ti≤SjT_i\leq S_jTi​≤Sj​，差分约束边权全部为非正值，可以不用跑 spfa，使用复杂度为 O(m2log⁡m)\mathcal{O}(m^2\log m)O(m2logm) 的 Dijkstra 求解即可。关于跑最长路能最小化解的正确性不再赘述，感性理解一下最短路算法的松弛过程即可。 我们发现这个做法的瓶颈主要在于图上的边数，如果能把边数缩小到 O(m)\mathcal{O}(m)O(m) 级别就 ...

前言 赛时四发罚时直接葬送 perf，写完还以为是个脑子题，过的人肯定不多。 累了，能不能数据加到 n≤107n\leq 10^7n≤107 把写 nlog⁡kn\log knlogk 的都叉掉（虽然我当时降智地使用了《倍增》来求树上 kkk 级祖先）。 思路 把每个 iii 向 xix_ixi​ 连边，形成一张 nnn 个点 nnn 条边的有向图。 由于每个点出度均为 111，这张图实际上是内向基环树森林。 观察到进行 kkk 次操作对 aia_iai​ 的影响实际上就是以 iii 为起点在图上走 kkk 次。 那么可以分类讨论两种情况：kkk 次操作后，第 iii 个点在环上 / 不在环上。 首先拓扑排序一遍找出所有在环上的点，dfs 出每个环的大小并对每个环上的节点从 000 开始进行标号。设某个环的大小为 sss，手玩发现如果已经走到了该环上的第 iii 个节点，还需要走 xxx 步，则最后一定落在环上的第 (i+x)mod  s(i+x)\mod s(i+x)mods 个节点。于是直接从环上的每个节点出发再 dfs 一遍，预处理出每个不在环上的节点将会到达的环上节点与需要走 ...

思路 不太一样的做法。 直接爆搜每条边的颜色复杂度是 2n2^n2n，我们可以尝试折半搜索然后合并答案。 具体地，把 n−1n-1n−1 条边分成两半，分别搜索每条边染黑还是白，搜索结果是一个二进制数，第 iii 位是否为 111 代表是否满足第 iii 个条件的限制。O(1)\mathcal{O}(1)O(1) 检查是否满足条件可以先预处理每个条件所包含的边集 EiE_iEi​，然后再把搜索出来的边集 SSS 与 EiE_iEi​ 做按位与即可，这部分预处理时间复杂度为 O(nm)\mathcal{O(nm)}O(nm)，搜索时间复杂度为 O(2n2m)\mathcal{O}(2^{\frac{n}{2}}m)O(22n​m)。 搜索完之后我们得到了两个二进制数组成的集合，分别代表前 n−12\frac{n-1}{2}2n−1​ 条边染色后满足条件的情况和后 n−12\frac{n-1}{2}2n−1​ 条边的情况。可以考虑对于第一个集合里的每个元素分别计算可以和多少个第二个集合里的元素配对。两个状态 a,ba,ba,b 可以配对当且仅当 aor⁡b=2m−1a\operatorn ...

前言 ABC 出题人喜欢出板子是吧，像这种出题人就应该好好用乱搞拷打一下。 拜谢 @RailgunZzzz 以及其他 HL 群群友在卡常和卡哈希时给予的若干帮助。 思路 先处理出整串哈希，然后我们考虑根号分治。 设根号分治的阈值为 TTT，则有两种算法可以用来回答询问： 对长度 >T>T>T 的串暴力。求出被询问的串的哈希，从左到右枚举被匹配的子串的右端点，把两个哈希 O(1)\mathcal{O}(1)O(1) 进行比较，单次询问复杂度 O(n)\mathcal{O}(n)O(n)。设 sum=∑∣t∣sum=\sum |t|sum=∑∣t∣（ttt 为被询问的串），长度 >T>T>T 的串最多被询问 O(sumT)\mathcal{O}(\frac{sum}{T})O(Tsum​) 次，所以这部分时间复杂度为 O(nsumT)\mathcal{O}(n\frac{sum}{T})O(nTsum​)。 对长度 ≤T\leq T≤T 的串预处理。预处理原串所有长度 ≤T\leq T≤T 的子串的哈希值，扔到 TTT 个 vector 里进行排序， ...

前言 感觉这个题跟 P7114 [NOIP2020] 字符串匹配 莫名有点联系啊，我如果没写过那题是肯定不会做这个题的。 思路 一开始先特判掉全 a 串，显然此时答案为长度 −1-1−1，以下讨论全部默认给定的串不是全 a 串。 性质 1：一个全 a 串一定不能成为答案，证明显然。 性质 2：一个合法的答案串一定是原串的一段前缀删去前缀的若干个 a。 证明：设原串 sss 中第一个非 a 的位置为 ppp，一个不满足该性质的 sss 的子串 t=slsl+1⋯srt=s_ls_{l+1}\cdots s_rt=sl​sl+1​⋯sr​（不妨设 lll 为 ttt 第一次出现的左端点），则条件等价于 p<lp<lp<l。如果 [1,l)[1,l)[1,l) 能被合法划分，由于 sp≠s_p≠sp​​= a，这段字符串中必然有一段 [l′,r′]=t (1≤l′≤p≤r′<l)[l',r']=t\ (1\leq l'\leq p\leq r'<l)[l′,r′]=t (1≤l′≤p≤r′<l)，否则第 ppp ...

题单 ABC305F 直接 dfs + 回溯一定不会让一个点被遍历超过 222 次，于是直接 dfs 就做完了。 CF1658C 首先转化题意， cic_ici​ 相当于把第 n−i+1n-i+1n−i+1 个元素右边的所有元素全扔到最前面所形成的排列的价值，此时排列开头的元素为 pn−i+2p_{n-i+2}pn−i+2​（c1c_1c1​ 例外，它是原排列）。于是发现当且仅当排列以 nnn 开头的时候才有 c=1c=1c=1，这题就已经做完一半了。 然后考虑以 pn,p1,p2,⋯ ,pn−1p_n,p_1,p_2,\cdots,p_{n-1}pn​,p1​,p2​,⋯,pn−1​ 这个排列为基础，一个一个把最右边的元素扔回第一个，发现这个过程中价值要么减少要么至多增加 111。于是这题就做完了。 如何证明价值无论减少多少都能构造出一个排列？发现当前排列里元素到底是多少并不重要，只需要在乎相对大小即可，故你往前扔的时候想吞掉前面几个元素都可以。 CF1905C 这个题比较考验注意力和手玩能力，你需要注意到我们实际上一直只是在对字符串字典序最大的一个子序列进行右移，然后你找出这个子 ...