李华

用户名：2645479600

访问量：17684

签　名：

等　　级
排　　名	471
经　　验	4572
参赛次数	2
文章发表	22
年　　龄	22
在职情况	学生
学　　校	华软、江理
专　　业	电信、计算机

　　自我简介：

欢迎探讨

TA的其他文章

蓝桥杯历届试题-国王的烦恼-题解(C语言 with STL)---参考啊哈算法,文字解释详细
浏览：1407

蓝桥杯2013年第四届真题-带分数-题解(C语言代码) ------------纯C语言,思路非常简单
浏览：1132

蓝桥杯2017年第八届真题-合根植物-题解(C语言代码)-----C语言
浏览：339

你可能喜欢

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

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

蓝桥杯算法提高VIP-3000米排名预测-题解(C++代码)---求出全部排列，逐个判断

　　作者: 李华　　　　发表时间：2020-03-24 22:05:33 浏览：574　|　评论：3　

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

解题思路：
1.**枚举全部排名的排列：**分别对每个排列进行判断
2**.每个排列判断方法是：**m个人说了m句话，该排列必须符合这全部的m句话，如果违反其中一句，就直接判错。
3**.判断是否符合某句话的方法：**
当说的是正确的时候，即c=1的时候。比如他说了4 1 2，那么我们取出当前排列'4''1''2'的位置，取出的位置必须满足每个数字的位置小于后一个数字的位置，才能说明该排列正确(末位数字除外,因为末位数字没有后一个数字)。因为如果'4'的位置比'1'的位置大的话，说明'4'在后面，和说出的话不符
当说的是错误的时候，即c=0的时候。比如他说了2 4 3，同理取出当前排列'2'''4''3'的位置，取出的位置存进一个数组，存好这三个数的位置后，这个数组如果是递增的，说明这种情况完美符合说错的话，不符。原因和上面同理

---
注意：
1.STL库有现成的next_permutation可以枚举全部排列，也可以用dfs手写全排列，时间复杂度会稍高一些，也可以跑得过。
**有疑问可以私信或评论。**
```cpp
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,c,flag[15],t,a[15],ans;
vector<int> vec[15];
vector<int> result[21000];
void a_init()
{
	for(int i=0;i<n;i++)
	{
		a[i]=i;
	}
}
int up_(vector<int> find_pos)	//判断数组是否严格递增 
{
	for(int i=0;i<find_pos.size()-1;i++)
	{
		if(find_pos[i]>find_pos[i+1])	return 0;
	}
	return 1;
}
int find(int item)
{
	for(int i=0;i<n;i++)
	{
		if(a[i]==item)
		return i;
	}
}
int check_right()	//判断说的是正确的时候，该排列是否符合情况 
{
	int find_a,find_b;
	for(int i=0;i<m;i++)	//如果说的是对的
	{
		if(flag[i]==1)
		{
			for(int j=0;j<vec[i].size()-1;j++)
			{
				find_a=find(vec[i][j]);	//取出说的数字在数组中的位置 
				find_b=find(vec[i][j+1]);
				if(find_a>find_b)	//如果说的前数字的位置在说的后数字的位置之后，说明是错误的
				{
					return 0;
				} 
			}
		}
	} 
	return 1;
}
int check_false()	//判断说的是错的时候，该排列是否符合情况 
{
	vector<int> find_pos;
	int temp,judge=0;
	for(int i=0;i<m;i++)	//如果说的是错误的,那么这种情况不可能出现 
	{
		if(flag[i]==0)
		{
			for(int j=0;j<vec[i].size();j++)
			{
				temp=find(vec[i][j]);
				find_pos.push_back(temp);	//取出在数组中的实际位置，如果取出的数字是完美的递增，说明符合说错的情况，这种情况是不能出现的 
			}
			if(up_(find_pos))	//如果完美递增，直接判错 
			return 0;
		}
		find_pos.clear();
	} 
	return 1;
}
int main()
{
	scanf("%d %d",&n,&m);
	a_init();
	for(int i=0;i<m;i++)	//m行观众 
	{
		scanf("%d",&c);
		for(int j=0;j<c;j++)	//将输入的数据先存档再处理 
		{
			scanf("%d",&t);
			vec[i].push_back(t);
		}
		scanf("%d",&flag[i]);
	}
	do	//枚举全部的排列，逐个判断，排列情况最多10！, 不会超时 
	{
		if(check_right()&&check_false())	//如果符合才存进结果数组。代码最后才打印结果数组 
		{
			for(int i=0;i<n;i++)
			{
				result[ans].push_back(a[i]);
			}
			ans++;
		} 
	}while(next_permutation(a,a+n));	//生成全排列 
	printf("%d\n",ans);
	for(int i=0;i<ans;i++)
	{
		for(int j=0;j<n;j++)
		{
			printf("%d ",result[i][j]);
		}
		printf("\n");
	}
	return 0;
}
```

0.0分

10 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

　　评论区

早起床

这就是思维大佬吗，把问题的实现这么简单

2022-10-09 20:19:54

JakeLin

太棒了，谢谢兄弟！

2020-03-25 21:45:53

Two.

可以

2020-03-24 22:20:56

李华

TA的其他文章

你可能喜欢

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

点我有惊喜！你懂得！

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

K-进制数（C++代码）

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

蓝桥杯算法提高VIP-3000米排名预测-题解(C++代码)---求出全部排列，逐个判断

评论区

精彩推荐

WU-输出九九乘法表（C++代码）

用筛法求之N内的素数。（C语言代码）

Hello, world! （C++代码）

C语言训练-自由落体问题（C语言代码）

K-进制数（C语言描述，蓝桥杯）

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

C二级辅导-阶乘数列（C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

输入输出格式练习（C语言代码）

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

李华

TA的其他文章

你可能喜欢

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

点我有惊喜！你懂得！

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

K-进制数 （C++代码）

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

蓝桥杯算法提高VIP-3000米排名预测-题解(C++代码)---求出全部排列，逐个判断

评论区

精彩推荐

WU-输出九九乘法表 （C++代码）

用筛法求之N内的素数。 （C语言代码）

Hello, world! （C++代码）

C语言训练-自由落体问题 （C语言代码）

K-进制数 （C语言描述，蓝桥杯）

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

C二级辅导-阶乘数列 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

输入输出格式练习 （C语言代码）

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

K-进制数（C++代码）

　　评论区

WU-输出九九乘法表（C++代码）

用筛法求之N内的素数。（C语言代码）

C语言训练-自由落体问题（C语言代码）

K-进制数（C语言描述，蓝桥杯）

C二级辅导-阶乘数列（C语言代码）

输入输出格式练习（C语言代码）