百度首页 | 百度空间
 
查看文章
 
TOj(10.60.101.7) 10000 题目解题报告
2008-06-26 19:57

题意:

         给定两个数,a,b,其中,两者都在1——9之间,输出两个数的和。

算法分析:

1)首先,该题可以通过线性规划的方式搞定,具体的思路是:

设立约束方程:

x1 >= a

x1 <= a

x2 >= b

x2 <= b

之后只需要求目标函数f = x1+x2的最小值即可

2)显然,线性规划代码实现复杂,而且“时间复杂度”比较高,必须进行优化,于是采用最大流的算法,解决方法如下:

首先,以 S T 表示流中的源和流水槽,

创造另外两个点(令之为 A B)并赋予其容量为输入的 a b ,图形貌似如下:

         a  a

      |--A--|

    S-|      |-T

      |--B--|

        b  b

最后,只要求出最大流量即可得到 A+B 的解了。

解决的代码也不长,看来是可行的办法:

#include<stdio.h>
#include<string.h>
        int c[4][4],f[4][4];
bool b[4];
int ans;
void init()
{
     int a,b;
     scanf("%d%d",&a,&b);
     c[0][1]=a;c[1][3]=a;
     c[0][2]=b;c[2][3]=b;
}
bool find(int x)
{
     if(x==3)return true;
     for(int i=0;i<4;i++)
    {
         if(f[x][i]<c[x][i]&&!b[i])
         {
             b[i]=true;
             if(find(i))
             {
                 f[x][i]++;f[i][x]--;
                 return true;
             }
         }
     }
     return false;
}
void process()
{
     ans=0;
    memset(b,false,sizeof(b));
     b[0]=true;
     while(find(0))
     {
         memset(b,false,sizeof(b));
         b[0]=true;
         ans++;
     }
}
int main()
{
     init();
     process();
     //if(ans!=a+b)ans=a+b;
     printf("%d\n",ans);
}

3)但是,这样的代码太长了,必须精简一下,于是精简后的代码出现了(FPC代码):

begin randomize;write(random(XX))end

4)显然,上面的代码的时间复杂度太高了,能不能快一点,这是个问题,于是想到了汇编应该快一点,因此就有了:

#include<stdio.h>
int cal(int a,int b)
{
     __asm
     {
         mov eax,a;
         mov ebx,b;
         add eax,ebx;
     }
}
int main()
{
     int a,b;
     scanf("%d%d",&a,&b);
     printf("%d\n",cal(a,b));
}

类别:扯淡栏 | 添加到搜藏 | 浏览() | 评论 (0)
 
最近读者:
 
网友评论:
发表评论:
姓 名:
网址或邮箱: (选填)
内 容:
验证码:
 

     

©2008 Baidu