POJ 2318 TOYS

[計算幾何]
寫計算幾何耍廢XDD

#include<cstring>
#include<stdio.h>
#include<algorithm>
int top,bottom;
class line
{
public:
    int U,L;
    line(){U=0;L=0;}
    void set(int _u,int _l){U=_u;L=_l;}
};
class point
{
public:
    int X,Y;
    point(){X=0;Y=0;}
};
bool operator<(line L1,line L2)
{
    return L1.U<L2.U;
}
bool operator<(line L,point P)
{
    return (((P.Y-bottom)*(L.U-L.L)+(L.L-P.X)*(top-bottom))<0);
}
bool operator<(point P,line L)
{
    return (1-(L<P));
}
line    Ls[5000];   int Lcnt;
int Pcnt;
int Boxcnt[5001];
int main()
{
    while(scanf("%d",&Lcnt)==1)
    {
        if(Lcnt==0) break;
        scanf("%d",&Pcnt);
        memset(Boxcnt,0,sizeof(Boxcnt));
        Lcnt+=2;
        int x1,x2;scanf("%d %d %d %d",&x1,&top,&x2,&bottom);
        Ls[0].set(x1,x1);
        Ls[Lcnt-1].set(x2,x2);
        for(int lx=1;lx<Lcnt-1;lx++)
        {
            scanf("%d %d",&x1,&x2);
            Ls[lx].set(x1,x2);
        }
        std::sort(Ls,Ls+Lcnt);
        point PP;
        for(int lx=0;lx<Pcnt;lx++)
        {
            scanf("%d %d",&PP.X,&PP.Y);
            for(int ly=0;ly<Lcnt-1;ly++)
            {
                if((Ls[ly]<PP)&&(PP<Ls[ly+1]))
                {
                    Boxcnt[ly]++;
                    break;
                }
            }
        }
        for(int ly=0;ly<Lcnt-1;ly++)
            printf("%d: %d\n",ly,Boxcnt[ly]);
        printf("\n");
    }
    return 0;
}

STEP5 0097 : 番外篇：ハト

[數學]
應該算是個純數學題@@不過因為原式有點醜，所以用遞迴的方式把他AC掉了

題目要求：





用這兩個性質：

#include<stdio.h>
#include<algorithm>
#include<math.h>
#define LL long long int
using namespace std;
LL f(LL N,LL q,LL p)
{
    //printf("call f(%d,%d,%d)\n",N,q,p);
    if((N*q/p)==0) return 0;
    if(q%p==0) return N*(N+1)/2*(q/p);
    if(q>p) return f(N,q%p,p) + N*(N+1)/2*(q/p);
    return N*((N*q)/p) - f(N*q/p,p,q)+N/p;
}
int main()
{
    LL n,a,b;
    while(scanf("%I64d %I64d %I64d",&n,&a,&b)!=EOF)
        printf("%I64d\n",f(n,a/__gcd(a,b),b/__gcd(a,b)));
    return 0;
}

TIOJ 1022 H.跑跑卡恩車

[BFS]

/* LANG:CPP
** http://tioj.redirectme.net:8080/JudgeOnline/showproblem?problem_id=1022
** 2013-11-03
** BFS
*/
#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#include<math.h>
#include<vector>
int table[101][101];
int dp[101][101];
int m,n;
struct point{
    int x,y;
    void Print()
    {
        printf("(%d,%d)\n",x,y);
    }
};
bool Check(int x,int y)
{
    return ((x>=1)&&(y>=1)&&(x<=m)&&(y<=n));
}
int main()
{
    point start;
    start.x=1;start.y=1;
    int T;scanf("%d",&T);
    while(T--)
    {
        memset(dp,0,sizeof(dp));
        scanf("%d %d",&m,&n);
        for(int lx=1;lx<=m;lx++)
            for(int ly=1;ly<=n;ly++)
                scanf("%d",&table[lx][ly]);
        std::vector<point> in;      in.push_back(start);
        std::vector<point> out;     out.clear();
        dp[1][1]=1;
        point tmp;
        int step=1;
        while(in.size()&&(dp[m][n]==0))
        {
            //printf("step=%d\n",in.size());
            step++;
            for(int lx=0;lx<in.size();lx++)
            {

                int px=in[lx].x,py=in[lx].y;
                //printf("On(%d,%d)=%d\n",px,py,dp[px][py]);
                if(Check(px-1,py)&&(dp[px-1][py]==0)&&(abs(table[px][py]-table[px-1][py])<=5))
                {
                    tmp.x=px-1; tmp.y=py;
                    out.push_back(tmp);
                    dp[px-1][py]=step;
                    //tmp.Print();
                }
                if(Check(px+1,py)&&(dp[px+1][py]==0)&&(abs(table[px][py]-table[px+1][py])<=5))
                {
                    tmp.x=px+1; tmp.y=py;
                    out.push_back(tmp);
                    dp[px+1][py]=step;
                    //tmp.Print();
                }
                if(Check(px,py-1)&&(dp[px][py-1]==0)&&(abs(table[px][py-1]-table[px][py])<=5))
                {
                    tmp.x=px; tmp.y=py-1;
                    out.push_back(tmp);
                    dp[px][py-1]=step;
                    //tmp.Print();
                }
                if(Check(px,py+1)&&(dp[px][py+1]==0)&&(abs(table[px][py]-table[px][py+1])<=5))
                {
                    tmp.x=px; tmp.y=py+1;
                    out.push_back(tmp);
                    dp[px][py+1]=step;
                    //tmp.Print();
                }
            }
            in.clear();
            for(int lx=0;lx<out.size();lx++)
                in.push_back(out[lx]);
            out.clear();
            /*for(int lx=1;lx<=m;lx++)
            {
                for(int ly=1;ly<=n;ly++)
                    printf("%d ",dp[lx][ly]);
                printf("\n");
            }
            system("PAUSE");*/
        }

        printf("%d\n",dp[m][n]-1);
    }
    return 0;
}

