A 小红的字符串处理

知识点：字符串、模拟

依次输出每个字符，并在除首字符外的每个字符前输出一个 $\texttt{.}$ 即可。

时间复杂度 $\mathcal{O}(|s|)$。

void solve() {
    string s;
    cin >> s;
    bool f = 1;
    for (auto v : s) cout << (f ? "" : ".") << v, f = 0;
    cout << endl;
}

B 小红的菊花构造

知识点：图论、构造

菊花树要求除中心外的每个节点都与中心直接相连，因此对所有 $i\ne k$，加入边 $(i,k)$。这样恰有 $n-1$ 条边，所有节点连通且不可能成环。

时间复杂度 $\mathcal{O}(n)$。

void solve() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        if (i == k) continue;
        cout << i << " " << k << endl;
    }
}

C/D 小红的 swap

知识点：字符串、构造、贪心、下界证明

记 $A$ 为满足 $s_i=\texttt{0},t_i=\texttt{1}$ 的位置集合，$B$ 为满足 $s_i=\texttt{1},t_i=\texttt{0}$ 的位置集合。由于两个字符串中 $\texttt{1}$ 的数量相同，必有 $|A|=|B|=m$。

若 $m=0$，不需要操作。否则按
$$A_1,B_1,A_2,B_2,\ldots,A_m,B_m,A_1$$
的顺序操作。第一次交换后 $\texttt{2}$ 暂存在 $A_1$，此后字符 $\texttt{0}$ 、$\texttt{1}$ 交替填入对应的错误位置，最后再操作一次 $A_1$，即可将其填成 $\texttt{1}$ 并收回 $\texttt{2}$ 。

所有 $2m$ 个错误位置都必须至少操作一次；同时字符总数守恒，最终字符串恢复为二进制串后，$c$ 仍须为 $\texttt{2}$ 。第一次操作放入字符串的 $\texttt{2}$ 因而必须通过重复操作某个位置取回，所以还至少需要一次操作。上述方案恰好操作 $2m+1$ 次，因此是最优方案。

时间复杂度 $\mathcal{O}(n)$。

void solve() {
    int n;
    string s, t;
    cin >> n >> s >> t;
    vector<int> A, B;
    for (int i = 0; i < n; ++i) {
        if (s[i] == '0' && t[i] == '1') A.push_back(i + 1);
        else if (s[i] == '1' && t[i] == '0') B.push_back(i + 1);
    }
    int m = A.size();
    if (m == 0) return cout << 0 << endl, void();
    vector<int> ans = {A[0]};
    for (int i = 0; i < m; ++i) {
        ans.push_back(B[i]);
        if (i + 1 < m) ans.push_back(A[i + 1]);
    }
    ans.push_back(A[0]);
    cout << ans.size() << endl;
    for (auto v : ans) cout << v << endl;
}

E 小红的分割线

知识点：计算几何、叉积、枚举

枚举点对 $(i,j)$ 确定直线，再枚举其余点。叉积
$$(p_j-p_i)\times(p_k-p_i)$$
的正负分别表示点 $p_k$ 位于有向直线的两侧，等于 $0$ 则表示共线，不计入任何一侧。统计两侧点数并判断是否相等即可。

时间复杂度 $\mathcal{O}(n^3)$。

int cross(pii a, pii b, pii c) {
    return (b[0] - a[0]) * (c[1] - a[1])
         - (b[1] - a[1]) * (c[0] - a[0]);
}

void solve() {
    int n;
    cin >> n;
    vector<pii> p(n);
    for (auto &[x, y] : p) cin >> x >> y;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int x = 0, y = 0;
            for (int k = 0; k < n; ++k) {
                int v = cross(p[i], p[j], p[k]);
                x += v > 0;
                y += v < 0;
            }
            ans += x == y;
        }
    }
    cout << ans << endl;
}

F 小红的网格图构造 2.0

知识点：构造、棋盘染色、分类讨论

按行列下标的奇偶性把格子分成四类。每个 $2\times2$ 区域恰好包含每一类各一个格子，因此若固定某一类全为 $\texttt{1}$ 、另一类全为 $\texttt{0}$ ，其余两类便可任意填充，条件始终成立。

先令所有“奇行奇列”格子为 $\texttt{1}$ ，再按需填充两个位于偶数行的类别，此时“奇行偶列”恒为 $\texttt{0}$ 。若仍凑不够 $k$ 个 $\texttt{1}$ ，则重新构造，依次填充除“奇行奇列”外的三个类别，并令“奇行奇列”恒为 $\texttt{1}$ 。由此能覆盖全部可行数量；若第一类必选格子已经超过 $k$，或第二种构造填满后仍不足 $k$，则无解。

时间复杂度 $\mathcal{O}(nm)$。

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    int bak = k;
    vector<vector<int>> a(n, vector<int>(m));
    auto fill = [&](int x, int y, bool f) {
        for (int i = x; i < n; i += 2)
            for (int j = y; j < m; j += 2) {
                if (f && k == 0) break;
                a[i][j] = 1, --k;
            }
    };
    fill(1, 1, 0);
    if (k < 0) return cout << "No" << endl, void();
    fill(0, 0, 1);
    fill(0, 1, 1);
    if (k) {
        k = bak;
        a.assign(n, vector<int>(m));
        fill(0, 0, 1);
        fill(0, 1, 1);
        fill(1, 0, 1);
        if (k) return cout << "No" << endl, void();
    }
    cout << "Yes" << endl;
    for (auto u : a) {
        for (auto v : u) cout << v;
        cout << endl;
    }
}

G 小红的网格图构造 1.0

知识点：构造、连通块、分类讨论、棋盘染色

当 $n=1$ 或 $m=1$ 时不存在 $2\times2$ 区域，只需间隔放置 1，最多构造 $\lceil nm/2\rceil$ 个连通块。

以下设 $n,m>1$，记
$$h=\left\lceil\frac n2\right\rceil,\qquad w=\left\lceil\frac m2\right\rceil,\qquad mid=hw.$$

当 $1\le k\le h$ 时，先将第 $0,2,4,\ldots$ 行全部置为 $\texttt{1}$ ，得到 $h$ 个横向连通块；再于相邻两行之间补一个 $\texttt{1}$ ，每次合并两个连通块，直至剩下 $k$ 个。
当 $h<k\le mid$ 时，仍只在偶数行放 $\texttt{1}$ ，再把这些行中的奇数列依次改为 $\texttt{0}$ 。每多挖一个空格，就把一段横条拆成两个连通块，可构造 $h$ 到 $hw$ 个连通块。
当 $mid<k\le\lceil nm/2\rceil$ 时，先在“偶行偶列”放置 $mid$ 个互不相邻的 $\texttt{1}$ ，再按需于“奇行奇列”放 $\texttt{1}$ 。新增的 $\texttt{1}$ 与已有格子只对角相邻，因此每个都新建一个连通块。

三种构造中，每个 $2\times2$ 区域都同时含有 $\texttt{0}$ 和 $\texttt{1}$ 。二维情况下全 $\texttt{0}$ 不合法，而棋盘格已达到连通块数量上界 $\lceil nm/2\rceil$，故其余情况无解。