【算法每日一练]-dfs (保姆级教程 篇9) #俄罗斯方块 #ABC Puzzle #lnc的工资

这篇具有很好参考价值的文章主要介绍了【算法每日一练]-dfs (保姆级教程 篇9) #俄罗斯方块 #ABC Puzzle #lnc的工资。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

今日知识点:

两两点匹配问题,注意去重方式的dfs的写法(组内升序即可)

二维图形的状态压缩,存下所有的合法状态然后暴力遍历

dfs的优化剪枝

二项式定理

最大边权和 

俄罗斯方块

ABC Puzzle

lnc的工资


        

         

最大边权和 

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 。

顺序不要写反。前面是不选此数(跳过此数去选别的数作为起点);后面的是此数已被选过,剩余的操作(选取终点)不能再执行。

第三:是for循环中的dfs(u+1,sum+a)。

说明我们是已经去重的,因为u作起点传进来,而for是从u+1开始找终点的。所以终点一定比起点大,就保证了组内的无重复性。然后我们再保证起点u一定是单增的。那么所有组就不可能再有重复的。

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++){//找到可以匹配的另外点,也就是终点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;
}
// 请欣赏我的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;
	}
}

         

      

俄罗斯方块

322D

题意:在4*4方格中分别给出3个俄罗斯方块,问是否可以经过旋转,平移操作恰好拼满整个4*4格子? 不能重叠和越界。

输入样例:

【算法每日一练]-dfs (保姆级教程 篇9) #俄罗斯方块 #ABC Puzzle #lnc的工资,bfsdfs,算法,数据结构,深度优先,图论,c++

样例解释 

【算法每日一练]-dfs (保姆级教程 篇9) #俄罗斯方块 #ABC Puzzle #lnc的工资,bfsdfs,算法,数据结构,深度优先,图论,c++

思路:

首先是如何存储图形以及变化后的图形,当然不仅要方便变换还要方便最后检查。然后就想到了状态压缩,一共最多16格子,最多需要16位就行。
也就是最大用2^16-1的数字即可表示这种状态,然后对3个俄罗斯方块一一组合遍历看看能否最4*4方格进行平铺。
    如何存入状态:4*4每个格子一一对应1~16的位置,有效的格子坐标转换到一维的二进制位置进行更新。(1<<?和二进制数字相或)平移操作就是把所有位置移动一下。旋转不过是对原字符串进行适当变化,然后把所有的变换后的有效状态存下来。
    如何遍历结果:将3个状态数字相或,然后看是否全是1即可,判断是否等于1<<(4*4)-1就行
要注意不能有重叠:任意两个状态数字不能相与必须为0

非常好的一道状态压缩题!!!

#include <bits/stdc++.h>
using namespace std;
const int SIZE=4;
void rotate(string s[]){//旋转函数(顺时针旋转)
	char tmp[SIZE][SIZE];
	for(int i=0;i<SIZE;i++){
		for(int j=0;j<SIZE;j++){
			tmp[j][SIZE-1-i]=s[i][j];//i为0时:tmp[0,1,2][2]=s[0][0,1,2]
		}//相当于横着的变成竖着的
	}
	for(int i=0;i<SIZE;i++){
		s[i]=string (tmp[i],tmp[i]+SIZE);//string函数:从第一个字符位置开始转换,长度位SIZE
	}
}
bool valid(int x){return x>=0&&x<SIZE;}
int get(string s[],int dx,int dy){
	int ret=0;
	for(int x=0;x<SIZE;x++){
		for(int y=0;y<SIZE;y++){
			if(s[x][y]=='#'){
				int xx=x+dx,yy=y+dy;
				if(!valid(xx)||!valid(yy)){//不能越界,函数重用嘛
					return -1;
				}
				ret |=1<<(xx*4+yy);//xx*4+yy是把每个对应格子给算成数字,然后和ret或运算修改对应位置(有1出1)
			}
		}
	}
	return ret;
}
vector<int>add(){
	vector<int>ret;//用于存放状态
	string s[SIZE];
	for(int i=0;i<SIZE;i++)cin>>s[i];//输入字符阵列
	
	for(int num=0;num<4;num++){//执行四个旋转操作
		for(int dx=-3;dx<=3;dx++){//执行平移操作,要注意的是不仅要向右平移,还要向左平移
			for(int dy=-3;dy<=3;dy++){//向上和下平移
				int v=get(s,dx,dy);//用一个数字来存下次时旋转和平移后的结果(1~16个1的状态,只需要16位即可最多2^16-1)
				if(v>=0){ret.push_back(v);
				}
			}
		}
		rotate(s);//旋转一下
	}
	return ret;//返回这个俄罗斯方块对应的全部状态
}
int main(){
	vector<int>mask[3];
	for(int id=0;id<3;id++){
		mask[id]=add();//输入字符阵列,获取四个方向,所有平移结果的状态数字,存入mask中
	}
	for(int x:mask[0]){//检查所有的情况有没有能成立的
		for(int y:mask[1]){
			for(int z:mask[2]){
				if((x|y|z)+1!=(1<<SIZE*SIZE))continue;//x|y|z就可以把1的位置全部标出来(要等于2^16-1嘛)
				if(x&y)continue;
				if(x&z)continue;
				if(z&y)continue;
				cout<<"Yes\n";
				return 0;
			}
		}
	}
	cout<<"No\n";
}

        

         

