欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2020.03.11【NOIP普及组】模拟赛C组15

程序员文章站 2022-06-04 12:46:40
...
题目编号 标题
0 水果盛宴(fruit)
1 愤怒的奶牛2(angry)
2 采访(interview)
3 房间开灯(light)

T1:

题目描述

贝茜又再一次地闯入了 Farmer John 的房子!她在厨房发现了一堆柠檬和一堆橘子(每堆都有无限多个),并且,她希望尽可能地多吃。
贝茜的有一个饱腹值上限 T(1<=T<=5,000,000)。吃一个橘子会增加她 A 点饱腹值,吃一个柠檬会增加她 B 点饱腹值(1<=A,B<=T),如果她愿意,贝茜可以最多喝一次水,这会立即使她的饱腹值变成一半,请你帮助贝茜求出她可以获得的最大饱腹值。

输入

一行三个整数 T,A 和 B

输出

一行一个整数,表示贝茜可获得的最大饱腹值

样例输入

8 5 6

样例输出

8

数据范围限制

爆力dfs,时间复杂度:O(n)

var
i,j,k,m,n,x,y:longint;
f:array[0..5000001]of longint;
procedure dfs(k,t:longint);
begin
    f[k]:=1;
    if(k+x<=n)then
    begin
        if(k+x>m)then m:=k+x;
        if(m=n)then
        begin
            write(n);
            close(input);
            close(output);
            halt;
        end;
        if(f[k+x]=0)then dfs(k+x,t);
    end;
    if(k+y<=n)then
    begin
        if(k+y>m)then m:=k+y;
        if(m=n)then
        begin
            write(n);
            close(input);
            close(output);
            halt;
        end;
        if(f[k+y]=0)then dfs(k+y,t);
    end;
    if(t=0)and(f[k div 2]=0)then
    begin
        dfs(k div 2,1);
    end;
end;
begin
    assign(input,'fruit.in');
    assign(output,'fruit.out');
    reset(input);
    rewrite(output);
    read(n,x,y);
    dfs(0,0);
    write(m);
    close(input);
    close(output);
end.

本人c++还不够熟练,请谅解

T2:

题目描述

贝茜这头奶牛设计了她所认为的下一个热门视频游戏—“愤怒的奶牛”。她认为这是她完全原创的:玩家将一个弹弓射到一个一维的场景中,该场景由位于数字线上各个点的一组干草包组成。每只奶牛都有足够的力量引爆其落地地点附近的干草包,我们的目的是使用一系列奶牛引爆所有的干草包。
有N捆干草包位于这一行的不同整数位置x1,x2,...,xN,如果一头奶牛以能量R着陆在了数轴上的任意一个位置x,那么会引起半径为R(R-x..R+x)的爆炸,并摧毁范围内的所有干草包。
一共有K头奶牛允许被用来作为炮弹,每头奶牛的能量R都相同。请帮忙决定这个最小的能量,使得用这K头奶牛可以摧毁所有的干草包。

输入

第一行包含两个整数N,K(1<=N<=50,000,1<=K<=10)
接下来N行,每行包含一个整数xi,表示每捆干草包的位置(0<=xi<=1,000,000,000)

输出

一行一个整数,表示最少所需要的每头奶牛的能量值R

样例输入

7 2
20
25
18
8
10
3
1

样例输出

5

数据范围限制

二分答案+判断

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int m,n,k;
int a[50001];
bool pd(int r){
	int e=a[1],b=a[1]+r+r,t=1;
	for(int i=2;i<=n;i++){
		if(a[i]>b){
			t++;
			e=a[i];
			b=a[i]+r+r;
			if(t>m)return 0;
		}
	}
	return 1;
}
int main(){
	freopen("angry.in","r",stdin);
	freopen("angry.out","w",stdout);
	cin>>n>>m;
	k=2147483647;
	int l,r=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		r=max(r,a[i]);
	}
	sort(a+1,a+1+n);
	l=0;
	while(l<r){
		int mid=(l+r)/2;
		if(pd(mid)){
			k=min(mid,k);
			r=mid-1;
		}
		else{
			l=mid+1;
		}
	}
	if(pd(l))k=min(l,k);
	if(pd(r))k=min(r,k);
	cout<<k;
	return 0;
}

T3:

题目描述

你是一名记者,现在要求你去采访n 个国家的*。采访每一个国家的*需要消耗你的时间为t[i],但你可以收获价值为v[i]的信息,然后就能写成报道……
然而尴尬的是,有一些国家之间的关系属于敌对关系,因此如果一个国家的*知道你采访了他的敌对国家*,那么他就会拒绝你的采访。总之,你采访的国家中,任意选出一对国家都不能构成敌对关系,你才能够完成你的采访,否则某些部分就要落空。
你的Boss他给了你一个时间限制T,如果你在时间限制内没有完成采访任务,你就会被炒鱿鱼。当然,他希望你在时间限制T 内完成的采访累计起来的价值总和最大。

输入

