「考试总结」2023省选武汉联测3

mqxmm · 2023-03-10 16:45:17 · 个人记录

时间：2023-03-10 07:30~12:00

可以说全是构造题吧。

\texttt {A-回文串(palindrome)}

脑袋有一瞬间闪过正解，但是没有往下想。

后来想到的做法被 hack 了，由于时间的原因就放弃这道题了。

\texttt {Description}

题目描述

给定一个长度为 n (1 \leq n \leq 10 ^ 5) 的字符串 s ，求出一个区间 [L, R] ，满足翻转区间 [L, R] 后 s 是一个回文串，无解则输出 -1 -1。

数据范围

多组输入， T 为数据组数。

哈希判断是否回文。

如果确定一个端点，那么就可以 \mathcal O (n) 求出这个区间。

如果两端字符不相同，那么答案区间一定包含其中一个端点，两种情况分别求区间即可。

如果两端字符相同，那么可以删去两端，不影响答案的存在性。

有 \to 有，证明：若答案区间不包含端点，显然成立；若答案区间包含端点，则答案区间的两端也相同（因为翻转之后首尾相同），那么答案区间删去两端后也满足。

无 \to 无，证明：反证法，如果删去后存在区间满足条件，那么两端添加一个相同的字符时此区间也是答案，即原来一定存在答案，与假设矛盾。

\texttt {Code}

#include <cstdio>

#define LL long long
#define uLL unsigned LL

LL rint() {
    LL x = 0, Fx = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        Fx ^= (c == '-');
        c = getchar();
    }
    while ('0' <= c && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return Fx ? x : -x;
}

template <typename T>
void read(T &x) {
    x = rint();
}

template <typename T, typename... Ts>
void read(T &x, Ts &... rest) {
    read(x);
    read(rest...);
}

const int MAX_n = 1e5;
const int P = 1e9 + 7;

int T, n;
char str[MAX_n + 5];

uLL pre[MAX_n + 5];
uLL suf[MAX_n + 5];
uLL qpow[MAX_n + 5];

uLL getpre(int L, int R) { return pre[R] - pre[L - 1] * qpow[R - L + 1]; }

uLL getsuf(int L, int R) { return suf[L] - suf[R + 1] * qpow[R - L + 1]; }

int main() {
    freopen("palindrome.in", "r", stdin);
    freopen("palindrome.out", "w", stdout);
    qpow[0] = 1;
    for (int i = 1; i <= MAX_n; i++) qpow[i] = qpow[i - 1] * P;
    read(T);
    while (T--) {
        read(n);
        scanf("%s", str + 1);
        for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] * P + str[i] - 'a' + 1;
        suf[n + 1] = 0;
        for (int i = n; i >= 1; i--) suf[i] = suf[i + 1] * P + str[i] - 'a' + 1;
        int L = 1, R = n;
        while (L < R && str[L] == str[R]) ++L, --R;
        if (L >= R) {
            printf("1 1\n");
            continue;
        }
        bool ok = false;
        for (int i = L; i <= R && !ok; i++)
            if (getsuf(L, i) * qpow[R - i] + getpre(i + 1, R) ==
                getsuf(i + 1, R) * qpow[i - L + 1] + getpre(L, i)) {
                printf("%d %d\n", L, i);
                ok = true;
                break;
            }
        for (int i = L; i <= R && !ok; i++)
            if (getpre(L, i - 1) * qpow[R - i + 1] + getsuf(i, R) ==
                getpre(i, R) * qpow[i - L] + getsuf(L, i - 1)) {
                printf("%d %d\n", i, R);
                ok = true;
                break;
            }
        if (!ok) {
            printf("-1 -1\n");
            continue;
        }
    }
    return 0;
}

\texttt {B-国际象棋(knight)}

想过正解，觉得没时间了就只打了暴力。

\texttt {Description}

题目描述

问一个 n \times m (1 \leq n, m \leq 10 ^ 3) 的棋盘中最多能放置多少对马，满足这对马能互相攻击，并给出方案。

马的攻击规则与国际象棋的规则相同。

数据范围

多组输入， T 为数据组数。

这题其实和某类构造题类似，求出小矩阵的答案，把小矩阵拼成所求矩阵。

下面的 \texttt {mx} 是一个参量。

如果 n, m \leq \texttt {mx} ，可以手算或者暴力构造。

否则假设 n > \texttt {mx} （ m > \texttt {mx} 的本质相同），只要 m \neq 1 ，我们就可以四行四行地构造：

其中红色数字相同的是一对（中间的省略表示依次递增），蓝色相连的是一对。

接着只需要把没完成的行递归处理即可，因为下一步要么是 m > \texttt {mx} 要么是 n, m \leq \texttt {mx} 。

容易验证 1 \times, 2 \times 是最优的，如果 n, m \geq 3 ；那么所得到的答案对数为 \lfloor \dfrac { n \times m } 2 \rfloor ，取到上界了肯定最优。所以这种构造是可行的。

对于这题， \texttt {mx} \geq 6 即可，手算或者暴力可以验证 5 \times, 6 \times 比 1 \times, 2 \times 更优。

\texttt {Code}

#include <cstdio>
#include <vector>
#include <utility>

#define LL long long
#define uLL unsigned LL

LL rint() {
    LL x = 0, Fx = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        Fx ^= (c == '-');
        c = getchar();
    }
    while ('0' <= c && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return Fx ? x : -x;
}

template <typename T>
void read(T &x) {
    x = rint();
}

template <typename T, typename... Ts>
void read(T &x, Ts &... rest) {
    read(x);
    read(rest...);
}

LL Max(LL u, LL v) { return (u > v) ? u : v; }
LL Min(LL u, LL v) { return (u < v) ? u : v; }

const int dx[10] = { 0, -2, -2, -1, -1, 1, 1, 2, 2 };
const int dy[10] = { 0, -1, 1, -2, 2, -2, 2, -1, 1 };

const int mx = 6;

int T, n, m, Time;
int cp[mx * mx + 5];
int vis[mx * mx + 5];

std::vector<int> G[mx * mx + 5];
std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > > ans;

std::pair<std::pair<int, int>, std::pair<int, int> > mk(int u, int v, int x, int y) {
    return std::make_pair(std::make_pair(u, v), std::make_pair(x, y));
}

bool dfs(int u) {
    if (vis[u] == Time)
        return false;
    vis[u] = Time;
    for (auto v : G[u]) {
        if (cp[v] == -1 || dfs(cp[v])) {
            cp[v] = u;
            return true;
        }
    }
    return false;
}

void solve(int n, int m) {
    if (n <= mx && m <= mx) {
        for (int i = 0; i < n * m; i++) vis[i] = 0, cp[i] = -1, G[i].clear();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int S = 1; S <= 8; S++) {
                    int x = i + dx[S], y = j + dy[S];
                    if (x >= 0 && x < n && y >= 0 && y < m)
                        G[i * m + j].push_back(x * m + y);
                }
            }
        }
        int res = 0;
        Time = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (((i & 1) ^ (j & 1)) == 1)
                    ++Time, res += dfs(i * m + j);
        for (int i = 0; i < n * m; i++)
            if (cp[i] != -1)
                ans.push_back(mk(cp[i] / m + 1, cp[i] % m + 1, i / m + 1, i % m + 1));
    } else {
        if (n > mx) {
            if (m != 1) {
                int i;
                for (i = n; i > mx; i -= 4) {
                    for (int j = 1; j + 2 <= m; j++) {
                        ans.push_back(mk(i - 3, j, i - 2, j + 2));
                        ans.push_back(mk(i - 1, j, i, j + 2));
                    }
                    ans.push_back(mk(i - 2, 1, i, 2));
                    ans.push_back(mk(i - 2, 2, i, 1));
                    ans.push_back(mk(i - 3, m - 1, i - 1, m));
                    ans.push_back(mk(i - 3, m, i - 1, m - 1));
                }
                solve(i, m);
            }
        } else if (m > mx) {
            if (n != 1) {
                int j;
                for (j = m; j > mx; j -= 4) {
                    for (int i = 1; i + 2 <= n; i++) {
                        ans.push_back(mk(i, j - 3, i + 2, j - 2));
                        ans.push_back(mk(i, j - 1, i + 2, j));
                    }
                    ans.push_back(mk(1, j - 2, 2, j));
                    ans.push_back(mk(2, j - 2, 1, j));
                    ans.push_back(mk(n - 1, j - 3, n, j - 1));
                    ans.push_back(mk(n, j - 3, n - 1, j - 1));
                }
                solve(n, j);
            }
        }
    }
}

int main() {
    freopen("knight.in", "r", stdin);
    freopen("knight.out", "w", stdout);
    read(T);
    while (T--) {
        read(n, m);
        ans.clear();
        solve(n, m);
        printf("%d\n", (int)ans.size());
        for (const auto &e : ans)
            printf("%d %d %d %d\n", e.first.first, e.first.second, e.second.first, e.second.second);
    }
    return 0;
}

\texttt {C-嘉心糖(sugar)}

场切的都是随机化。

\texttt {Description}

不会概括题目。

题目描述

向晚正在接受嘉然的考验。

首先，嘉然选出 n (2 \leq n \leq 2 \times 10 ^ 5) 名嘉心糖排成一个序列 a ，并依次编号为 1 \sim n 。

接着，嘉然对嘉心糖们发布了 m (1 \leq m \leq 2 \times 10 ^ 5) 条指令。每条指令都可以用一个整数 x (1 \leq x < n) 描述，表示让当前处于 x 号位置和 x + 1 号位置的嘉心糖贴贴并交换。

例如，对排列 [5, 1, 4, 2, 3] 发布 x = 3 的指令，会将其变为 [5, 1, 2, 4, 3] 。

最后，嘉然希望向晚能够找到一个尽可能大的嘉心糖集合 S ( S \subseteq \{ 1, 2, \cdots, n \}) ，使得集合内任意两个嘉心糖都曾经贴贴过。

数据范围

目前还不会正解。