ABC Puzzle

326D

题意:给两个长n的仅由ABC组成的字符串s1,s2,是否在n*n阵列中满足以下条件,若满足则输出,不满足输出No

  条件1:每行每列仅包含一个A,一个B,一个C           (3<=n<=5)
  条件2:第i行最左边的字符恰好是s1的第i个字符
  条件3:第i列最上边的字符恰好是s2的第i个字符

输入样例:             输出样例:
5                             Yes
ABCBC                    AC..B
ACAAB                    .BA.C
                                C.BA.
                                BA.C.
                                ..CBA
思路:

一道比较恶心的dfs题。

说一下dfs思路吧:

依次放每个格子可以放.  也可以放A或B或C这四种选择。然后全部放完就检查一下即可。因为走错就要回溯,这最大妥妥的4^25根本过不去。首先主要到每行每列最多两个. 那么就要加以剪枝。

设置cnt[0][i][?]表示第i行已经有几个. 字符,cnt[1][i][?]对应第i列已经有几个. 字符?(剪枝1)

if(cnt[0][x]['.']<n-3&&cnt[1][y]['.']<n-3){//这是放"."的情况,每行列最多放两个,因为只放一次,所以if语句即可
	an[x][y]='.';
	cnt[0][x]['.']++;cnt[1][y]['.']++;
	dfs(x,y+1);
	cnt[0][x]['.']--;cnt[1][y]['.']--;
	}

 然后是放置3种字母。首先是看看同行是否已经有该字符。同样设置cnt[0][x][c]代表第x行是否有该字符,cnt[1][y][c]代表第y行是否有该字符。(剪枝2)

        接着是看是否和原字符串的对应位置匹配。第一个字符串对应x行,第二个字符串对应y列,我们如果swap后如果传入的是s[0][x]是0,那么自动返回1,这种情况就对应已经有了开头字符了。如果没有开头字符那就直接和开头字符比较看是否相同。(剪枝3)

for(char c='A';c<='C';c++){//放3种字母
	if(cnt[0][x][c]==0&&cnt[1][y][c]==0){//第x行y列是否都没有该字符
		if(match(s[0][x],c)&&match(s[1][y],c)){
//开头都确定,开头一个确定另一个不确定但相等,开头都不确定但都相等
			an[x][y]=c;
			char tmp=0,tmp2=0;
			swap(tmp,s[0][x]);//0和0交换(开头已经确定),0和非0交换(开头未确定变已确定)
			swap(tmp2,s[1][y]);
			cnt[0][x][c]++;cnt[1][y][c]++;
			dfs(x,y+1);
			cnt[1][y][c]--;cnt[0][x][c]--;//失败,回溯(回溯尽量去swap,这样更容易恢复状态)
			swap(tmp,s[0][x]);//交换回来
			swap(tmp2,s[1][y]);
			}
		}
	}

好了,经过以上的剪枝,这个dfs就能过去了 

