AcWing 1209. 带分数(对next_permutation的解释)
原题链接
简单
作者:
qiao
,
2022-04-06 20:54:42
,
所有人可见
,
阅读 183
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n;
int num[11];
int calc(int l, int r)
{
int res = 0;
for (int i = l; i <= r; i++)res = res * 10 + num[i];
return res;
}
int main()
{
int cnt = 0;
for (int i = 1; i <= 9; i++)num[i] = i;
cin >> n;
do
{
//枚举中间区间(分为三段,枚举出中间段,其余两段自然可得)
for (int i = 2; i <= 8; i++)
for (int j = i; j <= 8; j++)
{
int a = calc(1, i - 1);
int b = calc(i, j);
int c = calc(j + 1, 9);
// 注意判断条件,因为C++中除法是整除,所以要转化为加减乘来计算
if (c * (n - a) == b)cnt++;
}
} while (next_permutation(num+1,num+10));
cout <<cnt;
}
/*
next_permutation函数
组合数学中经常用到排列,这里介绍一个计算序列全排列的函数:next_permutation(start,end)
,和prev_permutation(start,end)。这两个函数作用是一样的,区别就在于前者求的是当前排列的下一个排列,
后一个求的是当前排列的上一个排列。至于这里的“前一个”和“后一个”,我们可以把它理解为序列的字典序的前后
,严格来讲,就是对于当前序列pn,他的下一个序列pn+1满足:不存在另外的序列pm,使pn<pm<pn+1.
next_permutation(首地址,首地址+长度)
作用:将区间内数组修改为下一个全排列(按照字典序),如果成功return 1 如果当前是最后一个则return 0
因为返回的是下一个,所以一般配合do while使用
*/