【算法每日一練]-dfs （保姆級教程篇9） #俄羅斯方塊 #ABC Puzzle #lnc的工資

這篇具有很好參考價值的文章主要介紹了【算法每日一練]-dfs （保姆級教程篇9） #俄羅斯方塊 #ABC Puzzle #lnc的工資。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

今日知識點：

兩兩點匹配問題，注意去重方式的dfs的寫法(組內(nèi)升序即可)

二維圖形的狀態(tài)壓縮，存下所有的合法狀態(tài)然后暴力遍歷

dfs的優(yōu)化剪枝

二項式定理

最大邊權(quán)和?

俄羅斯方塊

ABC Puzzle

lnc的工資

????????

?????????

最大邊權(quán)和?

318D

題意：給你n個點的帶權(quán)w的完全無向圖（第1個點有n-1條邊，第2個點有n-2條……）問你相互沒有重點的所有邊最大權(quán)值和是多少？? ? ?n<=16; W<=10^9 ?

舉個例子：比如n=4，有(1,2)(1,3)(1,4)(2,3)(2,4)(3,4)的權(quán)值。搭配有:(1,2)(3,4)； (1,3)(2,4)； (1,4)(2,3)其中權(quán)值和最大的就是答案。

思路：

看似是一道跑圖題，實則就是一道配對題（你細(xì)品這個完全無向圖，在dfs時候完全沒有跑圖的影子）。如果選了一個點，那么無論匹配那個點，都會導(dǎo)致剩余n-2各點，剩下的點的選擇就會越來越少：故有15*13*11*9*7*5*3*1=2027025種答案，暴力完全能過。

先說一下這個dfs函數(shù)：

第一：是ans的獲?。?/p>
每遞歸一次就獲取一次。不用先存起來再求。免去了回溯的存數(shù)和刪數(shù)操作。

第二：是先dfs(u+1,sum)，再if(vis[u]) return 。

順序不要寫反。前面是不選此數(shù)（跳過此數(shù)去選別的數(shù)作為起點）；后面的是此數(shù)已被選過，剩余的操作(選取終點)不能再執(zhí)行。

第三：是for循環(huán)中的dfs(u+1,sum+a)。

說明我們是已經(jīng)去重的，因為u作起點傳進(jìn)來，而for是從u+1開始找終點的。所以終點一定比起點大，就保證了組內(nèi)的無重復(fù)性。然后我們再保證起點u一定是單增的。那么所有組就不可能再有重復(fù)的。