#include <bits/stdc++.h>
using namespace std;
int n;
int cnt[2][5][128];//cnt[0][i][?]表示第i行已经有几个?字符(ASCII),cnt[1][i][?]对应相关列
char an[5][7];//答案阵列
string s[2];
bool match(char c1,char c2){
	if(!c1)return 1;//如果说传过来的s[0,1][?]对应第?行,列已经有开头字符了(将会传过来0),那就直接返回正确
	return c1==c2;//否则就去比较这两个字符
}
//void型dfs 中return其实可有可无,其实就相当于是函数的continue功能,是为了防止进入走后面的代码,引发错误!
//dfs中的标记变量,一定要设置为局部变量,避免被别的dfs给修改
void dfs(int x,int y){//其实每个格子都有4种选择,不见得非ABC就要回溯,一定要细心
	if(x==n){
		cout<<"Yes\n";
		for(int i=0;i<n;i++)cout<<an[i]<<'\n';
		exit(0);//任务完全直接结束
	}
	if(y==n){dfs(x+1,0);return ;}
	if(cnt[0][x]['.']<n-3&&cnt[1][y]['.']<n-3){//这是放"."的情况,每行列最多放两个,因为只放一次,所以if语句即可
		an[x][y]='.';
		cnt[0][x]['.']++;cnt[1][y]['.']++;
		dfs(x,y+1);
		cnt[0][x]['.']--;cnt[1][y]['.']--;
	}
	for(char c='A';c<='C';c++){、、放3种字母
		if(cnt[0][x][c]==0&&cnt[1][y][c]==0){//第x行y列是否都没有该字符
			if(match(s[0][x],c)&&match(s[1][y],c)){
//开头都确定,开头一个确定另一个不确定但相等,开头都不确定但都相等
				an[x][y]=c;
				char tmp=0,tmp2=0;
				swap(tmp,s[0][x]);//0和0交换(开头已经确定),0和非0交换(开头未确定变已确定)
				swap(tmp2,s[1][y]);
				cnt[0][x][c]++;cnt[1][y][c]++;
				dfs(x,y+1);
				cnt[1][y][c]--;cnt[0][x][c]--;//失败,回溯(回溯尽量去swap,这样更容易恢复状态)
				swap(tmp,s[0][x]);//交换回来
				swap(tmp2,s[1][y]);
			}
		}
	}
}
int main(){
	cin>>n;
	for(int i=0;i<2;i++)cin>>s[i];
	dfs(0,0);
	cout<<"No\n";
}

        

        

lnc的工资

326E

题意:Inc的工资:给出n面的骰子,i对应a[i]元。问最终获得钱的期望是多少(结果对998244353取模)

规则如下:起初x=0,掷出y(>x)则给出a[y]元,同时x变成y,重复操作,直到y(<=x)时结束游戏

思路:

我们先算出现i的概率:
对于第一次:必然是1/n;
第二次:只能从1~i-1过来,所以是(i-1)/n*(1/n),化简成(i-1)*1/n^2
第三次:前两次都恰好从1~i-1中选了两个数,所以是C(2,i-1)*1/n^3   依次类推

【算法每日一练]-dfs (保姆级教程 篇9) #俄罗斯方块 #ABC Puzzle #lnc的工资,bfsdfs,算法,数据结构,深度优先,图论,c++

然后所有概率相加:∑(i-1,k=0) (1/n)*C(k,i-1)*(1/n)^k    

根据二项式定理转成∑(i-1,k=0) ((n+1)/n)^(i-1) 文章来源地址https://www.toymoban.com/news/detail-811228.html

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=998244353;
ll qpow(ll a,ll b){
	ll res=1;a%=MOD;
	while(b){
		if(b&1)res=(res*a)%MOD;
		a=(a*a)%MOD;
		b>>=1;
	}
	return res%MOD;
}
ll niyuan(ll x){
	return qpow(x,MOD-2);
}
int main(){
	int n;cin>>n;
	ll nn=niyuan(n);//nn为n的逆元,相当于1/n
	ll now=nn;//now即为当前的概率,最开始now就是i=1的概率
	ll ans=0;
	for(int i=1;i<=n;i++){
		int x;cin>>x;//输入每个a[i]
		ans=(ans+now*x)%MOD;//累加每个a[i]的期望
		now=now*(n+1)%MOD*nn%MOD;//求下一个a[i]的概率,只需要多乘一次(n+1)/n,也就是(n+1)*nn即可
	}	
	cout<<ans<<'\n';
}

