ZROJ#397. 【18提高7】模仿游戏(爆搜)

题意

sol

考试的时候调了1.5h没调出来我真是菜爆了。。。

读完题目后不难发现，每次约束的条件相当于是\(b[((x[i] + i) % n + (i / n) % n) % n] = y[i]\)

因为数据随机，暴力搜\(a_i\)就行了。搜索的时候结合给出的信息判断一下是否合法。

#include<bits/stdc++.h>
#define pair pair<int, int>
#define mp(x, y) make_pair(x, y)
#define fi first
#define se second 
using namespace std;
const int maxn = 1e6 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int t, n, x[maxn], y[maxn];
int a[30], b[30], vis[maxn];
struct node {
    int po, ti;
};
vector<node> v[maxn];
void dfs(int x) {
    if(x == n) {
        for(int i = 0; i < n; i++) printf("%d ", a[i]); puts("");
        for(int i = 0; i < n; i++) printf("%d ", b[i]);
        exit(0);
    }

    for(int i = 0; i < n; i++) {
        if(!vis[i]) {
            a[x] = i;
            bool flag = 0;
            for(int j = 0; j < v[x].size(); j++) {
                int pos = v[x][j].po, ti = v[x][j].ti;
                int date = (a[(pos + ti) % n] + (ti / n) % n) % n;
                if((b[date] == -1) || (b[date] == y[ti])) ;
                else {flag = 1; break;}
            }
            if(flag) continue;
            vector<int> cha;
            for(int j = 0; j < v[x].size(); j++) {
                int pos = v[x][j].po, ti = v[x][j].ti;
                int date = (a[(pos + ti) % n] + (ti / n) % n) % n;
                if(b[date] == -1) cha.push_back(date), b[date] = y[ti];
            }
            vis[i] = 1;
            dfs(x + 1);
            vis[i] = 0; 
            for(int j = 0; j < cha.size(); j++) b[cha[j]] = -1;
        }
    }
}
int main() {
    //freopen("ex_a2.in", "r", stdin);
    memset(b, -1, sizeof(b));
    t = read(); n = read();
    for(int i = 0; i < t; i++) x[i] = read();
    for(int i = 0; i < t; i++) y[i] = read();
    for(int i = 0; i < t; i++) {
        int ax = (x[i] + i) % n, pa = a[ax] + (i / n) % n;
        v[ax].push_back((node){x[i], i});
    }
    dfs(0);
    return 0;
}