2012 ACM/ICPC 金华赛区现场赛解题报告汇总

十月 29th, 2012 | Posted by diaorui in ICPC 2012 亚洲区 | 信息聚合 | 解题报告
欢迎转载,转载请注明出处。




针对2012 ACM/ICPC 金华赛区10月28日现场赛,本日志汇总网上ACMer们发布的解题报告,方便大家互相学习。欢迎补充和完善本日志。
感谢所有及时发布解题报告,和大家分享知识的各位神牛。

题目链接
官方解题报告
排行榜

A Physical Examination (HDU 4442)
http://blog.csdn.net/shuimu12345678/article/details/8123577
http://www.cnblogs.com/kuangbin/archive/2012/10/29/2745368.html
http://www.cnblogs.com/pony1993/archive/2012/10/29/2745454.html
http://www.cnblogs.com/moonbay/archive/2012/10/30/2745929.html
http://blog.sina.com.cn/s/blog_9d987af5010177xe.html

B Lost (HDU 4443)
http://hi.baidu.com/caiych/item/9dda9743d84e25ea1e19bc19
http://blog.csdn.net/zz_1215/article/details/8136840

C Walk (HDU 4444)
http://blog.csdn.net/asdfgh0308/article/details/8125832
http://blog.csdn.net/zz_1215/article/details/8125930
http://hi.baidu.com/_suxing11/item/d6269b29c4cd92c4a5275a38
http://winguse.com/blog/2012/10/30/hdu-4444-walk-2012%E4%BA%9A%E6%B4%B2%E5%8C%BA%E9%87%91%E5%8D%8E%E7%AB%99c%E9%A2%98/
http://iseasoul.com/jinhua-onsite-easy-sol
注:除最后一条外,其余可能都有错误,但因数据弱所以也通过了。

D Crazy Tank (HDU 4445)
http://blog.renren.com/blog/284250792/878678994
http://bu540402.diandian.com/post/2012-10-29/40042959509
http://winguse.com/blog/2012/11/01/4445-crazy-tank-2012%e4%ba%9a%e6%b4%b2%e5%8c%ba%e9%87%91%e5%8d%8e%e7%ab%99d%e9%a2%98/
http://www.cnblogs.com/jffifa/archive/2012/11/04/2754065.html

E IT Companies (HDU 4446)
http://hi.baidu.com/isaacpei/item/1c5c7fc1d9bddfd9ee183bc4

F Yuanfang, What Do You Think? (HDU 4447)
论文 https://docs.google.com/open?id=0B207bvwVi4QrSG5MclJkdmxkZE0
论文 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.121.3592&rep=rep1&type=pdf
http://hi.baidu.com/isaacpei/item/4f7807327e54c681b611db63
http://blog.csdn.net/cyberzhg/article/details/8139869
sixujie提供的源代码:https://skydrive.live.com/?cid=CA782D9BC2210D14&id=CA782D9BC2210D14%21117
如果打不开,也可以展开下面的代码直接看

#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

//#define DEBUG


const int N = 1200;

int gcd(int,int);


struct Node{
    Node(int _p, int _a):pow(_p), a(_a){}

    int pow;
    int a;

    void output(bool positiveSign=false)
    {
        if(positiveSign && a>0) putchar('+');

        if(pow==0){
            printf("%d",a);
            return;
        }

        if(a==-1){
            putchar('-');
        }
        else if(a!=1){
            printf("%d",a);
        }

        putchar('x');

        if(pow>1)
        printf("^%d",pow);
    }

    //bool operator < (const Node& nd)const{
    //    return pow > nd.pow;
    //}
    bool operator == (const Node& nd)const{
        return pow==nd.pow && a == nd.a;
    }
};



struct Expression{

    vector<Node> expression;

    // trivial case 1: order = p, where p is a prime
    void tr1(int order)
    {
        expression.clear();

        for(int i=1;i<order;++i){
            expression.push_back( Node(order-i,1) );
        }
        expression.push_back( Node(0,1) );
    }

    // trivial case 2: order = p^k, where p is a prime
    void tr2(int k, const Expression& xp)
    {
        expression.clear();

        for(int i=0; i< xp.expression.size();++i){
            expression.push_back(  Node( k*xp.expression[i].pow, xp.expression[i].a) );
        }
        //expression.push_back( Node(0,1) );
    }

    void norm()
    {
        if(expression.size()<1)return;

        int c=abs(expression[0].a);
        for(int i=0;i<expression.size();++i){
            c= gcd(c, abs( expression[i].a ) );
            if(c==1)break;
        }
        if(c==1)return;

        for(int i=0;i<expression.size();++i)
            expression[i].a/=c;
    }

