P16401 [ECUSTPC 2026 Spring] 题解 : 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 2026-05-01 #solution
ODT学习笔记 ODT 学习笔记 简介 ODT(old drive tree),又名珂朵莉树,是一种暴力的数据结构,可以解决区间推平操作的一类题目,举个例子,就是把一个序列中 [l,r][l,r][l,r] 这一个区间的数都修改为 xxx ,当然,可以用线段树完成,但是如果 l,rl,rl,r 足够大,线段树用不了,而且数据是随机的,就可以用珂朵莉树。 原理 定义 执行推平操作之后,只要推平的区域大于1, 2026-04-06 #study-notes
ABC452E You WILL Like Sigma Problem 思路 利用 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 2026-04-04 #solution
P15879 [ICPC 2026 NAC] Evil Judges 题意 给出一个字符串 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 2026-03-26 #solution
ABC450E Fibonacci String 思路 这道题要处理长度为 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 2026-03-23 #solution
ABC449C-Comfortable-Distance 大意 给定字符串 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] 2026-03-16 #solution
ABC449D-Make-Target-2 题目大意 给定矩形区域,点 (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 为偶数时点是黑色。我们将图形看作一层层套在一起的正方 2026-03-15 #solution
ABC448E-Simple-Division 题意大意 给定游程编码表示的整数 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 2026-03-15 #solution