QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #686296 | #9463. 基础 ABC 练习题 | Flamire | 0 | 0ms | 0kb | C++17 | 5.6kb | 2024-10-29 10:43:22 | 2024-10-29 10:43:23 |
answer
#include <bits/stdc++.h>
#define uint unsigned int
#define ull unsigned long long
#define TIME chrono::steady_clock::now().time_since_epoch().count()
using namespace std;
int t,n;
const int K=60;
vector<int> S1,S2;
char s[100101];
char W[11]="ABC";
const int B=801;
uint dp[62][62][40000];
bool ok[61][61][61];
int id[61][61][61],nn,tid[61][61];
// bitset<148840000> F;
inline int HSH(int a,int b,int x,int y,int z)
{
if(x+y+z>n)return 0;
return ((n-a)*(n+1)+n-b)*nn+id[x][y][z]+1;
}
ull S,CNT;
int main()
{
//freopen("abc.in","r",stdin);freopen("force4.out","w",stdout);setvbuf(stdout,0,_IONBF,0);
scanf("%d%*d",&t);while(t--)
{
scanf("%d",&n);
scanf("%s",s);S1.clear();for(int i=0;i<=n;++i)if(s[i]=='1')S1.push_back(i);
scanf("%s",s);S2.clear();for(int i=0;i<=n;++i)if(s[i]=='1')S2.push_back(i);
scanf("%s",s+1);
int c2=0;
for(int i=1;i<=3*n;++i)c2+=s[i]=='?';
if(n!=K)
{
puts("-1");
continue;
}
memset(ok,0,sizeof(ok));
for(int x:S1)for(int y:S2)if(x+y<=n)
{
int z=n-x-y;
ok[x][y][z]=1;
}
for(int x=n;~x;--x)for(int y=n;~y;--y)for(int z=n;~z;--z)
{//printf("x:%d y:%d z:%d\n",x,y,z);
if(x<n)ok[x][y][z]|=ok[x+1][y][z];
if(y<n)ok[x][y][z]|=ok[x][y+1][z];
if(z<n)ok[x][y][z]|=ok[x][y][z+1];
}
nn=0;
for(int x=0;x<=n;++x)for(int y=0;x+y<=n;++y)for(int z=0;x+y+z<=n;++z)id[x][y][z]=nn++;
for(int x=0;x<=n;++x)for(int y=0;x+y<=n;++y)tid[x][y]=id[x][y][0];
// printf("nn:%d\n",nn);
// dp[HSH(0,0,0,0,0)]=1;//F[HSH(0,0,0,0,0)]=1;
dp[0][0][0]=1;
// int CNT=0;
for(int i=0;i<3*n;++i)
{
char ch=s[i+1];
for(int a=min(i,n);~a;--a)
{
for(int b=min(i-a,n);~b;--b)
{
int c=i-a-b,tt=max(0,c-b);
if(c>n)continue;
if(ch=='?')
{
// S=TIME;
for(int x=max(0,a+1-c);x<=a;++x)
{
// for(int y=min(b,n-x);y>=max(0,b-a);--y)
for(int y=max(0,b-a),ii=tid[x][y];y<=min(n-x,b);ii+=n-x-y+1,++y)
{
// int ii=tid[x][y];
for(int z=ii+min(c,n-x-y);z>=ii+tt;--z)
{
dp[a+1][b][z]+=dp[a][b][z];
}
}
}
// CNT+=TIME-S;
int x=max(0,a-c);
if(x<max(0,a-c+1))
{
for(int y=max(0,b-a);y<=min(n-x-1,b);++y)
{
for(int z=min(c,n-x-1-y);z>=tt;--z)
{
dp[a+1][b][id[x+1][y][z]]+=dp[a][b][id[x][y][z]];
}
}
}
for(int x=max(0,a-c);x<=a;++x)
{
for(int y=max(0,b-a+1);y<=min(n-x,b);++y)
{
int ii=tid[x][y];
for(int z=ii+min(c,n-x-y);z>=ii+tt;--z)
{
dp[a][b+1][z]+=dp[a][b][z];
}
}
}
int y=max(0,b-a);
if(y<max(0,b-a+1))
{
for(int x=max(0,a-c);x<=a;++x)
{
for(int z=min(c,n-x-y-1);z>=tt;--z)
{
dp[a][b+1][id[x][y+1][z]]+=dp[a][b][id[x][y][z]];
}
}
}
for(int x=max(0,a-c);x<=a;++x)
{
// for(int y=min(b,n-x);y>=max(0,b-a);--y)
for(int y=max(0,b-a);y<=min(n-x,b);++y)
{
int z=max(0,c-b);
if(z<max(0,c-b+1)&&z<=c&&x+y+z+1<=n)
{
dp[a][b][id[x][y][z+1]]+=dp[a][b][id[x][y][z]];
dp[a][b][id[x][y][z]]=0;
}
}
}
}
else
{
// for(int x=a;x>=max(0,a-c);--x)
if(ch!='B'&&ch!='C')
{
for(int x=max(0,a+1-c);x<=a;++x)
{
// for(int y=min(b,n-x);y>=max(0,b-a);--y)
for(int y=max(0,b-a),ii=tid[x][y];y<=min(n-x,b);ii+=n-x-y+1,++y)
{
// int ii=tid[x][y];
for(int z=ii+min(c,n-x-y);z>=ii+tt;--z)
{
dp[a+1][b][z]+=dp[a][b][z];
}
}
}
// CNT+=TIME-S;
int x=max(0,a-c);
if(x<max(0,a-c+1))
{
for(int y=max(0,b-a);y<=min(n-x-1,b);++y)
{
for(int z=min(c,n-x-1-y);z>=tt;--z)
{
dp[a+1][b][id[x+1][y][z]]+=dp[a][b][id[x][y][z]];
}
}
}
}
if(ch!='C'&&ch!='A')
{
for(int x=max(0,a-c);x<=a;++x)
{
for(int y=max(0,b-a+1);y<=min(n-x,b);++y)
{
int ii=tid[x][y];
for(int z=ii+min(c,n-x-y);z>=ii+tt;--z)
{
dp[a][b+1][z]+=dp[a][b][z];
}
}
}
int y=max(0,b-a);
if(y<max(0,b-a+1))
{
for(int x=max(0,a-c);x<=a;++x)
{
for(int z=min(c,n-x-y-1);z>=tt;--z)
{
dp[a][b+1][id[x][y+1][z]]+=dp[a][b][id[x][y][z]];
}
}
}
}
if(ch=='A'||ch=='B')
{
for(int x=max(0,a-c);x<=a;++x)
{
// for(int y=min(b,n-x);y>=max(0,b-a);--y)
for(int y=max(0,b-a);y<=min(n-x,b);++y)
{
for(int z=min(c,n-x-y);z>=tt;--z)
{
dp[a][b][id[x][y][z]]=0;
}
}
}
}
else
{
for(int x=max(0,a-c);x<=a;++x)
{
// for(int y=min(b,n-x);y>=max(0,b-a);--y)
for(int y=max(0,b-a);y<=min(n-x,b);++y)
{
int z=max(0,c-b);
if(z<max(0,c-b+1)&&z<=c&&x+y+z+1<=n)
{
dp[a][b][id[x][y][z+1]]+=dp[a][b][id[x][y][z]];
dp[a][b][id[x][y][z]]=0;
}
}
}
}
}
}
}
}
// printf("CNT:%d\n",CNT);
uint ans=0;
for(int x=0;x<=n;++x)for(int y=0;x+y<=n;++y)for(int z=0;x+y+z<=n;++z)ans+=dp[n][n][id[x][y][z]]*ok[x][y][z];
printf("%u\n",ans);
//printf("CNT:%.9lfs\n",CNT/1e9);
}
fclose(stdin);fclose(stdout);return 0;
}
详细
Subtask #1:
score: 0
Memory Limit Exceeded
Test #1:
score: 0
Memory Limit Exceeded
input:
60 1 1 11 11 ABC 2 111 111 CABABC 3 1111 1111 CAABBCBAC 4 11111 11111 BACBBACBACAC 5 111111 111111 CABCCBBAABCCBAA 6 1111111 1111111 ABABABCACBCBCCACBA 7 11111111 11111111 BCAABACBBCBBABCCAACAC 8 111111111 111111111 CCBCBBBCAABCBCAAAAACBCBA 9 1111111111 1111111111 CCCCACABCBABAABCCAABABBCBBA 10 1111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Memory Limit Exceeded
Test #22:
score: 0
Memory Limit Exceeded
input:
60 3 1 11 11 ??? 2 111 111 ?????? 3 1111 1111 ????????? 4 11111 11111 ???????????? 5 111111 111111 ??????????????? 6 1111111 1111111 ?????????????????? 7 11111111 11111111 ????????????????????? 8 111111111 111111111 ???????????????????????? 9 1111111111 1111111111 ??????????????????????????? 10 1111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2103642368
result:
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%