暴力搜索类（学习自用）

P1149 [NOIP2008 提高组] 火柴棒等式

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （代码借鉴了好几个但文章我不记得了）

题目描述

给你?n?根火柴棍，你可以拼出多少个形如?A+B=C?的等式？等式中的?A、B、C?是用火柴棍拼出的整数（若该数非零，则最高位不能是?00）。用火柴棍拼数字?0～90～9?的拼法如图所示：

注意：

1. 加号与等号各自需要两根火柴棍；
2. 如果A不等于B，则?A+B=C?与?B+A=C?视为不同的等式（A,B,C≥0）；
3. n?根火柴棍必须全部用上。

输入格式

一个整数?n(1≤n≤24)。

输出格式

一个整数，能拼成的不同等式的数目。

输入输出样例

输入 #1复制

14

输出 #1复制

2

输入 #2复制

18

输出 #2复制

9

说明/提示

【输入输出样例 1 解释】

22?个等式为?0+1=10+1=1?和?1+0=11+0=1。

【输入输出样例 2 解释】

99?个等式为

0+4=40+4=4、0+11=110+11=11、1+10=111+10=11、2+2=42+2=4、2+7=92+7=9、4+0=44+0=4、7+2=97+2=9、10+1=1110+1=11、11+0=1111+0=11。

noip2008 提高第二题

#include <bits/stdc++.h>
using namespace std;
int s[1004]={6,2,5,5,4,5,6,3,7,6};
int n,ans;
int a[4];
void dfs(int st) {
	if(st>3) {
		if(a[1]+a[2]==a[3]&&n==0)
			ans++;
		return ;
	}
	for(int i=0;i<=999;i++) {
		if(n-s[i]>=0) {//还有火柴
			a[st]=i;//a[i]记录数字不是火柴数
			n-=s[i];//满足火柴数n==0;
			dfs(st+1);
			
			n+=s[i];
		}
	}
}
int main() {
	cin>>n;
	n=n-4;//减去符号用的火柴数
	for(int i=10;i<=999;i++)
		s[i]=s[i/10]+s[i%10];//第i个数需要是s[i]根火柴；
	dfs(1);
	cout<<ans;
	return 0;
} 

P1618 三连击（升级版）

时间限制1.00s

内存限制128.00MB

题目描述

将?1,2,…,91,2,…,9?共?99?个数分成三组，分别组成三个三位数，且使这三个三位数的比例是 A:B:C，试求出所有满足条件的三个三位数，若无解，输出?No!!!。

//感谢黄小U饮品完善题意

输入格式

三个数，A,B,C。

输出格式

若干行，每行?33?个数字。按照每行第一个数字升序排列。

输入输出样例

输入 #1复制

1 2 3

输出 #1复制

192 384 576
219 438 657
273 546 819
327 654 981

说明/提示

保证 A<B<C。

---

upd?2022.8.3upd?2022.8.3：新增加二组 Hack 数据。

#include <bits/stdc++.h>
using namespace std;
int a,b,c,ne_a,ne_b,ne_c;
int sum,ans;
bool used[10];
int z[20];
int cou(int m) {//把数组变成三位数的和
	sum=0;
	for(int i=3*m-2;i<=3*m;i++) {
		sum*=10;
		sum+=z[i];
	}
	return sum;
}

void dfs(int n) {
	if(n>9&&b*cou(1)==a*cou(2)&&c*cou(1)==a*cou(3)) {
		cout<<cou(1)<<" "<<cou(2)<<" "<<cou(3)<<endl;
		ans=1;
		return;
	}
	for(int i=1;i<=9;i++) {
		if(!used[i]) {
			used[i]=1;
			z[n]=i;
			dfs(n+1);
			
			used[i]=0;
		}
	}
	return;
}
int main() {
	cin>>a>>b>>c;
	sum=a*b*c;
//	ne_a=sum/a; 这里原本想用公倍数除的结果来判断相等，但可能因为太大了过不去？？？
//	ne_b=sum/b;
//	ne_c=sum/c;
	dfs(1);
	if(!ans) cout<<"No!!!";
	return 0;
}