Misaka16172's Blog

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\ ...

前言 简单的做法，不需要动脑子。 思路 O(nq)\mathcal{O}(nq)O(nq) 的暴力算法是从左往右顺序枚举，如果有塔顶与当前积木异色的塔就放上去，否则单开一座。设当前有 aaa 座塔顶颜色为红色，bbb 座为蓝色，当前遇到的是红色的积木，那么这个过程等价于 a←a+1,b←max⁡(b−1,0)a\leftarrow a+1,b\leftarrow \max(b-1,0)a←a+1,b←max(b−1,0)。这可以表示成一个 (max⁡,+)(\max,+)(max,+) 矩乘的形式（相当于给 [ab0]\begin{bmatrix} a\\ b\\ 0 \end{bmatrix}⎣⎢⎡​ab0​⎦⎥⎤​ 左乘一个东西），线段树或猫树维护静态区间矩乘即可优化至 O(ω⋅nlog⁡n)\mathcal{O}(\omega\cdot n\log n)O(ω⋅nlogn)。

14(2) 下部分的体积为 VB−AEFD,VB−CDFGV_{B-AEFD},V_{B-CDFG}VB−AEFD​,VB−CDFG​ 两个四棱锥的体积之和，直接算出来，上面的体积是总体积减去下面的体积。 15(4) 设数列极限为 LLL，an+1=an+an−1  ⟺  an+1an=1+an−1an  ⟹  L=1+1La_{n+1}=a_n+a_{n-1}\iff \frac{a_{n+1}}{a_n}=1+\frac{a_{n-1}}{a_n}\implies L=1+\frac{1}{L}an+1​=an​+an−1​⟺an​an+1​​=1+an​an−1​​⟹L=1+L1​，由于 L>0L>0L>0，解得 L=1+52L=\frac{1+\sqrt 5}{2}L=21+5​​。 17 看错字母，只剩 3 分。 (1) 作 CPCPCP 中点 FFF，连接 EF,DFEF,DFEF,DF。 ∵E,F\because E,F∵E,F 为 BP,CPBP,CPBP,CP 中点 ∴EF∥BC,EF=12BC\therefore EF \parallel ...

器材： 只需要刻度尺和打点计时器。 电磁打点计时器电压小（4∼6V4\sim 6V4∼6V），电火花打点计时器电压大（220V220V220V），二者都使用交流电源。 作图：描点时尽量让最多的点被直线连接，直线左端需要延伸至 t=0t=0t=0。 计算瞬时速度要用尽量多的点，假如打了 A∼EA\sim EA∼E 五个点，则 vC=∣AE∣4tv_C=\frac{|AE|}{4t}vC​=4t∣AE∣​。 时间间隔：有 444 个点未画出 ⇒\Rightarrow⇒ 时间间隔为 0.02×(4+1)=0.1s0.02\times (4+1)=0.1s0.02×(4+1)=0.1s。 刻度尺要估读一位，保留 xxx 位有效数字 = 从第一个非零位置开始数 xxx 位。 逐差法计算加速度：尽量利用更多的数据，减小误差。设有 2n2n2n 段（2n2n2n 为偶数，若给了奇数段的话，直接舍弃中间的那一段），第 1≤i≤n1\leq i\leq n1≤i≤n 段长度为 xix_ixi​，则将第 i≤ni\leq ni≤n 段与第 i+ni+ni+n 段匹配，用这两段计算出的加速度是 a ...

前言 唉， 思路 设询问串为 (s,t)(s,t)(s,t)，给定的串为 (a,b)(a,b)(a,b)。 证明一个 (a,b)(a,b)(a,b) 对一个 (s,t)(s,t)(s,t) 的贡献最多为 111 是平凡的，询问即对 (s,t)(s,t)(s,t) 计算有多少个满足条件的 (a,b)(a,b)(a,b)。 设 l=min⁡si≠ti{i},r=max⁡si≠ti{i}l=\min_{s_i≠t_i}\{i\},r=\max_{s_i≠t_i}\{i\}l=minsi​​=ti​​{i},r=maxsi​​=ti​​{i}，记 f(x,y)=(x[l⋯r],y[l⋯r])f(x,y)=(x[l\cdots r],y[l\cdots r])f(x,y)=(x[l⋯r],y[l⋯r])，L(x,y)L(x,y)L(x,y) 为 xxx 和 yyy 扣掉 f(x,y)f(x,y)f(x,y) 之后剩下的左边的子串（由定义，这两个串是同一个串），R(x,y)R(x,y)R(x,y) 为右边的（同理）。则 (a,b)(a,b)(a,b) 对 (s,t)(s,t)(s,t) 的贡 ...