题目大意

按升序排列打印所有满足以下条件的长度为 NN 的整数序列。

  • 第 ii 个元素介于 11 和 RiR_i 之间。
  • 所有元素之和是 KK 的倍数。

数据范围

  • 1≤N≤81 \le N \le 8
  • 2≤K≤102 \le K \le 10
  • 1≤Ri≤51 \le R_i \le 5

思路解析

因为题目中的NN和 RiR_i 都很小，直接暴力搜索11~NN就好了。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
int n,k,r[100010],b[1000010];
void dfs(int u,int sum=0){//u表示填第几个数 sum 表示所有数的总和
	if(u==n+1){//所有数都填好了
		if(sum%k!=0) return; //如果所有数的和不是 k 的倍数那么就不输出
		for(int i=1;i<u;i++) cout<<b[i]<<' ';//输出答案
		cout<<endl;
		return;
	}
	for(int i=1;i<=r[u];i++){
		b[u]=i;//记录答案
		dfs(u+1,sum+i);//继续搜下一个
		b[u]=0;//还原
	}
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>r[i];
	dfs(1);//从第一个数开始搜索
	return 0;
}