Misaka16172's Blog

前言 神秘新颖好玩的题，有个不知道是啥的做法，感觉讲不太明白。。 思路 第一步转化应该比较简单，先前缀和，然后 [l,r][l,r][l,r] 合法相当于 ∀x,y∈{B,C,S},prer,x−prel−1,x≠prer,y−prel−1,y\forall x,y\in \{B,C,S\},pre_{r,x}-pre_{l-1,x}≠pre_{r,y}-pre_{l-1,y}∀x,y∈{B,C,S},prer,x​−prel−1,x​​=prer,y​−prel−1,y​，即 prer,x−prer,y≠prel−1,x−prel−1,ypre_{r,x}-pre_{r,y}≠pre_{l-1,x}-pre_{l-1,y}prer,x​−prer,y​​=prel−1,x​−prel−1,y​，相当于得到三个数组 ai,0=prei,B−prei,C,ai,1=prei,B−prei,S,ai,2=prei,C−prei,Sa_{i,0}=pre_{i,B}-pre_{i,C},a_{i,1}=pre_{i,B}-pre_{i,S},a_{i,2}=pre_{i,C}-pre_ ...

嗯哦唉批告一段落，随之而来的是从零开始的文化课生活。 刚考完的时候真的好难受好难受啊，前两天出分数线的时候又好难受啊，努力了这么久换来的只是这种水平吗？ 高二整整一届除了我以外都被送退役了。傻逼 ccf，用一道题（edit）或者一纸公告就能让选手的努力付诸东流。很幸运这俩都没影响到我（不幸中的万幸吧。差点连个 1= 都没了。本来以为 1= 是下限中的下限来着。） 为啥老是尝试去骗自己。如果你想起来了 t4 2log 是你做过的会怎么样，如果你仔细看了 t3 的部分分、稍稍思考一下高档一点的部分分会怎么样。 但事实就摆在那里。无论怎么欺骗自己，你其实是有水平的，就是没发挥好之类的。全都是借口啊。把 whk 扔掉彻底疯狂训了一年，只有一个擦线 1= 的实力。 这个 whk 也是彻底司马了。目前没见过任何一个选手能让 whk 成为 oi 生涯里最大的绊脚石的。我真是奇异搞笑。家长也是奇异搞笑，闹这么大对我有任何好处没有？？？还觉得自己很牛逼很有爱心很为我着想？？？蓝的盆。 还有两周期末考，我能苟出一个好分的成绩的概率有多大？之前我信誓旦旦地觉得能够轻取三倍队线，付出了全部努力、且有足够精神 ...

いつもひとりで歩(ある)いてた 一路走来形单影只 行(い)く先(さき)には崖(がけ)が待(ま)ってた 路途前方险峻波折 それでもあたしは歩(ある)いた 即使如此我依然前行 強(つよ)さの証明(しょうめい)のため 只为证明这份坚强 省流：gg，100+100+[4,16]+[20,32]=[224,248]100+100+[4,16]+[20,32]=[224,248]100+100+[4,16]+[20,32]=[224,248]。 Day -2 吧唧到货了。 Day -1 最后一天，教练说不给我们布置模拟赛，想回家休息的甚至可以直接请假。 于是在机房打摆。 上午先和 hyf zzj cyx 随机打 gen，他们说玩 gen 可以在考场上化身 gen 王/tiao 然后跟 sch duel potpvp，太牛，拼尽全力无法战胜，换了十几个模式都是被薄纱/oh/oh 中午花了 120 七个人点了六个披萨，赤爽了！！ 下午发现我的 agc 还有一半没做，我草这咋办，赶紧滚回来做 agc 结果脑子特别不清楚，看一题不会一题，一下午就做了三道。。 放学之后赶往酒店，经典环节之在旁边的 ...

前言 没有发现 dsu on tree 题解，虽然复杂度不是很好不过胜在好想，来写一篇。 思路 首先考虑枚举一条边，则已经有一个联通块大小可以确定，那么剩下两个联通块大小尽量平均时最优。 两条边有祖孙关系是好搞的，直接 dfs 时把从根到当前节点的所有子树大小扔进 multiset 里并二分，回溯时 erase 掉即可。 两条边没有祖孙关系时，若当前遍历到节点 uuu，那么此时 multiset 中应当包括除了根到 uuu 和 uuu 子树里的所有节点的子树大小 szvsz_vszv​。如果一开始将所有点的子树大小全部插入，则有一个 O(n2log⁡n)\mathcal{O}(n^2 \log n)O(n2logn) 的暴力算法，即遍历到每个点都直接将子树里的所有值清空，然后再统计答案。 考虑使用 dsu on tree，计算重儿子答案时不还原 multiset 里的值，这样遍历到每个点时只需要暴力清空轻儿子的值就可以计算答案。 复杂度 O(nlog⁡2n)\mathcal{O}(n\log ^2n)O(nlog2n)，两个 log⁡\loglog 分别来自 dsu on tree ...

有些人去世了。 但他们仍会以一种近乎唯心的形式活在我们的记忆里，与我们一如往常地互动、交流。 将这个原理推广到因各种原因离我们渐行渐远的人身上。 于是我们就可以成功地将他们留下、 留在自己构筑的沙盘里，且好处是他们变得愈加完美了。

前言 第一次也是最后一次作为高中正式选手参加 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) 级别就 ...