题解 P3417 【[POI2005]BANK-Cash Dispenser】
小菜鸟
2019-09-26 16:28:11
作为一道POI的题，其实只有pj的难度。。。
简述题意：
给定n个数字序列。
每一位数字可以展开成任意长度，求有多少长度为4的、这些数字串的公共子序列。
---
显然有一个结论，就是同一个数字选得越靠前越优。
那么对于每一位数字，我们只要记录从它开始往后（包括自身）第一个$0..9$的位置即可。
开一个`next`数组，从后往前扫一遍。
然后枚举所有的四位数，对每一个数字进行判断。
耗时大概$10000 n + \sum t$，绝对可过。
为了防止爆空间，每读入一个数字串就可以判断一次，重用之前的`next`数组。
---
代码
```cpp
#include<cstdio>
const int N=10005;
int n,a[N],next[N][10];
bool invalid[N];
void check(int x)
{
int t[4];
t[0]=x/1000;
t[1]=x/100%10;
t[2]=x/10%10;
t[3]=x%10;
int now=1;
for(int i=0;i<4;++i)
{
if(next[now][t[i]]!=0)now=next[now][t[i]];
else
{
invalid[x]=1;
return;
}
}
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;++i)
{
int len;
scanf("%d",&len);
for(int j=1;j<=len;++j)
{
scanf("%1d",a+j);
}
for(int j=0;j<10;++j)next[len+1][j]=0;
for(int j=len;j>0;--j)
{
for(int k=0;k<10;++k)next[j][k]=next[j+1][k];
next[j][a[j]]=j;
}
for(int i=0;i<10000;++i)
{
check(i);
}
}
int res=0;
for(int i=0;i<10000;++i)res+=!invalid[i];
printf("%d",res);
}
```