题解 P3417 【[POI2005]BANK-Cash Dispenser】

【POI补全计划#1-POI2005 BAN】 题意花了半个小时才理解。。可能是我语文太差了 为了防止大家理解不了，我来几句话描述一下 定义一串数字的位置序列是将连续的相同数字只留一个后的结果 举例：2333的位置序列为23,552992999的位置序列为52929 给定 $ n $ 个位置序列( $ n \leq 1000 $,序列长度 $ \leq 10000 $ )， 求十进制4位数的个数，使得该密码的位置序列是每个给定位置序列的子串（可以不连续） 然后解释一下样例 $ n = 2 $ 给出的位置序列为123和234 找出公共部分为23 那么可能的4位数就为2222，2223，2233，2333，3333，共5种 --------------题解分割线--------------- 考虑每个四位数，只需要判断它的位置序列是不是所有给定位置序列的子串 用10个队列预处理出 “给定的位置序列的第 $ k $ 位（含第 $ k $ 位）后第一次出现数字 $ i $ 的位置，若不存在则为 $ -1 $ ” 的信息， 记录在NEXT[10][1000010]数组里 这样就可以 $ O(1) $ 查询一个不超过4位的位置序列是否是给定的位置序列的子串了 只需要对于每个输入位置序列标记一下不满足条件的4位数， 最后统计没有标记的4位数个数就好了 时间复杂度 $ O( \sum{t} * 10 + 10000 * n ) $ 具体实现可能需要卡常，不过我没卡常就过了 AC代码见下 ```cpp #include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; int NEXT[10][10010]; queue<int> num[10]; char buf[23333]; int ok[10000]; int main() { for(int i=0;i<10000;i++)ok[i]=true; int n,tmp; scanf("%d",&n); for(int t=1;t<=n;t++) { scanf("%d %s",&tmp,buf); int len=strlen(buf); for(int i=0;i<len;i++) { num[buf[i]-'0'].push(i); } for(int i=0;i<len;i++) { for(int k=0;k<10;k++) { if(num[k].empty())NEXT[k][i]=-1; else NEXT[k][i]=num[k].front(); //cout<<NEXT[k][i]<<' '; } num[buf[i]-'0'].pop(); //cout<<endl; } int i,j,k,l; for(int r=0;r<10000;r++) { if(ok[r]) { i=r/1000,j=r/100-i*10,k=r/10-i*100-j*10,l=r%10; //cout<<i<<j<<k<<l<<endl; if(NEXT[i][0]==-1||NEXT[j][NEXT[i][0]]==-1||NEXT[k][NEXT[j][NEXT[i][0]]]==-1||NEXT[l][NEXT[k][NEXT[j][NEXT[i][0]]]]==-1) ok[r]=false; } } } int ans=0; for(int i=0;i<10000;i++) if(ok[i]) ++ans; printf("%d\n",ans); return 0; } ```