跳转至

CF1392E

知识点

  • 构造

题意简述

这是一道交互题。

给定一个 \(n \times n\) 的矩阵,你可以令其中的每个元素为不超过 \(10^{16}\) 的一个数。

一共有 \(q\) 次询问,每次会告诉你从 \((1, 1)\)\((n, n)\),只能往右或往下走的某一条路径上的所有元素之和,求这条路径1

数据范围:\(1 \le n \le 25\)\(1 \le q \le 10^3\)

解题思路

一道非常有意思的构造题。

注意到 \(2^{2\times 25} \le 10^{16}\),那么我们可以让每条路径的和都对应着 \(2^2\)\(2^{2n}\) 中的每一个 \(2\) 的幂。

因此我们这么构造:令 $$ a_{i, j} = \begin{cases} 2^{i + j} & 2 | i \\ 0 & \textrm{otherwise} \end{cases} $$

\(n = 8\) 时的情形

如此: $$ \begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2^3 & 2^4 & 2^5 & 2^6 & 2^7 & 2^8 & 2^9 & 2^{10} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2^5 & 2^6 & 2^7 & 2^8 & 2^9 & 2^{10} & 2^{11} & 2^{12} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2^7 & 2^8 & 2^9 & 2^{10} & 2^{11} & 2^{12} & 2^{13} & 2^{14} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2^9 & 2^{10} & 2^{11} & 2^{12} & 2^{13} & 2^{14} & 2^{15} & 2^{16} \\ \end{matrix} $$

最后「得到路径和,求路径」的过程也是轻而易举的。

代码实现

核心部分已用高亮标出。

Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
#define LL long long

const int N = 25 + 5;

int n, q;
LL a[N][N];

void solve(LL x) {
    int curx = 1, cury = 1;
    std::cout << curx << ' ' << cury << '\n';
    std::cout.flush();
    for(int i = 3; i <= 2 * n; ++i) {
        if((curx & 1LL) == (x >> i & 1LL))
            ++curx;
        else
            ++cury;
        std::cout << curx << ' ' << cury << '\n';
        std::cout.flush();
    }
}

int32_t main() {
    std::cin >> n;
    for(int i = 2; i <= n; i += 2)
        for(int j = 1; j <= n; ++j)
            a[i][j] = 1LL << i + j;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j)
            std::cout << a[i][j] << ' ';
        std::cout << '\n';
        std::cout.flush();
    }
    std::cin >> q;
    for(int i = 1; i <= q; ++i) {
        LL sum;
        std::cin >> sum;
        solve(sum);
    }
    return 0;
}

  1. 原题链接: E. Omkar and Duck