Lins' Blog

题解 : P16401 [ECUSTPC 2026 Spring] 星露谷物语 分两类讨论，取最大值即可。注意第 k+1k+1k+1 天作物会枯萎，所以收获时间必须 ≤k\le k≤k。 单次作物：只有售价 >>> 进价才种。第 111 天种，第 1+t1+t1+t 天收，收完马上重种。最大次数 c=⌊k−1t⌋c = \lfloor \frac{k-1}{t} \rflo

ODT 学习笔记 简介 ODT(old drive tree)，又名珂朵莉树，是一种暴力的数据结构，可以解决区间推平操作的一类题目，举个例子，就是把一个序列中 [l,r][l,r][l,r] 这一个区间的数都修改为 xxx ，当然，可以用线段树完成，但是如果 l,rl,rl,r 足够大，线段树用不了，而且数据是随机的，就可以用珂朵莉树。 原理 定义 执行推平操作之后，只要推平的区域大于1，

思路 利用 i mod j=i−⌊ij⌋⋅ji \bmod j = i - \lfloor \frac{i}{j} \rfloor \cdot jimodj=i−⌊ji​⌋⋅j 将原式拆分为两部分： Ans=(∑i=1NAi⋅i)×(∑j=1MBj)−∑j=1M(Bj⋅j⋅∑i=1NAi⋅(⌊ij⌋))\text{Ans} = (\sum_{i=1}^N A_i \cdot i) \times

题意 给出一个字符串 sss 和一个整数 mmm，最多可以移动相邻字符 mmm 次，使最后的字符串含有的 AC\texttt{AC}AC 或 AK\texttt{AK}AK 最少，输出这个值。 思路 首先统计 sss 中 AC\texttt{AC}AC 或 AK\texttt{AK}AK 的子序列的数量，再减去 mmm ，因为每次交换最多去掉一个 AC\texttt{AC}AC 或 AK\te

思路 这道题要处理长度为 101810^{18}1018 的字符串，直接构造肯定不行。但仔细观察生成规则 Si=Si−1+Si−2S_i = S_{i-1} + S_{i-2}Si​=Si−1​+Si−2​，发现字符串长度的增长符合斐波那契数列。 1. 长度极长 斐波那契数列增长是指数级的。即使 ∣X∣,∣Y∣|X|, |Y|∣X∣,∣Y∣ 只有 1，大概不到 90 项，长度就会超过 1018

大意 给定字符串 SSS 和整数 L,RL, RL,R，求满足 Si=SjS_i=S_jSi​=Sj​ 且 L≤j−i≤RL \le j-i \le RL≤j−i≤R 的下标对 (i,j)(i,j)(i,j) 数量。 思路 暴力枚举 O(N2)O(N^2)O(N2) 会超时。利用字符集仅 26 个的特性，将每种字符的下标单独提取。 问题转化为在多个有序数组中，统计差值在 [L,R][L, R]

题目大意 给定矩形区域，点 (x,y)(x,y)(x,y) 颜色由 k=max⁡(∣x∣，∣y∣)k=\max(|x|，|y|)k=max(∣x∣，∣y∣) 决定：kkk 为偶数时为黑，为奇数时白。求区域内黑色点数。 思路 颜色由 k=max⁡(∣x∣,∣y∣)k=\max(|x|,|y|)k=max(∣x∣,∣y∣) 的奇偶性决定，kkk 为偶数时点是黑色。我们将图形看作一层层套在一起的正方

题意大意 给定游程编码表示的整数 NNN 和整数 MMM，游标编码即由 KKK 组 (ci,li)(c_i, l_i)(ci​,li​) 描述，表示数字 cic_ici​ 重复 lil_ili​ 次，求 ⌊NM⌋ mod 10007\left\lfloor \frac{N}{M} \right\rfloor \bmod 10007⌊MN​⌋mod10007。 由于 lil_ili​ 可达 109