【CF1392】E. Omkar and Duck（构造）

题目链接：https://codeforces.com/problemset/problem/1392/E

分析

要构造除每一条路径上的和都不同的矩阵
只需要根据类似字典序的构造方法即可

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define lson (k << 1)
#define rson (k << 1 | 1)const int INF = 0x3f3f3f3f;
const int N = 2e3 + 10;
const int M = 1e6 + 10;
const ll P = 1e9 + 7;int n, q;
ll a[30][30];
ll s;int main() {
    cin>>n;for(int k=2;k<=n;k++){
    ll tmp = 1ll << (k - 2);for(int i=k,j=1;i>=1&&j<=n;i--,j++){
    if(j % 2) a[i][j] = tmp;}}for(int k=2;k<n;k++){
    ll tmp = 1ll << (k + n - 3);for(int i=n,j=k;i>=1&&j<=n;i--,j++){
    if(j % 2) a[i][j] = tmp;}}for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++) cout<<a[i][j]<<" ";cout<<endl;}cin>>q;while(q--){
    cin>>s;int x = 1, y = 1;int cnt = 0;while(x <= n && y <= n){
    cout<<x<<" "<<y<<endl;if(x == n && y == n) break;if(x + 1 <= n && (s & (1ll << cnt)) == a[x + 1][y]){
    x++;cnt++;continue;}if(y + 1 <= n && (s & (1ll << cnt)) == a[x][y + 1]){
    y++;cnt++;continue;}}}return 0;
}