查看文章 |
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));
} |
最近读者: