2016 UESTC Training for Data Structures
就做了4题，其他的感觉好难！！QAQ
卿学姐与公主
某日，百无聊赖的卿学姐打开了某11区的某魔幻游戏
在这个魔幻的游戏里，生活着一个美丽的公主，但现在公主被关押在了魔王的城堡中。
英勇的卿学姐拔出利刃冲向了拯救公主的道路。
走过了荒野，翻越了高山，跨过了大洋，卿学姐来到了魔王的第一道城关。
在这个城关面前的是魔王的精锐部队，这些士兵成一字排开。
卿学姐的武器每次只能攻击一个士兵，并造成一定伤害，卿学姐想知道某时刻从L到R这个区间内，从开始到现在累计受伤最严重的士兵受到的伤害。
最开始每个士兵的受到的伤害都是0
Input
第一行两个整数N,Q
表示总共有N个士兵编号从1到N，和Q
个操作。
接下来Q
行，每行三个整数，首先输入一个t，如果t是1，那么输入p,x，表示卿学姐攻击了p这个位置的士兵，并造成了x的伤害。如果t是2，那么输入L,R，表示卿学姐想知道现在[L,R]
闭区间内，受伤最严重的士兵受到的伤害。
1≤N≤100000
1≤Q≤100000
1≤p≤N
1≤x≤100000
1≤L≤R≤N
Output
对于每个询问，回答相应的值
样例输入
5 4
2 1 2
1 2 4
1 3 5
2 3 3
样例输出
0
5
Hint
注意可能会爆int哦
题解：第一题还是很简单的，单点修改，区间查询的线段树
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#define LiangJiaJun main
#define LL long long
using namespace std;
LL tr[400004];
int n,q,up=1;
LL query(int l,int r){
LL ans=0;
for(l=l+up-1,r=r+up+1;r-l>1;r>>=1,l>>=1){
if(~(l&1)) ans=max(ans,tr[l+1]);
if(r&1) ans=max(ans,tr[r-1]);
}
return ans;
}
void change(int p,LL x){
int now = p + up ;
tr[now] += x;
now >>= 1;
while(now >= 1){
tr[now] =max( tr[now<<1] , tr[now<<1|1] );
now >>= 1;
}
}
int LiangJiaJun(){
scanf("%d%d",&n,&q);
while(up<n+2)up<<=1;
memset(tr,0,sizeof(tr));
while(q--){
int t,p,l,r;LL x;
scanf("%d",&t);
if(t==1){
scanf("%d%lld",&p,&x);
change(p,x);
}
if(t==2){
scanf("%d%d",&l,&r);
printf("%lld\n",query(l,r));
}
}
return 0;
}
卿学姐与诡异村庄
日复一日，年复一年，春去秋来。
卿学姐终于从天行廖那里毕业啦。出山的卿学姐首先来到了一个诡异的村庄。
在这个村庄中，只有两种人，一种是好人，一种是坏人。
好人只说真话，坏人只说假话。
村庄虚伪的平静由于卿学姐的到来，终于被打破了。
人们开始互相指控，每个人都会说另外一个人是否是好人。
卿学姐修行途中只学会了膜法，却不谙世事，所以卿学姐无法确认哪些人是好人，哪些人是坏人。
但是机智的卿学姐意识到可以通过这些人的指控来分辨。
现在告诉你村庄中每个人指控谁是否为好人，请问是否有个合理的分类能够符合所有的指控。
Input
第一行一个整数N
，表示村庄总共有N个人，村民从1开始编号到N
1≤N≤100000
接下来N行，每行两个整数，ai,t，如果t是1，那么说明第i个人认为第ai个人是好人。如果t是2，那么说明第i个人认为第ai
个人是坏人。（1≤ai≤N）
Output
如果存在一个好人坏人的分类能够满足所有的指控，那么输出"Time to show my power"，否则输出"One face meng bi"
样例输入1：
3
2 2
3 1
1 2
样例输出1：
Time to show my power
样例输入2：
3
2 2
3 2
1 2
样例输出2：
One face meng bi
题解：并查集入门。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<set>
#define LiangJiaJun main
#define LL long long
using namespace std;
bool ok=1;
int a[200004],t[200004],n;
int p,q,f[200014];
int find(int x){return (f[x] == x)?f[x]:f[x] = find(f[x]);}
int LiangJiaJun(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&t[i]);
for(int i=1;i<=2*n;i++) f[i]=i;
for(int i=1;i<=n;i++){
if(t[i] == 1) {
p=find(i);q=find(a[i]);
if(p!=q)f[p]=q;
p=find(i+n);q=find(a[i]+n);
if(p!=q)f[p]=q;
}
else{
p=find(i);q=find(a[i]+n);
if(p!=q)f[p]=q;
p=find(i+n);q=find(a[i]);
if(p!=q)f[p]=q;
}
if(find(i)==find(i+n) || find(a[i])==find(a[i]+n)){ok=0;break;}
}
if(ok)puts("Time to show my power");
else puts("One face meng bi");
return 0;
}
卿学姐与魔法
“你的膜法也救不了你”——蛤
在去拯救公主的道路上，卿学姐披荆斩棘，刀刃早已锈迹斑斑。
一日卿学姐正在为武器的问题发愁，碰到了正在赏树的天行廖。
天行廖嘴角微扬，似乎看穿了卿学姐的心思，故意在此等待。
“少年，你渴望掌握雷电的力量吗？”天行廖如是问道。
已经差不多是条咸鱼的卿学姐欣然答应了。于是卿学姐开始跟随魔法大师天行廖学习魔法的力量。
刚入门的卿学姐发现，每个魔法都是由两种基本元素构成的，A元素和B元素。
而每个魔法的魔力是合成这个魔法的A元素和B元素的大小的和。
例如一个大小为3的A元素和一个大小为6的B元素，能构成一个魔力为9的魔法。
现在卿学姐收集了N个A元素和N个B元素。敏锐的卿学姐立刻发现他能组合出N∗N种魔法。
谦虚的卿学姐并不希望自己太跳，所以他准备将这N∗N
种魔法中的最小的N种展示给天行廖检查。
现在卿学姐想知道，这N∗N种魔法中最小的N种是什么。
当然，得从小到大输出哦~
Input
第一行一个整数N
接下来一行有N
个数，表示N个A元素
接下来一行有N
个数，表示N个B元素
1≤N≤100000
1≤A[i],B[i]≤1000000000
Output
输出N行，每行一个整数
代表N∗N种魔法中最小的N个
样例输入
5
1 3 2 4 5
6 3 4 1 7
样例输出
2
3
4
4
5
题解：同 [洛谷P1631]序列合并/[codevs1245]最小的N个和
链接：http://blog.csdn.net/dxyinme/article/details/52211000
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<queue>
#define LiangJiaJun main
#define LL long long
#define pa pair<LL,int>
using namespace std;
priority_queue<pa , vector<pa> , greater<pa> >q;
LL A[100004],B[100004],ans[100004];
int n,qs[100004],cnt=0;
int LiangJiaJun(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",&A[i]);
for(int i=1;i<=n;i++)scanf("%lld",&B[i]);
sort(A+1,A+n+1);sort(B+1,B+n+1);
for(int i=1;i<=n;i++){
q.push(make_pair(A[1]+B[i],i));
qs[i] = 1;
}
cnt=0;
while(cnt <= n){
pa x = q.top();q.pop();
ans[++cnt] = x.first;
q.push(make_pair(A[++qs[x.second]]+B[x.second],x.second));
}
for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);
return 0;
}
郭大侠与Rabi-Ribi
最近郭大侠迷上了玩Rabi-Ribi这个游戏。
Rabi-Ribi呢，是一个打兔子的动作冒险游戏，萌萌哒的兔子在地上跑来跑去，好萌好萌呀~
这个游戏是这样玩的，郭大侠作为一个主角，拿着一个小锤子，他的目标是敲晕兔子，然后最后把这些敲晕的兔子都带回家。
当然咯，郭大侠想带回的兔子的总价值最高~
但是，兔子实在是太多了，郭大侠的锤子每一秒钟只能敲晕一只兔子，而且每一只兔子只会在地面上逗留a[i]秒，在a[i]秒之后，这一只兔子就会跑回自己的小窝里面。
所以郭大侠面临一些抉择，希望你能帮助他。
Input
第一行包含一个整数N
表示有N个兔子在地上跑来跑去。
第二行N个用空格分隔的整数a[i]
表示第i只兔子冒出后停留的时间
第三行N个用空格分隔的整数v[i]表示第i只兔子的价值。
1≤N≤100000
1≤a[i]≤5000
1≤v[i]≤1000
Output
输出郭大侠最多能获得的价值是多少
样例输入1：
5
5 3 6 1 4
7 9 2 1 5
样例输出1：
24
样例输入2：
3
1 1 1
1 2 3
样例输出2：
3
题解：我们先把所有兔子丢到一个以t为关键字的小头堆内，然后每一次取出堆头，如果当前时间小于当前兔子的消失时间，那么就将兔子丢到一个以v为关键字的小头堆中。如果当前时间大于等于当前兔子消失的时间，那么将其与以v为关键字的小头堆的堆头比较v的值，如果比堆头大，那么就将堆头兔子踢掉，将当前兔子加入堆中。计算结果的时候，只要将以v为关键字的小头堆内的兔子的v值都加起来就是答案了。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<queue>
#define LiangJiaJun main
#define LL long long
#define pa pair<int,int>
using namespace std;
priority_queue<pa , vector<pa> , greater<pa> >q,qf;
int n,tn=0,ans=0;
struct data{
int w,t;
}a[100004];
int LiangJiaJun(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i].t);
for(int i=1;i<=n;i++)scanf("%d",&a[i].w);
for(int i=1;i<=n;i++)q.push(make_pair(a[i].t,a[i].w));
while(!q.empty()){
pa x = q.top();q.pop();
if(x.first>tn){
tn ++;qf.push(make_pair(x.second,x.first));
}
else {
if(!qf.empty()&&x.second > qf.top().first){
qf.pop(); qf.push(make_pair(x.second,x.first));
}
}
}
ans = 0;
while(!qf.empty()){
ans += qf.top().first;
qf.pop();
}
printf("%d\n",ans);
return 0;
}