\(\texttt{Contest 100}\)
\(\texttt{Problem C:}\) \(\texttt{*3 or /2}\)
每次操作对长度为 n 的序列里的每个元素 \(\times 3\) 或 \(\div 2\) ，每次操作至少要一次 \(\div 2\)，求最多的操作数
因为 \(\times 3\) 其实对结果没有影响，所以我们只要数每个数有几个质因子 \(2\) 再求和即可。
\(\texttt{Problem D:}\) \(\texttt{Patisserie ABC}\)
有 \(n\) 种蛋糕，有三种属性：\(a, b, c\)，要选 \(m\) 种蛋糕，使得 \(m\) 种蛋糕的每种属性的绝对值之和最大，问最大是多少
最后组成的可能只有八种： {a, b, c}, {a, b, -c}, {a, -b, c}, {a, -b, -c}, {-a, b, c}, {-a, b, -c}, {-a, -b, c}, {-a, -b, -c}
于是对目标加和是负数的整个序列取反（取绝对值），取 \(\max\) 即是答案。
\(\texttt{Contest 101}\)
\(\texttt{Problem C:}\) \(\texttt{Minimization}\)
一个 \(n\) 的全排列，每次选择长度为 \(m\) 的子段，把所有元素变成子段中的最小值。求把 \(n\) 个元素变成一样的操作次数
显然，最后剩下的所有元素即是序列中的最小值，我们将如何考虑从最小值伸展出去。
\(\texttt{Problem D:}\) \(\texttt{Snuke Numbers}\)
\(\texttt{咕}^{\texttt{咕}_\texttt{咕}}\)?
\(\texttt{Contest 102}\)
\(\texttt{Problem C:}\) \(\texttt{Linear Approximation}\)
选择一个 \(b\) ，使得 \(\sum\limits_{i=1}^{n}\text{abs}(A_i - (b+i))\) 最小。
可以先处理出 \(A_i - i\)，进行排序， \(b\) 则是 \(A_i\) 的中位数。
\(\texttt{Problem D:}\) \(\texttt{Equal Cut}\)
把一个长度为 \(n\) 的序列分成 \(4\) 段，使得最大和与最小和之差最小。
先做一遍前缀和，前 \(i\) 个值的和标记为 \(sum_i\)
我们用 \(P_1, M, P_2(P_1 < M<P_2)\) 对他们进行分割，四段得出的值则如：
\(val_1 = sum_n - sum_{P_{2}}\)
\(val_2 = sum_{P_{2}} - sum_{Med}\)
\(val_3 = sum_{Med} - sum_{P_{1}}\)
\(val_4 = sum_{P_{1}}\)
我们尝试枚举 \(M\) ， 则只要使得 \(\text{abs}(val_1 - val_2)\) 与 \(\text{abs}(val_3 - val_4)\) 尽量小，过程中对 \(ans\) 取 \(\min\) 即可。
随着 \(M\) 的增大，若 \(P_1\) 与 \(P_2\) 不变，则 \(val_2\) 会越来越小，而 \(val_3\) 会越来越大，两个差值也会越来越大，所以 \(P_1\) 与 \(P_2\) 在过程中是单调不减的。
于是调整 \(P_1,P_2\) 实时更新即可。
\(\texttt{Contest 103}\)
\(\texttt{Problem C:}\) \(\texttt{Modulo Summation}\)
\(f(m) = (m \bmod A_1) + (m \bmod A_2) + \cdots +(m\bmod A_n)\) ， 求 \(f(m)\) 的最大值。
显然，令 \(p = \text{lcm}\{A_1,A_2\dots A_n\}\) ，则 \(f(p) = 0,f(p-1)=\sum\limits_{i=1}^{n}A_i-1\) ，直接求 \(f(p - 1)\) 即可。
\(\texttt{Problem D:}\) \(\texttt{Islands War}\)
一条长度为 \(N\) 的链（ \(i\) 与 \(i + 1\) 相交，共 \(N - 1\) 条边），有 \(M\) 个冲突条件： \(a_i\) 与 \(b_i\) 不连通，求最小需断掉边的条数。
口胡算法：把 \(a_i\) 和 \(b_i\) 看做区间左右端点，求不相交能放置的最多区间。
设已经按右端点排序过的的区间为 \(P\) ，则任意满足 \(P_i.r \le P_{i + 1}.r\) ，分两种情况讨论：
-
若 \(P_i.r>P_j.l\;(i <j)\) ，则一定可以找一个断点（在 \([P_i.l,P_i.r] \cap [P_j.l,P_j.r]\) 任意一点）分割，同时满足两个条件
-
若 \(P_i.r<P_j.l\;(i < j)\) ， 此时它们的区间交 \([P_i.l,P_i.r] \cap [P_j.l,P_j.r]\) 是没有元素的，于是要新创一个断点。
这就转化成在 \([1,n]\) 这个区间里能放置的最小不相交区间数。
\(\texttt{Contest 104}\)
\(\texttt{Problem C:}\) \(\texttt{All Green}\)
一共有 \(D\) 种题目，第 \(i\) 种题目有 \(p_i\) 道，每道分值为 \(100i\) ，把 \(p_i\) 道题目全部做完能多加 \(c_i\) 的分值。求要达到分值 \(G\) 至少要做的题目数。（ \(D \le 10\) ）
直接暴力枚举要做的题目（二进制最右边第 \(i\) 位是 \(1\) ，代表第 \(i\) 道题要做），再从大到小贪心即可。
时间复杂度： \(\mathcal{O}(D\cdot2^D)\)
\(\texttt{Problem D:}\) \(\texttt{We Love ABC}\)
有只包含字符
A，B，C，?的字符串，求其中有多少个子串ABC。（?可以代替任何字符）
分类讨论：
\(\text{if} \;p_i \not=\;?\)
\(\quad\quad f_{i,0/1/2} = f_{i-1, 0/1/2}\)
\(\quad\quad \text{if} \; p_i=a\quad\quad f_{i,0}\leftarrow f_{i,0}+3^{cnt}\)
\(\quad\quad \text{if} \; p_i=b\quad\quad f_{i,1}\leftarrow f_{i,1}+f_{i,0}\)
\(\quad\quad \text{if} \; p_i=c\quad\quad f_{i,2}\leftarrow f_{i,2} +f_{i,1}\)
\(\text{if} \;p_i = \;?\)
\(\quad\quad f_{i,0}\leftarrow f_{i-1,0}\times 3+3^{cnt}\)
\(\quad\quad f_{i,1}\leftarrow f_{i-1,1}\times 3+f_{i,0}\)
\(\quad\quad f_{i,2}\leftarrow f_{i-1,2}\times 3 +f_{i,1}\)
\(\texttt{Contest 105}\)
\(\texttt{Problem C:}\) \(\texttt{Base -2 Number}\)
把一个数转化成 \(-2\) 进制数。
显然可以使用短除法，但会出现三种余数： \(1, 0, -1\) 。我们考虑如何处理 \(-1\) 。
\(a\div -2=c\cdots\cdots -1\)
\(\quad-2c-1=a\)
\(=-2c + -2+1\)
\(=-2(c+1)+1\)
\(a\div-2=(c+1)\cdots\cdots 1\)
\(\texttt{Problem D:}\) \(\texttt{Candy Distribution}\)
求长度为 \(n\) 的序列中总和能被 \(m\) 整除的子段个数。
如果 \(\sum\limits_{i=l}^ra_i\equiv0\pmod m\) ，等同于 \(\text{sum}_r-\text{sum}_{l-1}\equiv0\pmod m\) ，于是可以得出 \(\text{sum}_r\equiv\text{sum}_{l-1}\pmod m\) 。
map 实时统计即可。
\(\texttt{Contest 106}\)
\(\texttt{Problem C:}\) \(\texttt{To Infinity}\)
一个只有
'1'~'9'的字符串 \(S\) ，每过一天'1'会变成'1'，'2'会变成'22'，'3'会变成'333'，'4'会变成'4444'\(\cdots\) 求过了 \(5\times 10^{15}\) 天后第 \(K\) 个字符是什么。
因为除了 '1' ，其他数字的个数都以指数型增长增加，所以求第 \(10^{18}\) 字符远远小于 \(2^{5\times10^{15}}\) 的。所以只要找到前 \(K\) 个字符的第一个不是 '1' 的数，若前 \(K\) 个数字都是 '1' ，则输出 '1' 即可。
\(\texttt{Problem D:}\) \(\texttt{AtCoder Express 2}\)
有 \(n\) 个区间，给定 \(q\) 个询问，每次询问 \(l_i\) 和 \(r_i\) 之间有多少个区间（ \(l_i \le x,y \le r_i\) ）。
先把区间存在数组里 \(p\) 里， \(p_{i, j}\) 表示区间 \([l, r]\) 有几个。
\(dp_{i, j}\) 表示区间 \([i, j]\) 中有几趟火车，得出如下转移方程：
\(dp_{i,j}\leftarrow dp_{i+1,j}+dp_{i, j - 1}-dp_{i + 1, j - 1} + p_{i, j}\)
于是 \(\mathcal{O}(n^2)\) 预处理， \(\mathcal{O}(1)\) 查询。
\(\texttt{Contest 107}\)
\(\texttt{Problem C:}\) \(\texttt{Candles}\)
数轴上有 \(n\) 根蜡烛，第 \(i\) 个蜡烛坐标为 \(x_i\) 。从 \(0\) 点开始，至少经过 \(k\) 根不同蜡烛的总路程最小值。
容易的出一个结论：
- 设两点分别为 \(i\) 和 \(j\) 且满足 \(x_i<0\le x_j\) ，路线肯定是 \(0\rightarrow x_i \rightarrow x_j\) 或者 \(0\rightarrow x_j \rightarrow x_i\) 。
直接暴力出奇迹
\(\texttt{Problem D:}\) \(\texttt{Median of Medians}\)
给你一个长度为 \(n\) 的序列，求每个子段的中位数集合的中位数。
二分答案。 \(\mathcal{O}(\log n)\)
以下是 check ，求子段中位数集合中比 \(\text{mid}\) 大的数是否 \(\ge\left\lceil\dfrac{n}{2}\right\rceil\) ：
-
给原数组重新赋值：小于 \(\text{mid}\) 赋 \(-1\) ，反之赋 \(1\) 。 \(\mathcal{O}(n)\)
-
做一遍前缀和，子段和大于 \(0\) 的说明中位数大于 \(\text{mid}\)。 \(\mathcal{O}(n)\)
-
用树状数组维护比 \(\text{mid}\) 大以 \(i\) 作为右端点的子段的中位数个数，也就是比 \(1\sim i\) 小的前缀（ \(\text{sum}_i < \text{sum}_j(i<j),\sum\limits_{p = i + 1}^j A_p > 0\) ），再向 \(\text{sum}_i\) 插入 \(1\) ，即可统计子段中位数大于 \(\text{mid}\) 的个数。 \(\mathcal{O}(n\log n)\)
总时间复杂度： \(\mathcal{O}(n \log^2 n)\)
\(\texttt{Contest 108}\)
\(\texttt{Problem C:}\) \(\texttt{Triangular Relationship}\)
求 \(a, b, c \le n\) 且 \(k|(a + b) ,k|(b + c) ,k|(a + c)\) ，求这样的三元组个数。
容易得 \(a=b=c\) 且 \(k|a\) ，则 \(a = b=c=pk\) ，若 \(k \bmod 2 \equiv 0\) ，则有 \(a=b=c=\dfrac{k}{2}+pk\) 。暴力统计。
\(\texttt{Problem D:}\) \(\texttt{All Your Paths are Different Lengths}\)
建一个有向图，最多 \(20\) 个点， \(60\) 条边，使得从 \(1\) 到 \(n\) 有 \(L\) 条路径且长度分别为 \(0\sim L-1\) 。
找到最大的 \(p\) 且 \(2^p-1 \le L\) ，再在 \(i\rightarrow i+ 1\) 各建一条长度为 \(0\) 和长度为 \(2^{i - 1}\) 的边（相当于二进制表示法），我们就表示出了长度为 \(0\sim 2^p-1\) 的边。
剩下的我们在原来基础上建边，循环执行以下操作：
- 令已建的边数为 \(k\) ，找到最大的 \(p_1\) 使得 \(k+2^{p_1}\) ，在 \(p_1+1\rightarrow p\) 建权值为 \(k+1\) 的边。
输出即可。
\(\texttt{Contest 109}\)
\(\texttt{Problem C:}\) \(\texttt{Skip}\)
在数轴上，从点 \(x\) 开始每次可以跳 \(d\) 步，求到达指定点的最大 \(d\) 。
对每个点与 \(x\) 的距离求一遍 \(\gcd\) 。
\(\texttt{Problem D:}\) \(\texttt{Make Them Even}\)
给定 \(H\times M\) 的矩阵，在 \((i,j)\) 有 \(a_{i,j}\) 个金币，每次可以将一个金币给相邻的格子，且每个格子只能执行一次，输出时整个棋盘偶数个金币格子最多的操作。
直接从左上角，找到奇数金币的格子转移到右边或下面，模拟水。
\(\texttt{Contest 110}\)
\(\texttt{Problem C:}\) \(\texttt{String Transformation}\)
给定字符串 \(S\) 和 \(T\) ，每次可以在字符串 \(S\) 里选择两个不同的字符 \(c_1\) 和 \(c_2\)，把 \(S\) 中所有 \(c_1\) 替换为 \(c_2\) ， \(c_2\) 替换为 \(c_1\) ，求 \(S\) 能否变成 \(T\) 。
因为如果把 \(c_1\) 连向 \(c_2\) ，最后得到的肯定是 \(k\) 个环。
判断每个点入度是否 \(>1\) 即可。
\(\texttt{Problem D:}\) \(\texttt{Factorization}\)
求 \(n\) 个正整数相乘等于 \(m\) 的个数（数字相同位置不同算不同）。
根据唯一分解定理，已知 \(m = a{_1}^{p_1}\times a{_2}^{p_2} \cdots a{_k}^{p_k}\) 则我们可以对每个 \(a{_i}^{p_i}\) 做一次隔板法，得出方法总数为 \(\sum\limits_{i=1}^{k}\dbinom{p_i+n-1}{n-1}\)
组合数的计算用乘法逆元。（ \(\text{mod}\) 请自写函数减少常数）
\(\texttt{Contest 111}\)
\(\texttt{Problem C:}\) \(/ \backslash/ \backslash / \backslash /\)
有一个长度为 \(N\) 的序列 \(A\) ，求使得序列满足 \(A_i = A_{i + 2}, A_i ≠ A_{i + 1}\) 的改变元素次数。
统计奇偶性相同的每个数的出现次数，贪心可得都统一成出现次数最多的数，若两边相同则取第二个。
\(\texttt{Contest 112}\)
\(\texttt{Problem C:}\) \(\texttt{Pyramid}\)
已知 \(h_i = \max\{H - |x_i-CX| - |y_i-CY|, 0\}\) ，问满足要求的 \(H\) ，\(CX\) ， \(CY\) 。
直接枚举 \(CX\) 和 \(CY\) ，判断后再输出。
\(\texttt{Problem D:}\) \(\texttt{Partition}\)
构造一个有 \(N\) 个数的正整数序列 \(a\) ，使得 \(\sum\limits_{i=1}^N a_i=m\) 。求出 \(\gcd\limits_{i=1}^N a_i\) 的最大值。
使得 \(\gcd\limits_{i=1}^N a_i\) 最大则满足 \(\min\limits_{i=1}^N a_i | m\) ， \(m\div \min\limits_{i=1}^N a_i\ge n\) 。
然后就暴力枚举。
\(\texttt{Contest 113}\)
\(\texttt{Problem C:}\) \(\texttt{ID}\)
\(A\) 国有 \(M\) 个县和 \(N\) 个市，第 \(i\) 个县属于第 \(P_i\) 个市，建立的年份为 \(Y_i\) 。现在想要分给每个县一个由 \(12\) 位数字组成的编号，如果第 \(i\) 个县属于第 \(P_i\) 个市且是第 \(x\) 个创立的，则该县编号前六位为 \(P_i\)
，后六位为 \(x\) 。试求出所有县的编号并按输入顺序输出。
结构体排序练手题。略。
\(\texttt{Problem D:}\) \(\texttt{Number of Amidakuji}\)
定义 \(dp_{i,j}\) 表示走到 \((i, j)\) 的方案数，则可以从 \((i - 1, j)\) ， \((i - 1, j - 1)\) ， \((i, j + 1)\) 转移过来。
问题在判断能不能转移。
我们枚举上一行的状态 \(s\) ，如果要从 \((i - 1, j + 1)\) 走过来，前提是 \(s \And 2^j\) ，也就是有路走过来。从 \((i - 1, j - 1)\) 走过来同理。
最后输出方案数即可。
\(\texttt{Contest 114}\)
\(\texttt{Problem C:}\) \(\texttt{755}\)
求在 \(1\sim N\) 之间各位数上各有 \(3\) ， \(5\) ， \(7\) 且没有其他数的数个数
看范围就应该断定广搜。
写起来是挺好写（我用 bitset 辣），只要存储有没有 \(3\) ， \(5\) , \(7\) ，以及数即可。
小细节不多。
\(\texttt{Problem D:}\) \(\texttt{756}\)
求 \(n!\) 的所有因数中因数有 \(75\) 个的数的个数。
珂以断定：数一定是 \(k^{74}\) ， \(k^{14}+k{_1}^4\) ， \(k^{24}+k{_1}^2\) ， \(k^{2}+k{_1}^4+k{_2}^4\) ，排列组合计数即可。
\(\texttt{Contest 115}\)
\(\texttt{Problem C:}\) \(\texttt{Christmas Eve}\)
话说最近几场的题目名怎么都那么鬼畜
从长度为 \(n\) 的序列里选 \(k\) 个数，使得 \(k\) 个数中的最大最小值差最小。
对数组进行一遍排序，每次选一段长度为 \(k\) 的连续子序列，求极大极小值的差即可。
\(\texttt{Problem D:}\) \(\texttt{Christmas}\)
定义 \(p_k\) 为 \(\texttt b + p_{k - 1} + \texttt p + p_{k - 1} + \texttt b\) ， \(p_0=p\) ，求 \(p_n\) 前 \(X\) 字符 \(p\) 的个数。
我们不断将范围缩小，确定 \(m\) 在第 \(i\) 的哪层，最后递归统计。