c/c++语言开发共享ZROJ#397. 【18提高7】模仿游戏(爆搜)

题意 “题目链接” Sol 考试的时候调了1.5h没调出来我真是菜爆了。。。 读完题目后不难发现,每次约束的条件相当于是$b[((x[i] + i) % N + (i / N) % N) % N] = y[i]$ 因为数据随机,暴力搜$a_i$就行了。搜索的时候结合给出的信息判断一下是否合法。 cp …


题意

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; }
www.ctvol.com true Article c/c++语言开发共享ZROJ#397. 【18提高7】模仿游戏(爆搜)

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。

ctvol管理联系方式QQ:251552304

本文章地址:https://www.ctvol.com/c-cdevelopment/606914.html

(0)
上一篇 2021年5月14日 上午7:18
下一篇 2021年5月14日 上午7:21

精彩推荐