Misaka16172's Blog

前言 场内选手来了。。。这个题的官方 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 的贡献，因为这个时候我们虽然 ...

考虑 vvv 是 prufer 点的充要条件：vvv 和 nnn 直接相连；vvv 是 n−1n-1n−1 的祖先，因为不是 n−1n-1n−1 祖先的点总先于 n−1n-1n−1 被删除。然后分讨： n−1n-1n−1 和 nnn 连通：只有同时是 nnn 的儿子和是 n−1n-1n−1 的祖先的那个点的答案不是 000，此时所有 nk−2∏i=1ksin^{k-2}\prod\limits^k_{i=1}s_ink−2i=1∏k​si​ 种方案都合法。 否则对每个点 vvv 考虑。下面默认 vvv 和 nnn 已经有边（没有边的话直接连上再处理即可），这时限制只剩 n−1n-1n−1 所在的树要接到 vvv 的子树里。答案是总方案数乘 vvv 子树的大小 svs_vsv​ 除 nnn 所在的这棵树总共的大小 SSS，即 svSnk−2∏i=1ksi\frac{s_v}{S}n^{k-2}\prod\limits^k_{i=1}s_iSsv​​nk−2i=1∏k​si​。这是关键的一步，因为所有方案是对称的，任意抽取一个方案，把 n−1n-1n−1 所在的子树接到 vvv 那一侧 ...

Preface 这是一篇英文题解。This is an English solution. Solution Consider the necessary and sufficient condition for P(T)=vP(T)=vP(T)=v: Edge (v,n)(v,n)(v,n) exists in TTT; Let nnn be the root of TTT. Then, n−1n-1n−1 is in the subtree of vvv. This is because every vertex u(u<n−1,u is not an ancestor of n−1)u(u< n-1,u\ \text{is not an ancestor of}\ n-1)u(u<n−1,u is not an ancestor of n−1) is removed before n−1n-1n−1. If n−1n-1n−1 and nnn are in the same tree, when vvv is both an ancestor of n− ...

Preface 这是一篇英文题解。This is an English solution. Solution Build an undirected graph with the given mmm constraints, connecting vertices xxx and yyy with an edge weighted zzz. After that, consider every connected component independently. Case 1: The connected component has at least ∣V∣|V|∣V∣ edges, i.e. it’s not a tree. In this case, there is a fixed solution if and only if there is an odd cycle in the graph. Conversely, every even cycle has a redundant edge. For example: {a+b=k1b+c=k2c+d=k3a+d=k4\ ...