寒假做题不完全记录（持续更新）
12.30-1.1
摆。
1.2
P4155 国旗计划
发现线段按左端点排序后右端点单调递增，所以可以确定每条线段最优的下一条，倍增求出每条的下 \(2^k\) 条，查询时倍增到 \(d_i<c_i+m\) 即可。
P4562 [JXOI2018]游戏
将所有数分为关键数，即不包括本身的倍数不在 \([l,r]\) 的数，和非关键数，答案即为最后一个关键数的位置。可由求所有关键数后的非关键数个数得到答案为
\[\frac{k}{k+1} (n+1)! \\ \]1.3
P6076 [JSOI2015]染色问题
容斥，大力推式子。
1.4
CF1446D1 Frequency Problem(Easy Version)
首先发现答案区间的众数一定包括整体的众数 \(x\)（可用反证法，考虑从整体众数不是区间众数的区间扩展，发现一定会有更大的），因此可以枚举除全局众数外的另一个众数 \(y\)，计算前缀和，遇到 \(x\) 就 \(+1\)，遇到 \(y\) 就 \(-1\)，看和为 \(0\) 的最长区间长度是多少。一个区间中 \(x\) 的出现次数与 \(y\) 出现次数相等且有 \(z\) 出现次数更多不会有影响，同样可以扩展发现更大的。
CF785D Anton and School - 2
推式子+容斥，用到组合数积之和化简。
1.5
CF856C Eleventh Birthday
一个数除以 11 的余数等于奇数位数字和减偶数位数字和，\(f_{i,j,k}\) 表示前 \(i\) 个奇数位 \(j\) 个开头是偶数位，求和奇减求和偶等于 \(k\) 的方案数，\(g_{i,j,k}\) 同理，最后把偶插到奇里。
1.6
UVA1608 Non-boring sequences
记录每个元素 \(a_i\) 的下一个相同的位置 \(nxt_i\) 和上一个 \(lst_i\)，容易发现对于任意 \(l\in(lst_i,i],r\in[i,nxt_i)]\)，区间 \([l,r]\) 中 \(a_i\) 出现且仅出现了一次。因此合法区间数可以转化成对角顶点为 \((lst_i+1,i),(i,nxt_i-1)\) 的矩形并的面积。
P2424 约数和
原问题可以转化成
\[\sum\limits_d d\sum\limits_{i=l}^r [d|i]=\sum\limits_d d(\left\lfloor \frac{r}{d} \right\rfloor-\left\lfloor \frac{l-1}{d} \right\rfloor) \\ \]，数论分块即可。
CF1367F1/AGC024B
观察样例发现答案为离散化后 \(n-\) 最长每次上升 \(1\) 的子序列长度。
1.7
P2260 [清华集训2012]模积和
大力推式子+二维数论分块。
CF208E Blood Cousins
用长剖求 \(k\) 级祖先，再跑 dsu on tree。
1.9
P5999 [CEOI2016] kangaroo
见题解。
CF704B Ant Man
和上题类似。
标签：limits,sum,更新,lst,寒假,做题,众数,区间 From： https://www.cnblogs.com/lxy-2022/p/17038523.html