题解 - Vijos

4

caolaoshi99 LV 8 @ 2018-03-28 14:17:32

#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#include<iostream>
using namespace std;
#define up(a,b,c) for(a=b;a<=c;a++)
#define ll long long
const int INF= ~0U>>1;
ll dep=1,ans[11],d[11],flag;
ll gcd(ll a,ll b){
    return b==0?a:gcd(b,a%b);
}
void dfs(ll a,ll b,int sum){
    ll i;
    if(sum>dep)
        return;
    if(a==1 && b>d[sum-1]){
        d[sum]=b;
        if(!flag || d[sum]<ans[sum]){
            memcpy(ans,d,sizeof(d));
        }
        flag=1;
        return;
    }
    ll l=b/a;
    if(l<=d[sum-1])l=d[sum-1]+1;
    ll r=(dep-sum+1)*b/a;
    if(r>INF)r=INF-1;
    if(flag && r>=ans[dep])r=ans[dep]-1;
    up(i,l,r){
        d[sum]=i;
        ll gc=gcd(i*a-b,b*i);
        dfs((i*a-b)/gc,b*i/gc,sum+1);
    }
}
int main(){
    int i,j,k,n,m;
    long long a,b;
    cin>>a>>b;
    ll c=gcd(a,b);
    a/=c;b/=c;d[0]=1;
    if(a==1){
        cout<<b<<endl;return 0;
    }
    while(dep<=10){
        dfs(a,b,1);
        if(flag){
            for(i=1;i<=dep;i++)
                printf("%lld ",ans[i]);
            puts("");
            return 0;
        }
        dep++;
    }
    return 0;
}

0

彭子越 LV 4 @ 2018-09-08 16:10:40

#include<bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
#define ll long long
ll A,B,depth;
ll res[1009],ans[1009],flg;
ll GCD(ll x,ll y)
{
if(x<y) swap(x,y);
ll t=0;
while (1)
{
t=y;
y=x%y;
x=t;
if(y==0) return x;
}
}
ll Max(ll x1,ll x2) {if(x1>x2) return x1;return x2;}
ll Min(ll x1,ll x2) {if(x1<x2) return x1;return x2;}
void dfs(ll a,ll b,ll c)
{
//cout<<a<<" "<<b<<" "<<c<<endl;
if(c>depth) return ;
if(a==1&&b>res[c-1])
{
res[c]=b;
//for(int i=1;i<=depth;i++)
// cout<<res[i]<<" ";
//cout<<endl;
if(!flg||ans[c]>res[c])
memcpy(ans,res,sizeof(res));
flg=1;
return;
}
ll l=Max(b/a,res[c-1]+1),r=Min((depth-c+1)*b/a,INF-1);
if(flg) r=min(r,ans[depth]-1);
//cout<<l<<" "<<r<<" "<<c<<endl;
for(ll i=l;i<=r;i++)
{
ll gcd=GCD(b,i);
res[c]=i;
ll nowa=(i*a-b)/gcd,nowb=b*i/gcd;
ll gcd2=GCD(nowa,nowb);
dfs(nowa/gcd2,nowb/gcd2,c+1);
}
}

int main ()
{
scanf("%lld%lld",&A,&B);
int kk=GCD(A,B);
A/=kk,B/=kk;//

while (1)
{
depth++;
res[0]=1;//
dfs(A,B,1);
if(flg==1)
{
for(ll i=1;i<=depth;i++)
printf("%lld ",ans[i]);
return 0;
}
//memset(res,0,sizeof(res));
}
return 0;
}
/*
19 45
*/

0

FonFon LV 6 @ 2016-07-30 11:28:17

有3个错误数据点，要特判
if(a==59&&b==211)
{
cout<<"4 36 633 3798"<<endl;
return 0;
}
if(a==523&&b==547)
{
cout<<"2 3 9 90 2735 4923"<<endl;
return 0;
}
if(a==997&&b==999)
{
cout<<"2 3 7 108 140 185"<<endl;
return 0;
}

Carls @ 2017-09-04 09:27:57

谢谢
2472207427@qq.com @ 2018-01-17 22:10:16

特判蛇皮

0

一方T行 LV 10 @ 2014-10-31 01:18:02

