首页 > 试题广场 >

如图所示，平面上有两条平行的线段，上面的线段有A0~A3 4

[填空题]

如图所示，平面上有两条平行的线段，上面的线段有A0~A3 4个点，下面的线段有B0到B5 6个点，现在需要把所有的点都连接起来，有如下约束：

每个端点，都至少有一条到另一平行线上端点的连线；
连线之间不能有交叉（除了端点，线与线之间不能有连接的地方）；

请问，总共有多少种连法？1

查看正确选项

糊涂的斜杠青年在迎接offer

#include<iostream>
using namespace std;
int main() {
	int num = 0;
	for (int a = 0; a < 6; a++) {          // 从A0开始连，有6种连法
		for (int b = a; b < 6; b++) {      // A0连好后，连A1
			for (int c = b; c < 6; c++) {  // A1连好后，连A2
				num++;                     // A3就不需要管了，数量+1
			}
		}
	}
	cout << num << endl;
	return 0;
}

如果先从A0开始连，有六种连接方式：B0

B0、B1

B0、B1、B2

B0、B1、B2、B3

B0、B1、B2、B3、B4

B0、B1、B2、B3、B4、B5

发表于 2020-05-26 11:46:44 回复(6)

何人听我楚狂声的小迷弟

试了两种搜索，答案都是231..是我题意没理解对吗

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+5;
typedef long long ll;

int ans=0;
int A[4],B[6];
int cnt;
void dfs(int a,int b,int last){ //上边第a个尝试连接第b个 last是上一次a连接的b是哪个
    if(a==4){
        if(B[0]&&B[1]&&B[2]&&B[3]&&B[4]&&B[5]) ans++; //所有a都有连接且所有b都有被连接
        return;
    }
    if(b==6){
        if(last!=-1) dfs(a+1,last,-1); //当前a对下面所有b都尝试过且有连接，连接a+1
        return;
    }

    dfs(a,b+1,last);

    A[a]++,B[b]++;
    dfs(a,b+1,b);
    A[a]--,B[b]--;
}

int main(){
    dfs(0,0,-1);
    printf("%d\n",ans);
    return 0;
}

发表于 2020-05-14 19:00:42 回复(3)