前言
年刷千题时刻图置顶。我超级刷的完！
2023.06.09
1368D - AND, OR and square sum
个人感觉这题有两个解题思路。
其一是，我们需要发现题目中给定的操作只会将 \(x\) 二进制模式下的全部 \(1\) 移动到 \(y\) 的对应位置上。这个规律可以打表得到，如下图：
bool Solve() {
int A, B;
cin >> A >> B;
bitset<10> x = A;
bitset<10> y = B;
_(x);
_(y);
_(x|y);
_(x&y);
return 0;
}
这有什么用呢？这说明 \(1\) 是可以无损移动的，那么我们尽可能让 \(a_i\) 的大小差距拉开（大的尽可能大、小的尽可能小），就可以使得所求最大。
第二个做法更不容易想到，如下。首先，位运算有个公式：\(x+y=x|y+x\&y\) 。根据这个公式我们可以知道，题目中定义的操作不会影响 \(\displaystyle\sum_{i=1}^n a_i\) 的值。
那么，问题在于 \(\displaystyle\sum_{i=1}^n a_i\) 和我们要求解的式子有什么关系呢……显然，根据高中数学，我们有公式 \(\displaystyle\sum_{i=1}^n a_i^2 =(\sum_{i=1}^n a_i)^2-2\cdot \sum_{i=1}^{n}\sum_{j=i+1}^{n}a_ia_j\) ，此时已知操作不会改变 \(\displaystyle(\sum_{i=1}^n a_i)^2\) 的值，所以要使得 \(\displaystyle\sum_{i=1}^n a_i^2\) 最大，即要让 \(\displaystyle\sum_{i=1}^{n}\sum_{j=i+1}^{n}a_ia_j\) 最小。
现在的问题变成了怎样分配 \(a_i\) ，使得 \(\displaystyle\sum_{i=1}^{n}\sum_{j=i+1}^{n}a_ia_j\) 最小，我们发现，当 \(0\) 的数量最多时，乘积也有最多的 \(0\) 。所以，我们需要让 \(a_i\) 的大小差距拉开。
2023.04.26 \(^{9\text{；*2000乱刷}}\)
1716D - Chip Move \(^{*2000\text{；DP优化}}\)
容易发现，由于 \(k\) 这一限制的存在，一轮最多转移 \(\mathcal O(\sqrt{N})\) 次，于是，一个单轮复杂度 \(\mathcal O(N\sqrt{N})\) 的DP转移跃然纸上：\(dp_{i,j}\) 代表跳了 \(i\) 次后位于 \(j\) 位置的方案数。
那么，面对多轮问题时，前缀和优化是很容易被想到的，且显然，这道题是可以使用这一优化的，于是，多轮复杂度也为 \(\mathcal O(N\sqrt{N})\) ，可以过题。但是有一个小差异在于，这题的前缀和并不是连续的，所以，在处理时需要多留一个心眼。\(pre_{i,j}\) 代表跳 \(i\) 次后位于 \(j\) 位置的方案数之和。
最后分析空间复杂度，发现以现在的定义一定会出事，考虑优化。pre 数组可以直接压缩为一维；而 dp 数组由于中途需要用于更新 pre 数组，故使用滚动数组替代。我们能够很方便的写出如下代码：
vector<Z> dp0(n + 1), ans(n + 1), pre(n + 1);
dp0[0] = 1;
for (int i = 1; i <= m; i++) {
vector<Z> dp(n + 1);
for (int j = 0; j <= n; j++) {
pre[j] = dp0[j];
if (j >= k + i - 1) {
pre[j] += pre[j - (k + i - 1)];
dp[j] = pre[j - (k + i - 1)];
ans[j] += dp[j];
}
}
dp0 = dp;
}
如果你的常数略大——很不幸，您T了。我们分析这样写的精确复杂度，即便不考虑内层循环中的操作复杂度，总复杂度也会来到 \(\mathcal O(\sqrt{N} \cdot 3N)\) 的层级。当 \(N_{MAX}=2\cdot 10^5\) 时，需要计算 \(3\cdot 10^8\) 次，这是非常危险的。
我们考虑优化滚动数组。回忆刚刚的分析，“dp 数组由于中途需要用于更新 pre 数组，故使用滚动数组替代”，故我们强制在本轮更新掉整个 pre 数组即可。
vector<Z> dp(n + 1), ans(n + 1), pre(n + 1);
dp[0] = 1;
for (int i = 1; i <= m; i++) {
for (int j = 0; j <= n; j++) {
Z val = 0;
if (j >= k + i - 1) {
val += pre[j - (k + i - 1)];
}
pre[j] = val + dp[j]; // 借助val强制更新整个pre数组
dp[j] = val;
ans[j] += dp[j];
}
}
最后补充两点做这题时遇到的问题:
GNU C++20 (64)跑DP的速度比GNU C++17快一倍，直接是AC和超时的区别！
Zmod类速度与手动取模不相上下，不要再觉得超时是类导致的了，其实效率极高。
2023.04.25 \(^{9\text{；*2000乱刷}}\)
两个小时多一点点六题*2000……即便最近刷题这么多，还是感到很吃惊。
个人总结，和此前结论一致——*2000分段有一个极其显著的特点是，题目代码都不太长，且总给我一种虚高的感觉，并没有遇到过特别坑的题目，以思维+贪心为主。暂时主观评价这样，等过几日我刷的题多了再做二轮评价。
1296E2 - String Coloring (hard version) \(^{*2000\text{；DP}}\)
由于实在没题目总结了，把这道题搬上来。总体感觉并没有DP思想，且与easy版本思维差距极小，如果先做easy版本很容易就被带歪思路。
当然也可以拥抱DP，用最长下降子序列的思路解这道题，和正解大差不差，由于我DP并不好，所以直接没有管这个。留坑，看会不会填。
710E - Generate a String \(^{*2000\text{；DP}}\)
转化成跳方格这一经典问题。列出转移方程（但不是最终的答案方程）。
注意当 \(n\) 为奇数时的第二种情况是由 \(\left \lfloor \frac{n+1}{2} \right \rfloor\) 先乘二转移到 \(n+1\) 、再减一转移而来。
（典）注意到当 \(n\) 为偶数时没有从 \(n+1\) 转移过来的情况，而这也是这个线性DP复杂度正确的关键，那么为什么呢。这里记 \(u\) 为偶数、\(v=u+1\) ，考虑 \(F_v\) ，其必然不会从 \(F_u\) 转移而来，而会从 \(F_{\left \lfloor \frac{v+1}{2} \right \rfloor}\) 转移，其代价等价于直接从 \(F_{\left \lfloor \frac{u}{2} \right \rfloor}\) 转移，为 \(x+y\) 。故可以略去这一步转移，得到线性递推方程。
2023.04.24 \(^{6\text{；主要集中于*1900的区间DP题}}\)
另这一晚有Div3，小做了几道。
区间DP专题：P4170 [CQOI2007]涂色
特点在于，如果某个区间左端和右端颜色一致，那么 dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]) 转移过来。原因在于，既然一个端点的颜色是这个，那么在涂这个端点的时候完全可以顺手把另一个端点也一起涂了，这样是不需要额外的操作步骤的，其余与标准区间DP一致。
区间DP专题：1132F - Clear the String \(^{*2000\text{；DP}}\)
虚高题，顶天*1600了。特点在于，如果某个区间左端和右端颜色一致，那么删除次数需要 \(-1\) 。原因显而易见，这段可以一起删掉。
区间DP专题：P3847 [TJOI2007]调整队形
特点在于，环形数组，倍增后处理即可；其次特点还在于，每个区间都是有初始值的。
区间DP专题：149D - Coloring Brackets \(^{*1900\text{；DP}}\)
因为条件有“相邻两个括号颜色不能相同”，所以采用了思维数组，但是判断比较麻烦，所以这里这种采用了记忆化递归的方式进行。总体来说与区间DP模板关系不大，属于较为独立的题目。
区间DP专题：1572C - Paint \(^{*2700\text{；DP}}\)
《涂色》的逆向加强版，难度虚高，但是以我的理解暂时说不出过程，所以先留坑。
478D - Red-Green Towers \(^{*2000\text{；DP}}\)
比较好想的递推题（也可以理解为DP，但是我总感觉沾上DP之后心理作用会觉得题目难度上升了），容易想到的是用 \(F_{i,j,k}\) 分别代表在第 \(i\) 层使用了 \(j\) 个红块和 \(k\) 个绿块的方案数量，但是显然这是不可行的，因为空间超了。于是尝试优化，发现每层数量固定、红块数量已知的情况下可以推出绿块数量，于是减少一维；新一层方案数只与上一层相关，于是用滚动数组再减少一维，得解。
本题洛谷题解写的很别扭，明明很清晰的一道题整的非常曲折；于是我参考了Jimanbanashi的思路，大佬写的非常清晰，好评。
2023.04.23 \(^{11\text{；主要集中于*1900的几何题}}\)
1656D - K-good \(^{*1900\text{；数论}}\)
首先我们发现连续的 \(k\) 个数一定满足“余数各不相同”这一条件，随后我们尝试证明：如果有解，则一定可以转换为连续的 \(k\) 个数之和（不懂严格证明，这里就不写出来了）。
经过证明，我们可以根据等差数列 \(p,(p+1),\dots,(p+k-1)\) 得到公式 \(n=\dfrac{(p + p + k - 1) \cdot k}{2}=pk +\dfrac{k(k-1)}{2}\) 。随后，我们用到一个典：分析奇偶性。
对上式变形：\(2\cdot n=k\cdot(2p+k-1)\) ，我们可以发现，左边一定为偶数，右边为一个奇数乘以一个偶数，那么我们如果将\(2\cdot n\) 里的全部 \(2\) 都取出来，那么左边也能变成一个奇数乘以一个偶数的形式。而又因为右边 \(k<2p+k-1\) ，所以左边变形后得到的较小的那个数即为 \(k\) 。
举例：\(20=2^2*5\) ，那么 \(k=2^2,(2p+k-1)=5\) 。之所以是典是因为这样做的复杂度为 \(\mathcal O(\log N)\) 。
bool Solve() {
int n; cin >> n;
int x = 2;
while (n % 2 == 0) {
n /= 2;
x *= 2;
}
int k = min(n, x);
cout << (k >= 2 ? k : -1) << endl;
return 0;
}
1430E - String Reversal \(^{*1900\text{；数据结构}}\)
某种程度上可以看作是典题。容易发现，逆序对的数量是一个可行解，但不是最优解。
观察第三组样例：
icpcsguru
123456789
对于相同的一对 u 和 c ，最优方案一定是不对其进行交换，于是翻转后，我们需要对相同字符对的下标进行修改，使得小的下标在前面，大的下标在后面。
修改前
urugscpci
987654321
修改后
urugscpci
789654321
这样的修改带来的好处是显而易见的，小的数据在前可以最大程度的减少逆序对的数量。最后，对于修改后的下标计算逆序对数量即可。
另补充一组数据：
4
puut
答案为 \(5\) ，当你意识到数据中的这一对 u 对于答案的意义所在，本题即能轻松化解。
342C - Cupboard and Balloons \(^{*1900\text{；几何}\)
不考虑半圆部分，我们发现，最多可以放置 \(\left\lfloor \dfrac{h}{r} \right\rfloor\cdot 2\) 个气球，此时，矩形部分剩余的空白高度为 \(H=h-\left\lfloor \dfrac{h}{r} \right\rfloor\cdot r\) 。
随后我们考虑半圆部分，如上图所示，一定可以放下至少一个气球，那么，能否放下两个气球呢？
如上图所示，当 \(H > \dfrac{r}{2}\) 时可以放下两个气球。
最后我们观察放下三个气球的情况，如上图所示，线段DB的值与 \(H\) 等价，故当 \(H^2>r^2+\dfrac{h}{2}^2\) 时可以放下三个气球。
bool Solve() {
int r, h; cin >> r >> h;
int H = h - h / r * r, ans = h / r * 2 + 1;
if (H * 2 >= r) ans++;
if (4LL * H * H >= 3LL * r * r) ans++;
cout << ans;
return 0;
}
1163C2 - Power Transmission (Hard Edition) \(^{*1900\text{；几何}\)
要求解决如下几个问题：
- 对于给定的互不不相同的点，两两组合，求解出它们能组出的不同的直线数量；
- 对于计算得到的不同的直线，两两组合，求解出有多少对直线间有交点。
对于Easy版本，给出至多 \(50\) 个点，能组合出至多 \(250\) 条直线，允许 \(\mathcal O(N^2)\) 的算法通过。所以我们暴力计算出全部的直线，然后两两组合，使用叉乘判断是否平行即可。
对于Hard版本，能组合出至多 \(10^6\) 条直线，故需要进行优化，这里我直接储存斜率并计算，以 \(\mathcal O(N)\) 的复杂度通过。
总体来说，如果是初学几何，Hard版本的思路可能比Easy版的更容易想到，因为Easy版本的更为模板。而两个版本算法的本质都是围绕直线的两点式、一般式公式的转换以及斜率的计算所展开的。总的来说，本题两个版本的解法都非常有趣，同时重要的是模板的积累。
这里罗列一下使用到的模板，在此感谢 \(\mathcal Hamine\) 的几何模板整理。
using i64 = long long;
const double eps = 1e-8;
struct point {
i64 x, y;
point operator+(const point &p) const { return point{x + p.x, y + p.y}; }
point operator-(const point &p) const { return point{x - p.x, y - p.y}; }
point operator*(i64 t) const { return point{x * t, y * t}; }
point operator/(i64 t) const { return point{x / t, y / t}; }
friend auto &operator<<(ostream &o, const point &j) {
return o << j.x << " " << j.y;
}
friend bool operator<(const point &i, const point &j) {
return (i.x != j.x ? i.x < j.x : i.y < j.y);
}
};
i64 dis(point p1, point p2) { // 曼哈顿距离公式
return abs(p1.x - p2.x) + abs(p1.y - p2.y);
}
double cross(point p1, point p2) { // 叉乘
return p1.x * p2.y - p1.y * p2.x;
}
int sign(double k) {
if (k > eps) return 1;
else if (k < -eps) return -1;
else return 0;
}
bool parallel(point p1, point p2, point p3, point p4) { // 判断是否平行
return sign(cross(p1 - p2, p3 - p4)) == 0;
}
auto getfun(point p1, point p2) { // 两点式转换为一般式
int A = p1.y - p2.y, B = p2.x - p1.x, C = p1.x * A + p1.y * B;
if (A < 0) A = -A, B = -B, C = -C;
else if (A == 0)
if (B < 0) B = -B, C = -C;
else if (B == 0 && C < 0) C = -C;
if (A == 0) {
if (B == 0) C = 1;
else {
int g = gcd(abs(B), abs(C));
B /= g, C /= g;
}
} else if (B == 0) {
int g = gcd(abs(A), abs(C));
A /= g, C /= g;
} else {
int g = gcd(gcd(abs(A), abs(B)), abs(C));
A /= g, B /= g, C /= g;
}
return tuple{A, B, C};
}
bool same(point p1, point p2, point p3, point p4) { // 判断两条直线是否是同一条
return getfun(p1, p2) == getfun(p3, p4);
}
point intersection(point p1, point p2, point p3, point p4) { //两直线交点
double w1 = cross(p1 - p2, p4 - p2);
double w2 = -cross(p1 - p2, p3 - p2);
return (p3 * w1 + p4 * w2) / (w1 + w2);
}