题解 CF1382A 【Common Subsequence】

· · 题解

题目大意

给定 a,b 两个序列，求最小公共子串。

分析

有两种方法。\begin{cases} \text{ 1.暴力212ms} \\\text{ 2.桶 272ms} \end{cases}

暴力竟然比桶快！

先说暴力。

正常读入 a 数组。

读入 b 数组时每读入一个数，就暴力枚举 a 数组（这里似乎可以先对 a 进行 sort 接着二分），看看有没有数与之相同。

数据那么小，轻松 \color{#52C41A}\text{AC}。

#include<bits/stdc++.h>
#define FOR(i,j,k)  for(int i=(j);i<=(k);i++)
using namespace std;
int n,m,tc;
int a[1001],x;
bool vis[1001];
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int main()
{
    tc=read();
    while(tc--)
    {
        memset(vis,false,sizeof(vis));
        bool flag=false;
        n=read(),m=read();
        for(int i=1;i<=n;i++)
            a[i]=read(),vis[a[i]]=true;
        for(int i=1;i<=m;i++)
        {
            x=read();
            if(!flag)
            {
                for(int j=1;j<=n;j++)
                    if(a[j]==x)
                    {
                        puts("YES");
                        printf("1 %d\n",x);
                        flag=true;
                        break;
                    }   
            }

        }
        if(!flag)   puts("NO");
    }

    return 0;
}

方法 2

显然，最小公共子串长度要么为 1 要么没有。于是我们考虑运用桶的思想，记录这个数字是否在 a 串中出现，如果当前输入的数在 a 数组中出现，直接输出。

code 
#include<bits/stdc++.h>
#define FOR(i,j,k)  for(int i=(j);i<=(k);i++)
using namespace std;
int n,m,tc;
int a[1001],x;
bool vis[1001];
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int main()
{
    tc=read();
    while(tc--)
    {
        memset(vis,false,sizeof(vis));
        bool flag=false;
        n=read(),m=read();
        for(int i=1;i<=n;i++)
            a[i]=read(),vis[a[i]]=true;
        for(int i=1;i<=m;i++)
        {
            x=read();
            if(vis[x]&&!flag)
            {
                puts("YES");
                printf("1 %d\n",x);
                flag=true;
            }
        }
        if(!flag)   puts("NO");
    }

    return 0;
}