红色警报
战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序，当失去一个城市导致国家被分裂为多个无法连通的区域时，就发出红色警报。注意：若该国本来就不完全连通，是分裂的k个区域，而失去一个城市并不改变其他城市之间的连通性，则不要发出警报。
输入格式：
输入在第一行给出两个整数N（0 < N ≤ 500）和M（≤ 5000），分别为城市个数（于是默认城市从0到N-1编号）和连接两城市的通路条数。随后M行，每行给出一条通路所连接的两个城市的编号，其间以1个空格分隔。在城市信息之后给出被攻占的信息，即一个正整数K和随后的K个被攻占的城市的编号。
注意：输入保证给出的被攻占的城市编号都是合法的且无重复，但并不保证给出的通路没有重复。
输出格式：
对每个被攻占的城市，如果它会改变整个国家的连通性，则输出Red Alert: City k is lost!，其中k是该城市的编号；否则只输出City k is lost.即可。如果该国失去了最后一个城市，则增加一行输出Game Over.。
输入样例：
5 4
0 1
1 3
3 0
0 4
5
1 2 0 4 3
输出样例：
City 1 is lost.
City 2 is lost.
Red Alert: City 0 is lost!
City 4 is lost.
City 3 is lost.
Game Over.
输入一张图，每次去除一个节点，判断图的连通性变化。每次图变化后可利用并查集判断图被分割为几份，以此来输出答案。
#include<bits/stdc++.h>
using namespace std;
int n, m, k, u;
int father[505], vis[505];
struct node{
int a, b;
} road[5005];
//通过并查集查找连通分支数
int count(){
int count = 0;
for (int i = 0; i < n; i++)
if (father[i] == i && vis[i] == 0)
count++;
return count;
}
void init(){
for (int i = 0; i < 505; i++)
father[i] = i;
}
int find(int x){
int t = x;
while (t != father[t]){
t = father[t];
}
return t;
}
void Union(int x, int y){
int fx = find(x);
int fy = find(y);
if (fx != fy)
father[fy] = fx;
}
int main(){
cin >> n >> m;
init();//初始化并查集
for (int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
road[i].a = a;
road[i].b = b;
Union(a, b);//记录节点并合并
}
int sum = count();//记录初始连通性
cin >> k;
for (int t = 0; t < k; t++){
cin >> u;
vis[u] = 1;
init();
for (int i = 0; i < m; i++){
int a = road[i].a;
int b = road[i].b;
if (vis[a] == 0 && vis[b] == 0)//如果某个节点被删除（标记为1），就跳过不合并
Union(a, b);
}
int cur = count();
if (cur <= sum){
printf("City %d is lost.\n", u);
}else{
printf("Red Alert: City %d is lost!\n", u);
}
sum = cur;
}
if (n == k){
printf("Game Over.\n");
}
return 0;
}
列车调度
两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{8，4，2，5，3，9，1，6，7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？
输入格式：
输入第一行给出一个整数N (2 ≤ N ≤10^5)，下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。
输出格式：
在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。
输入样例：
9
8 4 2 5 3 9 1 6 7
输出样例：
4
给出车进入的顺序，判断需要几条平行铁轨才能使之按顺序使出。在平行铁轨上可用于停车，并且可停任意辆，而在平行铁轨上停的车必须是递增的，因为前面的车必定先驶出。题目规定大编号先驶出。先将车分配到平行铁轨，因为车辆是递增的，所以可以保证一定有一个序列可以使之递减驶出。我们需要判断最少需要几个这样的平行序列。此时我们可利用贪心的思想，对于每一辆行驶进来的车，停靠在最接近并且比他大的车的后面，比如：此时已使用两条铁轨，在末尾的分别为9，5 号,此时进来一个1号，理应放在5号后面，因为如果后续来一个8号，则必须放在新的平行铁轨上。
#include<cstdio>
#include<set>
using namespace std;
int main(){
int n,num;
scanf("%d", &n);
set<int> cp;
cp.insert(100009);//初始化一条铁轨
for(int i = 0; i < n; i++){
scanf("%d", &num);
//
if(num < *cp.rbegin()){//rbegin()为集合内最大值，如果大于集合内的所有值，则必须新加一条轨道
//upper_bound(num)为集合内刚好必num大的数的指针
//因为我们只考虑有几条轨道，故只记录末尾的元素，插入后可将上一个数删除， //因此set集合内元素的数量就是答案
cp.erase(*cp.upper_bound(num));
}
cp.insert(num);
}
printf("%d",int(cp.size()));
}
互评成绩
学生互评作业的简单规则是这样定的：每个人的作业会被k个同学评审，得到k个成绩。系统需要去掉一个最高分和一个最低分，将剩下的分数取平均，就得到这个学生的最后成绩。本题就要求你编写这个互评系统的算分模块。
输入格式：
输入第一行给出3个正整数N（3 < N ≤104，学生总数）、k（3 ≤ k ≤ 10，每份作业的评审数）、M（≤ 20，需要输出的学生数）。随后N行，每行给出一份作业得到的k个评审成绩（在区间[0, 100]内），其间以空格分隔。
输出格式：
按非递减顺序输出最后得分最高的M个成绩，保留小数点后3位。分数间有1个空格，行首尾不得有多余空格。
输入样例：
6 5 3
88 90 85 99 60
67 60 80 76 70
90 93 96 99 99
78 65 77 70 72
88 88 88 88 88
55 55 55 55 55
输出样例：
87.667 88.000 96.000
简单的模拟题
#include<bits/stdc++.h>
using namespace std;
int main() {
int n,k,m;
cin>>n>>k>>m;
int i,j;
float sum=0;
float stu[n];
int x;
for(i=0;i<n;i++){
sum=0;
int mx=INT_MIN,mn=INT_MAX;
for(j=0;j<k;j++){
cin>>x;
mx=max(x,mx);
mn=min(x,mn);
sum+=x;
}
sum=sum-mx-mn;
stu[i]=sum/(k-2);
}
sort(stu,stu+n);
for(i=n-m;i<n;i++){
printf("%.3f",stu[i]);
if(i<n-1){
cout<<" ";
}
}
return 0;
}
愿天下有情人都是失散多年的兄妹
呵呵。大家都知道五服以内不得通婚，即两个人最近的共同祖先如果在五代以内（即本人、父母、祖父母、曾祖父母、高祖父母）则不可通婚。本题就请你帮助一对有情人判断一下，他们究竟是否可以成婚？
输入格式：
输入第一行给出一个正整数N（2 ≤ N ≤104），随后N行，每行按以下格式给出一个人的信息：
本人ID 性别 父亲ID 母亲ID
其中ID是5位数字，每人不同；性别M代表男性、F代表女性。如果某人的父亲或母亲已经不可考，则相应的ID位置上标记为-1。
接下来给出一个正整数K，随后K行，每行给出一对有情人的ID，其间以空格分隔。
注意：题目保证两个人是同辈，每人只有一个性别，并且血缘关系网中没有乱伦或隔辈成婚的情况。
输出格式：
对每一对有情人，判断他们的关系是否可以通婚：如果两人是同性，输出Never Mind；如果是异性并且关系出了五服，输出Yes；如果异性关系未出五服，输出No。
输入样例：
24
00001 M 01111 -1
00002 F 02222 03333
00003 M 02222 03333
00004 F 04444 03333
00005 M 04444 05555
00006 F 04444 05555
00007 F 06666 07777
00008 M 06666 07777
00009 M 00001 00002
00010 M 00003 00006
00011 F 00005 00007
00012 F 00008 08888
00013 F 00009 00011
00014 M 00010 09999
00015 M 00010 09999
00016 M 10000 00012
00017 F -1 00012
00018 F 11000 00013
00019 F 11100 00018
00020 F 00015 11110
00021 M 11100 00020
00022 M 00016 -1
00023 M 10012 00017
00024 M 00022 10013
9
00021 00024
00019 00024
00011 00012
00022 00018
00001 00004
00013 00016
00017 00015
00019 00021
00010 00011
输出样例：
Never Mind
Yes
Never Mind
No
Yes
No
Yes
No
No
模拟题，定义一个结构体存储每个人的信息，然后进行dfs递归搜索，判断是否有相同的父母。
ps:题目保证两个人是同辈，每人只有一个性别，并且血缘关系网中没有乱伦或隔辈成婚的情况。故不需要考虑不同深度的人是否一样。
ps2:在记录父母的同时也要记录一下父母的性别，不然有的测试用例不能判断其性别是否相同.
#include<bits/stdc++.h>
int f[100],c;
struct family{
int mnum,fnum;
int sex;
}s[100000];//家庭结构
int check(int x,int y,int c){
if(c > 5 || x == -1 || y == -1)return 1;
if(x == y)return 0;
return check(s[x].fnum,s[y].fnum,c + 1) && check(s[x].mnum,s[y].mnum,c + 1) && check(s[x].fnum,s[y].mnum,c + 1) && check(s[x].mnum,s[y].fnum,c + 1);
}
int main(){
int n,k,a,b,num;
char ch;
scanf("%d",&n);
for(int i = 0;i<100000;i ++)///初始化 所有人及其父母为不可考
s[i].fnum = s[i].mnum = s[i].sex = -1;
for(int i = 0;i < n;i ++){
scanf("%d %c %d %d",&num,&ch,&a,&b);
s[num].mnum = a;
s[num].fnum = b;
if(ch == 'M')s[num].sex = 0;///男
else s[num].sex = 1;///女
if(a != -1)s[a].sex = 0;///记录父亲
if(b != -1)s[b].sex = 1;///记录母亲
}
scanf("%d",&k);
for(int i = 0;i < k;i ++){
scanf("%d %d",&a,&b);
if(s[a].sex == s[b].sex)
printf("Never Mind\n");
else{
if(check(a,b,1)) printf("Yes\n");
else printf("No\n");
}
}
}