杨老师的游戏 （暴力枚举）
题目链接： 新疆大学ACM-ICPC程序设计竞赛五月月赛（同步赛）B - 杨老师的游戏
题意
杨老师给同学们玩个游戏，要求使用乘法和减法来表示一个数，他给大家9张卡片，然后报出一个数字，要求大家用表达式的形式来表示出这个数 100 可以表示为这样的形式：100 = 129*67-8543 ， 还可以表示为：100 = 13*489-6257 注意特征：表达式中，数字1~9分别出现且只出现一次（不包含0）。 类似这样的表达式，100 有 20 种表示法。 题目要求： 从标准输入读入一个正整数N(N<1000 * 1000) 程序输出该数字用数码1~9不重复不遗漏地组成的全部种数。 注意：不要求输出每个表示，只统计有多少表示法！
思路
数字都确定了，为1~9的所有数字，那么循环的次数最多为其枚举次数三十多万吧，所以我们可以直接上暴力，但是我为了优化，人为增加了复杂度
代码一
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)(j);i <= (int)(k);i ++)
#define per(i,j,k) for(int i = (int)(j);i >= (int)(k);i --)
#define mmm(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
typedef long long ll;
const int INF = (
int)
0x3f3f3f3f;
const int MAXN = (
int)
1e5+
7;
int N;
int a[
12] = {
0,
1,
2,
3,
4,
5,
6,
7,
8,
9};
int ans;
int q,w,e;
int num[
12];
int flag;
typedef pair<
int,
int> pi;
set<pi> se;
int main()
{
ios::sync_with_stdio(
false);
cin.tie(
0);
cout.tie(
0);
cin >> N;
do {
q =
0;
rep(i,
1,
9){
q = q*
10 + a[i];
w =
0;
rep(j,i+
1,
9){
w = w*
10 + a[j];
e = (q*w)-N;
if (e <=
0)
continue;
mmm(num,
0);
while (e){
num[e%
10] ++;
e /=
10;
}
rep(k,j+
1,
9) {
num[a[k]] --;
}
flag =
0;
rep(k,
0,
9){
if (num[k] !=
0) flag =
1;
}
if (!flag){
se.insert(mp(q,w));
break;
}
}
}
}
while (next_permutation(a+
1,a+
10));
cout << sz(se) << endl;
}
代码二
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
int s[
9] = {
1,
2,
3,
4,
5,
6,
7,
8,
9};
int main()
{
int n;
scanf(
"%d",&n);
ll sum =
0;
int a =
0,b =
0,c =
0;
do{
a =
0;
for(
int i =
0;i <
7;i ++){
a = a*
10 + s[i];
for(
int j = i+
1;j <=
7;j ++){
b = b*
10 + s[j];
for(
int k = j+
1;k <=
8;k ++){
c = c*
10 + s[k];
}
if((a*b-c) == n) sum ++;
c =
0;
}
b =
0;
}
}
while(next_permutation(s,s+
9));
printf(
"%lld",sum);
}
