QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#781269 | #9802. Light Up the Grid | xcxc82 | WA | 37ms | 24172kb | C++23 | 1.5kb | 2024-11-25 15:27:46 | 2024-11-25 15:27:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = (1<<16);
struct Node {
int node,T,ans;
bool operator < (const Node x) const {
return ans > x.ans;
}
};
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=0;i<(1<<16);i++) {
if (!vis[i][0]) dfs(i,0);
}
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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 27ms
memory: 24056kb
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: 23ms
memory: 24112kb
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: 29ms
memory: 24116kb
input:
1 1000000 1000000 1000000 1000000 1 11 11
output:
2000000
result:
ok 1 number(s): "2000000"
Test #4:
score: -100
Wrong Answer
time: 37ms
memory: 24172kb
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 38 38 45 29 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 40 40 37 40 38 29 36 40 39 34 ...
result:
wrong answer 27th numbers differ - expected: '37', found: '38'