1 条题解
-
0
交互题。认真读题。
给定 ，要求你构造（注意）一个 的矩阵，其中的元素 。
输出这个矩阵后会给你 次询问，每次询问给出一条 到 路径（只能向下或右）上所有元素的和，要求你输出这条路径。你的路径与答案不相同即会 WA，这意味着路径是唯一的。
，。
让你构造一个矩阵没有两条路径值相同，显然构造题，容易想到和二进制有关。
注意到 ，走过的点的数量 ，诶，对上了，有戏。
考虑将用二进制第 位表示经过时第 个点是向下还是向右了。
这样的话，就要保证向下和向右一个是 , 一个是 。所以对于所有 ，即所有可能在第 步经过的点，一条对角线，让 和 交替出现即可。（以上可能有加一减一的问题。）
比如 时的一个矩阵：
0 0 0 0 2 4 8 0 0 0 16 0 8 0 32 0CODE
#include <bits/stdc++.h> using namespace std; #define int long long inline int read() { int x = 0, f = 0; char c = 0; while (!isdigit(c)) f |= c == '-', c = getchar(); while (isdigit(c)) x = (x << 3) + (x << 1) + (c & 15), c = getchar(); return f ? -x : x; } #define N 110 int n, s[N], a[N][N]; signed main() { int n = read(); for (int i = 1; i <= n; i ++) { for (int j = 1; j <= n; j ++) { int x = i + j; a[i][j] = (s[x] ++ & 1ll) << x - 2; } } for (int i = 1; i <= n; i ++) { for (int j = 1; j <= n; j ++) { printf("%lld ", a[i][j]); } puts(""), fflush(stdout); } for (int T = read(); T --;) { int s = read(), x = 1, y = 1; while (x != n || y != n) { printf("%lld %lld\n", x, y), fflush(stdout); int st = s & (1ll << (x + y - 1ll)); (st == a[x + 1][y] && x < n) ? x ++ : y ++; } printf("%lld %lld\n", x, y), fflush(stdout); } return 0; }TIP
使用位运算时别忘了
1ll，这两天被坑了几次了 。
- 1