TIOJ 1356 河內之塔-便當塔

[D&C]

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int prc=0;
void MSG(int a,int b)
{
    prc++;
    printf("#%d : move the dish from #%d to #%d\n",prc,a,b);
}
void move(int a,int to)
{
    if(a==1)
    {
        MSG(4-to,2);
        MSG(2,to);
        return;
    }
    move(a-1,to);
    MSG(4-to,2);
    move(a-1,4-to);
    MSG(2,to);
    move(a-1,to);
}
int main()
{
    int a;scanf("%d",&a);
    move(a,3);
    return 0;
}

STEP5 0085 切木棒

[背包]

/*      LANG:CPP
**      STEP5 http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0085
**      2013-11-2
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 10000
#define max(x,y) (((x)>(y)) ? (x):(y))
int money[N+1];
int dp[2][N+1];
int main()
{
    int L;scanf("%d",&L);
    for(int lx=1;lx<=L;lx++)
        scanf("%d",&money[lx]);
    for(int lx=0;lx<=L;lx++)
        dp[0][lx]=0,dp[1][lx]=0;
    for(int lx=1;lx<=L;lx++)
    {
        for(int lm=1;lm<=L;lm++)
            if(lm<lx)
                dp[1][lm]=dp[0][lm];
            else
                dp[1][lm]=max(dp[0][lm],dp[0][lm-lx]+money[lx]);
        for(int lm=0;lm<=L;lm++)
            dp[0][lm]=dp[1][lm];
    }

    /*for(int lx=1;lx<=L;lx++)
    {
        for(int ly=1;ly<=L;ly++)
            printf("%d ",dp[lx][ly]);
        printf("\n");
    }*/
    printf("%d\n",dp[0][L]);
    return 0;
}

TIOJ 1355 河內之塔-蘿莉塔

[D&C]

#include<stdio.h>
int prc=0;
void Deal(int a,int s,int e)
{
        if(a==1)
        {
                printf("#%d : move the dish from #%d to #%d\n",++prc,s,e);
                return;
        }
        Deal(a-1,s,6-s-e);
        printf("#%d : move the dish from #%d to #%d\n",++prc,s,e);
        Deal(a-1,6-s-e,e);
}
int main()
{
        int k;scanf("%d",&k);
        Deal(k,1,3);
        return 0;
}

STEP5 0132 汁男區間

[線段樹]

原本可以10分鐘寫完的QAQ 竟然卡__gcd

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<iostream>
using namespace std;
#define N 100000
int a[N];
int gcdTree[4*N];
int base;
int n;
int gcd(int a,int b)
{
    if(a*b==0)
        return a+b;
    if(b>a)
        a^=b^=a^=b;
    if(a%b==0)
        return b;
    return gcd(b,a%b);
}
void BuildTree()
{
    base=(int)pow(2,ceil(log2(n)))-1;
    if(base==(n-1))
        base=base*2+1;
    for(int lx=0;lx<n;lx++)
        gcdTree[lx+base+1]=a[lx];
    for(int lx=base;lx;lx--)
        gcdTree[lx]=gcd(gcdTree[lx*2],gcdTree[lx*2+1]);
}
int Ask(int a,int b)
{
    int re=0;
    for(a+=base-1,b+=base+1;a^b^1;a>>=1,b>>=1)
    {
        if(~a&1) re=gcd(re,gcdTree[a^1]);
        if(b&1) re=gcd(re,gcdTree[b^1]);
    }
    return re;
}
int main()
{
    int q;
    scanf("%d %d",&n,&q);
    for(int lx=0;lx<n;lx++)
        scanf("%d",&a[lx]);
    BuildTree();
    int a,b;
    while(q--)
    {
        scanf("%d %d",&a,&b);
        printf("%d\n",Ask(a,b));
    }
    return 0;
}