新疆大学ACM-ICPC程序设计竞赛五月月赛(同步赛)--B-杨老师的游戏

  • 题目来源:https://www.nowcoder.com/acm/contest/116/B
  • 题目描述:杨老师给同学们玩个游戏,要求使用乘法和减法来表示一个数,他给大家9张卡片,然后报出一个数字,要求大家用表达式的形式来表示出这个数 100 可以表示为这样的形式:100=129∗67−8543100 = 129*67-8543 , 还可以表示为:100=13∗489−6257100 = 13*489-6257 注意特征:表达式中,数字1~9分别出现且只出现一次(不包含0)。 类似这样的表达式,100 有 20 种表示法。
  • 题目要求:从标准输入读入一个正整数N(N<1000∗1000)N(N<1000 * 1000) 程序输出该数字用数码1~9不重复不遗漏地组成的全部种数。 注意:不要求输出每个表示,只统计有多少表示法!
  • 输入描述: 一个正整数N
  • 输出描述: 输出有多少种表示法
  • 示例1 输入 100 输出 20
  • 备注: 注意只有一个乘法和一个减法,*号保证在-的前面
  • 题目分析:对于一个正整数N,满足N=i∗j+kN=i*j+k的式子有多少个,其中i,j,ki,j,k只能包含1~9这9个数字,且不重不露。
  • 我的思路:上面的式子可以表示为 N=i∗j+kN=i*j+k 的形式,所以可以分成 3 部分,对于每个部分暴力枚举。其次,由于1~9不重不漏,这样就可以对于 1 – 9 去枚举其各个部分的排列,然后对于一个确定的排列,接着枚举,1~9就死3个部分数字的排序组合。最后,对于一个确定的排序组合,看是否满足了N=i∗j+kN=i*j+k,累加就是答案。
  • 代码如下:
#include<iostream>
#include<cstring> 
#include<string>
#include<algorithm> 
#include<vector> 
#include<stack> 
#include<bitset>
#include<cstdio> 
#include<cstdlib> 
#include<cmath> 
#include<set> 
#include<list> 
#include<deque> 
#include<map> 
#include<queue>
using namespace std;
typedef unsigned long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 998244353;
bool flag[10];
int que[10];
int ans, num;
void judge() {
    int Li, Lk, Lj, di, dj, i;
    for (di = 1; di < 9; ++di) {
        Li = 0;
        for (i = 1; i <= di; ++i) {
            Li = Li * 10 + que[i];
        }
        for (dj = 1; di + dj < 9; ++dj) {
            Lj = 0;
            for (i = di + 1; i <= di + dj; ++i) {
                Lj = Lj * 10 + que[i];
            }
            Lk = 0;
            for (i = di + dj + 1; i < 10; ++i) {
                Lk = Lk * 10 + que[i];
            }
            if (Li * Lj - Lk == num) {
                ++ans;
            }
        }
    }
}

void dfs(int number) {
    if (number > 9) {
        judge();
    }
    int i;
    for (i = 1; i < 10; ++i) {
        if (!flag[i]) {
            flag[i] = true;
            que[number] = i;
            dfs(number + 1);
            flag[i] = false;
        }
    }
}

int main()
{
    cin >> num;
    dfs(1);
    cout << ans << endl;
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

P3382 【模板】三分法

题目描述 如题,给出一个N次函数,保证在范围[l,r]内存在一点x,使得[l,x]上单调增,[x,r]上单调减。试求出x的值。 输入输出格式 输入格式: 第一行...

35690
来自专栏和蔼的张星的图像处理专栏

138. 子数组之和 map存储加规律

给定一个整数数组,找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置。 假定一定存在这样的字数组。 样例 给出 [-3, 1, 2,...

12710
来自专栏王肖的UT

GLSL-内置函数

66730
来自专栏CDA数据分析师

入门 | 数据科学初学者必知的NumPy基础知识

NumPy(Numerical Python)是 Python 中的一个线性代数库。对每一个数据科学或机器学习 Python 包而言,这都是一个非常重要的库,S...

14020
来自专栏数据结构与算法

洛谷T21776 子序列

题目描述 你有一个长度为 nn 的数列 ,这个数列由 0,10,1 组成,进行 mm 个的操作: 1~l~r1 l r :把数列区间 [l, r][l,r] ...

42880
来自专栏专知

Numpy教程第1部分 - 阵列简介(常用基础操作总结)

【导读】这里是numpy教程的基础部分,涵盖了使用numpy的ndarrays执行数据操作和分析的一些操作。众所周知,Numpy是Python中最基本和最强大的...

29440
来自专栏ATYUN订阅号

NumPy中einsum的基本介绍

einsum函数是NumPy的中最有用的函数之一。由于其强大的表现力和智能循环,它在速度和内存效率方面通常可以超越我们常见的array函数。但缺点是,可能需要一...

1.3K30
来自专栏落影的专栏

iOS开发-OpenGL ES入门教程2

教程 OpenGLES入门教程1-Tutorial01-GLKit 这次的是shader编译链接、glsl入门和简单图形变换。 OpenGL ES系列教程在这...

32580
来自专栏不止思考

算法的时间与空间复杂度(一看就懂)

算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,但在过程中消耗的资源和时间却会有...

11720
来自专栏mathor

搜索(6)

 题目大意是在一个nxn的方阵地图上,每一个方格都标记+号或者-号,要从A点到B点。题目要求移动路线要+-交替,问怎么移动从A到B才是最短路径?  同样...

14330

扫码关注云+社区

领取腾讯云代金券