深搜专题训练

已结束 OI 开始于: 2024-2-5 9:00 2.5 小时 主持人: 21

我是最帅的

B

#include<bits/stdc++.h>
using namespace std;

int n,m;
int h[20];
int p[20];
int a[20];
int cnt = 0;
void dfs(int k) {
	if (k>n) {
		for (int i = 2; i <= n ; i ++ )
		  if (abs(a[i]-a[i-1])>m) return ;
		if (abs(a[n]-a[1])>m) return ;
		cnt++;
		return ;
	}
	for (int i = 1; i <= n ; i ++ )
	   if (!p[i]) {
	   		a[k]=h[i];
	   		p[i]=true;
			dfs(k+1);
	   		p[i]=false;
	   } 
}
int main() {
	cin>>n>>m;
	for (int i = 1; i <= n ; i ++ ) cin>>h[i];
	dfs(1);
	cout<<cnt/n<<endl;
	return 0;
}

C

#include<bits/stdc++.h>
using namespace std;
int n,m;
bool a[20][20];
int c[20];
int cnt = 0;
void dfs(int k) {
	if (k>n) {
		cnt++;
		return ;
	}
	//1..k-1
	for (int i = 1; i <= 4 ; i ++ ) {
		bool flag=true;
		for (int j = 1; j < k ; j ++)
		   if (a[k][j]&&c[j]==i) flag=false;
		if (flag) {
			c[k]=i;
			dfs(k+1);
		}		  
	}
}
int main() {
	cin>>n>>m;
	for (int i = 1; i <= m ; i ++ ) {
		int x,y;cin>>x>>y;
		a[x][y]=a[y][x]=true;
	} 
	dfs(1);
	cout<<cnt<<endl;
	return 0;
}

D

#include<bits/stdc++.h>

using namespace std;

int n,m;
int a[11];
bool used[11];
int cnt = 0;
void DFS(int k) {
	if (k==n) {
		for (int i = 1; i <= n ; i ++ ) 
		   if (!used[i]) {
		   		if (m==a[i]) {
				   	cnt++;
					break;
				}
		   }
		return ;
	}
	for (int i = 1; i <= n ; i ++ )
	   if (used[i]==false) {
	   	  int j = i + 1;
	   	  while (j<=n&&used[j]) j ++;
	   	  if (j>n) break;
		  used[j]=true;
	   	  a[i]-=a[j];
	   	  DFS(k+1);
	   	  a[i]+=a[j];
	   	  used[j]=false;
	   }
}
int main() {
	cin>>n>>m;
	for (int i = 1; i <= n ; i ++ ) {
		cin>>a[i]; 
	}	
	DFS(1);
	cout<<cnt<<endl;
	return 0;
}
状态
已结束
规则
OI
题目
4
开始于
2024-2-5 9:00
结束于
2024-2-5 11:30
持续时间
2.5 小时
主持人
参赛人数
21