Misaka16172's Blog

前言 懒得喷。。。。。。 更可爱的阅读体验 思路 考虑树形 dp。在 dp 过程中枚举每个点的状态：没有进行交换，跟父亲交换或是跟某个儿子交换。将其记在状态里，用 fu,0f_{u,0}fu,0​ 代表不交换，fu,1f_{u,1}fu,1​ 代表跟父亲交换，fu,i+2f_{u,i+2}fu,i+2​ 代表跟第 iii 个儿子交换（下标从 000 开始）。有如下转移： {fu,0=∑v∈son(u)max⁡(fv,0+[au=av]wu,max⁡x≥2{fv,x+[au=ason(v)x]wu})fu,1=∑v∈son(u)max⁡(fv,0+[afau=av]wfau,max⁡x≥2{fv,x+[afau=ason(v)x]wfau})fu,i(i≥2)=fson(u)i,1+∑v∈son(u),v≠son(u)imax⁡(fv,0+[ason(u)i=av]wson(u)i,max⁡x≥2{fv,x+[ason(u)i=ason(v)x]wson(u)i})\begin{cases} f_{u,0}=\sum\limits_{v\in son(u)}\max(f_{v,0}+[ ...

前言 更可爱的阅读体验 思路 先拆一下题目里的条件。令被矩形包含的所有点的 hih_ihi​ 构成的可重集为 SSS，从小到大对 SSS 考虑，那么对任意三个相邻的 Si,Si+1,Si+2S_{i},S_{i+1},S_{i+2}Si​,Si+1​,Si+2​ 均满足 Si+Si+1≤Si+2S_{i}+S_{i+1}\leq S_{i+2}Si​+Si+1​≤Si+2​ 是答案为 000 的充要条件。发现 SSS 中的元素增长得很快，因为值域有限制，尝试构造出一个最大的答案为 000 的 SSS，满足 Si+2=Si+1+SiS_{i+2}=S_{i+1}+S_iSi+2​=Si+1​+Si​。其实这个时候 SSS 里的数就是斐波那契数列 FFF，由于 F45>109F_{45}>10^9F45​>109，我们得到了当 ∣S∣≥45|S|\geq 45∣S∣≥45 时答案必然为 111。 做一遍矩形数点排除掉 ∣S∣≥45|S|\geq 45∣S∣≥45 的询问后，我们直接将每个点插入将其包含的剩下的询问中。这个过程可以用扫描线 + 线段树实现，对线段树每个节点 ...

所有不过滤行末空格的评测系统，祝你们的妈妈在天堂相遇。 t1 没过，真神了，数据是不是有问题？ t3 前七分调了一个半小时（比赛时间 3h），最后发现是评测系统不过滤行末空格？？？？？？？？ 后八分最后十分钟写完没过，晚上回酒店发现死因是，输出方案数输出成了行数。，。？ t4 k=0k=0k=0。 t5 没交。 认识了考场里两位 icc 的同学。蹭了顿饭😋。除了比赛之外的部分都很开心！！ 能不能不要给我发奖？？？

前言 场内选手来了。。。这个题的官方 spj 是脑残，不过滤行末空格，以及比赛的时候我没读到最后一个 sub 每个猜测选的数必须不交。。。 思路 先看前 888 分，这个 gcd⁡\gcdgcd 的条件是诈骗的，考虑更弱的限制：奇偶性。 如果两个数都是偶数它们的 gcd⁡\gcdgcd 一定 ≥2\geq 2≥2，于是考虑凑两个偶数出来： 如果序列里有两个偶数 ci,cjc_i,c_jci​,cj​，令 A={i},B={j}A=\{i\},B=\{j\}A={i},B={j}。 否则，如果序列里有一个偶数 xxx 和 ≥2\geq 2≥2 个奇数，令前两个奇数的出现位置为 i,ji,ji,j，令 A={x},B={i,j}A=\{x\},B=\{i,j\}A={x},B={i,j}。 否则，如果序列里有 ≥4\geq 4≥4 个奇数，令它们的出现位置为 a,b,c,da,b,c,da,b,c,d，令 A={a,b},B={c,d}A=\{a,b\},B=\{c,d\}A={a,b},B={c,d}。 否则，一定有 n≤3n\leq 3n≤3。暴力枚举子集检查是否有解即可。 再看 ...

/fendou A d(y)d(y)d(y) 是 O(log⁡V)\mathcal{O}(\log V)O(logV) 的，枚举 x+d(y)x+d(y)x+d(y) 并检查。 B 这个是经典结论，判一下 aaa 去重后是不是 ppp 的子序列即可。 证明：P10297 [CCC 2024 S3] Swipe - 洛谷 C 假设最后 Bob 赢了，此时的分数是 2x3x\frac{2x}{3x}3x2x​。那么分子被操作了 p−2xp-2xp−2x 次，分母被操作了 q−3xq-3xq−3x 次。当 p−2x=q−3xp-2x=q-3xp−2x=q−3x 时，Bob 有如下策略：如果 Alice 操作分子，那 Bob 就操作分母；如果 Alice 操作分母，那 Bob 就操作分子。否则，这是不可能的，因为 Alice 有如下策略：若 p−2x<q−3xp-2x<q-3xp−2x<q−3x，那么 Alice 一直操作分子，反之则一直操作分母，可以确保某个时刻分子 <2x<2x<2x 或分母 <3x<3x<3x。可以解出唯一的 x=q ...

前言 思路 题意：称一个区间对 ([l1,r1],[l2,r2])([l_1,r_1],[l_2,r_2])([l1​,r1​],[l2​,r2​]) 是好的，当且仅当可重集 S={al1,al1+1,⋯ ,ar1},T={al2,al2+1,⋯ ,ar2}S=\{a_{l_1},a_{l_1+1},\cdots ,a_{r_1}\},T=\{a_{l_2},a_{l_2+1},\cdots ,a_{r_2}\}S={al1​​,al1​+1​,⋯,ar1​​},T={al2​​,al2​+1​,⋯,ar2​​} 满足 S=TS=TS=T。单点修改，每次输出所有好的区间对的区间长度最大值 kmax⁡k_{\max}kmax​ 和区间长度为 kmax⁡k_{\max}kmax​ 的区间对的个数 fff。 两个可重集相等，上来直接和哈希变成两个区间和相等，吗？那就倒闭了，不可做的。发现这个限制看起来非常强，尝试找一下性质将其弱化。首先观察到两个区间一定有交或至少是相邻才可能成为答案，否则不如把中间也选上。 手摸一下样例或者自己造几组数据，发现大部分情况的答案都满足 al1=ar2a_{ ...

输了。 A 如果 r>min⁡(x,y)−1r>\min(x,y)-1r>min(x,y)−1，总能通过再添加一个 min⁡(x,y)\min(x,y)min(x,y) 使 rrr 变得更小。直接输出 n=min⁡(x,y)−1n=\min(x,y)-1n=min(x,y)−1 即可。 B 令 x≤yx\leq yx≤y。若 z=y+1z=y+1z=y+1，可以构造 x=10x−1,y=10y−1x=10^x-1,y=10^y-1x=10x−1,y=10y−1，若 z=yz=yz=y，可以构造 x=10x−1,y=10y−1x=10^{x-1},y=10^{y-1}x=10x−1,y=10y−1。其余情况无解。 C 前缀和，模拟即可。也可以做到线性。 D 横着移动其实就是在求 min⁡j=1n{∣axi−bj∣}\min\limits_{j=1}^n\{|a_{x_i}-b_j|\}j=1minn​{∣axi​​−bj​∣}，用 set 查一下每个 aaa 在 bbb 里的前驱后继即可。因为还要处理竖着移的情况，一种简单的实现方式是交换所有 x,yx,yx,y 和 ...

https://constructor2026.contest.codeforces.com/group/XdjJUfzFUt/contest/668785 A ~ D 模拟即可。 E 切第 iii 刀时，会多出 ⌊i2⌋+1\lfloor\frac{i}{2}\rfloor+1⌊2i​⌋+1 块巧克力。答案即为 ∑i=0k⌊i2⌋+1=(⌊k2⌋+1)2+(⌊k2⌋+1)[kmod  2]\sum\limits_{i=0}^k \lfloor\frac{i}{2}\rfloor+1=(\lfloor\frac{k}{2}\rfloor+1)^2+(\lfloor\frac{k}{2}\rfloor+1)[k\mod 2]i=0∑k​⌊2i​⌋+1=(⌊2k​⌋+1)2+(⌊2k​⌋+1)[kmod2]。 F dp。设 fi,jf_{i,j}fi,j​ 为确定到十进制第 iii 位（从 000 开始），mod  2n\mod 2^nmod2n 目前为 jjj 时第 iii 位的取值。可以从 fi,(j−2×10i)mod  2nf_{i,(j-2\times 10^{i})\mod ...

A 贪心。每删除 k−1k-1k−1 个栅栏必须留下一个。答案为 ⌊nk⌋(k−1)+nmod  k\lfloor \frac{n}{k}\rfloor(k-1)+n\mod k⌊kn​⌋(k−1)+nmodk。 B 假设我们已经确定了最后把钱放在哪个银行，对于其余的银行 iii，除了 aimod  xa_i \mod xai​modx 余下的钱都是可以被转移到最后那个银行去的。枚举即可。 为什么 aimod  xa_i \mod xai​modx 的余数不能被转移？假设我们为了转移这个余数 kkk，将另外 c0c_0c0​ 笔钱移过来，凑好了一些钱，转移了 c1c_1c1​ 次到最后的目标银行里。那么这个过程中凑到这个银行里的钱数就是 c0⋅y+kc_0\cdot y+kc0​⋅y+k，转出的钱数是 c1⋅xc_1\cdot xc1​⋅x，最后对答案的贡献是 c1⋅yc_1\cdot yc1​⋅y。如果 c1<c0c_1<c_0c1​<c0​，那这个过程是劣的，不如直接把钱转到最后的银行里。而 c0≤c1,y≤x,k<xc_0\leq c_1,y\leq x ...

前言 这个乌克兰 OI 的题感觉都挺套路的。 思路 固定区间一端，随着区间另一端的扩展，gcd⁡\gcdgcd 每次变化至少减半，最多变化 log⁡V\log VlogV 次。因为求的是 [l,r][l,r][l,r] 内所有子区间的答案，考虑扫描线，钦定 lll 维护 rrr。具体地，倒序枚举到 lll 时每次用 st 表倍增跳到以 lll 为左端点的区间 gcd⁡\gcdgcd 变化的交界处 xxx，然后对于 r>xr>xr>x，ansr←max⁡(ansr,w∑i=lxai)ans_r\leftarrow \max(ans_r,w\sum\limits_{i=l}^xa_i)ansr​←max(ansr​,wi=l∑x​ai​)，其中 w=gcd⁡i=lxaiw=\gcd\limits_{i=l}^xa_iw=i=lgcdx​ai​，ansrans_ransr​ 是区间 [l,r][l,r][l,r] 的答案。需要支持后缀取 max⁡\maxmax 单点查询，树状数组即可。但是这样做会漏掉 rrr 所在段的 gcd⁡\gcdgcd 的贡献，因为这个时候我们虽然 ...