Noip模拟水题

2017-10-19

T1——原创题

在这个世界上,一个人的好友可能和他作对,变成敌人;他用慈爱所培
养起来的儿女也可能变的不忠不孝;那些我们最感密切和亲近的人, 那些我们用全部幸福和名誉所痴信的人,都可能会舍弃忠诚而成为叛逆.在这个自私的世界上,一个人唯一不自私的朋友,唯一不抛弃他的朋友,唯一不忘恩负义的朋友,就是他的犬。

但是，一天，我来到了一个公园。我发现这里有 n 群狗，但这里
的狗都对我不友好，我想击败几群狗，我要花 k[i][j]的时间并消耗 w[i][j]
的体力值来打败这群狗的一部分。
现在我想知道自己最多能打赢多少群狗。
输入：第一行是我的体力值 x，接着是 n,m（m 表示打败狗有几个程
度）；接下来 n 行，每行 m 个数，表示打狗消耗的体力值 w[i][j]值；
接下来 n 行，每行 m 个数，表示打败狗的期望值 k[i][j]值。
输出：一个数，表示一共可以打败几群狗。（保留 2 位小数）
样例
输入：fight.in
By lml
（1）

（2）

输出 fight.out

（1）2.00
（2）1.80
数据范围
40% x<=20,n,m<=10;
100% x<=300,n<=100，m<=70;
保证数据纯随机。
吐槽（人是打不赢狗的）。

做法

因为这是原创题，我不知道部分分。
正解是三维dp
而且是由以前的二维升维来的，我们可以用dp[i][j][k]来记录当取第i群狗第j个还剩k点体力时的状态。
而转移
dp[i][j][k-f[i][j]]=
max(dp[i-1][jj][k]+w[i][j],dp[i][j][k-f[i][j]]);
jj由上一个的状态转移。
相信大佬们肯定ac。
附代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,x,f[200][200];
double w[200][200],dp[200][200][500],maxn;
int main(){
	//freopen("fight.in","r",stdin);
	//freopen("fight.out","w",stdout);
	scanf("%d%d%d",&x,&n,&m);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&f[i][j]);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%lf",&w[i][j]);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			for(int k=x;k>=0;k--)
			{
				for(int qwe=1;qwe<=m;qwe++)
				{dp[i][j][k]=max(dp[i][j][k],dp[i-1][qwe][k]);
				dp[i][j][k-f[i][j]]=max(dp[i-1][qwe][k]+w[i][j],dp[i][j][k-f[i][j]]);}
			}
		}
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
	maxn=max(dp[i][j][0],maxn);
	printf("%.2lf",maxn);
}

毕竟是自己想出来的，所以要写下来。

T2——来自luogu 1462/1951

我来到了一个神奇的地方，这里有很多宝藏，但宝藏在 n 号房间，
这里有 n 个房间，共有 m 条路，每条路上有机关，我走过会受伤，
掉 x 点血。每个房间都有防御装置，我要进去的话要花费 ci 点体力，
我现在想去 n 号房间，但我的有一定的血量值，所以我不能一直走。
现在，我想知道我所经过的房间中最多消耗的体力的最小是多少。
我初始在 1 号房间。
其实 n 号房间就在 1 号房间附近。（什么用都没有）
输入：find.in
第一行是 n，m，接着是我的血 x。
第二行是 n 个数，表示进入每个房间的消耗体力值。房间只当我进入
时耗费体力。
接下来的 m 行，每行三个数 a，b，c；表示 a,b 之间有一条长度为 c
的路，耗费 c 点血，双向边。
输出：find.out 一个数，表示我最少耗费多少体力。若我在到达前没血了，输出-1。
样例
输入

输出
10
数据范围：保证数据纯随机。
对于 30%的数据，满足 n≤200，m≤10000，b≤200
对于 100%的数据，满足 n≤10000，m≤50000，b≤1000000000
良心话，这里数据全随机，而且没几组大的。
想法：
所经过的房间中最多消耗的体力的最小是多少
很明显是二分，并跑spfa就可以过了。
我还是要%楼下高一大佬，这么快就学指针了，我们那时才学数组。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
int n,m,tot,to[100010],head[100010],nx[100010],b,co[10010],bloom[100010],ans=-1,qwe[10010];
long long dis[50010];
bool vis[50010];
queue<int>q;
inline void read(int &x) {
	x=0;int f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}x*=f;
}
inline void add(int a,int b,int c){
	to[++tot]=b;
	nx[tot]=head[a];
	head[a]=tot;
	bloom[tot]=c;
}
int spfa(int mid){
	memset(dis,0x7f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[1]=0;vis[1]=1;
	q.push(1);
	while(!q.empty()){
		int x=q.front();q.pop();vis[x]=0;
		for(int i=head[x];i;i=nx[i]){
			int t=to[i];
			if(co[t]>mid)continue;
			if(bloom[i]+dis[x]<dis[t]){
				dis[t]=bloom[i]+dis[x];
				if(!vis[t]){
					q.push(t);vis[t]=1;
				}
			}
		}
	}
	return dis[n]<b;
}
int main(){
	//freopen("find.in","r",stdin);
	//freopen("find.out","w",stdout);
	read(n);read(m);read(b);
	for(int i=1;i<=n;i++)read(co[i]),qwe[i]=co[i];
	sort(qwe+1,qwe+1+n);
	for(int i=1;i<=m;i++){
		int a,b,c;
		read(a);read(b);read(c);
		add(a,b,c);add(b,a,c);
	}
	int l=1,r=n;
	while(l<=r){
		int mid=(l+r)>>1;
		if(spfa(qwe[mid]))ans=qwe[mid],r=mid-1;
		else l=mid+1;
	}
	if(ans==0||ans==-1){printf("-1");return 0;}
	printf("%d",ans);
	return 0;
}

##T3———大水题
1.一遍bfs就可以过了,但有些要特判。
2.dfs+剪枝