House_of_Fan

CQCPC 2026 游记 可能对题目有部分意义上的剧透，谨慎观看。 成都 - 重庆 本来是统一提前一天去的，但是校领导怕“学生半夜溜出酒店，有安全隐患”，所以只能用诡异的出行方式当天去。 早上 5:30 起床出发准备坐地铁首班车，6:00 在校门口的草路 C 口集合。 最后几分钟教练骑着电瓶车赶到，但是 Gaochenxi103_QAQ 询问存放在教练处的手机时才发现忘拿了，还在办公室。 教练表示办公室门没锁，让 Gaochenxi103_QAQ 跑去拿，不出意外地出了意外：“门是锁着的”。 耽误了 5min，坐的第二班车。 车上大家都在打游戏，最整齐的一集，没有手机的 DimStar 看起来快急哭了。 到站之后高铁还有 18min 开走，于是全机房如同蝗虫过境地冲到了检票口，好在因为比较早没什么人，顺利上车了。 本来想和队友商量下策略，结果发现我爸为了让我早上休息给我们买了静音车厢的票，那商量不成了。 休息是不可能休息的，吃完早餐直接爽打。 到重庆的时候还没撤离但是已经清图了不慌，展示陀螺仪神力，单手跑到撤离点，刚好出站。 坐大巴前往考点重庆大学，DimStar 本来想看我打...

SCCPC 2026 游记 省流：打星队，怎落笔都不队，Ag。 坐大巴车前往参赛地点。 感谢路上@WBJ0429 开热点，爽打 K，尝试了德日直海构筑，前几局老是忘记 IJN 御藏号的再来一次爆自己手牌，有熟练度之后感觉自己堪比爱因斯坦，吊打傻子比日波。 在大约 1h 后电脑没电了，车上又没有插座，于是坐了一小会牢，但是没多久就到了。 @_ztyroy 在路上又在玩神秘游戏蛋仔派对，不做评价。 我马上就要上超级凤凰蛋了！ 开赛前领物资，居然有价值 120 RMB 的餐券，还是昨天的，我去太有用了，100 RMB 卖给同学居然都不要，简直没搞懂。 队友是@Love_Song 和 @InRedBrother_QWQ。 开赛看题，三个人随机跳题，很快 @Love_Song 会了 D，我会了 H。 然后让@Love_Song 先写 D，没多久写完了，交一发 WA 了，哎哎不是你这不对啊，我轻易构造出 hack，交一发咋又 WA 了，我草你这个假了一半，哦对的，然后过了。 我上机写 H，写完并提交，然后 WA 了，进行一个调试，哦假了一点，但是好像是本质相同的，展示直觉，又交两发还是有问题...

P16604 [SYSUCPC 2025] SYSU III 思路 神神原神原神 uu。 贪心找到的串一定合法，但不一定最优，所以答案不会大于正解。 考虑怎么使得贪心得到的值小于正解，只需构造 ssysysuu 这样的一个串，就可以使得贪心的第一个串的第一个 s 用掉了本该给第二个串的第二个 s 导致错误。 扩展一点，s...ys...u... 这样的结构每有两组就会使得贪心比正解少一。 那么我们只需要放 $(y-x)\times 2$ 组 s...ys...u...，再在最后加上 $x$ 组 sysu 就可以了。 代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include<bits/stdc++.h>#define fir first#define sec second#define int long long#define pii pair<int,int>#d...

P16605 [SYSUCPC 2025] Sum 思路 数据范围一眼根号分治。 首先考虑暴力枚举进制，也就是进制转换，对于 $10$ 进制转 $k$ 进制，不断取 $n\bmod k$ 再除 $k$ 直到 $n=0$ 即可。 时间复杂度 $O(B\log n)$，其中 $B$ 是阈值。 然后考虑如何得到一个 $\frac{n}{B}$ 状物，分析上面的方法，发现若 $k>\sqrt n$，那么只能进行两次除法就归零，会取两个值： $n\bmod k,\lfloor\frac{n}{k}\rfloor$。 那么对于既定的 $k$，贡献则是 $n\bmod k+\lfloor\frac{n}{k}\rfloor$。 推一下式子： 原式 $=n-\lfloor\frac{n}{k}\rfloor\times k+\lfloor\frac{n}{k}\rfloor=n-(k-1)\times \lfloor\frac{n}{k}\rfloor$。 枚举 $\lfloor\frac{n}{k}\rfloor$，要使得原式子在既定的 $\lfloor\frac{n}{k}\rfloo...

CF2231B Another Sorting Problem 思路 思维好题。 首先题目允许最多一次操作，选择一个正整数 $k$ 和一个子序列，将该子序列的所有元素加上 $k$。问能否使数组变为非递减序列。 如果开始的序列就满足条件，则直接特判掉。 由于只能加不能减，且只能操作一次，这意味着如果某个位置 $i$ 需要增加（因为 $a_i>a_{i+1}$），那么 $i$ 及其之后的某些元素一定被选中。 这就相当于把整个数组划分为两个互补的子序列，且两个子序列内都是有序的（若无序，同时加 $k$ 还是无序）。 那么我们首先找出所有逆序对位置，这些逆序对的前一个数一定被选中，后一个数一定不选中，不然就会导致无序。 如果存在连续的逆序对（如位置 $i$ 和 $i+1$ 都是某逆序对的前一个数），则不可能，因为同一个位置不可能既被选中又未被选中。 在这一步中，我们可以计算出 $k$ 的最小上界 $L$。 再按照选中和未选中划分数组，找到从每个选中段到未选中段的最大差值，这决定了 $k$ 的最大下界 $K$。 然后判断 $K\le L$ 是否成立即可得出有没有合法 $k$。 代码 ...

