首页 > 代码库 > 序列 xulie （2017青岛）

序列 xulie （2017青岛）

2024-09-26 05:42:02   374人阅读

技术分享

 

这是三道题中最水的一道

就是判断一个序列是否是另一个序列的子序列

这是o（nm）的算法

但时间复杂度其实由∑L决定

可以看到数据给出的∑L<=100000

时恰好不超时的

可作正解

（又愚蠢的人想过用KMP做，但KMP是处理字符子串的，哎，愚蠢）

（*想知道KMP是什么吗？自己百度去吧%%%有亮点）

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int a[1000005];
 5 int n,m,l,c;
 6 int s,t;
 7 int main(){
 8     scanf("%d",&n);
 9     for(int i=1;i<=n;i++){
10         scanf("%d",&a[i]);
11     }
12     scanf("%d",&m);
13     for(int i=1;i<=m;i++){
14         scanf("%d",&l);
15         s=1;
16         for(int j=1;j<=l;j++){
17             scanf("%d",&c);    
18             for(;s<=n;s++){
19                 if(a[s]==c){
20                     break;
21                 }
22             }
23             if(j==l&&s<=n){
24                 printf("TAK\n");
25             }
26             if(j==l&&s>n){
27                 printf("NIE\n");
28             }
29             s++;
30         }
31     }
32     return 0;
33 }

 

序列 xulie （2017青岛）


联系
我们