打了场abc，被一个从来没见过的知识点击败了，无所谓，反正以前确实从来没学过计算几何。

E - Laser Takahashi

前置准备——极角排序

极角排序就是使用极坐标对平面图上的点进行排序。为什么要用极坐标呢？因为斜率排序太复杂了，斜率排序需要考虑无穷大、正负号、分母为零等问题，而极坐标只需要考虑角度的范围即可。

极角排序并不需要我们写出计算出 $arctan$ 的值，而是通过比较两个点的象限和叉积来实现排序。计算向量叉乘比计算 $arctan$ 容易得多。

假设我们有一个参考点 $P(x_0, y_0)$（一般是 $(0, 0)$），以及两个待排序的点 $A(x_1, y_1)$ 和 $B(x_2, y_2)$。

struct Point {
    int x, y;

    // 重载一个叉乘运算符
    long long operator @ (const Point &b) const {
        return (long long)x * b.y - (long long)y * b.x;
    }
    // 重载小于运算符用于排序
    bool operator < (const Point &b) const {
        int ah = (y < 0 or (y == 0 and x < 0));
        int bh = (b.y < 0 or (b.y == 0 and b.x < 0));
        if (ah != bh) return ah < bh;
        return (*this) @ b > 0;
    }
};


long long cross(const Point &a, const Point &b) {
    return (long long) a.x * b.y - (long long) a.y * b.x;
}

bool cmp(const Point &a, const Point &b) {
    int ah = (a.y < 0 or (a.y == 0 and a.x < 0));
    int bh = (b.y < 0 or (b.y == 0 and b.x < 0));
    if (ah != bh) return ah < bh;
    return cross(a, b) > 0;
}

题解思路

有了极角排序的技术，我们要做的无非就是简单的离散化和排序，然后迭代计数即可。

因为这个问题也有点RMQ的背景，所以我们选择用数组 $l$ 来记录与点 $i$ 极角相同的点中，编号最小的 $j$（满足 $L_i ≤ i ≤ R_i$）和数组 $r$ 来记录与点 $i$ 极角相同的点中，编号最大的 $j$。这样我们就可以在 $O(N)$ 的时间内回答每个询问。

// 假设我们已经有数组 pt 存储所有点
vector<int> ord(n); // 存储点的索引
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), cmp);
reverse(ord.begin(), ord.end()); // 因为我们需要逆时针排序

vector<int> rev(n); // rev[i] 表示点 i 在排序后的数组中的位置
for (int i = 0; i < n; i++) {
    rev[ord[i]] = i;
}

vector<int> l(n), r(n);
l[0] = 0;
r[0] = n - 1;

for (int i = 1; i < n; i++) {
    l[i] = (cmp(pt[ord[i]], pt[ord[i - 1]]) ? i : l[i - 1]);
}
for (int i = n - 2; i >= 0; i--) {
    r[i] = (cmp(pt[ord[i + 1]], pt[ord[i]]) ? i + 1 : r[i + 1]);
}
while (q--) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    a = l[rev[a]];
    b = r[rev[b]];
    if (a < b) cout << b - a << '\n';
    else cout << n - a + b << '\n';
}

F - Diagonal Separation 2

看出来了要用动态规划，但是实在想不出来怎么写递推式，可能也因为太久没写dp了。

题解思路

我们发现，从行的角度考虑，如果第 $i$ 行有 $A_i$ 个白色，那么我们可以确定 $A_1 \geq A_2 \geq ... \geq A_N$ ，否则就会在列上出现不符合题目条件的情况。所以我们有 $dp[i][j]$ 来表示 重画 前 $i$ 行所需的最小操作次数，$A_i = j$ 。

设 $D[i][j]$ 为使第 $i$ 行变成前 $j$ 个为白色，其余为黑色所需的操作次数，那么我们有如下的状态转移方程：

$$dp[i][j] = \min_{j \leq k \leq N} dp[i-1][k] + D[i][j]$$

int main() {
    int N;
    cin >> N;
    vector<string> grid(N);
    for (int i = 0; i < N; ++i) {
        cin >> grid[i];
    }
    
    // 预处理 D[i][j]: 将第i行前j个格子涂成白色，其余涂成黑色所需的操作数
    vector<vector<int>> D(N+1, vector<int>(N+1, 0));
    vector<vector<int>> pre(N, vector<int>(N+1, 0));
    vector<vector<int>> suf(N, vector<int>(N+1, 0));
    
    // 计算前缀和数组 pre[i][j]: 第i行前j个格子需要涂成白色的数量（不是'.'的数量）
    for (int i = 0; i < N; ++i) {
        for (int j = 1; j <= N; ++j) {
            pre[i][j] = pre[i][j-1] + (grid[i][j-1] != '.');
        }
    }
    
    // 计算后缀和数组 suf[i][j]: 第i行从j到N-1的格子需要涂成黑色的数量（不是'#'的数量）
    for (int i = 0; i < N; ++i) {
        for (int j = N-1; j >= 0; --j) {
            suf[i][j] = suf[i][j+1] + (grid[i][j] != '#');
        }
    }
    
    // 计算 D[i][j]
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= N; ++j) {
            D[i+1][j] = pre[i][j] + suf[i][j];
        }
    }
    
    // DP数组，dp[i][j]表示前i行，第i行选择A_i = j时的最小操作数
    vector<vector<int>> dp(N+1, vector<int>(N+1, 1e9));
    
    // 初始化第一行
    for (int j = 0; j <= N; ++j) {
        dp[1][j] = D[1][j];
    }
    
    // 动态规划转移
    for (int i = 2; i <= N; ++i) {
        // 维护后缀最小值数组
        vector<int> suffix_min(N+2, 1e9);
        for (int j = N; j >= 0; --j) {
            suffix_min[j] = min(suffix_min[j+1], dp[i-1][j]);
        }
        
        // 计算当前行的dp值
        for (int j = 0; j <= N; ++j) {
            dp[i][j] = D[i][j] + suffix_min[j];
        }
    }
    
    // 答案是最后一行的最小值
    int ans = 1e9;
    for (int j = 0; j <= N; ++j) {
        ans = min(ans, dp[N][j]);
    }
    
    cout << ans << endl;
    
    return 0;
}

C - 2026

暴力思路：对于所有 $n$，枚举所有小于 $\sqrt{n}$ 的 $a$ 和它对应的 $b$，判断 $a^2 + b^2 = n$ 的个数。如果个数为 $1$，则计数加一，并记录下这个 $n$。

直接暴力枚举可以做，但是会爆TLE，我们可以选择开一个数组来记忆枚举过程。新算法的思路是直接寻找所有可能的 $a$ 和 $b$，然后将 $a^2 + b^2$ 的值存入数组中进行计数。最后再遍历数组，找出值为 $1$ 的个数和对应的下标。

这个时间复杂度十分优秀，是 $O(\sqrt{N} \times \sqrt{N}) = O(N)$。

解答

#include <bits/stdc++.h>
using namespace std;

int c[10000024];

int main() {
    int N;
    cin >> N;
    
    for (int i = 1; i * i <= N; i++) {
        for (int j = i + 1; i * i +  j * j <= N; j++) {
            c[i * i + j * j]++; 
        }
    }
    int ans = 0;
    for (int i = 0; i <= N; i++) {
        if (c[i] == 1) ans++;
    }
    cout << ans << '\n';
    int cnt = 0;
    for (int i = 0; i <= N; i++) {
        
        if (c[i] == 1) {
            cout << i;
            if (!cnt) {
                cout << ' '; 
            } else cnt++;
        } 
    }
}