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

  • 题目来源:https://www.nowcoder.com/acm/contest/116/B
  • 题目描述:杨老师给同学们玩个游戏,要求使用乘法和减法来表示一个数,他给大家9张卡片,然后报出一个数字,要求大家用表达式的形式来表示出这个数 100 可以表示为这样的形式:100=129∗67−8543100=129∗67−8543100 = 129*67-8543 , 还可以表示为:100=13∗489−6257100=13∗489−6257100 = 13*489-6257 注意特征:表达式中,数字1~9分别出现且只出现一次(不包含0)。 类似这样的表达式,100 有 20 种表示法。
  • 题目要求:从标准输入读入一个正整数N(N<1000∗1000)N(N<1000∗1000)N(N<1000 * 1000) 程序输出该数字用数码1~9不重复不遗漏地组成的全部种数。 注意:不要求输出每个表示,只统计有多少表示法!
  • 输入描述: 一个正整数N
  • 输出描述: 输出有多少种表示法
  • 示例1 输入 100 输出 20
  • 备注: 注意只有一个乘法和一个减法,*号保证在-的前面
  • 题目分析:对于一个正整数N,满足N=i∗j+kN=i∗j+kN=i*j+k的式子有多少个,其中i,j,ki,j,ki,j,k只能包含1~9这9个数字,且不重不露。
  • 我的思路:上面的式子可以表示为 N=i∗j+kN=i∗j+kN=i*j+k 的形式,所以可以分成 3 部分,对于每个部分暴力枚举。其次,由于1~9不重不漏,这样就可以对于 1 – 9 去枚举其各个部分的排列,然后对于一个确定的排列,接着枚举,1~9就死3个部分数字的排序组合。最后,对于一个确定的排序组合,看是否满足了N=i∗j+kN=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 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券