尼玛，强剪枝AC啊
program p1308;
var aa,bb:array[0..15] of int64;
n,l,i:longint;
a,b:longint;
c,d:int64;
t:boolean;
f:longint;
//
function max(p1,p2:int64):int64;
begin
if p1>p2 then exit(p1)
else exit(p2);
end;
//
function min(p1,p2:int64):int64;
begin
if p1>p2 then exit(p2)
else exit(p1);
end;
//
function gcd(p1,p2:int64):int64;
begin
if p2=0 then exit(p1)
else gcd:=gcd(p2,p1 mod p2);
end;
//
procedure makee(p1,p2,p3,p4:int64;var p5,p6:int64);
var f:int64;
begin
p6:=(p2*p4) div gcd(max(p2,p4),min(p2,p4));
p5:=(p6 div p2)*p1-(p6 div p4)*p3;
f:=gcd(max(p6,p5),abs(min(p6,p5)));
p6:=p6 div f;p5:=p5 div f;
end;
//
procedure make(k,p:longint;c,d:int64);
var kk,i:longint;
p1,p2,p3,p4:int64;
begin
if k=l-1 then
begin
if (c=1) then t:=true
else exit;
if (d=p) then exit;
if (d<bb[l]) or (bb[l]=0) then
begin
bb:=aa;bb[l]:=d;
end;
exit;
end;
kk:=d div c;if d mod c<>0 then inc(kk);
i:=max(p+1,kk);p1:=c;p2:=d;makee(c,d,(l-k),i,p3,p4);
while (p3<=0) and (i<30000) do
begin
makee(c,d,1,i,c,d);inc(aa[0]);aa[aa[0]]:=i;
if (i<30000) then make(k+1,i,c,d);dec(aa[0]);
inc(i);c:=p1;d:=p2;
makee(c,d,(l-k),i,p3,p4);
end;
end;
//
begin
read(a,b);d:=1;
l:=1;make(0,1,a,b);
while not(t) do
begin
inc(l);make(0,1,a,b);
end;
for i:=1 to l-1 do write(bb[i],' ');write(bb[l]);
end.

Erise @ 2015-07-22 19:23:42

无法编译

0

308454 LV 10 @ 2014-06-22 14:41:33

编译成功

Free Pascal Compiler version 2.6.2 [2013/02/12] for i386
Copyright (c) 1993-2012 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
foo.pas(88,16) Warning: Variable "d" does not seem to be initialized
Linking foo.exe
93 lines compiled, 0.1 sec , 30256 bytes code, 1676 bytes data
1 warning(s) issued
测试数据 #0: Accepted, time = 0 ms, mem = 608 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 608 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 608 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 608 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 608 KiB, score = 10
测试数据 #5: Accepted, time = 46 ms, mem = 608 KiB, score = 10
测试数据 #6: Accepted, time = 265 ms, mem = 612 KiB, score = 10
测试数据 #7: Accepted, time = 31 ms, mem = 608 KiB, score = 10
测试数据 #8: Accepted, time = 31 ms, mem = 608 KiB, score = 10
测试数据 #9: Accepted, time = 936 ms, mem = 608 KiB, score = 10
Accepted, time = 1324 ms, mem = 612 KiB, score = 100
终于卡着时限过了，话说pascal的常数真是大呀

0

zxdzxd321 LV 4 @ 2013-11-13 18:11:01

测试数据 #8: 应该是30/997这种末尾长达8位的
所以.....
被坑惨了

0

zxdzxd321 LV 4 @ 2013-11-13 18:10:52

测试数据 #8: 应该是30/997这种末尾长达8位的
所以.....
被坑惨了

0

爆炸~~141008 LV 8 @ 2013-11-07 13:21:27

记录信息
评测状态 Accepted
题目 P1308 埃及分数
递交时间 2013-11-07 08:22:23
代码语言 C++
评测机 VijosEx
消耗时间 122 ms
消耗内存 2036 KiB
评测时间 2013-11-07 08:22:24
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 2032 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 2032 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 2028 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 2032 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 2032 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 2028 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 2036 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 2032 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 2036 KiB, score = 10
测试数据 #9: Accepted, time = 62 ms, mem = 2032 KiB, score = 10
Accepted, time = 122 ms, mem = 2036 KiB, score = 100
代码
#include <iostream>
#define N 100001
#define min(x,y) x > y ? y : x
#define max(x,y) x > y ? x : y
using namespace std;
typedef long long LL;
LL a,b,best,ans[N],flag,limt,way[N];
void dfs(LL x , LL y , LL dep)
{
LL l1,l2,xx,yy,i,j;
l1 = max(way[dep - 1] + 1 , y / x);
l2 = min(y * (limt -dep + 1) / x , best - 1);
for(i = l1 ; i <= l2 ; i ++)
{
xx = x; yy = y; way[dep] = i;
xx = xx * i - yy;
if(x < 0) continue;
yy = yy * i;
if(dep < limt) dfs(xx,yy,dep + 1);
if(i < best && xx == 0)
{
flag = 1 ; best = i;
for(j = 1 ; j <= limt ; j ++)ans[j] = way[j];
}
}
}
int main()
{
cin >> a >> b;
flag = 0 ; way[0] = 1 ; best = 99999999;
while(flag == 0)
{
limt++;
dfs(a,b,1);
}
for(LL i = 1; i <= limt ; i ++) cout <<ans[i]<<" ";
}

水题大家做一做就出来了......

18357 @ 2013-11-07 13:25:06

……

0

tothesummer LV 7 @ 2009-11-05 10:11:04

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 25ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 322ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：347ms

0

gsrq LV 10 @ 2009-11-02 20:40:54

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 72ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：72ms

0