    void output()
    {
        putchar('(');
        for(int i=0;i<expression.size();++i){
            expression[i].output(i!=0);
        }
        putchar(')');
    }

    void positive()
    {
        //if( expression.size() <=0  )return;

        if(expression[0].a > 0)return;

        for(int i=0;i<expression.size();++i){
            expression[i].a = - expression[i].a;
        }
    }

    void timesK(int k)
    {
        if(k>1)

        //Expression res;
        for(int i=0;i<expression.size();++i)
            expression[i].a  *= k;
            //res.push_back( Node( expression[i].pow,k*expression[i].a ) );
        //return res;
    }
    void timesX(int k)
    {
        if(k>0)

        for(int i=0;i<expression.size();++i)
            expression[i].pow  += k;

    }

    void minus(const Expression& exp){
        Expression res;
        int i=0,j=0;
        int sz1 = expression.size();
        int sz2 = exp.expression.size();

        while(i<sz1 && j<sz2){
            const Node& np = expression[i];
            const Node& nq = exp.expression[j];

            if(np.pow < nq.pow){
               res.expression.push_back( Node(nq.pow, -nq.a) );
               j++;
            }
            else if(np.pow == nq.pow){
                i++;j++;
                if(np.a==nq.a)continue;
                res.expression.push_back( Node(np.pow, np.a-nq.a) );
                // i++; j++// continue_bug
            }

            else{
                res.expression.push_back( Node(np.pow, np.a) );
                i++;
            }
        }

        while(i<sz1){
            res.expression.push_back( Node( expression[i].pow, expression[i].a) );
            i++;
        }

        while(j<sz2){
            res.expression.push_back( Node(exp.expression[j].pow, - exp.expression[j].a) );
            j++;
        }

        expression = res.expression;
        //return res;

    }

    bool operator < (const Expression& exp) const{
        int sz1 = expression.size();
        int sz2 = exp.expression.size();

        for(int i=0;i<sz1 && i<sz2; ++i){
            if(expression[i] == exp.expression[i])continue;

            const Node& np = expression[i];
            const Node& nq = exp.expression[i];

            if( np.pow < nq.pow ){
                return true;
            }
            else if (np.pow==nq.pow){
                if( abs(np.a) != abs(nq.a) )
                    return abs(np.a) < abs(nq.a);

                return np.a < nq.a;

            }
            else{
                return false;
            }

        }

        return sz1 < sz2;

    }

    bool constant()
    {
        if(expression.size()<1)return true;

        if(expression.size()==1 && expression[0].pow==0) return true;

        return false;
    }
};

int gcd(int a, int b){  return b==0 ? a : gcd(b,a%b);}

Expression gcd(Expression& a, Expression& b)
{
    a.positive();
    b.positive();
#ifdef DEBUG

    puts("now:");
    puts("a=");
    a.output();puts("");
    puts("b=");
    b.output();puts("");
#endif

    if(b.constant()){
        return a;
    }


    Expression cpb = b;

    while(b.expression[0].pow <= a.expression[0].pow){

#ifdef DEBUG
        puts("next: a=");

        printf("a:pow=%d co=%d\n", a.expression[0].pow,a.expression[0].a);
#endif

        a.positive();
        b.positive();
        int ca = a.expression[0].a;
        int cb = b.expression[0].a;
        int c = (long long)ca*cb/gcd(ca,cb);

#ifdef DEBUG
        printf("c=%d\n",c);
        printf("a:pow=%d co=%d\n", a.expression[0].pow,a.expression[0].a);
        printf("b:pow=%d co=%d\n", b.expression[0].pow,b.expression[0].a);
#endif
        a.timesK(c/ca);
        b.timesK(c/cb);

#ifdef DEBUG
        puts("after timesK");
        printf("a:pow=%d co=%d\n", a.expression[0].pow,a.expression[0].a);
        printf("b:pow=%d co=%d\n", b.expression[0].pow,b.expression[0].a);
#endif
        b.timesX( a.expression[0].pow - b.expression[0].pow );

        a.minus(b);

        if(a.constant())break;

        b = cpb;


    }

    a.norm();
    b.norm();


    return gcd(cpb,a);
}



Expression ans[1200];

void deal(int k)
{
    int p,q;
    p=1;
    q=k;

    int i=1;
    while(i*i<k)i++;

    if(k>2)
    for(;i>=2;--i){
        if(k%i)continue;
        if(gcd(i,k/i)!=1)continue;
        p = i;
        q = k/i;
        break;
    }

    if (p==1){
        int b=2;
        while(b<k && k%b)b++;

        //trivial case 1
        if(b==k)
            ans[k].tr1(k);
        else
        //trivial case 2
            ans[k].tr2(k/b, ans[b] );
    }
    else{

        Expression ea;
        ea.tr2(k/p,ans[p]);

        Expression eb;
        eb.tr2(k/q,ans[q]);

        ans[k] = gcd(ea, eb);
    }
}


