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

2021.05.03【NOIP提高B组】模拟 总结

程序员文章站 2024-03-18 21:54:28
...

比较水的一场比赛,却不能 AK

T1

\(n\) 次,每次给 \(A_i,B_i\) 问以 \(i\) 结尾的 \(A,B\) 的匹配中最大和的最小值

问最大和的最小值,却不用二分。

如果暴力排序,显然会超时

但是 \(A_i,B_i\le 100\) ,一个桶解决的事!

#include<bits/stdc++.h>
using namespace std;
const int N=100005,M=105;
int n,x[N],y[N],tx[M],ty[M],p[M],q[M],l,r,ans;
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d%d",&x[i],&y[i]);
		tx[x[i]]++,ty[y[i]]++;
		for(int i=1;i<=100;i++)
			p[i]=tx[i],q[i]=ty[i];
		l=1,r=100,ans=0;
		while(1) {
			while(!p[l] && l<=100)++l;
			while(!q[r] && r)--r;
			if(l>100 || !r)break;
			ans=max(ans,l+r);
			if(p[l]>q[r])p[l]-=q[r],q[r]=0;
			else q[r]-=p[l],p[l]=0;
		}
		printf("%d\n",ans);
	}
}

T2

从 1 到 \(n\) 依次经过 \(n\) 个点,每个点有 \(t_i,x_i\),有一个初始能力是 \(w\) 的钻头

设当前钻头能力是 \(p\)

\(t_i=1\) 可选择开采,获得 \(x_i\cdot p\) 的价值,损耗 \(k\%\),即 \(p=p*(1-0.01k)\)

\(t_i=2\) 可选择修复,支付 \(x_i\cdot p\) 的价值,修复 \(c\%\),即 \(p=p*(1+0.01c)\)

问最大价值。

显然的 dp

若正来,会发现算法的瓶颈是钻头能力,考虑舍去这一维

因为舍去了,正来会有后效性,于是果断反过来。

可以发现当前钻头对后面的影响无非就是乘上一个值,

可以把初始能力变为 1 ,最后乘上 \(w\)

\(f_i\) 为经过 \([i,n]\) 的最大价值,转移不难,如果 \(t_i=1\)

那么 \([i+1,n]\) 的初始钻头能力就是 \(f_{i+1}*(1-0.01k)\)

\(f_i=\max\{f_{i+1},f_{i+1}*(1-0.01k)+x_i\}\)

\(t_i=2\) 同理

好像 \(f\) 可以压掉,于是一个变量就搞定了

#include<bits/stdc++.h>
using namespace std;
typedef double db;
const int N=100005;
int n,K,C,W,x[N];
db ans,y[N];
int main() {
	freopen("exploit.in","r",stdin);
	freopen("exploit.out","w",stdout);
	scanf("%d%d%d%d",&n,&K,&C,&W);
	for(int i=1;i<=n;i++)scanf("%d%lf",&x[i],&y[i]);
	for(int i=n;i;i--) {
		if(x[i]==1)ans=max(ans,ans*(1-0.01*K)+y[i]);
		else ans=max(ans,ans*(1+0.01*C)-y[i]);
	}
	printf("%.2lf",ans*W);
}

T3

给一个 \(n\times m\) 的地图,图中有一些怪兽,

其对其他格点产生的威胁是两点的曼哈顿距离

问从起点到终点的最优路径,使得路径中最小威胁值最大

一个 bfs 求出威胁,然后一个 spfa ,没了

#include<bits/stdc++.h>
using namespace std;
const int N=505,dx[5]={1,-1,0,0},dy[5]={0,0,1,-1};
int n,m,sx,sy,ex,ey,vis[N][N],dag[N][N],dis[N][N];
char mp[N][N];
struct po {
	int x,y; po() { }
	po(int _x,int _y):
		x(_x),y(_y) { }
}u;
queue<po>q;
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) {
		scanf("%s",mp[i]+1);
		for(int j=1;j<=m;j++) {
			dag[i][j]=2500000;
			if(mp[i][j]=='V')sx=i,sy=j;
			if(mp[i][j]=='J')ex=i,ey=j;
			if(mp[i][j]=='+')q.push(po(i,j)),dag[i][j]=0;
		}
	}
	while(!q.empty()) {
		u=q.front(),q.pop();
		for(int i=0,xx,yy;i<4;i++) {
			xx=u.x+dx[i],yy=u.y+dy[i];
			if(xx<1||xx>n||yy<1||yy>m)continue;
			if(dag[u.x][u.y]+1<dag[xx][yy]) {
				dag[xx][yy]=dag[u.x][u.y]+1;
				q.push(po(xx,yy));
			}
		}
	}
	dis[sx][sy]=dag[sx][sy];
	vis[sx][sy]=1;
	q.push(po(sx,sy));
	while(!q.empty()) {
		u=q.front(),q.pop();
		vis[u.x][u.y]=0;
		for(int i=0,xx,yy;i<4;i++) {
			xx=u.x+dx[i],yy=u.y+dy[i];
			if(xx<1||xx>n||yy<1||yy>m)continue;
			if(min(dis[u.x][u.y],dag[xx][yy])>dis[xx][yy]) {
				dis[xx][yy]=min(dis[u.x][u.y],dag[xx][yy]);
				if(!vis[xx][yy])q.push(po(xx,yy)),vis[xx][yy]=1;
			}
		}
	}
	printf("%d",dis[ex][ey]);
}

总结

  • 学会反着来 & 思路转换