[C++知识库]22/2/4 字典与集合

A - 子集和判断 51Nod - 3202
子集和判断 51Nod - 3202

核心问题：//A是B的子集吗？
查了七八遍才发现，做题的时候把A组和B组的输入看反了。
flag标记变量，有利于最终的输出
m和n的比较，不写也可，写了可以减少一些工作量
有快读：Time(ms), Mem(MB) 125 3
无快读： 453 3.1
有快读，无m和n的比较 140 3.032

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=50010;
int a[N],b[N],c[N],t,m,n,x,flag;
inline int read(){
	int a=0,k=1;
	char ch=233;
	while(ch>'9'||ch<'0'){
		if(ch=='-')
			k=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		a=a*10+ch-'0';
		ch=getchar();
	}
	return a*k;
}
int main(){
	t=read();//groups
	while(t--){
		flag=0;
		int maxn1=0,maxn2=0;
		m=read(),n=read();
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(c,0,sizeof(c));
		for(int i=0;i<m;i++){
			x=read();
			b[x]++;
		}
		for(int i=0;i<n;i++){
			c[i]=read();
			a[c[i]]++;
		}
		if(m<n){//length
			printf("No\n");
			continue;
		}
		for(int i=0;i<n;i++){
			if(b[c[i]]<a[c[i]]){
				flag++;
				break;
			}
		}
		if(flag)	printf("No\n");
			else	printf("Yes\n");
	} 
	return 0;
}

C - 小明爱集合 51Nod - 3058
两个集合长度之和 - 两个集合去重合并后的元素数量 = 相同元素的数量

#include<cstdio>
#include<iostream>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
set<int>a;
int T,n,m,x,l, same,percent;
inline int read(){
	int a=0,k=1;
	char ch=233;
	while(ch>'9'||ch<'0'){
		if(ch=='-')	k=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		a=a*10+ch-'0';
		ch=getchar();
	}
	return a*k;
}
inline void write(int x){
	if(x<0)	
		putchar('-'),x=-x;
	if(x>9)
		write(x/10);
	putchar(x%10+'0');
}
int main(){
	T=read();
	while(T--){
		a.clear();
		n=read(),m=read();
		for(int i=0;i<n+m;i++){
			x=read();
			a.insert(x);
		}
	same=n+m-a.size();
	percent=(same*100/a.size());
	write(percent);
	printf("\n");
	}
	return 0;
}

*输出的百分数为整数，都开int即可
cin和cout会TLE
scanf和printf或者手写快读快写函数都可以

E - 数字去重 51Nod - 3057

#include<cstdio>
#include<iostream>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
set<int>a; 
int n,i,x; 
int main() { 
  cin>>n;
  for(i=1;i<=n;i++) { 
  cin>>x; 
  a.insert(x); 
  }
  set<int>::iterator it; 
  for(it=a.begin();it!=a.end();it++) 
	  printf("%d\n",*it); 
  return 0; 
  }

F - 最近的一对 51Nod - 3059

#include<cstdio>
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
inline int read(){
	int a=0,k=1;
	char ch=233;
	while(ch>'9'||ch<'0'){
		if(ch=='-')
			k=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		a=a*10+ch-'0';
		ch=getchar();
	}
	return a*k;
}	
inline void write(int x){
	if(x<0)
		putchar('-'),x=-x;
	if(x>9)
		write(x/10);
	putchar(x%10+'0');
}
int a[100010];
int n,x,ans,l,r=100010;
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		x=read();
		if(a[x]&&i-a[x]<r-l)
		//小于号确保了相同距离下取下标靠前的数 
			l=a[x],r=i,ans=x;
		a[x]=i;
		//a[x]暂时储存“起点” 
		//length=r-l; 
	}
	if(ans)
		printf("%d\n",ans);
	else
		printf("No\n");	
	return 0;
}