Vijos P1000 A+B Problem 题解综述
2009-08-26 17:51
【题目描述】
输入两个自然数，输出他们的和
【输入数据】
两个自然数x和y(0<=x,y<=32767)
【输出数据】
一个数，即x和y的和
【思路】 by cjf00000
此题考查动态规划思想
首先我们需要把输入字符转换为数字a,b 然后使用动态规划求解A+B的值 最后输出答案
我们可以设计出如下DP方程
令f[j]
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示i+j的值 则有
1. f[0][0]=0
2. f[j]=max
3. { f[i-1][j]+1,
4. f[i][j-1]+1 }
由于对于每个i,j我们都要计算出f[j],因此时间复杂度与空间复杂度都为O(n^2)
但是 对于题目提供的最大数字n=32767明显超时！
【优化1】by wusu5545
对于DP方程 由于每次计算只需要f[i-1][j]或f[j-1]
因此我们可以使用滚动数组优化DP的空间复杂度
使用两个整数x,y分别保存f[i-1][j]与f[j-1]
空间复杂度降为O(2) 然而时间复杂度O(n^2)仍然超时!
“时间复杂度，到目前为止还没有更好的优化方法。因此，此题被称为史上最难的dp题!”
【优化2】by 匿名大牛
对于整数的运算 我们可以利用位运算的思想简化复杂度
题目显然要我们求两非负整数之和。
我们知道，在非负整数加法的二进制逻辑运算中，每一位上的结果取决于以下两方面：
1、本位上两个逻辑位的异或值
2、后一位的结果是否溢出
利用这种性质，可以考虑如下做法：
令f[j]表示，考虑两个加数的后i、j位相加的结果，显然有以下状态转移方程
1. f[j]= max
2. { f[i][j-1]+y & (1 << (j-1))
3. f[i-1][j]+x & (1 << (i-1)) }
复制代码
赋初值f[0][0]=(x & 1) ^ (y & 1)
两个循环变量i,j从1循环到log(2,maxint)
我们成功的把时空复杂度降为O(log^2n)
利用滚动数组，可以进一步吧空间复杂度降为O(2)
至此,我们得到了一个较为圆满的解答
【题目评价】 by Coldwings 修改 by h4x
此题实质上非常复杂
全面考察到了数学史和计算机史 经典代数 常用计算与输入输出 动态规划思想以及位运算思想等
等等等知识点
考虑到题目的所有可能性 我们应当从计算机存储的二进制的角度来逐步考虑数的表示 以字节计
数，采用多字节合用的方式表示一个大整数如今已经是高级程序语言编译器轻松可以达到的目标
可是为了加强对计算机计数的了解 此题可以考虑仍以最原始的方式进行计算——并且考虑最终
将二进制数转变为十进制输出的全部过程 期间还考察了对ASCII码的熟悉程度
然而此题再VIJOS上的通过人数竟然高达59% 可以看出VIJOS上大牛之多 不禁令人感叹啊
宋神牛用最小网络流
program problem;
var
en,et,ec,eu,ep,ex:Array[0..250000] of longint;
dis:array[0..1000] of longint;
v:array[0..1000] of boolean;
i,j,k,n,m,w,cost,l:longint;
a,b,ans,left,right:longint;
function min(a,b:longint):longint;
begin
if a
0 do
begin
if (eu[i]>0)and not v[et[i]] and(dis[et[i]]+ec[i]=dis[no]) then
begin
d:=aug(et[i],min(m,eu[i]));
if d>0 then
begin
dec(eu[i],d);
inc(eu[ep[i]],d);
ex[no]:=i;
exit(d);
end;
end;
i:=en[i];
end;
ex[no]:=i;
exit(0);
end;
function modlabel:boolean;
var
d,i,j:longint;
begin
d:=maxlongint;
for i:=1 to n do
if v[i] then
begin
j:=en[i];
while j<>0 do
begin
if (eu[j]>0)and not v[et[j]] and(ec[j]-dis[i]+dis[et[j]]0 do
fillchar(v,sizeof(v),0);
until modlabel;
work:=cost;
end;
function solve(x,d:longint):longint;
var i,k,t,p,last,cost,lk:longint;
begin
fillchar(en,sizeof(en),0);
fillchar(dis,sizeof(dis),0);
k:=0; n:=2; t:=x; p:=0;
while x<>0 do
begin
k:=k+x mod 10;
x:=x div 10;
inc(p);
end;
n:=1; x:=t; l:=k+p+1; last:=1; cost:=1; lk:=0;
while x<>0 do
begin
k:=x mod 10;
for i:=1 to k do
begin
inc(n);
build(last,n,1,-cost);
build(n,last+k+1,1,0);
end;
cost:=cost*10;
inc(n);
if last<>1 then
begin
if lk15000 do
begin
ans:=(left+right)shr 1;
if solve(ans,b)>a then
right:=ans
else left:=ans;
end;
for i:=left to right do
if solve(i,b)=a then
begin
writeln(i);
halt;
end;
end.
还有一位用什么一个PASCAL的面向对象的解法
program p1000;
var a,b,c:qword;
function max(a,b:qword):qword;
begin
if ab
then exit(b)
else exit(a);
end;
operator :=(a:qword):b:qword;
begin
b:=0;
if max(a,b)=a
then b:=max(a,b)
else b:=min(a,b);
end;
operator +(a,b:qword)c:qword;
begin
c:=0;
c:=max(a,b)+min(a,b);
end;
begin
readln(a,b);
c:=a+b;
writeln(c);
end.
浙公网安备 33021202002483