14015problem I 方案数
程序员文章站
2022-03-15 11:39:06
14015problem I 方案数计时器游戏结束后,晨晨的同学明明取了其中的K个计时器设计出拼数字游戏:明明和晨晨各自把K个计时器排成一行,看谁拼出的数最大。例如:有K=3个计时器,上面数字分别是31,3,331,两人拼的方案分别是:明明拼的数字是333131,晨晨拼的数字是331313,显然明明赢。明明掌握了拼出最大值的核心算法,晨晨下决心也要研究。不过她首先要编程统计这K个计时器能拼出多少种不同的方案?注意,现在的计时器更先进,可以显示4位数字。输入第一行:1个整数K。(1 ≤ K...
14015problem I 方案数
计时器游戏结束后,晨晨的同学明明取了其中的K个计时器设计出拼数字游戏:明明和晨晨各自把K个计时器排成一行,看谁拼出的数最大。例如:有K=3个计时器,上面数字分别是31,3,331,两人拼的方案分别是:
明明拼的数字是333131,晨晨拼的数字是331313,显然明明赢。
明明掌握了拼出最大值的核心算法,晨晨下决心也要研究。不过她首先要编程统计这K个计时器能拼出多少种不同的方案?
注意,现在的计时器更先进,可以显示4位数字。
输入
第一行:1个整数K。(1 ≤ K ≤ 4)
第二行K个整数:表示K个计时器上的数。(所有数均为大于0小于10000的整数)
输出
一个整数,表示拼成不同数的方案数。
样例输入 Copy
3
31 3 331
样例输出 Copy
5
解题思路
- 首先利用搜索与回溯的方法求出所有组合数。
- 减去重复的个数。
附上代码
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
int n,a[100],b[100],c[100],v[100],k,len,t,x,i,ans; //a数组放n个输入的值,b数组为搜索条件,0可搜,1不可搜
//c数组是暂存a中的值, v数组用于记录去重的下标
long long d[100];
char s[100][100];
long long fun (long long x){ //判断位数
int t=0;
do{
t++;
x=x/10;
}while(x);
return t;
}
void dfs(int x){
for(int i=1;i<=n;i++){ //搜索种类个数
if(x==n+1) { t=0; //如果搜索的个数满足要求,将该次搜索的值放到d数组中
for(int i=1;i<=n;i++)
{
t+=fun(c[i]); //计算的时候先确定每个数的位数
d[k]=d[k]+pow(10,len-t)*c[i];
}
k++; //记录有多少种组合
return;
}
else {
if(b[i]==0){ //如果当前i没用 才可搜索
c[x]=a[i]; //暂存到c数组中方便计算每次的组合
b[i]=1;
dfs(x+1); //搜索
b[i]=0; //回溯
}
}
}
}
int main(){
memset(b,0,sizeof(int));
scanf("%d",&n);
for(i=1;i<=n;i++)
{scanf("%d",&a[i]); //输入值
len+=fun(a[i]); //计算n个数的总位数
}
dfs(1); //搜索
ans=k;
for(int i=0;i<k;i++){
for(int j=0;j<k;j++)
if(d[i]==d[j]&&i!=j&&v[j]==0&&v[i]==0){
ans--;
v[j]=1;
}//每次找到一个相同的总组合数减1,并且v[j]=1
}
printf("%lld",ans);
return 0;
}
如果实在不理解搜索,可以尝试一下全排列,这题搜索思路与那题一致。
本文地址:https://blog.csdn.net/qq_52273733/article/details/110137218
推荐阅读
-
1.2万Intel i7-8086K信仰主机配置推荐 高端超频水冷电脑装机方案
-
i7-6700/GTX1080高端电脑配置推荐: 高端轻奢DIY装机方案
-
春节爽玩游戏 6500元i5 8400六核独显吃鸡游戏配置推荐方案
-
畅玩各种游戏大作 8000元i7-7700K配GTX1070电脑主机配置方案推荐
-
主流装机配置方案 3500元i5-7500配GTX1050游戏电脑配置清单推荐
-
新游戏平台装机方案 4500元i3-7350K配GTX1060电脑配置清单推荐
-
i3-7100配什么主板及显卡好 Intel酷睿i3-7100装机指南(附装机方案)
-
2017最强CPU显卡结合 2.6万元i9-7900X/GTX1080Ti最牛主机配置方案推荐
-
leetcode1193. 每月交易 I 编写一个 sql 查询来查找每个月和每个国家/地区的事务数及其总金额、已批准的事务数及其总金额。
-
643 LeetCode 子数组最大平均数I