P10040 [CCPC 2023 北京市赛] 替换 思路 首先这个题字符串的每一位只有三种情况。 我们考虑用两个 bitset 来存，一个代表当前位是否为 $1$，另一个代表当前位是否为问号。 有一种暴力做法：先存前 $k$ 位，然后再一组一组往后扩展，逻辑是第 $i$ 位若是问号就改为 $i-k$ 位的值。 这个暴力的时间复杂度是 $O(\frac{n^2}{w\times k})$，在 $k$ 更大时更优。 还有另一种暴力：直接线性遍历枚举，时间复杂度为 $O(n)$。 显然这两种都无法单独通过本题，考虑数据分治。 设置阈值 $B$，当 $k>B$ 时取第一种，否则取第二种。 那么操作总次数为 $B\times n+\frac{n^2\ln n}{\ln B\times w}$（后半部分是调和级数）。 那么我们考虑常数因子，将 $B$ 取到 $\sqrt n$，可以通过本题。 莫名其妙地，将 $B$ 取到 $0$ 也可以通过本题，鉴定为数据过水常数优秀。 代码 123456789101112131415161718192021222324252627282930313...

CF2223A Zhily and Bracket Swapping 思路 首先一个不合法的括号序列有两种情况： 两种括号数量不相等。 存在某个前缀中的后括号数量大于前括号的数量。 又因为两个字符串的括号不可以跨位交换，所以我们枚举 $i\in [0,n)$，对于每个 $i$ 维护四个值 $sw_1,sw_2,v_1,v_2$ 分别代表序列 $1$ 可以往序列 $2$ 交换过去的前括号数量，序列 $2$ 可以往序列 $1$ 交换过去的前括号数量，此时序列 $1$ 中前括号比后括号多多少个，此时序列 $2$ 中前括号比后括号多多少个。 首先特判若两者中总的两种括号数量不相等，则不成立。 然后考虑如何维护上面的四个值以及它们分别有什么用。 首先维护 $sw1,sw2$，根据定义可得： 12if(a2[i]==1&&a1[i]==-1)sw1++;if(a1[i]==1&&a2[i]==-1)sw2++; 若在某个 $i$，$v1,v2$ 中有一个小于 $0$ 且无法“挽回”，则不存在合法构造。 “挽回”是什么意思呢，就是通过将前面某处可交换的交换使...

CF2223B Zhily and Barknights 思路 题目的意思是：把 $b$ 数组随机打乱，然后和 $a$ 对应位置相乘得到新数组 $c$，问 $c$ 里逆序对数量的期望值。 期望可以拆成每一对位置 $i,j(i<j)$ 的逆序概率之和。 对于固定的 $i$ 和 $j$，我们关心的是 $a_i\times b_i>a_j\times b_j$ 的概率，其中 $b_i$ 和 $b_j$ 是从 $b$ 里随机抽的两个不同数。 把 $b$ 里的数两两配对（有序），总共有 $n\times (n-1)$ 种可能。 条件 $a_i\times u>a_j\times v$ 等价于 $u\div v > a_j\div a_i$。 所以问题变成：给定一堆 $u,v$ 对，以及一堆比值 $a_j\div a_i$，统计有多少组满足 $u\div v$ 大于这个比值。 可以先把所有 $u\div v$ 排好序，然后对于每个比值二分查找，一次性累加结果。 最后除以总方案数 $n\times(n-1)$ 即可。 代码 12345678910111213141516...

CF2224B Zhily and Mex and Max 思路 假设整个数组中的最大值是 $mx$，最小未出现数是 $me$。 我们考虑拆分两种贡献，发现 $\operatorname{mex}$ 的每一位贡献最多为 $me$，而 $\max$ 的每一位贡献最多为 $mx$。 直觉上显然是 $\max$ 的每位贡献更大，此时我们将最大值放在最前面，后面从大到小放上 $0,1,\dots,me-1$。 考虑 $me>mx$ 的情况： 首先 $mx\ge me-1$，因为 $me-1$ 一定在数组中出现过。 然后就得到 $me>mx\ge me-1$，那么显而易见，$mx=me-1$。 下文的 $i\times cnt_i$ 均指填 $cnt_i$ 个 $i$。 那么数组从大到小排序之后整体大概就是 $0\times cnt_0,1\times cnt_1,\dots,(me-1)\times cnt_{me-1}$，这里 $cnt_i$ 指的是出现的次数，且 $\forall i\in[0,me),cnt_i>0$。 我们考虑 $\max$ 贡献更大时的那种构造...

P15352 [COCI 2025/2026 #4] 魔术 / Magija 思路 倍增并查集，以下描述忽略反阿克曼函数 $\alpha(n)$。 首先考虑直接 $O(nq)$ 的维护，显然简单，用并查集维护哪些点可以相互到达，合并时压缩路径并统计答案，数据比较水所以甚至有 $73$ 分。 ▶ [73 pts Code] 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071#include<bits/stdc++.h>#define fir first#define sec second //#define int long long#define pii pair<int,int>#defin...