【算法每日一练】- 今天回顾一下写过的最蠢的代码 #旅游买票 竞争主席 #哨兵游戏 #最大边权和

2024-01-09 17:32:51

目录

今日知识点:

整体考虑,把问题转化成装大于一半的背包问题

两两点匹配问题,注意去重方式的dfs的写法

旅游买票

竞争主席

哨兵游戏

最大边权和?


????????

????????

旅游买票

318C:要旅游n天,一共有两种选择,一种是买当日票Fi元,一种是买D日票P元(这任意D天都可以免票) ?问旅游n天最少花多少钱?

思路:

刚开的思路是贪心:先Fi排序,然后把票价低于P/D的都买掉,然后凑D票张数。但是我突然注意如果只剩余一天,再去买D票就不划算了。这个想法肯定不是最优解,因为本可以再少买几张当日票,使D日票没有剩余。故贪心不成立。再一看仅仅是一道C题。应该没那么麻烦吧。

然后我就想到了可以暴力模拟买D日票的数量,然后剩余的票买当日票,计算对应最优的价格,然后用前缀和优化速度即可!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int f[N],n,d,p;
ll sum[N],ans=1e15;
//ll min(ll x,ll y){
//	if(x>y)return y;
//	else return x;
//}
int main(){
	cin>>n>>d>>p;
	sum[0]=0;
	for(int i=1;i<=n;i++){
		scanf("%d",&f[i]);
	}
	sort(f+1,f+n+1);
	for(int i=1;i<=n;i++)sum[i]+=sum[i-1]+f[i];
	int len=0,tmp=n/d;	
	for(ll i=0;i<=tmp+1;i++){
		len=n-i*d;
		if(i==tmp+1)ans=min(ans,p*i);//爆int了
		else ans=min(ans,p*i+sum[len]-sum[0]);
	}
	cout<<ans;
}

????????

?????????

竞争主席

317D?

题意:AB两人竞争主席一共n场,每场有x,y,z。x+y为奇数且x,y代表A,B的支持人数,z为席位数,支持数多的一方赢得z席位数,最终席位数多的赢。问为了让A赢,最少要使多少支持B的人转向支持A?

思路:

原思路是:只考虑A和B目前两者之间的Z差距,并记录每个Zi的代价Wi,然后求使Z为负值所需的最少代价,负值???诶我去?

然后又想了几想:(这肯定能转化成背包的)

其实应该从头考虑,考虑A和B的Z之和,同样记录每个Zi的代价Wi,然后求拿到至少大于Z/2所需的最少代价即可,这样就能做了。

设置dp[i][j]表示遍历到i场,且已经获得j席位时对应的最少贿赂人数。求dp[n][>=Z/2]的最小值
背包问题都是这个式子:dp[i][j]=min(dp[i-1][j],dp[i-1][j-z]+w)?

又因为都只和上一场有关,降成二维就是:dp[i]=min(dp[i],dp[i-z]+w)
其实本题就是装至少一半的背包问题。

#include <bits/stdc++.h>
using namespace std;     
typedef long long ll;
const int N=105,M=1e5+5;//dp[i][j]表示遍历到i场,且已经获得j席位时对应的最少贿赂人数
ll dp[M],w[N],v[N],s,n,ans=1e18;//W[i]为A获得Zi席位数需要的代价,V[i]即Zi
int main(){
	cin>>n;ll x,y,z;
	for(int i=1;i<=n;i++){
		cin>>x>>y>>z;
		v[i]=z;w[i]=max(0ll,(x+y+1)/2-x);//max只能处理同类型的
		s+=z;
	}
	memset(dp,0x7f,sizeof(dp));
	dp[0]=0;
	for(int i=1;i<=n;i++){
		for(int j=s;j>=v[i];j--){
			dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
		}
	}
	for(int i=(s+1)/2;i<=s;i++)//找最佳答案
	ans=min(ans,dp[i]);
	cout<<ans;
}

????????

????????

哨兵游戏

317 E

一个h*w大小的地图:>? <? v ?^ 为四种看哨兵可以向右,左,下,上看到障碍物或人为止 ?.为道路 ?#为墙 ?S为起点 ?G为终点。问能否从起点走到终点且不被发现(哨兵格子也不能走)

思路:

先对地图进行预处理,然后进行正常跑图就完事了。

