QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #781313 | #9802. Light Up the Grid | xcxc82 | WA | 63ms | 24080kb | C++23 | 1.6kb | 2024-11-25 15:41:20 | 2024-11-25 15:41:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = (1<<16)+10;
int ans;
int tag[10] = {0,1,2,4,8,3,12,5,10,15};
int f[MAXN][20];//计算答案
int vis[MAXN][20];
int T,a1,a2,a3,a4;
void dfs(int S,int T) {//当前状态为S，异或值为T时的最优解
ans++;
vis[S][T] = 1;
if (S==(1<<16)-1) {
f[S][T] = 0;
return;
}
for (int i=1;i<=9;i++) {
int now = tag[i]^T;
int w = 0;
int pos = (15^now);
int Snxt = S;
if (i<=4) w = a1;
else if (i<=6) w = a2;
else if (i<=8) w = a3;
else w = a4;
if ((S&(1<<pos))==0) Snxt|=(1<<pos);
if (!vis[Snxt][now]) dfs(Snxt,now);
f[S][T] = min(f[S][T],f[Snxt][now]+w);
}
}
signed main(){
memset(f,0x3f,sizeof(f));
cin>>T>>a1>>a2>>a3>>a4;
for (int i=1;i<=16;i++) {
for (int j=0;j<(1<<16);j++) {
if (__builtin_popcount(j)!=i) continue;
for (int k=0;k<15;k++) {
if (!vis[j][k]) dfs(j,k);
}
}
}
//cout<<ans<<endl;
while (T--) {//1次单 1次行 2次列 一次全
int m;
cin>>m;
int S = (1<<16)-1;
for (int i=1;i<=m;i++) {
char a,b,c,d;
cin>>a>>b>>c>>d;
int now = 0;
if (a=='1') now++;
if (b=='1') now+=2;
if (c=='1') now+=4;
if (d=='1') now+=8;
S ^= (1<<now);
}
cout<<f[S][0]<<endl;
}
}
/*
2 1000 100 10 1
4
10
00
01
00
00
10
00
01
1
11
11
*/
详细
Test #1:
score: 100
Accepted
time: 34ms
memory: 24076kb
input:
2 1000 100 10 1 4 10 00 01 00 00 10 00 01 1 11 11
output:
1121 2
result:
ok 2 number(s): "1121 2"
Test #2:
score: 0
Accepted
time: 47ms
memory: 24076kb
input:
2 1 1 1 1 4 10 00 01 00 00 10 00 01 1 11 11
output:
5 2
result:
ok 2 number(s): "5 2"
Test #3:
score: 0
Accepted
time: 43ms
memory: 24080kb
input:
1 1000000 1000000 1000000 1000000 1 11 11
output:
2000000
result:
ok 1 number(s): "2000000"
Test #4:
score: -100
Wrong Answer
time: 63ms
memory: 24040kb
input:
10000 8 2 7 8 8 00 01 00 11 00 10 11 11 10 10 01 10 01 00 10 11 8 11 01 11 00 01 10 11 11 00 01 01 01 01 00 11 10 9 00 00 01 01 10 11 00 01 11 10 11 00 11 11 00 11 01 10 9 11 11 10 00 11 00 11 01 00 10 01 11 00 01 01 01 10 01 11 00 01 01 01 10 10 00 11 11 11 11 10 ...
output:
34 32 36 36 40 36 42 38 40 41 36 44 34 37 37 32 29 39 39 40 38 39 44 37 29 37 38 38 34 34 32 41 34 36 41 40 44 34 37 34 29 36 39 40 42 35 40 37 41 39 41 33 40 41 36 41 43 40 41 34 42 39 38 33 34 38 38 37 42 40 34 36 28 34 32 38 36 40 39 37 36 38 34 34 34 34 42 40 38 38 44 40 37 40 38 29 36 40 39 34 ...
result:
wrong answer 27th numbers differ - expected: '37', found: '38'