| 比赛 |
省选2023Day2复现 |
评测结果 |
AAAAAETEEEEWWWWWWWWWWWWWW |
| 题目名称 |
填数游戏 |
最终得分 |
20 |
| 用户昵称 |
flyfree |
运行时间 |
8.594 s |
| 代码语言 |
C++ |
内存使用 |
7.62 MiB |
| 提交时间 |
2025-12-13 11:36:17 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
// #define LOCAL
#define ll long long
#define db double
#define Ciallo true
#define pir pair <ll,ll>
#define fs first
#define sc second
#define MAXN 1000010
inline ll read(){
ll f = 1, num = 0;
char c = getchar();
while(c < '0' || c > '9'){
if(c=='-') f = -1;c = getchar();
}
while(c>='0'&&c<='9') num = num * 10 + c - '0', c = getchar();
return num * f;
}
int siza[MAXN],sizb[MAXN];
int S[MAXN][2], T[MAXN][2];
int n,m;
void solve1(){
int ans = -1;
int all = (1 << n) - 1;
for(int SA = 0;SA <= all; ++ SA){
int ret = n + 1;
for(int SB = 0;SB <= all; ++ SB){
bool flag = Ciallo;
int now = 0;
for(int i = 1;i <= n; ++i){
if((SA & (1 << i - 1)) && siza[i] == 1)flag = false;
if((SB & (1 << i - 1)) && sizb[i] == 1)flag = false;
}
bool vis[11];
for(int i = 1;i <= m; ++i)vis[i] = false;
for(int i = 1;i <= n; ++i){
int X = S[i][(SA & (1 << i - 1)) ? 1 : 0];
int Y = T[i][(SB & (1 << i - 1)) ? 1 : 0];
if(vis[Y]){
flag = false;
break;
}
vis[Y] = Ciallo;
now += (X == Y);
}
// cerr << SA << " " << SB << " " << flag << endl;
if(!flag)continue;
ret = min(ret, now);
}
if(ret == n + 1){
continue;
}
ans = max(ans, ret);
}
cout << ans << endl;
}
void work(){
n = read(),m = read();
for(int i = 1;i <= n; ++i){
siza[i] = read();
for(int j = 0;j < siza[i]; ++j)S[i][j] = read();
}
for(int i = 1;i <= n; ++i){
sizb[i] = read();
for(int j = 0;j < sizb[i]; ++j)T[i][j] = read();
}
if(n <= 10)solve1();
else{
cout << "I can't solve it now\n";
}
}
int main(int argc, char* argv[]){
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
#ifdef FS
freopen(argv[1], "r", stdin);
freopen(argv[2], "w", stdout);
#elif defined(LOCAL)
freopen("w.in", "r", stdin);
freopen("w.out", "w", stdout);
#endif
int T = read();
while(T --)work();
cerr << "Time : " << 1.0 * clock() / CLOCKS_PER_SEC << "s \n";
return 0;
}