#include <bits/stdc++.h>
using namespace std;
char s[2005][2005];
int flag,h,w,ans,s1,s2;
int vis[2005][2005],dx[]={1,0,-1,0},dy[]={0,1,0,-1};
struct node{int x;int y;};
void bfs(int x,int y){
	queue<node>q;
	q.push(node{x,y});
	while(!q.empty()){
		if(flag==1)return;
		ans++;int sz=q.size();//一步一步的bfs即可
		while(sz--){
			node cur=q.front();q.pop();
			for(int i=0;i<4;i++){
				int nx=cur.x+dx[i],ny=cur.y+dy[i];
				if(nx<0||nx>=h||ny<0||ny>=w||vis[nx][ny]==1)continue;//这里不能写 s[nx][ny]!='.'(好了,你现在知道了我那时候多蠢了吧,呜呜呜呜呜)
				if(s[nx][ny]=='G')flag=1;
				if(s[nx][ny]=='.')q.push(node{nx,ny}),vis[nx][ny]=1;//入队后就赶紧标记
			}
		}	
	}
}
int main(){
	cin>>h>>w;int tmp;
	for(int i=0;i<h;i++)
	scanf("%s",s[i]);
	for(int i=0;i<h;i++)
	for(int j=0;j<w;j++){//对地图预处理一下,把不能走的 . 变成!
		if(s[i][j]=='S')s1=i,s2=j;
		if(s[i][j]=='>'){
			tmp=1;
			while(j+tmp<w&&(s[i][j+tmp]=='.'||s[i][j+tmp]=='!')){//这里要加上! 因为!只是我们自己加上去的
				s[i][j+tmp]='!';tmp++;	
			}
		}
		if(s[i][j]=='v'){
			tmp=1;
			while(i+tmp<h&&(s[i+tmp][j]=='.'||s[i+tmp][j]=='!')){
				s[i+tmp][j]='!';tmp++;	
			}
		}
		if(s[i][j]=='<'){
			tmp=1;
			while(j-tmp>=0&&(s[i][j-tmp]=='.'||s[i][j-tmp]=='!')){
				s[i][j-tmp]='!';tmp++;	
			}
		}
		if(s[i][j]=='^'){
			tmp=1;
			while(i-tmp>=0&&(s[i-tmp][j]=='.'||s[i-tmp][j]=='!')){
				s[i-tmp][j]='!';tmp++;	
			}
		}
	}
	vis[s1][s2]=1;bfs(s1,s2);
	if(flag==0)cout<<-1;
	else cout<<ans;
}

????????

?????????

最大边权和?

318D

题意:给你n个点的带权w的完全无向图(第1个点有n-1条边,第2个点有n-2条……)问你相互没有重点的所有边最大权值和是多少?? ? ?n<=16; W<=10^9 ?

举个例子:比如n=4,有(1,2)(1,3)(1,4)(2,3)(2,4)(3,4)的权值。搭配有:(1,2)(3,4); (1,3)(2,4); (1,4)(2,3)其中权值和最大的就是答案。

思路:

看似是一道跑图题,实则就是一道配对题(你细品这个完全无向图,在dfs时候完全没有跑图的影子)。如果选了一个点,那么无论匹配那个点,都会导致剩余n-2各点,剩下的点的选择就会越来越少:故有15*13*11*9*7*5*3*1=2027025种答案,暴力完全能过。

先说一下这个dfs函数:

首先是ans的获取:每递归一次就获取一次。不用先存起来再求。免去了回溯的存数和删数操作。

然后是先dfs(u+1,sum);? 再if(vis[u]) return ;顺序不要写反。前面是不选此数(跳过此数去选别的数),后面的是此数已被选过,剩余的操作不用再执行。

最后是dfs(u+1,sum+a);其实我们是已经去重的,因为u+1表示被选的另一个点一定比此点更大,就保证了无重复。而不是保持升序来去重,那样子只是相当于所有数的全排去重,而此题只需要两两数的全排去重。

void dfs(ll u,ll sum){//u是层数,sum和当前权值和。没有必要去重,重复就重复吧
	ans=max(ans,sum);//处理一次获取一次答案,没必要全部选完后再获取答案
	if(u==n+1)return ;//处理越界:因为下一句就是无条件dfs
	dfs(u+1,sum);//这是当前点不选对应的情况,因为我们题上可能会给出奇数点,必然有个点选不上
	if(vis[u]) return ;
	for(int i=u+1;i<=n;i++){//找到可以匹配的另外点
		if(vis[i])continue;//是否已经被匹配
		vis[u]=1;vis[i]=1;
		dfs(u+1,sum+a[u][i]);//找下一组匹配点,之所以不从i+1开始递归是因为中间的点也可以和别的点配对的
		vis[u]=0;vis[i]=0;//回溯
	}
}

完整代码:?

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,ans,a[18][18],vis[18];
void dfs(ll u,ll sum){//u是层数,sum和当前权值和。没有必要去重,重复就重复吧
	ans=max(ans,sum);//处理一次获取一次答案,没必要全部选完后再获取答案
	if(u==n+1)return ;//处理越界:因为下一句就是无条件dfs
	dfs(u+1,sum);//这是当前点不选对应的情况,因为我们题上可能会给出奇数点,必然有个点选不上
	if(vis[u]) return ;
	for(int i=u+1;i<=n;i++){//找到可以匹配的另外点
		if(vis[i])continue;//是否已经被匹配
		vis[u]=1;vis[i]=1;
		dfs(u+1,sum+a[u][i]);//找下一组匹配点,之所以不从i+1开始递归是因为中间的点也可以和别的点配对的
		vis[u]=0;vis[i]=0;//回溯
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	dfs(1,0);
	cout<<ans;
}

注意dfs要一次处理一层,处理两层的话,遇到奇数层就会很麻烦?

// 请欣赏我的shit代码     千万不要学
void dfs(int u,int cnt){//dfs要一次处理一层,一次处理两层的话,万一一共奇数层怎么办
	ans=max(ans,cnt);
	if(u==n+1)return ;
	int t=1;
	while(vis[t])t++;
	for(int i=t;i<=n;i++){
		if(vis[i])continue;
		vis[i]=1;
		for(int j=i+1;j<=n;j++){
			if(vis[j])continue;
			vis[j]=1;
			dfs(u=1,cnt+a[i][j]);
			vis[j]=0;	
		}
		vis[i]=0;
	}
}

文章来源:https://blog.csdn.net/m0_69478376/article/details/135480838
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。