P3500 [poi2010]tes intelligence test (two points & offline)

P3500 [POI2010]TES-Intelligence Test( Two points & offline )

Law 1

vector Save the corresponding position of each number .

Then for each position of each query string , Two points to find the minimum >$last$ Of . In fact, the essence of sequential automata is to find the next smallest position , It's just that sequential automata limits the size of the character set .

Time complexity ：$O(Tmlogm)$

#include <cstdio>
#include <vector>
using namespace std;
int poi;
bool yes;
vector <int> a[1000010];
int b[1000010];
int dd(int now,int l,int r)
{
    
    int ans=-1;
    while (l<=r)
    {
    
        int m=(l+r)/2;
        if (a[now][m]>poi)
        {
    
            ans=a[now][m];
            yes=true;
            r=m-1;
        }
        else
            l=m+1;
    }
    return ans;
}
int main()
{
    
    int m;
    scanf("%d",&m);
    for (int i=1;i<=m;i++)
    {
    
        int t;
        scanf("%d",&t);
        a[t].push_back(i);
    }
    int T;
    scanf("%d",&T);
    while (T--)
    {
    
        bool flag=true;
        int n;
        poi=0;
        scanf("%d",&n);
        for (int j=1;j<=n;j++)
            scanf("%d",&b[j]);
        for (int j=1;j<=n;j++)
        {
    
            int now=b[j];
            int l=0,r=a[now].size();
            if (r==0)
            {
    
                flag=false;
                break;
            }
            r--;
            yes=false;
            int ttt=dd(now,l,r);
            if (yes)
                poi=ttt;
            else
            {
    
                flag=false;
                break;
            }
        }
        if (flag)
            printf("TAK\n");
        else
            printf("NIE\n");
    }
    return 0;
}

Law 2

You can do it offline , Consider building drawings , First connect the corresponding number with the first position of the query string .

Then traverse the position of the template string in order $i$ , Edge the next position .

Pay attention to remove the front edge , direct $h[i]=0$.

Time complexity ：$O(n+\sum m)$

// SeptEtavioxy
#include<cstdio>
#include<cctype>
#include<cstring>
#define re register
#define ll long long
#define il inline
#define rep(i,s,t) for(re int i=(s);i<=(t);i++)
#define pt(ch) putchar(ch)
#define pti(x) printf("%d",x)
using namespace std;
// c_ints
il int ci(){
    
	re char ch;
	while(!isdigit(ch=getchar()));
	re int x= ch^'0';
	while(isdigit(ch=getchar()))x=(x*10)+(ch^'0');
	return x;
}
enum{
    N=1000024};

class node{
    
public:
	int nxt,pos;//pos Is the sequence to which it belongs id
}bow[N];
int tot;
int head[N];
il void add(int x,int y){
    
	bow[++tot].nxt= head[x];
	bow[tot].pos= y;
	head[x]= tot;
}// Adjacency list ,bow[x] Representation number x Ask on 

int a[N];
int k[N],*p[N];
int d[N*2],*last=d;// Pointer storage 

int cur[N];// Ask the current position of the sequence 
bool ok[N];// answer 

int main(){
    
	
    int m= ci();
	rep(i,1,m) a[i]= ci();
	
    int n= ci();
	rep(i,1,n){
    
		k[i]= ci();
		//p[i]= last;
		p[i] = new int[k[i]+1];
		rep(j,1,k[i]) p[i][j]= ci();
		//last+= k[i]+1;
		add(p[i][1],i);// Add first item 
	}
    
	rep(i,1,m){
    
		int u= a[i];
		int j= head[u];
		head[u]= 0;// Clear adjacency table 
		for(;j;j=bow[j].nxt){
    
			int t= bow[j].pos;
			if( ++cur[t] == k[t] ) ok[t]= 1;// A successful match 
			else add(p[t][cur[t]+1],t);// Join next 
		}
	}
    
	rep(i,1,n) puts(ok[i]?"TAK":"NIE");
    
	return 0;
	//end Noodles ()
}