ultmaster edited 6 年，11 月前
首先考虑 $r+1$ 的周期。在一个周期内，就是把 $n$ 个物品分成 $r+1$ 份，使得每份的重量超过 $C$，且价值最小。这个问题是典型的状压 DP，使用状态 dp[i][mask]，取第 $i$ 天的 mask，可以递推到第 $i+1$ 天的。我们发现接下来每 $r+1$ 天的选择方案都是由这 $r+1$ 天决定的。所以可以一直推理下去。
但存在一个小问题就是最后的 $m \bmod (r+1)$ 天。在这些天中，选择方案也是由前 $r+1$ 天决定的，带来的问题就是，前 $m \bmod (r+1)$ 天在上面的最优情况中不能保证是最优的。一种常见的繁琐的解决方案是通过一系列特判和精确的比较来获得这几天的方案。但有一种更简单的方案，就是在前面的计算收益过程中考虑当天出现的次数，从而将当天的数目和卡路里同时乘以这个系数，然后再进行约束和比较。
某验题人野鸡解法：周期为 $ r+1 $ ，为方便令 $ r=\min{r+1,m} $ 方便处理，状态压缩直接对周期进行递推推出第 $ i $ 天取食物状态为 $ j $ 时是否能够达到。若 $ m\leq r $ 则直接就能遍历获得结果。若 $ m>r $ ，由于不一定正好取完周期，仍然需要进一步处理，需要知道周期多余的天数 $ m \bmod r $ 加上之前 $ \lfloor m/r \rfloor $ 个周期总和的最优值，这里可以反向递推，每天去看前一天能转移过来的状态，将周期的数目和卡路里值更新过去，取最优，这样就能够求某天某状态能达到的最优的周期，取第 $ m \bmod r $ 天的值拼上该状态最优周期的值乘以 $ \lfloor m/r \rfloor $ 就是结果。
可以考虑预处理出 $1$ 到 $10^6$ 中所有的数的所有因数。给每个数开个 vector，然后用类似筛法的方法，从小到大枚举，然后给所有这个数的倍数的 vector 加上这个数，结果我们就可以在因数总个数的线性时间内获得所有因数。如果你有统计过的话，是 $10^7$ 多一点。
然后我们对每两个数求出 gcd，由于第 $k$ 大的 gcd 一定是 gcd 的因数，所以我们只要求 gcd 第 $k$ 小的因数然后除以它就可以了。如果不存在就是 $-1$。
此题还可以通过离线处理加速（因为可能取到的 $k$ 值是有限的），通过欧拉筛加速。但对于本题来说时限够宽以至于不做优化也能 AC。
作为一道简（防）单（AK）题没人过真是太不可思议了。
这道题就是 trick 非常多。首先 $n=1,2,3$ 要特判，$a_i=0$ 要特判。使用 $b^2=ac$ 是会爆 64 位整数的，使用 double 会爆精度依然 WA。但很多 WA 的并不是一个小问题，而是出了很多小问题。从而花了大量时间来调试这道（简单）题，打出 GG。
一种解法是使用定义，特判 $n=1,2,3$，枚举每一个数作为错误的数的可能性，然后进行 check。$n \geq 4$ 时，我们改一个数，依然一定会有两个数相邻。我们把那两个数的比值作为正确的公比，约分，存成分数。然后从前往后、从后往前，用分数乘法把其余的数一个一个乘出来。另外注意输出格式中规定的范围以免不慎溢出。
另一个比较显然的解法是利用 long double 检查公比，对于 $n = 1$ 和 $n = 2$ 的情况进行特判；
其余直接对每一个数用相邻数公比替换后，再对整个数列进行检查：注意检查等比数列中每一个数都得是正整数且在 $1$ 到 $10^{18}$ 之间。
此题数据较强，因而检查公比相同时建议使用 long double 以及 eps = 1e-20。
一种方法是先判英文（可以用常用词 a, the 等等来判断），然后在通过单词长度来判中文和日文。注意判的时候不要太绝对，应该设置适当的阈值以免误判。
另外一种方法是直接复制三段样文，然后开一个 set 找在哪个 set 中出现的最多。
将 $n, m$ 均乘 $4$ 之后，就转化为整数求解，进行 $2000 \times 2000$ 的递推。
对于每个状态 $a[i][j]$ ，暴力枚举看能转移到哪些状态，若能转移到 $k$ 个状态，则每个转移到的状态的概率增加 $\frac{a[i][j]}{k}$ ，若有一种食物卖完就可以停止进行累加或丢掉，具体实现记忆化搜索会好写一点，然后时限较紧可能需要进行有优化。
首先二分答案，我们考虑对长度 $k$ 进行 check。
我们记录 common[i][j]，表示 $T[0..j]$ 和 $s_i$ 的最长公共子串。利用这一信息，我们从左向右扫，贪心地让满足要求的下标尽可能小。
那么，剩下的问题就是如何求 common[i][j] 了。考虑后缀自动机的做法。对于 $s_i$ 分别建后缀自动机后，就是一个 $T$ 和 $s_i$ 求 LCS 的经典题。由于使用后缀自动机求 LCS 要逐步读入 $T$ 的每一个字符，恰好能获得其前缀的 LCS，这题就做完了。
也可以考虑哈希，先做 check，check 的时候把每一个子串去 $s_i$ 中找，如果 $s_i$ 中已经找到了，对 $T$ 进行扫描的指针要加 $k$，同时要对 $s_{i+1}$ 进行处理。如果最后所有的 $s_i$ 都处理完了就是符合要求的。这里没有卡自然溢出。哈希虽然复杂度多一个 $\log n$，但实际运行速度甚至会比后缀自动机快一点。
这道题图中只需要满足以下四个条件即为项链：
整数的情况 $O(\sqrt x)$ 枚举即可。不妨构造 $pq=a^2+c^2$ 两边除以 $q^2$ 可以得到 $p/q=(a/q)^2+(c/q)^2$ ，于是 $a,q,c,q$ 就是一组解。
因为数据保证有解，那么我们在 $O(\sqrt x)$的复杂度下枚举即可。
正确性：显然，$pq$ 有整数平方和则 $p/q$ 有有理数平方和。若 $pq$ 没有整数平方和而 $p/q$ 有有理数平方和，可两边同乘 $(qbd)^2$ 等式右边为两整数平方和，由于乘平方不改变质因子幂次奇偶性，$pq$ 也应有解，推出矛盾，因而 $pq$ 没有整数平方和则 $p/q$ 没有理数平方和，逆否命题加之前结论可推出等价。
本题需要使用前缀和和差分约束的知识。令 $sum_i=\sum_{j=1}^i{a_i}$ ，则给定约束等价于 $ans=sum_{r}-sum_{l-1}$ ，对于每个约束从 $l-1$ 向 $r$ 连一条权为 $ans$ 的边，反向连一条权为 $-ans$ 的边，则如果存在 $u$ 到 $v$ 权为 $c$ 的一条边则必有 $sum_v=sum_u+c$ ，然后这这张图上 dfs 推出每个点的值即可，dfs 过程存在矛盾就进行标记，这样就能判断是否存在矛盾了。
本题是一道很经典的问题。可以数位 DP 进行求解，也可以预处理十的次方和 $0$ 到多少位全 $9$ 能产生多少 $6$ ，直接递推求解。
使用一个栈来模拟，当方向为 $1$ 时入栈，方向为 $0$ 时与栈顶比较即可。
先检查矩形的四个顶点是否在圆内，分成以下情况讨论：
NO；YES；NO；YES；否则即为 NO。枚举双方分别得分，然后模拟翻牌过程计算一下就好了。
注意每一个目标所需要的体力要一次性计算之后记录一下，重复计算可能会超时。
一种做法是跑到 $(0,0)$，然后绕一圈，然后回来就可以了。细节处理中需要回溯，可能会有一点繁琐。
另一种做法是 dfs，把所有的空白的点全部跑一遍再回来，可能稍微简单一点（误）？
正确的做法（可能）是每一次加糖的时候考虑前 $r$ 天的。如果没有能加的新糖，就加跟昨天一样的；否则则加任意一种可加的新糖。
比赛中这题的数据有误，导致错误的解法莫名 AC，正解却被卡掉了 25 分。对于这样的问题给大家造成的困扰，本人深感抱歉。但事到如今，对于因此而输给了 XXX、因此而没有拿到三等奖的同学，我只能说不要纠结了（？）……你要相信自己的实力，并相信比（出）赛（题）一（人）定（会）会（背）办（更）得（大）更（的）好（锅）的！
一种解法是枚举两个点，然后对和第三个点组成的平面的法向量（用叉乘得到）进行约分（矫正）处理，然后用一个 map 存一下，或者排个序，然后求出现次数最多的法向量就好了。时间复杂度是 $O(n^3 \log n)$。
另一个暴力解法是直接枚举每三个点所构成的平面，其中平面方程 $Ax + By + Cz + D = 0$ 计算如下：
A = (y[j] - y[i]) * (z[k] - z[i]) - (y[k] - y[i]) * (z[j] - z[i]);
B = (z[j] - z[i]) * (x[k] - x[i]) - (z[k] - z[i]) * (x[j] - x[i]);
C = (x[j] - x[i]) * (y[k] - y[i]) - (x[k] - x[i]) * (y[j] - y[i]);
D = -A * x[i] - B * y[i] - C * z[i];
然后再检查每一个点是否在该平面上，复杂度为 $O(n^4 / 24)$，故可以在规定时间内通过。
对 a[i] 进行排序后，特判一种全部打电话的情况，其余就是 ans = min(ans, a[i] * 2 + (n - i - 1) * b)。注意计算过程中可能会超出 int 范围。
配图好可爱呀 (๑•ᴗ•๑)，我每次路过的时候都要多看一眼 QAQ。
直接暴力就好了啦，排个序，然后二重循环。注意 a[i]+a[j]>max 的时候就跳出，不然会超时。
事实上 $a_i$ 的范围这么小，可以使用 bitset 进行压位。每次加的时候就直接左移相差的位数就可以了。把自己的两倍的位置设为 0，然后把二进制跟原来的二进制进行与运算，看看有没有哪一位是 1。
比赛中好像有人不排序就直接暴力艹过去了？闹了个大新闻？
20% 的数据点可以用深搜直接暴过去。不说了。
50% 的数据点可以用一种类似背包的 DP，由于 $a_i$ 的范围不大，可以从前往后进行递推，用 dp[i][mask] 来表示前 $i$ 个数 & 之后得到了 mask 的方案数。然后可以通过后一个数取和不取两种情况进行递推。
大数据需要使用高维前缀和和容斥原理。首先高维前缀和求出有多少个数的二进制是某数 $x$ 二进制的超集，不妨令这个值为 $b_x$ ，则应有 $2^{b_x}-1$ 个方案交起来为 $x$ 的超集，然后直接根据二进制位为 $1$ 的个数的奇偶性对方案数进行容斥原理即可。
这个是比赛前夜的真实事情，加了两道最简单的题目，让新生组没有成为事故现场。直接扫一遍判断，没有中档就输出，否则就再扫一遍输出，替换第一个中档的。忽略空格所以不必处理，否则需要注意行末的空格。
枚举日期，或者用数组记录然后循环一下都可以。不符合的加两个 if 判一判就好了。
滑动窗口法，枚举左端点，移动右端点。
$n \geq 2017$ 输出 YES；否则输出 NO。