暴力求解法
有错还请指正
简单枚举
例题7-1 除法（Division, UVa 725）
输入正整数n，按从小到大的顺序输出所有形如abcde/fghij = n的表达式，其中a～j恰好 为数字0～9的一个排列（可以有前导0），2≤n≤79。
样例输入：
62
样例输出：
79546 / 01283 = 62
94736 / 01528 = 62
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include<stdio.h>
#include<string.h>
int main()
{
int i,j,n,s1,s2,flag[10];
while(~scanf("%d",&n))
{
for(i=1234;i<50000;i++)
{
memset(flag,0,sizeof(flag));
s1=i;
s2=i*n;
while(s1||s2)
{
if(!flag[s1%10])
{
flag[s1%10]=1;
s1/=10;
}
else
break;
if(!flag[s2%10])
{
flag[s2%10]=1;
s2/=10;
}
else
break;
}
for(j=0;j<10;j++)
if(!flag[j])
break;
if(j==10&&i*n<=98765)
{
if(i<10000)
printf("%d / 0%d = %d\n",i*n,i,n);
else
printf("%d / %d = %d\n",i*n,i,n);
}
}
}
return 0;
}
|
例题7-2 最大乘积（Maximum Product, UVa 11059）
输入n个元素组成的序列S，你需要找出一个乘积最大的连续子序列。如果这个最大的乘 积不是正数，应输出0（表示无解）。1≤n≤18，-10≤Si≤10。
样例输入：
3
2 4 -3
5
2 5 -1 2 -1
样例输出：
8 20
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include<stdio.h>
long long max=-1e19;
int main()
{
int t;
scanf("%lld",&t);
while(t--){
long long int n,a[20]={0},ret=1;
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
for(int i=1;i<=n-1;i++){
for(int j=i+1;j<=n;j++){
ret=1;
for(int k=i;k<=j;k++){
ret=ret*a[k];
}
if(ret>max)
max=ret;
}
}
if(max<0)
printf("0\n");
else
printf("%lld\n",max);
}
return 0;
}
|
例题7-3 分数拆分（Fractions Again?!, UVa 10976）
输入正整数k，找到所有的正整数x>=y,使得1/k=1/x + 1/y;
样例输入：
2
12
样例输出：
2
1/2 = 1/6 + 1/3；
1/2 = 1/4 + 1/4；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #include <stdio.h>
int main()
{
int k;
while(~scanf("%d",&k)){
for(int y=k+1;y<=2*k;y++){
if(k*y%(y-k)==0){
int x = k*y/(y-k);
printf("1/%d = 1/%d + 1/%d\n",k,x,y);
}
}
}
return 0;
}
|
从1/12=1/156+1/13可以看出，x可以比y大很多。由于x>=y,有1/x<=1/y,因此1/k-1/y<=1/y，即y<=2 * k.这样，只需要在2 * k范围之内枚举y，然后根据y尝试计算出x即可
枚举排列
7.2.1 生成1～n的排列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include<stdio.h>
int a[1000];
void print_permutation(int n,int *A,int cur){
if(cur==n){
for(int i=0;i<n;i++)
printf("%d ",A[i]);
printf("\n");
}
else
for(int i=1;i<=n;i++){
int ok=1;
for(int j=0;j<cur;j++)
if(A[j]==i)
ok=0;
if(ok){
A[cur]=i;
print_permutation(n,A,cur+1);
}
}
}
int main()
{
int n,cur=0;
scanf("%d",&n);
print_permutation(n,a,0);
return 0;
}
|
当然我知道c++STL里有next_permutation函数，这里是函数的一种实现方式（递归）
1
2
3
4
5
6
7
8
9
| void next_pre(int n,int x){
do
{
for(int i=0;i<n;i++){
printf("%d",p[i]);
}
printf("\n");
}while(next_permutation(p,p+n));
}
|
7.2.2 生成可重集的排列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include<cstdio>
#include<algorithm>
using namespace std;
int ans[30],a[30];
void print_permutation(int n,int*x,int pos){
if (pos==n) {
for (int i=0;i<n;i++)
printf("%d ",x[i]);
printf("\n");
}
else for (int i=0;i<n;i++){
if (!i||(a[i]!=a[i-1])){
int c1=0,c2=0;
for (int j=0;j<pos;j++)
if (x[j]==a[i]) c1++;
for (int j=0;j<n;j++)
if (a[i]==a[j]) c2++;
if (c1<c2) {
x[pos]=a[i];
print_permutation(n,x,pos+1);
}
}
}
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n);
print_permutation(n,ans,0);
return 0;
}
|
7.2.4 下一个排列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include<cstdio>
#include<algorithm>
using namespace std;
int main(){
int n,p[10];
scanf("%d",&n);
for(int i = 0; i < n; i++)
scanf("%d", &p[i]);
sort(p, p+n);
do {
for(int i = 0; i < n; i++)
printf("%d ", p[i]);
printf("\n");
}while(next_permutation(p, p+n));
return 0;
}
|
待更新。。。
