CoreJava IntelliJ IDEA idea离线安装 LVS golang VMware oracle oauth seo git视频 bootstrap文件上传样式 idea整理代码 oracle连接字符串 websocket库 flutter优缺点 python中的for循环 python安装 python如何定义变量 python基础代码 java包 java的继承 java接口怎么写 java终止线程 java流程 摩尔斯电码翻译器 电脑必备软件排行榜 navicat注册机 电脑密码查看器 dep 美国地址生成器 linux运维之道 社区网格化管理平台 c4d文字 灰色按钮激活精灵 上单塞拉斯 深入解析windows操作系统 qq黑客软件 方正徐静蕾字体 炫舞爱的惊喜 寂静城
当前位置: 首页 > 学习教程  > 编程语言

AcWing 1209. 带分数【DFS】【枚举】

2020/10/8 20:14:40 文章标签:

题目链接:AcWing 1209. 带分数 100 可以表示为带分数的形式:100369258/714 还可以表示为:100823546/197 注意特征:带分数中,数字 1∼9 分别出现且只出现一次(不包含 0)。 类似这样的带分数&…

题目链接:AcWing 1209. 带分数

100 可以表示为带分数的形式:100=3+69258/714

还可以表示为:100=82+3546/197

注意特征:带分数中,数字 1∼9
分别出现且只出现一次(不包含 0)。

类似这样的带分数,100有 11种表示法。

输入格式
一个正整数。

输出格式
输出输入数字用数码 1∼9
不重复不遗漏地组成带分数表示的全部种数。

数据范围
1≤N<106

输入样例1:
100

输出样例1:
11

输入样例2:
105

输出样例2:
6

程序说明:

先求出1~9的全排列,然后划分成三段(隔板法),判断每段是否满足要求。

代码如下:

#include <iostream>
using namespace std;

int a[10], st[10], n, res;

int cal(int l, int r) {
    int t = 0;
    for(int i = l; i <= r; i++)
        t = t * 10 + a[i];
    return t;
}
void dfs(int k) {
    if(k == 9) {
        for(int i = 0; i < 7; i++) {
            for(int j = i + 1; j < 8; j++) {
                int a = cal(0, i);
                int b = cal(i + 1, j);
                int c = cal(j + 1, 8);
                if(c * n == c * a + b)
                    res++;
            }
        }
        return;
    }
    for(int i = 1; i <= 9; i++) {
        if(!st[i]) {
            st[i] = 1;
            a[k] = i;
            dfs(k + 1);
            st[i] = 0;
        }
    }
}
int main() {
    cin>>n;
    dfs(0);
    cout<<res;
    return 0;
}	

本文链接: http://www.dtmao.cc/news_show_250233.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?