void dfs(ll u,ll sum){//u是起點編號，起點編號必須單增。sum和當(dāng)前權(quán)值和。
	ans=max(ans,sum);//處理一次獲取一次答案，沒必要全部選完后再獲取答案
	if(u==n+1)return ;//處理越界：因為下一句就是無條件dfs
	dfs(u+1,sum);//這是當(dāng)前點不選對應(yīng)的情況，因為我們題上可能會給出奇數(shù)點，必然有個點選不上
	if(vis[u]) return ;
	for(int i=u+1;i<=n;i++){//找到可以匹配的另外點，也就是終點i
		if(vis[i])continue;
		vis[u]=1;vis[i]=1;//起點終點同時被打標(biāo)記
		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是層數(shù)，sum和當(dāng)前權(quán)值和。沒有必要去重，重復(fù)就重復(fù)吧
	ans=max(ans,sum);//處理一次獲取一次答案，沒必要全部選完后再獲取答案
	if(u==n+1)return ;//處理越界：因為下一句就是無條件dfs
	dfs(u+1,sum);//這是當(dāng)前點不選對應(yīng)的情況，因為我們題上可能會給出奇數(shù)點，必然有個點選不上
	if(vis[u]) return ;
	for(int i=u+1;i<=n;i++){//找到可以匹配的另外點
		if(vis[i])continue;//是否已經(jīng)被匹配
		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代碼     千萬不要學(xué)
void dfs(int u,int cnt){//dfs要一次處理一層，一次處理兩層的話，萬一一共奇數(shù)層怎么辦
	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個俄羅斯方塊，問是否可以經(jīng)過旋轉(zhuǎn)，平移操作恰好拼滿整個4*4格子？不能重疊和越界。

輸入樣例：

【算法每日一練]-dfs （保姆級教程篇9） #俄羅斯方塊 #ABC Puzzle #lnc的工資,bfsdfs,算法,數(shù)據(jù)結(jié)構(gòu),深度優(yōu)先,圖論,c++

樣例解釋?

【算法每日一練]-dfs （保姆級教程篇9） #俄羅斯方塊 #ABC Puzzle #lnc的工資,bfsdfs,算法,數(shù)據(jù)結(jié)構(gòu),深度優(yōu)先,圖論,c++

思路：

首先是如何存儲圖形以及變化后的圖形，當(dāng)然不僅要方便變換還要方便最后檢查。然后就想到了狀態(tài)壓縮，一共最多16格子，最多需要16位就行。
也就是最大用2^16-1的數(shù)字即可表示這種狀態(tài)，然后對3個俄羅斯方塊一一組合遍歷看看能否最4*4方格進(jìn)行平鋪。
? ? 如何存入狀態(tài)：4*4每個格子一一對應(yīng)1~16的位置，有效的格子坐標(biāo)轉(zhuǎn)換到一維的二進(jìn)制位置進(jìn)行更新。（1<<?和二進(jìn)制數(shù)字相或）平移操作就是把所有位置移動一下。旋轉(zhuǎn)不過是對原字符串進(jìn)行適當(dāng)變化，然后把所有的變換后的有效狀態(tài)存下來。
?? ?如何遍歷結(jié)果：將3個狀態(tài)數(shù)字相或，然后看是否全是1即可，判斷是否等于1<<(4*4)-1就行
要注意不能有重疊：任意兩個狀態(tài)數(shù)字不能相與必須為0

非常好的一道狀態(tài)壓縮題?。。?/p>

#include <bits/stdc++.h>
using namespace std;
const int SIZE=4;
void rotate(string s[]){//旋轉(zhuǎn)函數(shù)（順時針旋轉(zhuǎn)）
	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]
		}//相當(dāng)于橫著的變成豎著的
	}
	for(int i=0;i<SIZE;i++){
		s[i]=string (tmp[i],tmp[i]+SIZE);//string函數(shù)：從第一個字符位置開始轉(zhuǎn)換，長度位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)){//不能越界，函數(shù)重用嘛
					return -1;
				}
				ret |=1<<(xx*4+yy);//xx*4+yy是把每個對應(yīng)格子給算成數(shù)字，然后和ret或運算修改對應(yīng)位置（有1出1）
			}
		}
	}
	return ret;
}
vector<int>add(){
	vector<int>ret;//用于存放狀態(tài)
	string s[SIZE];
	for(int i=0;i<SIZE;i++)cin>>s[i];//輸入字符陣列
	
	for(int num=0;num<4;num++){//執(zhí)行四個旋轉(zhuǎn)操作
		for(int dx=-3;dx<=3;dx++){//執(zhí)行平移操作，要注意的是不僅要向右平移，還要向左平移
			for(int dy=-3;dy<=3;dy++){//向上和下平移
				int v=get(s,dx,dy);//用一個數(shù)字來存下次時旋轉(zhuǎn)和平移后的結(jié)果（1~16個1的狀態(tài)，只需要16位即可最多2^16-1）
				if(v>=0){ret.push_back(v);
				}
			}
		}
		rotate(s);//旋轉(zhuǎn)一下
	}
	return ret;//返回這個俄羅斯方塊對應(yīng)的全部狀態(tài)
}
int main(){
	vector<int>mask[3];
	for(int id=0;id<3;id++){
		mask[id]=add();//輸入字符陣列，獲取四個方向，所有平移結(jié)果的狀態(tài)數(shù)字，存入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的位置全部標(biāo)出來（要等于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根本過不去。首先主要到每行每列最多兩個. 那么就要加以剪枝。

設(shè)置cnt[0][i][?]表示第i行已經(jīng)有幾個. 字符，cnt[1][i][?]對應(yīng)第i列已經(jīng)有幾個. 字符？（剪枝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種字母。首先是看看同行是否已經(jīng)有該字符。同樣設(shè)置cnt[0][x][c]代表第x行是否有該字符，cnt[1][y][c]代表第y行是否有該字符。（剪枝2）

????????接著是看是否和原字符串的對應(yīng)位置匹配。第一個字符串對應(yīng)x行，第二個字符串對應(yīng)y列，我們?nèi)绻鹲wap后如果傳入的是s[0][x]是0，那么自動返回1，這種情況就對應(yīng)已經(jīng)有了開頭字符了。如果沒有開頭字符那就直接和開頭字符比較看是否相同。（剪枝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交換（開頭已經(jīng)確定），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，這樣更容易恢復(fù)狀態(tài)）
			swap(tmp,s[0][x]);//交換回來
			swap(tmp2,s[1][y]);
			}
		}
	}

