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个房间里的灯。
^
#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;
}