1.lpy 的魔法农场
Description
有 n 个人在 lpy 的农场里面工作。员工从 1 到 n 编号。每一个人种一种蘑菇。刚开始每一个人在自己的田地负责自己的蘑菇，这样的话公司里面就有 n 种蘑菇。
Lpy 种变异的蘑菇，变异蘑菇需要许多普通蘑菇通过魔法合成，blong(x) 表示 x 这个人所在的部门。有以下两种合成操作：
魔法合成 blong(x) 和 blong(y)。 x 和 y (1≤x,y≤n)是员工编号。如果 blong(x) 和 blong(y)是种的同一种蘑菇，那么就不操作。
魔法合成 blong(x),blong(x+1),...,blong(y)，x 和 y (1≤x≤y≤n)是员工编号。
有一些查询操作，查询员工 x 和 y (1≤x,y≤n)是否种同一种蘑菇。
Input
单组测试数据。
第一行有两个整数 n 和 q (1≤n≤200000, 1≤q≤500000)表示员工的数目和操作数目。接下来 q 行，每行的格式是 type x y。type∈{1，2，3}。如果 type=1 或者 type=2，那么表示第一种或者第二种魔法合成操作。如果 type=3，表示查询员工 x 和 y 是否种同一种蘑菇。
Output
对于第三种查询，如果种同一种蘑菇输出 YES，否则输出 NO。
Example
Input
8 6
3 2 5
1 2 5
3 2 5
2 4 7
2 1 2
3 1 7
Output
NO
YES
YES
题目大整容！！！
51Nod 1525 重组公司
题目来源： CodeForces
基准时间限制：1 秒 空间限制：131072 KB 分值: 80 难度：5级算法题
Description
有n个人在公司里面工作。员工从1到n编号。每一个人属于一个部门。刚开始每一个人在自己的部门负责自己的项目，这样的话公司里面就有n个部门。
然而，公司内部出现了危机，需要合并一些部门，以提高工作效率。team(person) 表示person这个人所在的部门。有以下两种合并操作：
1. 合并 team(x) 和 team(y)。 x和 y (1≤x,y≤n)是员工编号。如果team(x) 和 team(y)是同一个部门，那么就不操作。
2. 合并team(x),team(x+1),...,team(y)，x 和 y (1≤x≤y≤n)是员工编号。
有一些查询操作，查询员工x 和 y (1≤x,y≤n)是否属于同一部门。
Input
单组测试数据。
第一行有两个整数n 和 q (1≤n≤200000, 1≤q≤500000)表示员工的数目和操作数目。
接下来q行，每行的格式是type x y。type∈{1，2，3}。如果type=1 或者 type=2，那么表示第一种或者第二种合并操作。如果type=3，表示查询员工x和y是否属于同一部门。
Output
对于第三种查询，如果属于同一部门输出YES，否则输出NO。
Input示例
样例输入1
8 6
3 2 5
1 2 5
3 2 5
2 4 7
2 1 2
3 1 7
Output示例
样例输出1
NO
YES
YES
思路：
详解博客：
xxy开讲了
考场裸写并查集，TLE！！！
上代码：
#include
#define M 200033
using namespace std;
int n,q,x,y,f【M】,near【M】,type;
int reads() {
int x=0;
char c=getchar();
while(c[span style="color: rgba(128, 0, 0, 1)">'0'||c>'9') c=getchar();
while(c>='0' c<='9') x=x*10+c-'0',c=getchar();
return x;
}
inline int find(int x) {
if(f【x】!=x) f【x】=find(f【x】);
return f【x】;
}
inline int unionn(int a,int b) {
int x1=find(a), x2=find(b);
if(x1!=x2)
f【x1】=x2;
}
inline void qj() {
int step,r=y;
while(r>=x (step=near【r】)>=x) {
//unionn(r,step);
f【find(step)】=f【find(r)】;
near【r】=near【step】;
//t在i前面，i与t合并后，i到t之间的全都合并了，i之前的第一个没合并的就是t之前的第一个没合并的
r=step;
}
}
int main() {
n=reads();
q=reads();
for(int i=1; i<=n; i++) f【i】=i,near【i】=i-1;
for(int i=1; i<=q; i++) {
type=reads();
x=reads();y=reads();
if(type == 1) unionn(x,y);
if(type == 2) qj();
if(type == 3) {
if(find(x) == find(y)) puts("YES\n");
else puts("NO\n");
}
}
return 0;
}
2.Hkd 打 magic mouse
Description
hkd 最近迷上了打 magic mouse 游戏。
magic mouse 游戏是一项需要反应速度和敏捷判断力的游戏。游戏开始时，会在地板上一下子冒出很多magic mouse 来，然后等 hkd 用榔头去敲击这些 magic mouse，每个 magic mouse 被敲击后，将会增加相应的游戏分值。问题是这些 magic mouse 不会傻傻地等你去敲击，它总会在冒出一会时间后又钻到地板下面去（而且再也不上来），每个 magic mouse 冒出后停留的时间可能是不同的，而且每个 magic mouse 被敲击后增加的游戏分值也可能是不同，为了胜出，hkd 就必须根据每个 magic mouse 的特性，有选择地尽快敲击一些 magic mouse，使得总的得分最大。
这个极具挑战性的游戏 hkd 特别喜欢，最近他经常在星期天上午玩这个游戏，慢慢地他不但敲击速度越来越快（敲击每个 magic mouse 所需要的耗时是 1 秒），而且他还发现了游戏的一些特征，那就是每次游戏重新开始后，某个 magic mouse 冒出来后停留的时间都是固定的，而且他记录了每个 magic mouse被敲击后将会增加的分值。于是，他在每次游戏开始后总能有次序地选择敲击不同的 magic mouse，保证每次得到最大的总分值。
Input
输入包含 3 行，第一行包含一个整数 n（1<=n<=100）表示有 n 个 magic mouse 从地上冒出来，第二行 n 个用空格分隔的整数表示每个 magic mouse 冒出后停留的时间，第三行 n 个用空格分隔的整数表示每个 magic mouse 被敲击后会增加的分值（<=100）。每行中第 i 个数都表示第 i 个 magic mouse 的信息。
Output
输出只有一行一个整数，表示 hkd 所能获得的最大游戏总分值。
Example
Input
5
5 3 6 1 4
7 9 2 1 5
Output
24
题目大整容！！！
2.1052 地鼠游戏
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题解
题目描述 Description
王钢是一名学习成绩优异的学生，在平时的学习中，他总能利用一切时间认真高效地学习，他不但学习刻苦，而且善于经常总结、完善自己的学习方法，所以他总能在每次考试中得到优异的分数，这一切很大程度上是由于他是一个追求效率的人。
但王钢也是一个喜欢玩的人，平时在学校学习他努力克制自己玩，可在星期天他却会抽一定的时间让自己玩一下，他的爸爸妈妈也比较信任他的学习能力和学习习惯，所以在星期天也不会象其他家长一样对他抓紧，而是允许他在星期天上午可以自由支配时间。
地鼠游戏是一项需要反应速度和敏捷判断力的游戏。游戏开始时，会在地板上一下子冒出很多地鼠来，然后等你用榔头去敲击这些地鼠，每个地鼠被敲击后，将会增加相应的游戏分值。问题是这些地鼠不会傻傻地等你去敲击，它总会在冒出一会时间后又钻到地板下面去（而且再也不上来），每个地鼠冒出后停留的时间可能是不同的，而且每个地鼠被敲击后增加的游戏分值也可能是不同，为了胜出，游戏参与者就必须根据每个地鼠的特性，有选择地尽快敲击一些地鼠，使得总的得分最大。
这个极具挑战性的游戏王钢特别喜欢，最近他经常在星期天上午玩这个游戏，慢慢地他不但敲击速度越来越快（敲击每个地鼠所需要的耗时是1秒），而且他还发现了游戏的一些特征，那就是每次游戏重新开始后，某个地鼠冒出来后停留的时间都是固定的，而且他记录了每个地鼠被敲击后将会增加的分值。于是，他在每次游戏开始后总能有次序地选择敲击不同的地鼠，保证每次得到最大的总分值。
输入描述 Input Description
输入包含3行，第一行包含一个整数n（1=n<=100）表示有n个地鼠从地上冒出来，第二行n个用空格分隔的整数表示每个地鼠冒出后停留的时间，第//代码效果参考：http://www.zidongmutanji.com/bxxx/253096.html<p
三行n个用空格分隔的整数表示每个地鼠被敲击后会增加的分值（<=100）。每行中第i个数都表示第i个地鼠的信息。输出描述 Output Description
输出只有一行一个整数，表示王钢所能获得的最大游戏总分值。
样例输入 Sample Input
5
5 3 6 1 4
7 9 2 1 5
样例输出 Sample Output
24
数据范围及提示 Data Size Hint
分类标签 Tags 点此展开
动态规划 贪心 堆 树结构
思路：
考场思路：纯贪心，按时间排序，如果时间相同按价值排序，那么从时间短的开始打地鼠，打一个其他时间都跟着减1s，如果碰到时间相同的就打价值大的。。。mmp这么大的坑，我当时是脑抽了吗？？如果时间短的很多，价值却都很小，那么时间大价值也大的就不能选。。。orz
AC思路：贪心+并查集 详解见xxy博客 xxy开讲啦
为什么要用并查集呢？？？
xxy是这样解释的：
开始的时候所有的fa【i】=i，表示从第i秒往前第一个可以打地鼠的时间就是第i秒
一秒只能打一个，第3秒已经打了第一只，如果还有一只要在3秒内打完，最晚用第2秒 2333。。。
上代码：
#include
#include
#include
#define M 200033
using namespace std;
int f【M】,n,ans;
struct Mouse{
int t,v;
}mouse【M】;
int find(int x) {
if(f【x】 != x) f【x】=find(f【x】);
return f【x】;
}
int cmp(Mouse a,Mouse b) {
return a.v > b.v;
}
int main() {
scanf("%d",n);
for(int i=1; i<=n; i++) scanf("%d",mouse【i】.t);
//代码效果参考：http://www.zidongmutanji.com/bxxx/531240.html
for(int i=1; i<=n; i++) scanf("%d",mouse【i】.v);sort(mouse+1,mouse+n+1,cmp);
for(int i=1; i<=100; i++) f【i】=i;
for(int i=1; i<=n; i++) {
int no = find(mouse【i】.t);
if(no) {
f【no】=f【no-1】;
ans+=mouse【i】.v;
}
}
printf("%d",ans);
return 0;
}
3.上白泽慧音
Description
在幻想乡，上白泽慧音是以性格怪异闻名的生物学家。他养了 N 只猴子。有一天，这些被月光刺激，发生了变异。猴子们进行了一次奇怪的活动。第一只猴子的尾巴挂在树上，剩下的 N-1 只，要么被其他的猴子抓住，要么抓住了其他的猴子，要么两者均有。当然一只猴子最多抓两只另外的猴子。现在给出这 N 只猴子抓与被抓的信息，并且在某个时刻可能某只猴子抓累了，会放掉它其中一只手的猴子，导致某些猴子落地。上白泽慧音想知道每只猴子落地的时间。
Input
第一行两个数 N、M，表示有 N 只猴子，并且总时间为 M-1。接下来 N 行，描述了每只猴子的信息，每行两个数，分别表示这只猴子左手和右手抓的猴子的编号，若果是-1，表示该猴子那只手没抓其他猴子。再接下来 M 行，按时间顺序给出了一些猴子放手的信息，第 1+N+i 行表示第 i-1 时刻某只猴子的放手信息，信息以两个数给出，前者表示放手的猴子编号，后者表示其放的是哪只手，1 左 2 右。
Output
共输出 N 行，第 i 行表示第 i 只猴子掉落的时刻，若第 i 只猴子岛 M-1 时刻以后还没掉落，就输出-1。
Example
Input
3 2
-1 3
3 -1
1 2
1 2
3 1
Output
-1
1
1
Hint
30%的数据，N≤1000，M≤1000;
100%的数据，1≤N≤200000，1≤M≤400000。
题目大整容！！！
P1653 猴子 【暂停提交】
题目描述
有N只猴子，第一只尾巴挂在树上，剩下的N-1只，要么被其他的猴子抓住，要么抓住了其他的猴子，要么两者均有。当然一只猴子最多抓两只另外的猴子。现在给出这N只猴子抓与被抓的信息，并且在某个时刻可能某只猴子会放掉它其中一只手的猴子，导致某些猴子落地。求每只猴子落地的时间。
输入输出格式
输入格式：
第一行两个数N、M，表示有N只猴子，并且总时间为M-1。接下来N行，描述了每只猴子的信息，每行两个数，分别表示这只猴子左手和右手抓的猴子的编号，若果是-1，表示该猴子那只手没抓其他猴子。再接下来M行，按时间顺序给出了一些猴子放手的信息，第1+N+i行表示第i-1时刻某只猴子的放手信息，信息以两个数给出，前者表示放手的猴子编号，后者表示其放的是哪只手，1左2右。
【数据规模】
30%的数据，N≤1000，M≤1000;
100%的数据，1≤N≤200000，1≤M≤400000。
输出格式：
共输出N行，第i行表示第i只猴子掉落的时刻，若第i只猴子岛M-1时刻以后还没掉落，就输出-1。
输入输出样例
输入样例#1：
3 2
-1 3
3 -1
1 2
1 2
3 1
输出样例#1：
-1
1
1
详解见m大神的博客
自己选的路，跪着也要走完！！！