到了这里,关于【算法每日一练]-dfs (保姆级教程 篇9) #俄罗斯方块 #ABC Puzzle #lnc的工资的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 编写一个俄罗斯方块

    编写俄罗斯方块 思路。 1、创建容器数组,方块, 2、下落,左右移动,旋转,判断结束,消除。  定义一个20行10列的数组表示游戏区。初始这个数组里用0填充,1表示有一个方块,2表示该方块固定了, 然后随机出一个方块,操作左右转,触底变2后,再随机下一个方块,循

    2024年02月12日
    浏览(49)
  • pygame俄罗斯方块游戏

    1.安装python 2.引入游戏库pygame 3.引入随机数 俄罗斯方块初始形状 这里使用一个二维数组 用来标记俄罗斯相对应的方块形状 代码如下: 游戏移动方向是否可能判断 这里为了不让他出现穿墙,跨过方块下落 都做对应的碰撞判断 具体代码如下: 俄罗斯方块旋转变形代码实现 俄

    2024年02月08日
    浏览(43)
  • python制作俄罗斯方块

    作者简介 :一名后端开发人员,每天分享后端开发以及人工智能相关技术,行业前沿信息,面试宝典。 座右铭 :未来是不可确定的,慢慢来是最快的。 个人主页 :极客李华-CSDN博客 合作方式 :私聊+ 这个专栏内容 :BAT等大厂常见后端java开发面试题详细讲解,更新数目10

    2024年02月12日
    浏览(47)
  • c语言——俄罗斯方块

    俄罗斯方块是久负盛名的游戏,它也和贪吃蛇,扫雷等游戏位列经典游戏的⾏列。 《俄罗斯方块》(Tetris,俄文:Тетрис)是一款由俄罗斯人阿列克谢·帕基特诺夫于1984年6月发明的休闲游戏。 该游戏曾经被多家公司代理过。经过多轮诉讼后,该游戏的代理权最终被任天堂

    2024年02月05日
    浏览(44)
  • Javascript 俄罗斯方块 游戏代码

    本俄罗斯方块代码采用 JavaScript 脚本代码写成,简单易懂; 全代码采用静态类及静态变量成员组成; 全脚本通过实现代码全局配置 OLSFK.Options = {...} 定义方块起始坐标及定义各自的旋转点; 从初始化俄罗斯方块界面开始,再监听键盘事件;以及左右,向下及旋转动作判断,

    2024年02月07日
    浏览(47)
  • 俄罗斯方块小游戏开发

    代码图: 结果图:

    2024年02月04日
    浏览(54)
  • 用python制作俄罗斯方块

    代码如下,可以直接运行:

    2024年02月11日
    浏览(48)
  • 用Pygame写俄罗斯方块

    此文章参考的是吃饭超人的文章 首先我们先打开cmd输入如下令命 然后打开python或者pycharm 输入如下代码

    2024年02月12日
    浏览(34)
  • 俄罗斯方块游戏(C语言)

    简介:俄罗斯方块(Tetris)是一款经典的游戏,下面是用C语言实现俄罗斯方块的示例代码: code 这是一个非常简单的俄罗斯方块游戏,只有基本的方块形状和控制操作。如果想要更加完整的游戏体验,可以添加更多的方块形状、音效、背景音乐、计分系统等等。 分析 这份代

    2024年02月07日
    浏览(42)
  • python基础项目实战-俄罗斯方块

    一、俄罗斯方块游戏设计分析: 俄罗斯方块是一款风靡全球,从一开始到现在都一直经久不衰的电脑、手机、掌上游戏机产品,是一款游戏规则简单,但又不缺乏乐趣的简单经典小游戏,上手容易,适用范围广泛,人所共知。俄罗斯方块游戏基本规则是油4个小方块组成的7种不

    2024年02月12日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包