暴力求解法

2019/11/26

第一次通过写博客来记录自己的学习进程。
在之前的学习过程中，
深刻认识到我应该与自己的键盘多多培养感情。

于是，放下我的纸笔，开始写这第一篇博客。

除法（Division，UVa 725）

题目：
输入整数n，按从小到大的顺序输出所有形如 abcde/ fghij = n 的表达式，其中 a ~ j 恰好为数字 0 ~ 9 的一个排列（可以有前导0），2<= n <= 79 。

样例输入：
62

样例输出：
79546 / 01283 = 62
94736 / 01528 = 62

骚操作：

1. 使用 sprintf函数快速将两个int型数据转换成字符串并且进行拼接
2. 按照题意，满足条件的必须是 0 ~ 9 的一个排列，因此，先进行排序，再进行判断，会更加迅速且准确。
   （判断条件：‘0’+i）
3. 利用 bool 型 flag 对其是否满足条件进行标记
   （应该属于基操）

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int main()
{
    int n;
    char s[99];
    while(scanf("%d",&n)==1 && n)
    {
        int cnt=0;
        for(int fghij=1234;;fghij++)
        {
            int abcde=fghij*n;
            sprintf(s,"%05d%05d",abcde,fghij);
            if(strlen(s)>10)
            break;

            sort(s,s+10);
            bool flag=true;
            for(int i=0;i<10;i++)
            {
                if(s[i]!='0'+i) flag=false;
            }
            if(flag)
            {
                cnt++;
                printf("%05d / %05d = %d\n",abcde,fghij,n);
            }
           
        }
         if(!cnt)
        {
            printf("There is no solutions!");
        }
    }
    return 0;
}

最大乘积（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. 数据范围：1 <= n <= 18, -10 <= Si <= 10
   刚好最大可能乘积不超过10^18，使用 long long 存储。
2. 从头到尾枚举，max判断大小。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int main()
{
    int n;
    int s[19];
    while(scanf("%d",&n)==1 && n)
    {
        long long ans=1,temp=1;
        for(int i=0;i<n;i++)
        scanf("%d",&s[i]);
        for(int i=0;i<n;i++)
        {
         temp=temp*s[i];
         ans=max(ans,temp);
        }
        if(ans>0)
            printf("%lld\n",ans);
        else
            printf("0\n");
    }
    return 0;
}

分数拆分（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
8
1 / 12 = 1 / 156 +1 / 13
1 / 12 = 1 / 84 +1 / 14
1 / 12 = 1 / 60 +1 / 15
1 / 12 = 1 / 48 +1 / 16
1 / 12 = 1 / 36 +1 / 18
1 / 12 = 1 / 30 +1 / 20
1 / 12 = 1 / 28 +1 / 21
1 / 12 = 1 / 24 +1 / 24

骚操作：

1. 由于 x >= y ,有 1 / x <= 1 / y ,因此 1 / k - 1 / y <= 1 / y
   即 y <= 2k (暴力枚举)

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int main()
{
    int k;
    while(scanf("%d",&k)==1 && k)
    {
        int kase=0;
        int j=0;
        float x=0;
        int a[100],b[100];
        for(float i=k+1;i<=2*k;i++)
        {
            x=(i*k)/(i-k);
            int temp;
            temp = (int) x;
            if(x==temp)
            {
                kase++;
                a[j]=x;
                b[j]=i;
                j++;
            }
        }
        printf("%d\n",kase);
        for(int i=0;i<j;i++)
        {
            printf("1 / %d = 1 / %d +1 / %d\n",k,a[i],b[i]);
        }
    }
    return 0;
}