2020.02.25【NOIP普及组】模拟赛C组10

题目编号	标题
0	朋友(friend)
1	分数统计(score)
2	跳棋(jump)
3	迷宫大门(door)

T1:

题目描述

经过六年的努力，小明终于被一所知名中学录取。优秀的小明总是对一些奇奇怪怪的事情感兴趣，这次他想知道谁在这所新学校拥有的朋友最多，由于大家都才刚报到，所以小明只知道大家两两之间是否是朋友关系。

输入

输入文件friend.in的第一行有两个整数n和m，n表示总人数，m表示总关系数。
接下来m行，每行有2个以空格隔开的整数a和b，表示a和b是朋友，a和b均为1到n之间的整数。不会给出重复的朋友关系。

输出

输出文件friend.out中仅有一行，表示朋友数最多的人所拥有的朋友，每两个整数之间用空格隔开，按照字典序从小到大输出。如果存在多个人朋友数都是最多的情况，请输出字典序最小的那人的答案，具体见样例。

样例输入

3 3
1 2
2 3
1 3

样例输出

2 3

数据范围限制

50%的数据，1 <= n <= 10
80%的数据，1 <= n <= 1000
100%的数据，1 <= n <= 10000，m <= 500000

提示

1、2、3均拥有2个朋友，因此输出字典序较小的1的朋友即可。
1的朋友为2和3，按照字典序从小到大输出，数字之间用空格隔开。

这就是一个邻接表

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int a[10001],m,n,x,y,head[1000000],tot,maxx;
struct node{
	int to,next;
}b[1000000];
void ljb(int x,int y){
	tot++;
	b[tot].to=y;
	b[tot].next=head[x];
	head[x]=tot;
}
int main(){
	freopen("friend.in","r",stdin);
	freopen("friend.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		a[x]++;
		a[y]++;
		ljb(x,y);
		ljb(y,x);
	}
	for(int i=1;i<=n;i++){
		if(a[i]>maxx){
			maxx=a[i];
			x=i;
		}
	}
	y=0;
	for(int i=head[x];i;i=b[i].next){
		y++;
		a[y]=b[i].to;
	}
	sort(a+1,a+y+1);
	for(int i=1;i<=y;i++)cout<<a[i]<<' ';
	return 0;
}

T2:

题目描述

在统计完朋友情况之后，小明又对大家的毕业学校产生兴趣，但是他觉得单纯的统计人数是一件非常无聊的事情，于是他设计了一个算法，同一所学校毕业的学生，第1个将获得1分，第2个获得2分，第3个获得4分…，第i个将获得2^(i-1)分，总分就是这所小学的得分，小明想知道得分最高的学校有多少分。

输入

输入文件score.in的第一行有两个整数n和m，n表示总人数，m表示已知的同校关系数量。
接下来m行，每行有2个以空格隔开的整数a和b，表示a和b是来自同一所学校，a和b均为1到n之间的整数。不会给出重复的信息。

输出

输出文件score.out只有一行，为所有学校中的最高得分。最后得分可能会很大，你只需要输出后100位即可，不足100位的请直接输出。

样例输入

5 3
1 2
3 4
1 3

样例输出

15

数据范围限制

60%的数据，1 <= n <= 10
80%的数据，1 <= n <= 70
100%的数据，1 <= n <= 10000，1 <= m <= 100000

提示

1、2、3、4来自同一所学校，该所学校所得的分数为1+2+4+8=15

这就是并查集

#include<iostream>
#include<cstdio>
using namespace std;
int m,n,k,x,y,fa[1000100],h[1000100],maxx=1,a[101];
bool flag;
int get(int x){
	if(fa[x]==x)return x;
	return fa[x]=get(fa[x]);
}
void cheng(){
	int k=0;
	for(int i=100;i>=1;i--){
		a[i]=a[i]*2+k;
		k=a[i]/10;
		a[i]=a[i]%10;
	}
	if(k!=0)flag=1;
}
int main(){
	freopen("score.in","r",stdin);
	freopen("score.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		fa[i]=i;
		h[i]=1;
	}
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		int fx=get(x);
		int fy=get(y);
		if(fx!=fy){
			fa[fx]=fy;
			h[fy]+=h[fx];
			if(h[fy]>maxx)maxx=h[fy];
		}
	}
	a[100]=1;
	for(int i=1;i<=maxx;i++)
	cheng();
	a[100]--;
	if(flag==0){
		int i=1;
		while(a[i]==0)i++;
		while(i<=100){
			cout<<a[i];
			i++;
		}
    }
    else
    {
    	for(int i=1;i<=100;i++){
    		cout<<a[i];
		}
	}
	return 0;
}

