题解 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代码见下

#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;
}