void verify()
{
    Expression t1,t2;

    Expression f2;
    Expression f3;

    f2.tr1(2);
    puts("f2=");
    f2.output();
    puts("");

    f3.tr1(3);
    puts("f3=");
    f3.output();
    puts("");

    t1.tr2(3, f2);
    t2.tr2(2, f3);

    Expression f6 = gcd(t1,t2);

    puts("f6=");
    f6.output();
    puts("");


    Expression f5;
    f5.tr1(5);
    Expression f7;
    f7.tr1(7);

    t1.tr2(5,f3);
    t2.tr2(3,f5);

    Expression f15 = gcd(t1,t2);

    puts("f15=");
    f15.output();
    puts("");

    t1.tr2(15,f2);
    t2.tr2(2,f15);

    Expression f30 = gcd(t1,t2);

    puts("f30=");
    f30.output();
    puts("");

    t1.tr2(15,f7);
    t2.tr2(7,f15);



    Expression f105 = gcd(t1,t2);
    puts("f105=");
    f105.output();
    puts("");

    t1.tr2(3,f7);
    t2.tr2(7,f3);
    Expression f21 = gcd(t1,t2);
    puts("f21=");
    f21.output();
    puts("");

    t1.tr2(5,f7);
    t2.tr2(7,f5);
    Expression f35 = gcd(t1,t2);
    puts("f35");
    f35.output();
    puts("");


    Expression f4;
    f4.tr2(2,f2);
    puts("f4=");
    f4.output();
    puts("");

    t1.tr2(4,f5);
    t2.tr2(5,f4);

    Expression f20 = gcd(t1,t2);

    puts("f20=");
    f20.output();
    puts("");

    t1.tr2(7,f20);
    t2.tr2(20,f7);

    Expression f140 = gcd(t1,t2);

    puts("f140=");
    f140.output();
    puts("");

    Expression f11;
    f11.tr1(11);

    puts("f11==");
    f11.output();
    puts("");

    t1.tr2(11,f35);
    t2.tr2(35,f11);

    Expression f385 = gcd(t1,t2);

    puts("f385=");
    f385.output();


}

int main()
{
    int n;


    //verify();
    //return 0;

    ans[1].expression.push_back( Node(1,1) );
    ans[1].expression.push_back( Node(0,-1) );

    for(int i=2;i<=1100;++i){
        deal(i);
    }

    while(scanf("%d",&n),n){
        if(n==1){
            puts("x-1");
            continue;
        }

        vector<Expression> ansv;

        for(int i=1;i<=n;++i){
            if(n%i==0) ansv.push_back( ans[i] );
        }

        sort(ansv.begin(),ansv.end());

        for(int i=0;i<ansv.size();++i){
           ansv[i].output();
        }
        puts("");

    }

    return 0;
}

G Spade 7 (HDU 4448)

H Building Design (HDU 4449)
http://blog.csdn.net/d891320478/article/details/8127374

I Draw Something (HDU 4450)
http://blog.csdn.net/shuimu12345678/article/details/8124566
http://www.cnblogs.com/kuangbin/archive/2012/10/29/2745368.html
http://nstxacm.blog.163.com/blog/static/2114423512012929920971/
http://blog.sina.com.cn/s/blog_71fda4350101a60o.html
http://blog.sina.com.cn/s/blog_9d987af5010177xh.html

J Dressing (HDU 4451)
http://blog.csdn.net/xinge008/article/details/8124544
http://www.cnblogs.com/kuangbin/archive/2012/10/29/2745368.html
http://blog.csdn.net/youngyangyang04/article/details/8126594
http://blog.sina.com.cn/s/blog_71fda4350101a6g8.html
http://blog.sina.com.cn/s/blog_9d987af5010177xj.html

K Running Rabbits (HDU 4452)
http://blog.csdn.net/zzxyyx_1/article/details/8125433
http://www.cnblogs.com/kuangbin/archive/2012/10/29/2745368.html
http://blog.sina.com.cn/s/blog_71fda4350101a6g0.html
http://www.cnblogs.com/moonbay/archive/2012/10/29/2745493.html
http://blog.sina.com.cn/s/blog_9d987af5010177xm.html

You can follow any responses to this entry through the RSS 2.0 You can skip to the end and leave a response. Pinging is currently not allowed.

22 Responses



留言

电子邮件地址不会被公开。 必填项已用*标注