T3:

题目描述

小明迷恋上了一个新的跳棋游戏，游戏规则如下：棋盘是一排从0开始，顺序编号的格子，游戏开始时你位于0号格子，你每次只能往编号大的格子跳，而且你每次至少需要跳过L个格子，至多只能跳过R个格子。每个格子都有一个给定的伤害值，显然你希望得到的伤害值越少越好。
你能告诉小明他当他跳到最后一个格子时受到的累积伤害值最小为多少吗？
如果无论如何小明都无法跳到最后一个格子，这个时候你需要输出”-1”。
注：从i号格子跳过x个格子表示从i号格子跳到第i+x+1号格子。

输入

输入文件jump.in第一行有三个整数n、L和R，n表示格子的编号从0到n。L和R表示最少需要跳过的格子数和最多能够跳过的格子数。	
第二行有n个正整数，两个数字间用空格隔开，表示每个格子的伤害值。

输出

输出文件jump.out仅有一个整数，表示受到的最小伤害值，保证结果小于maxlongint。

样例输入

10 2 6
1 3 5 7 9 2 4 6 8 10

样例输出

12

数据范围限制

50%的数据，1 <= n <= 1000
65%的数据，1 <= n <= 10000
100%的数据，1 <= n <= 1000000，1 <= L <= R <= n
其中有15%的数据，1 <= n <= 1000000，1 <= L <= R <= 10

提示

这就是单调队列+DP
单调队列就是用来维护区间最值得一种东西

#include<iostream>
#include<cstdio>
using namespace std;
int MAX=2147483647;
long long m,n,k,l,r,head=1,tail,q[1000001],a[1000001],f[1000001];
int main(){
	freopen("jump.in","r",stdin);
	freopen("jump.out","w",stdout);
	cin>>n>>l>>r;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		f[i]=MAX;
	}
	for(int i=1;i<=n;i++){
		if(i-l-1>=0){
			while(head<=tail&&f[q[tail]]>=f[i-l-1])tail--;
			tail++;
			q[tail]=i-l-1;
		}//没用的干掉
		while(head<=tail&&q[head]<(i-r-1))head++;//过时的去除
		if(head<=tail)f[i]=f[q[head]]+a[i];
	}
	if(f[n]>=MAX)cout<<-1;
	else cout<<f[n];
	return 0;
}

T4:

题目描述

在跳棋游戏大获全胜后，小明就开始一个人在校园里溜达了。突然他在校园角落里发现了一面神奇的墙壁，墙壁上有一排钉子，每个钉子上都挂着一根两端系有小球的绳子，如下图所示

小明可以调整每一根绳子在钉子左右两端的长度，当来自不同绳子的相邻小球高度一样时（具体可见样例说明），便可获得积分1分。当小明的方案获得最高积分时，迷宫大门就会开启，小明就可以进去寻找宝藏啦！

输入

输入文件door.in第一行为一个正整数n，表示墙上的绳子数。
接下来n行，每行2个整数a和b，表示绳子左右两端的初始长度。

输出

输出文件door.out仅有一个正整数，表示小明可以获得的最高积分。

样例输入

3
1 1
3 2
1 4

样例输出

2

数据范围限制

提示

这就是一道贪心
记录一下可以滑动的区间就好了

#include<iostream>
#include<cstdio>
using namespace std;
int m,n,k,x,y,a[10001000],l,r;
int main(){
	freopen("door.in","r",stdin);
	freopen("door.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x>>y;
		a[i]=x+y;
	}
	l=0;r=a[1];
	for(int i=2;i<=n;i++){
		if(a[i]<l){
			l=0;r=a[i];
		}
		else{
			k++;
			x=a[i]-min(a[i],r);
			y=a[i]-l;
			l=x;
			r=y;
		}
	}
	cout<<k;
	return 0;
}