若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1303: 猜算式

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,267

题目描述

看下面的算式:

□□ x □□ = □□ x □□□

它表示:两个两位数相乘等于一个两位数乘以一个三位数。

如果没有限定条件,这样的例子很多。

但目前的限定是:这9个方块,表示1~9的9个数字,不包含0。
该算式中1至9的每个数字出现且只出现一次!

比如:
46 x 79 = 23 x 158
54 x 69 = 27 x 138
54 x 93 = 27 x 186
…..

请编程,输出所有可能的情况!

注意:
左边的两个乘数交换算同一方案,不要重复输出!
不同方案的输出顺序不重要

输入

暂无

输出

暂无

样例输入

暂无

样例输出

暂无

参考代码

#include<stdio.h>
#define N 1005
FILE *f1,*f2;
typedef struct node 
{
    long w,s,num;
}
node;
node a[N];
long f[N],b[N],q[N],n;
int bigger(node x,node y) 
{
    if (x.w!=y.w) return (x.w>y.w); else return (x.s<y.s);
}
void sort(long left,long right) 
{
    long i,j;
    node x,t;
    i=left;
    j=right;
    x=a[(i+j)/2];
    while (i<=j) 
    {
        while (bigger(x,a[i])) i++;
        while (bigger(a[j],x)) j--;
        if (i<=j) 
        {
            t=a[i];
            a[i]=a[j];
            a[j]=t;
            i++;
            j--;
        }
    }
    if (left<j) sort(left,j);
    if (i<right) sort(i,right);
}
int main() 
{
    long i,j,k,max;
    i=1;
    while (scanf("%ld%ld",&a[i].w,&a[i].s)==2)  a[i].num=i++;
    n=i-1;
    sort(1,n);
    for (i=1;i<=n;i++) 
    {
        f[i]=1;
        b[i]=i;
    }
    for (i=1;i<=n;i++)
            for (j=1;j<i;j++)
                if (a[j].w<a[i].w&&a[j].s>a[i].s&&f[j]+1>f[i]) 
    {
        f[i]=f[j]+1;
        b[i]=j;
    }
    max=0;
    for (i=1;i<=n;i++)
            if (f[i]>max) 
    {
        max=f[i];
        k=i;
    }
    printf("%ldn",max);
    q[1]=a[k].num; i=1;
    while (b[k]!=k) {q[++i]=a[b[k]].num; k=b[k];}
    for (i=max;i>=1;i--)
        printf("%ldn",q[i]);
    return 0;
}

解析

暂无

hustoj

发表评论 取消回复

邮箱地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

Dreams孤独患者 原站点 Skip
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist