QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #781316 | #9802. Light Up the Grid | xcxc82 | WA | 57ms | 24308kb | C++23 | 1.6kb | 2024-11-25 15:41:58 | 2024-11-29 22:52:07 |
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=9;i>=1;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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 43ms
memory: 24236kb
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: 48ms
memory: 24308kb
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: 50ms
memory: 24304kb
input:
1 1000000 1000000 1000000 1000000 1 11 11
output:
2000000
result:
ok 1 number(s): "2000000"
Test #4:
score: -100
Wrong Answer
time: 57ms
memory: 24308kb
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 39 36 40 36 42 42 40 41 36 44 34 37 37 32 29 39 39 40 38 39 44 39 29 37 37 38 34 34 32 45 34 36 41 40 44 34 37 34 29 36 43 44 42 35 39 37 38 38 41 30 41 41 36 41 43 40 41 34 42 43 37 33 34 38 38 37 42 43 34 36 28 34 32 38 36 39 38 37 36 38 34 34 34 34 42 40 38 38 44 40 37 40 38 29 36 40 39 34 ...
result:
wrong answer 3rd numbers differ - expected: '36', found: '39'