若至题集

CF1333E Road to 1600

STATEMENT

把 依次填入 的方格中。然后你需要访问每个格子恰好一次。有两种访问方式。

Rook 式：

1. 从1所在方格开始；
2. 如果与它同行 / 同列中存在未被访问过的格子，选择一数字最小的格子走过去；
3. 否则，从未访问过的方格中选择一个数字最小的方格并走过去。花费 个代价。

Queen 式：

1. 从 所在方格开始；
2. 如果与它同行 / 同列 / 同对角线（两个方向）中存在未被访问过的格子，选择一数字最小的格子走过去；
3. 否则，从未访问过的方格中选择一个数字最小的方格并走过去。花费 个代价。

现在要求你构造一种填数方案，使得 Rook 式的代价严格小于 Queen 式的代价。

s.t.

SOLUTION

考虑暴搜出小方格的情况。然后其他地方构造成 Queen 和 Rook 走一样的路线。最后引导到这个小方格即可。

CODE

constexpr int N = 505;
int n, a[N][N];

signed main() {
    fastio();
    cin >> n;
    if (n <= 2) {
        cout << -1 << endl;
        return 0;
    }
    int cnt = 0, m = n * n - 9;
    a[1][1] = 1 + m; a[1][2] = 7 + m; a[1][3] = 9 + m;
    a[2][1] = 3 + m; a[2][2] = 2 + m; a[2][3] = 5 + m;
    a[3][1] = 4 + m; a[3][2] = 8 + m; a[3][3] = 6 + m;
    Fe(i, 1, n - 3) {
        if (i & 1) {
            Fe(j, 1, i + 2) a[i + 3][j] = ++cnt;
            a[i + 3][i + 3] = ++cnt;
            Fer(j, i + 2, 1) a[j][i + 3] = ++cnt;
        } else {
            Fe(j, 1, i + 2) a[j][i + 3] = ++cnt;
            a[i + 3][i + 3] = ++cnt;
            Fer(j, i + 2, 1) a[i + 3][j] = ++cnt;
        }
    }
    Fe(i, 1, n) Fe(j, 1, n) cout << a[i][j] << nli(j, n);
    return 0;
}

REFLECION

场上打暴力时间来不及，错失此题

2022 CCPC 广州站 L. Station of Fate

STATEMENT

There are people standing in stations, forming queues.

You don't know which person is in which station, or in what order they are standing in queue, so you want to count the number of different schemes. Two schemes are considered different, if and only if there exists a station whose queue consists of different people, or has different orders.

Calculate the number of different schemes modulo .

Translate: 有 个人和 个车站，求将所有人分派到车站且每个车站保证有人的前提下的方案数

SOLUTION

我们有 显然

REFLECTION

场上做复杂了, 用了容斥做这道题