列公子

用户名：lielielie

访问量：10578

签　名：

等　　级
排　　名	1695
经　　验	2703
参赛次数	0
文章发表	20
年　　龄	0
在职情况	学生
学　　校	哈尔滨工程大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯路径之谜 DFS
浏览：132

1924题 - 01背包 - 动态规划 + 一维数组空间优化
浏览：535

你可能喜欢

A+B for Input-Output Practice (III) （C语言代码）

蓝桥杯 3000米排名预测 - DFS/全排列

　　作者: 列公子　　　　发表时间：2020-03-10 23:37:33 浏览：260　|　评论：0　

原题链接：蓝桥杯算法提高VIP-3000米排名预测

# [1478] 3000 米排名预测  DFS/全排列

## 完整代码 (AC)
```cpp
//
// 蓝桥杯题库 算法提高 1478 3000米排名预测
// DFS, 全排列
//
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 15;
int N, M;    // 选手数, 观众数
int arr[maxn];      // 存储当前的排列

int numAns = 0;             // 总方案数
int ans[100000][maxn];      // 合法的排列

int prediction[maxn][maxn];  // prediction[i][0] 预测的人数, 接着预测的排名, 最后为是否正确

bool check(const int p[]){
    // 遍历每个猜测
    for (int i = 0; i < M; i++) {
        int len = prediction[i][0];         // 预测的总人数
        int flag = prediction[i][len + 1];     // 是否预测正确

int r = 0, s = 1;       // s 指向排列, r 指向该预测序列
        int matched = 0;        // 匹配的数目

while (r < N && s <= len){
            if (matched == len){
                break;
            }
            if (p[r] == prediction[i][s]){
                matched ++;
                r++;
                s++;
            } else {
                while (p[r] != prediction[i][s] && r <= N)   // 指向排列的指针后移动
                    r++;
            }
        }

if (!flag && matched == len)    // 匹配了一个错误预测
            return false;
        else if (flag && matched != len){    // 未能匹配正确预测
            return false;
        }
    }
    return true;
}

void dfs(){
    for (int i = 0; i < N; i++)   // 初始化一个字典序最小的排列
        arr[i] = i;

do{     // 全排列
        if (check(arr)){
            for (int i = 0; i < N; i++)
                ans[numAns][i] = arr[i];
            numAns++;
        }
    } while (next_permutation(arr, arr + N));
}

int main(){
    scanf("%d%d", &N, &M);
    memset(prediction, 0, sizeof(prediction));

for (int i = 0; i < M; i++){
        int total;
        scanf("%d", &total);    // 第一个是预测的人数
        prediction[i][0] = total;

for (int j = 1; j <= total+1; j++)      // 依次是预测的位置, 最后是 正确与否
            scanf("%d", &prediction[i][j]);
    }

dfs();
	
    printf("%d", numAns);
    for (int i = 0; i < numAns; i++) {
        printf("\n");
        for (int j = 0; j < N; j++)
            printf("%d ", ans[i][j]);
    }
    return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

列公子

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C++代码）

计算质因子（C++代码）100以内质数直接打表就好了

整人!!

蓝桥杯 3000米排名预测 - DFS/全排列

评论区

精彩推荐

人见人爱A+B （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C++代码）

校门外的树（C语言代码）

C语言训练-计算1977！* （C++代码）

数组输出（C语言代码）错误？？？

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

WU-输出正反三角形（C++代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

列公子

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C++代码）

计算质因子 （C++代码）100以内质数直接打表就好了

整人!!

蓝桥杯 3000米排名预测 - DFS/全排列

评论区

精彩推荐

人见人爱A+B （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C++代码）

校门外的树 （C语言代码）

C语言训练-计算1977！* （C++代码）

数组输出 （C语言代码）错误？？？

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

WU-输出正反三角形 （C++代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

计算质因子（C++代码）100以内质数直接打表就好了

　　评论区

校门外的树（C语言代码）

数组输出（C语言代码）错误？？？

WU-输出正反三角形（C++代码）