有两个长度为 N 的序列 A 和 B，在 A 和 B 中各任取一个数可以得到 N^2 个和，求这N^2 个和中最小的 N个。
第一行输入一个正整数N；第二行N个整数Ai 且Ai≤10^9；第三行N个整数Bi，
且Bi≤10^9
输出仅一行，包含 n 个整数，从小到大输出这 N个最小的和，相邻数字之间用
空格隔开。
5
1 3 2 4 5
6 3 4 1 7
2 3 4 4 5
【数据规模】 对于 100%的数据，满足 1≤N≤100000。
分类标签 Tags 点此展开
最暴力的方法：我们可以把所有情况都算出来，再排序，很显然，空间和时间都会爆。
网上的思路：（其实不是很明白这样算出来的i*j-1的前n个解就是最优解）
想办法把一些一定不可能的状态给消除掉。
首先还是给A，B排序，同样还是这个表：
| B\A | 1 | 2 | … | i | … | n |
|---|---|---|---|---|---|---|
| 1 | ||||||
| 2 | ||||||
| … | ||||||
| i | ||||||
| … | ||||||
| n |
观察到，对于(i,j)这个点，比它小的元素至少有i×j−1个。
由于我们要求前N小的，所以满足要求的点至少要满足i×j−1<n即i×j≤n。
这样我们可以把点的个数缩小至
时间复杂度：O(nlog2n)
空间复杂度：O(nlogn)
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define N 100010
int n,cnt,a[N],b[N];
priority_queue<int,vector<int>,greater<int> >que;
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",a+i);
for(int i=;i<=n;i++) scanf("%d",b+i);
sort(a+,a+n+);
sort(b+,b+n+);
for(int i=;i<=n;i++){
for(int j=;i*j<=n;j++){
que.push(a[i]+b[j]);
}
}
for(int i=;i<=n;i++){
printf("%d ",que.top());que.pop();
}
return ;
}
堆是一种常用的数据结构。二叉堆是一个特殊的二叉树，他的父亲节点比两个儿子节点要大，且他的左右子树也是二叉堆。现在输入一颗树(用二叉树的数组表示，即a[i]的左儿子与右儿子分别为a[2i],a[2i+1])，要求判断他是否是一个堆。
一个整数N，表示结点数。
第二行N个整数，表示每个结点代表的数字
如果是，输出‘Yes’
否则输出‘No’
5
1 2 3 4 5
No
1<N<100
数字在2^31以内
分类标签 Tags 点此展开
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
#define N 1000010
int n,a[N];
void query(int t){
if(t>=n){
printf("Yes\n");exit();
}
if(a[t<<]>a[t]||a[t<<|]>a[t]){
printf("No\n");exit();
}
if(a[t<<]) query(t<<);
if(a[t<<|]) query(t<<|);
return ;
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",a+i);
query();
return ;
}
#include<cstdio>
#include<iostream>
using namespace std;
int n,a[];
int main(){
cin>>n;
for(int i=;i<=n;i++) cin>>a[i];
for(int i=;i<=n/;i++)
if(a[i]<=a[i<<]||a[i]<=a[i<<|]){printf("No\n");goto out;}
printf("Yes\n");
out:return ;
}
S 城现有两座*，一共关押着N 名罪犯，编号分别为1~N。他们之间的关系自然也极
不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨
气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之
间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一*，他们俩之间会发生摩擦，并
造成影响力为c 的冲突事件。
每年年末，警察局会将本年内*中的所有冲突事件按影响力从大到小排成一个列表，
然后上报到S 城Z 市长那里。公务繁忙的Z 市长只会去看列表中的第一个事件的影响力，
如果影响很坏，他就会考虑撤换警察局长。
在详细考察了N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在
两座*内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只
要处于同一*内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那
么，应如何分配罪犯，才能使Z 市长看到的那个冲突事件的影响力最小？这个最小值是少？
第一行为两个正整数N 和M，分别表示罪犯的数目以及存在仇恨的罪犯对数。
接下来的M 行每行为三个正整数aj，bj，cj，表示aj 号和bj 号罪犯之间存在仇恨，其怨气值为cj。数据保证，且每对罪犯组合只出现一次。
共1 行，为Z 市长看到的那个冲突事件的影响力。如果本年内*
中未发生任何冲突事件，请输出0。
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
3512
罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件
影响力是3512（由2 号和3 号罪犯引发）。其他任何分法都不会比这个分法更优。
【数据范围】
对于30%的数据有N≤ 15。
对于70%的数据有N≤ 2000，M≤ 50000。
对于100%的数据有N≤ 20000，M≤ 100000。
分类标签 Tags 点此展开
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define maxn 150100
struct node{
int x,y,v;
}e[maxn];
int fa[maxn];
int cmp(node a,node b){
return a.v>b.v;
}
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){
int n,m,u,v;
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].v);
for(int i=;i<=*n;i++) fa[i]=i;
sort(e+,e+m+,cmp);
for(int i=;i<=m;i++){
int fx=find(e[i].x);
int fy=find(e[i].y);
if(fx==fy){printf("%d\n",e[i].v);return ;}
fa[fx]=find(e[i].y+n);
fa[fy]=find(e[i].x+n);
}
printf("0\n");
return ;
}
动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A吃B，B吃C，C吃A。
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是“1 X Y”，表示X和Y是同类。
第二种说法是“2 X Y”，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。
你的任务是根据给定的N（1<=N<=50,000）和K句话（0<=K<=100,000），输出假话的总数。
第一行是两个整数N和K，以一个空格分隔。
以下K行每行是三个正整数D，X，Y，两数之间用一个空格隔开，其中 D 表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。
只有一个整数，表示假话的数目。
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
3
输入文件
对7句话的分析 100 7
1 101 1 假话
2 1 2 真话
2 2 3 真话
2 3 3 假话
1 1 3 假话
2 3 1 真话
1 5 5 真话
NOI 2001 食物链(eat)
分类标签 Tags 点此展开
#include<cstdio>
int n,k,ans,fa[];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
inline void merge(int x,int y){
fa[find(x)]=find(y);
}
inline bool same(int x,int y){
return find(x)==find(y);
}
int main(){
scanf("%d%d",&n,&k);
for(int i=;i<=n*;i++) fa[i]=i;
for(int i=,d,x,y;i<=k;i++){
scanf("%d%d%d",&d,&x,&y);
if(x>n||y>n){ans++;continue;}
if(d==)
if(same(x,y+n)||same(x,y+n*))ans++;
else merge(x,y),merge(x+n,y+n),merge(x+n*,y+n*);
else
if(same(x,y)||same(x,y+n*)) ans++;
else merge(x,y+n),merge(x+n,y+n*),merge(x+n*,y);
}
printf("%d",ans);
return ;
}
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。 规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。
第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。 以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Ai和Bi具有亲戚关系。 接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。
P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6
Yes
Yes
No
n<=5000,m<=5000,p<=5000
分类标签 Tags 点此展开
#include<cstdio>
using namespace std;
int n,m,k,fa[];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void megre(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy) fa[fy]=fx;
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n;i++) fa[i]=i;
for(int i=,x,y;i<=m;i++){
scanf("%d%d",&x,&y);
megre(x,y);
}
for(int i=,x,y;i<=k;i++){
scanf("%d%d",&x,&y);
printf("%s\n",find(x)==find(y)?"Yes":"No");
}
return ;
}