自动搬运

查看原文

来自洛谷，原作者为

	oscar **

搬运于2025-08-24 21:48:48，当前版本为作者最后更新于2017-09-08 22:04:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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