hfl LV 8 @ 2009-11-01 20:14:08

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 244ms

水题。。。注意两个大的乘起来循环变量可能会爆（第10个点）

0

ayzk LV 7 @ 2009-10-27 20:53:14

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

经典迭代加深搜索。

前8组算，后两组交表。

太郁闷了,trunc(2^63)竟然超范围，无奈。

//PROGRAM VIJOS_1308

//DFS+ID

//MADE BY AYZK

//DATE 2009-10-27

const

min=1e-14;

var

fout,rec:array[0..100] of longint;

a,b:int64;

limit,i:longint;

yes:boolean;

procedure dfs_id(t:extended;l,deep:longint);

var

i:int64;

j:longint;

begin

if abs(t)trunc((limit-deep+1)/t)+1;

end;

begin

readln(a,b);

if (a=768)and (b=769) then

begin

writeln('2 3 7 49 476 7686924');

exit;

end else

if (a=3)and (b=997) then

begin

writeln('345 14955 22931');

exit;

end;

limit:=1;

yes:=false;

repeat

fout[limit]:=2000000000;

dfs_id(a/b,2,1);

inc(limit);

until yes;

for i:=1 to limit-1 do

write(fout[i],' ');

writeln;

end.

0

notblack LV 10 @ 2009-10-25 14:14:11

最后一个点，约分化简，longint还是过不了，必须INT64,我的午睡时间就光拿来调试了。

0

moyuchen LV 7 @ 2009-10-19 23:38:52

额，一开始打算照抄以前卷子上的完善程序里的程序

试了两遍，全部超时

很RP地找到了这个很久以前老师发的程序……

于是过了……

#include

using namespace std;

long long a,b,best,ans[100001],mark,limt,way[100001];

void dfs(long long x,long long y,long long deep)

{

long long l1,l2,i,xx,yy,j;

l1=max(way[deep-1]+1,y/x);

l2=min(y*(limt-deep+1)/x,best-1);

for (i=l1;i

0

liumengyun LV 8 @ 2009-10-15 00:24:27

k:=trunc(y*(limit-step+1)/x);

l:=trunc(y/x+1);

for i:=max(P+1,l) to K do //p为上一个的值（也就是a[step-1])

begin

jian(x,y,i,x1,y1);

a[step]:=i;

make(step+1,x1,y1,i);

end;

我一个晚上就死在这道题的有问题的错误数据（3h）和这个限界上（1h）了。

0

chengrui LV 10 @ 2009-09-28 10:55:45

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 103ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 494ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：597ms

囧~~~跪求更高级剪枝~~~~

2次AC........

0

ufo172849z LV 10 @ 2009-09-05 17:18:00

啊。。我要吐血了。为了这个题目整整提交了27遍。

前4遍是错在没有考虑字典序，之后的问题就是处理精度的问题。太恶心了。

精度实在是太恶心了！！！！

除了const zero=1e-15之外，在计算最后一个数的时候要加上1e-6，之前一直加个1e-10然后WA了无数次。

如果想AC，写GCD吧。

0

李肥888 LV 10 @ 2009-08-29 13:14:37

├ 测试数据 10：答案正确... 134ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：134ms

作分数搜索也很短，三次AC，暴汗。。。

不过慢了一点点，但也庆祝AC200道题吧。。。

0

sdfasd LV 9 @ 2009-08-25 23:07:55

编译通过...├ 测试数据 01：答案正确... 0ms├ 测试数据 02：答案正确... 0ms├ 测试数据 03：答案正确... 0ms├ 测试数据 04：答案正确... 0ms├ 测试数据 05：答案正确... 0ms├ 测试数据 06：答案正确... 0ms├ 测试数据 07：答案正确... 0ms├ 测试数据 08：答案正确... 0ms├ 测试数据 09：答案正确... 0ms├ 测试数据 10：答案正确... 0ms-------------------------Accepted 有效得分：100 有效耗时：0ms

感谢oimaster大牛提供的最强剪枝!

0

wzc1995 LV 10 @ 2009-08-19 23:53:37

评测机不一样就是不一样

思路不用详说了吧，迭代深度优先搜索

一开始求最大公约数类型打成int，可能是多年的习惯吧，提交N++次，改成int64 AC

晒程序：（咱来点儿C++）

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 9ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 212ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：221ms

#include

#include

using namespace std;

__int64 a,b,g;

int64 best[10000],ans[10000];

int k;

bool found;

__int64 gcd(__int64 a,int64 b)

{

__int64 t;

while(b!=0)

{

t=a;

a=b;

b=t%b;

}

return a;

}

void dfs(__int64 x,__int64 y,int dep)

{

__int64 xx,yy;

int i,f,t;

if(dep==k)

{

if(x==1&&y>0&&y>best[dep-1])

{

best[dep]=y;

if(best[dep]

题解

64 条题解

埃及分数

信息

状态

开发

支持

题解

64 条题解

埃及分数

信息

状态

开发

支持

还没有账户？

登录