DFS

Problem 1

题目描述
给定M根小木棍,每根木棍有各自的长度,能否把它们全部用上来围成一个正方形?其中4≤M≤20,每根木棍的长度是1到10000之间的整数

输入格式
第一行是一个整数T表示测试数据的组数。 对于每组测试数据,输入一行,包含M+1个整数,第一个整数表示M,接下来M个整数表示M个木棍的长度

输出格式
对于每组数据一行,如果能够围成正方形 输出“yes” 否则输出“no”

输入输出样例

输入

1
2
3
4
3
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5

输出

1
2
3
yes
no
yes

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

int len[25],v[25],m,l;

bool dfs(int p,int g,int d){
if(d==3) return true;
for(int i=p; i>=0; i--){
if(!v[i]){
v[i]=1;
int t=g+len[i];
if(t<l){
if(dfs(p-1,t,d))
return true;
}
else if(t==l){
if(dfs(m-1,0,d+1))
return true;
}
else{
v[i]=0;
}
}
}
return false;
}

int main(){
int t;
scanf("%d",&t);
while(t--){
int sum=0;
scanf("%d",&m);
for(int i=0; i<m; i++){
scanf("%d",&len[i]);
sum+=len[i];
}
sort(len,len+m);
memset(v,0,sizeof(v));
l=sum/4;
if(sum%4!=0 || m<4 || l<len[m-1]) printf("no\n");
else if(dfs(m-1,0,0)) printf("yes\n");
else printf("no\n");
}
return 0;
}

Problem 2

题目描述
小埋会告诉你一盘扫雷,用一个 n*m 的矩阵表示,1 是雷 ,0 不是雷,请你告诉她这盘扫雷的 3bv 。

周围八格没有“雷”且自身不是“雷”的方格称为“空格”,周围八格有“雷”且自身不是“雷”的方格称为“数字”,由“空格”组成的八连通块称为一个“空”。3bv = 周围八格没有“空格”的“数字”个数 + “空”的个数。

输入格式
第一行有两个整数 n 和 m,代表这盘扫雷是一个 n*m 的矩阵。

后面的 n 行每行有 m 个整数,表示这个矩阵,每个数字为 0 或 1,1 代表是雷,0 代表不是雷。

输出格式
一个整数,代表这盘扫雷的 3bv 。

输入

1
2
3
4
5
6
7
8
9
8 8
0 0 0 1 1 0 0 0
1 0 0 1 0 0 0 1
1 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0

输出

1
13

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
using namespace std;

int a[1000][1000],v[1000][1000],bv3,n,m;
int x[8]={-1,-1,-1,0,0,1,1,1},y[8]={-1,0,1,-1,1,-1,0,1};

bool noBlank(int l,int r){ //周围八格没有“空格”的
for(int i=0; i<8; i++){
int ll=l+x[i]; int rr=r+y[i];
if(ll>=0 && ll<n && rr>=0 && rr<m && !a[ll][rr])
return 0;
}
return 1;
}

void incr(int l,int r){ //让“雷”周围八格中不是“雷”的都增加1
for(int i=0; i<8; i++){
int ll=l+x[i]; int rr=r+y[i];
if(ll>=0 && ll<n && rr>=0 && rr<m && a[ll][rr]!=-1)
a[ll][rr]++;
}
}

void dfs(int l,int r){
for(int i=0; i<8; i++){
int ll=l+x[i]; int rr=r+y[i];
if(ll>=0 && ll<n && rr>=0 && rr<m && !a[ll][rr] && !v[ll][rr]){ //判断是否越界,用v判重
v[ll][rr]=1;
dfs(ll,rr);
}
}
}

int main(){
scanf("%d%d",&n,&m);
for(int i=0; i<n; i++)
for(int j=0; j<m; j++){
scanf("%d",&a[i][j]);
if(a[i][j])
a[i][j]=-1;
}
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
if(a[i][j]==-1)
incr(i,j);
for(int i=0; i<n; i++)
for(int j=0; j<m; j++){
if(a[i][j] && a[i][j]!=-1 && noBlank(i,j)) //周围八格没有“空格”的“数字”的个数
bv3++;
}
for(int i=0; i<n; i++)
for(int j=0; j<m; j++){
if(!a[i][j] && !v[i][j]){ //“空”的个数
bv3++;
dfs(i,j);
}
}
printf("%d\n", bv3);
return 0;
}

Problem 3

将数字 1…9 填入一个 3×3 的九宫格中,使得格子中每一横行和的值全部相等,每一竖列和的值全部相等。请你计算有多少种填数字的方案。

next_permutation

https://www.cnblogs.com/eudiwffe/p/6260699.html

https://blog.csdn.net/c18219227162/article/details/50301513

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <algorithm>
using namespace std;

int a[10];

int main(){
int ans = 0;
for(int i = 1; i <= 9; i++)
a[i] = i;
do{
if(a[1] + a[2] + a[3] == a[4] + a[5] + a[6]
&& a[4] + a[5] + a[6] == a[7] + a[8] + a[9]
){
if(a[1] + a[4] + a[7] == a[2] + a[5] + a[8]
&& a[2] + a[5] + a[8] == a[3] + a[6] + a[9]
)
ans++;
}
}while(next_permutation(a + 1, a + 10));
printf("%d\n", ans);
return 0;
}
//72

Problem 4

右侧代码是将 6 个整数按照任意顺序组合到一起,计算能组合出的最大数字。

例如:4123,25,66 组合到一起就是 66412325。

请阅读程序补全代码,实现这个功能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>
#include <algorithm>

long long test(int a[], int n) {
long long ret = 0;
for (int i = 0; i < n; ++i) {
int tp = a[i];
int j = 1;
while(tp) {
j *= 10;
tp /= 10;
}
ret = ret * j + a[i];
}
return ret;
}

long long f(int a[], int k) {
if (k == 6) {
return test(a, k);
}
long long ret = 0;
for(int i = k; i < 6; ++i) {
int t = a[k];
a[k] = a[i];
a[i] = t;
ret = std::max(ret, f(a, k + 1));
t = a[k];
a[k] = a[i];
a[i] = t;
}
return ret;
}

int main() {
int a[6] = {517, 283, 429, 65, 6566, 32};
printf("%lld\n", f(a, 0));
return 0;
}

Author

preccrep

Posted on

2020-07-17

Updated on

2020-07-20

Licensed under

You need to set install_url to use ShareThis. Please set it in _config.yml.
You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

Comments

You forgot to set the shortname for Disqus. Please set it in _config.yml.
You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.