第一行有三个数,第一个数为时间限制T,第二个数为国家数量n,第三个数为国家之间的敌对组数m。
接下来n 行,每行两个数,第一个数为t[i],第二个数为v[i]。
接下来m 行,每行有m[i]+1 个数,首先输入m[i],表示这一组中一共有多少国家是敌对关系,之后输入m[i]个数,表示这m[i]个国家两两之间为敌对关系(一组敌对关系的国家中,每两个国家都构成敌对关系,比如这一组是1,3,4,那么1 和3,1 和4,3 和4 都构成敌对关系),若m[i] = 1,那么这个国家与其他国家都不构成敌对关系。

输出

一个整数,表示最大价值V。

样例输入

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

样例输出

22

数据范围限制

60%的数据:m=1;
100%的数据:0≤T≤50000,0≤n≤500,1≤m≤10,n=∑m[i],即m[1]+m[2]+.....=n,且敌对关系中每个国家编号只会出现一次。

典型的分组背包,只不过初始化要注意i-1,不用滚数组

#include<iostream>
#include<cstdio>
using namespace std;
int m,n,k,x,y;
int t[10010],v[10010];
int f[11][50001];
int a[100][100];
int main(){
	freopen("interview.in","r",stdin);
	freopen("interview.out","w",stdout);
	cin>>n>>k>>m;
	for(int i=1;i<=k;i++){
		cin>>t[i]>>v[i];
	}
	for(int i=1;i<=m;i++){
		cin>>a[i][0];
		for(int j=1;j<=a[i][0];j++)
		cin>>a[i][j];
	}
	for(int i=1;i<=m;i++){
		for(int j=0;j<=n;j++)f[i][j]=f[i-1][j];
		for(int k=1;k<=a[i][0];k++){
			for(int j=n;j>=t[a[i][k]];j--)
			f[i][j]=max(f[i][j],f[i-1][j-t[a[i][k]]]+v[a[i][k]]);
		}
	}
	cout<<f[m][n];
	return 0;
}

T4:

题目描述

Farmer John 最近正在修建一个巨大的包含 N×N 个房间的牲口棚,这些房间从(1,1)标号到(N,N)。由于某些原因而害怕黑暗,贝茜这头奶牛想要尽可能地开更多房间的灯。贝茜从房间(1,1)出发,这个房间是唯一一个一开始就亮着的房间。在一些房间中,她会找到一些电灯开关,这些开关她可以用来切换其他房间的灯的状态。比如,在(1,1)这个房间中可能存在一个电灯开关来控制(1,2)房间中的电灯。贝茜只能进电灯开着的房间,并且贝茜只能从房间(x,y)走到四个方向的房间(x-1,y),(x+1,y),(x,y-1)和(x,y+1)(如果在边界的话,那可能会更少)。请帮忙统计贝茜最多可以照亮多少房间。

输入

第一行两个整数 N,M(2<=N<=100,1<=M<=20,000)
下面 M 行,每行用四个整数 x,y,a,b 来表示房间(x,y)存在着可以控制房间(a,b)的灯的开关。一个房间可能有多个开关,一个房间的灯的开关可能存在于多个房间中。

输出

一行一个整数,表示贝茜最多可以照亮的房间数

样例输入

3 6
1 1 1 2
2 1 2 2
1 1 1 3
2 3 3 1
1 3 1 2
1 3 2 1

样例输出

5

数据范围限制

提示

在这个样例中,贝茜可以使用房间(1,1)内的开关打开房间(1,2)和(1,3)的灯。然后她可以走到(1,3),使用(1,3)内的开关打开(2,1)的灯,接着可以通过(2,1)打开(2,2)的灯,然而(2,3)是黑暗的,她无法去打开(2,3)房间里的开关,因此,她最多只能打开 5个房间里的灯。

2020.03.11【NOIP普及组】模拟赛C组15
2020.03.11【NOIP普及组】模拟赛C组15
2020.03.11【NOIP普及组】模拟赛C组15

^

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,next[200001],lx[200001],ly[200001],rx[200001],ry[200001];
int head[101][101],a[101][101],f[101][101];
int b[1000100][3],ans;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
void bfs(){
	b[1][1]=1;b[1][2]=1;
	a[1][1]=1;
	f[1][1]=1;
	ans++;
	int hd=0,tl=1;
	while(hd<tl){
		hd++;
		int x1=head[b[hd][1]][b[hd][2]];
		while(x1!=0){
			if(a[rx[x1]][ry[x1]]==0)ans++;
			a[rx[x1]][ry[x1]]=1;
			x1=next[x1];
		}
		for(int i=1;i<=hd;i++){
			for(int j=0;j<4;j++){
				int xx=b[i][1]+dx[j];
				int yy=b[i][2]+dy[j];
				if(a[xx][yy]==1&&f[xx][yy]!=1){
					tl++;
					b[tl][1]=xx;
					b[tl][2]=yy;
					f[xx][yy]=1;
				}
			}
		}
	}
}
int main(){
	freopen("light.in","r",stdin);
	freopen("light.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>lx[i]>>ly[i]>>rx[i]>>ry[i];
		next[i]=head[lx[i]][ly[i]];
		head[lx[i]][ly[i]]=i;
	}
	bfs();
	cout<<ans;
	return 0;
}
相关标签: 比赛