Codeforces Round #658 (Div. 2) A. Common Subsequence
程序员文章站
2022-04-30 22:49:38
...
A. Common Subsequence
题目链接-A. Common Subsequence
题目大意
给出两个数组,请你找出二者最短的公共子序列
解题思路
- 如果两个数组中没有一样的数字,那说明没有公共子序列,直接输出
NO
即可 - 如果有相同的数字,最短公共子序列肯定为,任意输出一个相同的数字即可
- 具体操作见代码
附上代码
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x &(-x))
#define endl '\n'
using namespace std;
const int INF=0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const double PI=acos(-1.0);
const double e=exp(1.0);
const double eps=1e-10;
const int M=1e9+7;
const int N=2e5+10;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
int a[N],b[N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--){
int ass=0;
map<int,int> mp;
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
mp[a[i]]=i;
}
for(int i=1;i<=m;i++){
cin>>b[i];
if(mp[b[i]]){
ass=b[i];
}
}
if(!ass) cout<<"NO"<<endl;
else cout<<"YES"<<endl<<1<<" "<<ass<<endl;
}
return 0;
}
推荐阅读
-
Codeforces Round #655 (Div. 2) A. Omkar and Completion
-
Codeforces Round #649 (Div. 2)-B. Most socially-distanced subsequence(思维)
-
Codeforces Round #659 (Div. 2) A. Common Prefixes(字符串,思维)
-
Codeforces Round #658 (Div. 2)C1. Prefix Flip (Easy Version)(贪心)
-
Codeforces Round #658 (Div. 2) (C1、C2)
-
Codeforces Round #648 (Div. 2) E、Maximum Subsequence Value
-
Codeforces Round #658 (Div. 2) B. Sequential Nim
-
Codeforces Round #658 (Div. 2) D. Unmerge(dp,01背包)
-
Educational Codeforces Round 93 (Rated for Div. 2) A. Bad Triangle
-
Codeforces Round #664 (Div. 2) A. Boboniu Likes to Color Balls