Misaka16172's Blog

带阻力的运动学方程推导 问题：假如某个物体从高空由静止释放，受到重力 mgmgmg 和空气阻力。 前提条件：低速状态下，空气阻力一般与速度成正比，即 f=kvf=kvf=kv。 规定竖直向下为正方向，试分析物体在任意时刻的速度。 进行受力分析，有 mg−kv=mamg-kv=mamg−kv=ma，即： mg−kv=mdvdtmg-kv=m\frac{dv}{dt} mg−kv=mdtdv​ 分离参数 v,tv,tv,t： dvmg−kv=dtm\frac{dv}{mg-kv}=\frac{dt}{m} mg−kvdv​=mdt​ 对两边积分： ∫1mg−kv dv=∫1m dt\int \frac{1}{mg-kv}\ dv=\int \frac{1}{m}\ dt ∫mg−kv1​ dv=∫m1​ dt 转成定积分形式，左边从 000 积到任意时刻的速度 vvv，右边从 000 积到该时刻 ttt： ∫0v1mg−kv dv=∫0t1m dt\int^v_0 \frac{1}{mg-kv}\ dv=\int^t_0 \frac{1}{m}\ dt ∫0v​mg−kv1​ dv ...

前言 好想哭啊 思路 定义 f2(u)f_2(u)f2​(u) 为：在从根到 uuu 的路径上的点的点权构成的集合中插入 f(u)f(u)f(u) 后，新集合的 mex⁡\operatorname{mex}mex 值。开局先预处理所有 f(u)f(u)f(u) 和 f2(u)f_2(u)f2​(u) 的值，在 dfs 时用 set 维护从根到 uuu 的集合的补集即可。 考虑对 uuu 进行操作后对其子树的影响。 首先特判 f(u)=pu+1f(u)=p_u+1f(u)=pu​+1 的情况，此时操作后树上没有 pup_upu​，整个 uuu 子树内的点的 fff 值都会变为 pup_upu​。 我们考虑将一次操作拆成两次：插入 f(u)f(u)f(u) 和删除 pup_upu​。 插入 f(u)f(u)f(u) 时，对于所有 uuu 子树中的点 vvv，若 f(v)=f(u)f(v)=f(u)f(v)=f(u) 则 f(v)f(v)f(v) 会变成 f2(v)f_2(v)f2​(v)，否则没有影响。 删除 pup_upu​ 时，对于所有 f(v)>puf(v)>p_u ...

前言 最近突然想起来了，写给自己看的。 更可爱的阅读体验 思路 性质 A，52 pts 其实跟正解关系不大，但我比赛的时候会的是这个。 只修改 aaa，不修改 bbb。首先将所有点按 bbb 重标号方便后续讨论。大力对 aaa 分块，设块长为 BBB。对每个块处理 fS=max⁡u∈S{au}f_S=\max\limits_{u\in S}\{a_u\}fS​=u∈Smax​{au​}，修改的时候直接对单块暴力重构，查询的时候整块用手写 bitset 查询点 uuu 在每块所属的区间内的可达性集合，散块暴力枚举，总复杂度 O(q2B+nqB+qB)\mathcal{O}(q2^B+\frac{nq}{B}+qB)O(q2B+Bnq​+qB)，取 B=12B=12B=12 时平衡。 100 pts 定期重构。设重构周期为 BBB。对于在上次重构后有修改的点，查询时暴力枚举判断是否满足条件。这部分复杂度 O(qB)\mathcal{O}(qB)O(qB)。依旧对 aaa 分块，每次重构预处理对每个点 uuu 和每个块 iii 预处理块中能被 uuu 到达的点的 bvb_vbv​ 最大值。 ...

前言 懒得喷。。。。。。 更可爱的阅读体验 思路 考虑树形 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 和 ...