I::::::::::::::::：蓝桥侦探（种类并查集）
题目描述
小明是蓝桥王国的侦探。
这天，他接收到一个任务，任务的名字叫分辨是非，具体如下：
蓝桥皇宫的国宝被人偷了，犯罪嫌疑人锁定在 N 个大臣之中，他们的编号分别为 1∼N。
在案发时这 N 个大臣要么在大厅1，要么在大厅2，但具体在哪个大厅他们也不记得了。
审讯完他们之后，小明把他们的提供的信息按顺序记了下来，一共 M条，形式如下：
x y，表示大臣 xx 提供的信息，信息内容为：案发时他和大臣 y不在一个大厅。
小明喜欢按顺序读信息，他会根据信息内容尽可能对案发时大臣的位置进行编排。
他推理得出第一个与先前信息产生矛盾的信息提出者就是偷窃者，但推理的过程已经耗费了他全部的脑力，他筋疲力尽的睡了过去。作为他的侦探助手，请你帮助他找出偷窃者！
输入描述
第 1 行包含两个正整数 N,M，分别表示大臣的数量和口供的数量。
之后的第 2∼M+1 行每行输入两个整数 x,y，表示口供的信息。
1≤N,M≤5×105，1≤x,y≤N。
输出描述
输出仅一行，包含一个正整数，表示偷窃者的编号。
输入输出样例
示例 1
输入
4 5 1 2 1 3 2 3 3 4 1 4
输出
2
运行限制
最大运行时间：1s
最大运行内存: 256M
#include <iostream> using namespace std; int n,m; int ans; int a[10000005]; int find(int x){ if(a[x]==x) return x; return a[x]=find(a[x]); } void jiaru(int x,int y){ int tx=find(x); int ty=find(y); if(tx!=ty){ a[tx]=ty; } } int main(){ cin>>n>>m; for(int i=1;i<=2*n;i++){ a[i]=i; } for(int i=1;i<=m;i++){ int x,y; cin>>x>>y; if(ans){ break; } if(find(x)==find(y)||find(x+n)==find(y+n)){ ans=x; } jiaru(x,y+n); jiaru(y,x+n); } cout<<ans; return 0; }
J::::::::::::::::：最长公共子序列（LCS）
题目描述
给定一个长度为 N 数组 a 和一个长度为 M 的数组 b。
请你求出它们的最长公共子序列长度为多少。
输入描述
输入第一行包含两个整数 N,M，分别表示数组 a 和 b 的长度。
第二行包含 N 个整数 a1,a2,...,an。
第三行包含 M 个整数b1,b2,...,bn。
1≤N,M≤103，1≤ai,bi≤109。
输出描述
输出一行整数表示答案。
输入输出样例
示例 1
输入
5 6 1 2 3 4 5 2 3 2 1 4 5
输出
4
#include <iostream> #include <cmath> using namespace std; long long a[1005]; long long b[1005]; int n,m; long long dp[1005][1005]; int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int j=1;j<=m;j++){ cin>>b[j]; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i]==b[j]){ dp[i][j]=dp[i-1][j-1]+1; }else{ dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } } cout<<dp[n][m]; return 0; }
K::::::::::::::::：123（前缀和）
题目描述
小蓝发现了一个有趣的数列，这个数列的前几项如下：
1,1,2,1,2,3,1,2,3,4,⋯
小蓝发现，这个数列前 11 项是整数 1，接下来 2 项是整数 1 至 2，接下来 3 项是整数 1 至 3，接下来 4 项是整数 1 至 4，依次类推。
小蓝想知道，这个数列中，连续一段的和是多少。
输入描述
输入的第一行包含一个整数 T，表示询问的个数。
接下来 T 行，每行包含一组询问，其中第 ii 行包含两个整数 li 和 ri，表示询问数列中第 li 个数到第 ri 个数的和。
输出描述
输出 T 行，每行包含一个整数表示对应询问的答案。
输入输出样例
示例
输入
3 1 1 1 3 5 8
输出
1 4 8
#include <iostream> using namespace std; int t; long long sum1[1500000]; long long qiuhe(long long x) { return (1+x)*x/2; } long long sum(long long x){ if(x==0) return 0; long long l=0,r=1500000; while(r>=l){ long long mid=(l+r)>>1; if(qiuhe(mid)>x){ r=mid-1; }else{ l=mid+1; } } return sum1[r]+qiuhe(x-qiuhe(r)); } int main(){ cin>>t; long long c,len=0; for(long long i=1;len<=1e12;i++){ sum1[i]=sum1[i-1]+qiuhe(i); len+=i; // c=i; } // cout<<c; c=1414214行 for(int i=0;i<t;i++){ long long l,r; cin>>l>>r; cout<<sum(r)-sum(l-1)<<endl; } return 0; }
L::::::::::::::::：美丽的区间（尺取法）
题目描述
给定一个长度为 n 的序列 a1,a2,⋯,an 和一个常数 S。
对于一个连续区间如果它的区间和大于或等于 S，则称它为美丽的区间。
对于一个美丽的区间，如果其区间长度越短，它就越美丽。
请你从序列中找出最美丽的区间。
输入描述
第一行包含两个整数 n,S，其含义如题所述。
接下来一行包含 n 个整数，分别表示a1,a2,⋯,an。
0≤N≤105，1×ai≤104，1≤S≤108。
输出描述
输出共一行，包含一个整数，表示最美丽的区间的长度。
若不存在任何美丽的区间，则输出 0。
输入输出样例
示例 1
输入
5 6 1 2 3 4 5
输出
2
#include <iostream> using namespace std; int n,s; int a[1000005]; int ans=1e9; int main(){ cin>>n>>s; for(int i=0;i<n;i++){ cin>>a[i]; } int l=0,r=0; int m=0; while(r<n){ if(m<s){ m=m+a[r]; r++; }else if(m>=s){ ans=min(ans,r-l); m=m-a[l]; l++; } } if(ans==1e9){ cout<<0; return 0; } cout<<ans; return 0; }