好了，經(jīng)過以上的剪枝，這個dfs就能過去了?

#include <bits/stdc++.h>
using namespace std;
int n;
int cnt[2][5][128];//cnt[0][i][?]表示第i行已經(jīng)有幾個？字符(ASCII)，cnt[1][i][?]對應(yīng)相關(guān)列
char an[5][7];//答案陣列
string s[2];
bool match(char c1,char c2){
	if(!c1)return 1;//如果說傳過來的s[0,1][?]對應(yīng)第？行，列已經(jīng)有開頭字符了（將會傳過來0），那就直接返回正確
	return c1==c2;//否則就去比較這兩個字符
}
//void型dfs 中return其實可有可無，其實就相當(dāng)于是函數(shù)的continue功能，是為了防止進(jìn)入走后面的代碼，引發(fā)錯誤！
//dfs中的標(biāo)記變量，一定要設(shè)置為局部變量，避免被別的dfs給修改
void dfs(int x,int y){//其實每個格子都有4種選擇，不見得非ABC就要回溯，一定要細(xì)心
	if(x==n){
		cout<<"Yes\n";
		for(int i=0;i<n;i++)cout<<an[i]<<'\n';
		exit(0);//任務(wù)完全直接結(jié)束
	}
	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交換（開頭已經(jīng)確定），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，這樣更容易恢復(fù)狀態(tài)）
				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對應(yīng)a[i]元。問最終獲得錢的期望是多少（結(jié)果對998244353取模）

規(guī)則如下：起初x=0，擲出y(>x)則給出a[y]元，同時x變成y，重復(fù)操作，直到y(tǒng)(<=x)時結(jié)束游戲

思路：

我們先算出現(xiàn)i的概率：
對于第一次：必然是1/n；
第二次：只能從1~i-1過來，所以是(i-1)/n*(1/n)，化簡成(i-1)*1/n^2
第三次：前兩次都恰好從1~i-1中選了兩個數(shù)，所以是C(2,i-1)*1/n^3 ? 依次類推

【算法每日一練]-dfs （保姆級教程篇9） #俄羅斯方塊 #ABC Puzzle #lnc的工資,bfsdfs,算法,數(shù)據(jù)結(jié)構(gòu),深度優(yōu)先,圖論,c++

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

根據(jù)二項式定理轉(zhuǎn)成∑(i-1,k=0) ((n+1)/n)^(i-1)?文章來源地址http://www.zghlxwxcb.cn/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的逆元，相當(dāng)于1/n
	ll now=nn;//now即為當(dāng)前的概率，最開始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';
}

到了這里，關(guān)于【算法每日一練]-dfs （保姆級教程篇9） #俄羅斯方塊 #ABC Puzzle #lnc的工資的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！