题解

64 条题解

  • 4
    @ 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
    @ 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
    @ 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;
    }

  • 0
    @ 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.

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

      无法编译

  • 0
    @ 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
    @ 2013-11-13 18:11:01

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

  • 0
    @ 2013-11-13 18:10:52

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

  • 0
    @ 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]<<" ";
    }

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

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

      ……

  • 0
    @ 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
    @ 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
    @ 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
    @ 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
    @ 2009-10-25 14:14:11

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

  • 0
    @ 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
    @ 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
    @ 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
    @ 2009-09-05 17:18:00

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

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

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

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

    如果想AC,写GCD吧。

  • 0
    @ 2009-08-29 13:14:37

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

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

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

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

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

  • 0
    @ 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
    @ 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]

信息

ID
1308
难度
8
分类
搜索 | 搜索与剪枝 点击显示
标签
(无)
递交数
3391
已通过
495
通过率
15%
被复制
4
上传者