TIOJ 1607 Problem A 山稜線 (CATALN)

[DP+模逆]
把卡特蘭數炸開就可以了= =

複雜度：

卡 unsigned long long int 卡超久= =

#include<stdio.h>
#include<cstring>
#include<algorithm>
#define LL unsigned long long int
LL MOD = 1000000007;
LL _POW(LL a,LL n)
{
    a%=MOD;
    //printf("_POW(%I64d,%I64d)\n",a,n);
    if(a<=1) return a;
    if(n==0) return 1;
    if(n==1) return a;
    LL k = _POW(a,n/2);
    if(n%2==0) return (k*k)%MOD;
    else    return (k*((k*a)%MOD))%MOD;
}
LL dp[500001];
LL Sn[500001];
int main()
{
    //printf("D=%I64d\n",_POW(10,MOD-1));
    int T;scanf("%d",&T);
    LL S2n=1;
    Sn[0]=1;
    for(LL prc=1;prc<=500000;prc++)
    {
        Sn[prc]=(Sn[prc-1]*prc)%MOD;
        S2n=(((((prc*(2*prc-1))%MOD)*2)%MOD)*S2n)%MOD;
        //LL D=(((Sn*(prc+1))%MOD)*(Sn))%MOD;
        //printf("D=%I64d\n",_POW(100,MOD-1));
        //D=_POW(D,MOD-2);
        dp[prc]=S2n;
    }
    while(T--)
    {
        int n;scanf("%d",&n);n/=2;
        LL D=(((Sn[n]*(n+1))%MOD)*(Sn[n]))%MOD;
        D=_POW(D,MOD-2);
        printf("%I64u\n",(dp[n]*D)%MOD);
    }
    return 0;
}

POJ 2653 Pick-up sticks

[計算幾何:叉積]
原本以為直接爆會超時ㄎㄎ

#include<cmath>
#include<algorithm>
#include<stdio.h>
#include<vector>
#include<cstring>
#define MAX 100000
#define EPS 1E-8
using namespace std;
class Point
{
public:
    double x,y;
    Point(){}
    Point(double _x,double _y) : x(_x),y(_y){}
};
class Segment
{
public:
    Point aa,bb;
    Segment(){}
    Segment(Point _aa,Point _bb): aa(_aa),bb(_bb){}
};
double GetCrossMult(const Point _A,const  Point _B,const Point _O)
{
    return (_A.x-_O.x)*(_B.y-_O.y)-(_B.x-_O.x)*(_A.y-_O.y);
}
bool IsIntersect(Segment sg1,Segment sg2)
{
    return (GetCrossMult(sg2.aa, sg2.bb, sg1.aa)*GetCrossMult(sg2.aa, sg2.bb, sg1.bb)<EPS)&&
                (GetCrossMult(sg1.aa, sg1.bb, sg2.aa)*GetCrossMult(sg1.aa, sg1.bb, sg2.bb)<EPS);
}
Segment Sgs[MAX];
int Sgscnt;
int main()
{
    vector<int> tmp;
    while(scanf("%d",&Sgscnt)&&Sgscnt)
    {
        tmp.clear();
        for(int lx=0;lx<Sgscnt;lx++)
            scanf("%lf %lf %lf %lf",&Sgs[lx].aa.x,&Sgs[lx].aa.y,&Sgs[lx].bb.x,&Sgs[lx].bb.y);
        for(int lx=0;lx<Sgscnt;lx++)
        {
            bool IsCross=false;
            for(int ly=lx+1;ly<Sgscnt&&!IsCross;ly++)
                IsCross=IsIntersect(Sgs[lx],Sgs[ly]);
            if(IsCross==false)
                tmp.push_back(lx);
        }
        printf("Top sticks:");
        for(int lx=0;lx<tmp.size();lx++)
            printf(" %d%c",tmp[lx]+1,((lx==tmp.size()-1) ? '.':','));
        printf("\n");
    }
    return 0;
}

POJ 3304 Segments

[計算幾何：叉積]
Note double指定次數越少越好

#include<stdio.h>
#include<cstring>
#include<cmath>
#define MAX 110
#define EPS 1E-8
using namespace std;
class Point
{
public:
    double x,y;
    Point(){x=0,y=0;}
    void Print(){printf("(%.2lf %.2lf)",x,y);}
};
class Segment
{
public:
    Point aa,bb;
    Segment(){}
    Segment(const Point _aa,const Point _bb):aa(_aa),bb(_bb){}
    void set(Point _aa,Point _bb){aa=_aa,bb=_bb;}
    void Print(){aa.Print();bb.Print();puts("\n");}
};
Segment Sgs[MAX];
int Sgscnt;
double Cross(Point _A,Point _B,Point _O)
{
    return ((_A.x-_O.x)*(_B.y-_O.y)-(_B.x-_O.x)*(_A.y-_O.y));
}
bool Check(Segment sg)
{
    //sg.Print();
    if((abs(sg.aa.x-sg.bb.x)<EPS)&&
        (abs(sg.aa.y-sg.bb.y)<EPS))
        return false;
    for(int lx=0;lx<Sgscnt;lx++)
        if(Cross(sg.aa,sg.bb,Sgs[lx].aa)*Cross(sg.aa,sg.bb,Sgs[lx].bb)>EPS)
            return false;
    return true;
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&Sgscnt);
        for(int lx=0;lx<Sgscnt;lx++)
            scanf("%lf %lf %lf %lf",&Sgs[lx].aa.x,&Sgs[lx].aa.y,&Sgs[lx].bb.x,&Sgs[lx].bb.y);
        bool CHECK=(Sgscnt<3);
        for(int lx=0;lx<Sgscnt&&!CHECK;lx++)
        {
            for(int ly=lx+1;ly<Sgscnt&&!CHECK;ly++)
            {
                if(Check(Segment(Sgs[lx].aa,Sgs[ly].aa))) CHECK=true;
                else if(Check(Segment(Sgs[lx].aa,Sgs[ly].bb))) CHECK=true;
                else if(Check(Segment(Sgs[lx].bb,Sgs[ly].aa))) CHECK=true;
                else if(Check(Segment(Sgs[lx].bb,Sgs[ly].bb))) CHECK=true;
            }
        }
        if(CHECK)
            printf("Yes!\n");
        else
            printf("No!\n");
    }
    return 0;
}

POJ 1269 Intersecting Lines

[計算幾何]
NOTE:
誤差((double)i/(double)j) > 誤差(i/(double)j)

#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#include<algorithm>
using namespace std;
class Point
{
public:
    int x,y;
    Point(){x=0,y=0;}
    Point(int _x,int _y){x=_x,y=_y;}
    void set(int _x,int _y){x=_x,y=_y;}
    void Scan(){scanf("%d %d",&x,&y);}
};
class Line
{
public:
    int a,b,c;//ax+by+c=0;
    Line(){a=0,b=0,c=0;}
    void set(int _a,int _b,int _c)
    {
        a=_a,b=_b,c=_c;
    }
    void set(Point p1,Point p2)
    {
        set((p1.y-p2.y),(p2.x-p1.x),p1.x*p2.y-p1.y*p2.x);
    }
    void Scan()
    {
        Point a,b;
        a.Scan();b.Scan();
        set(a,b);
    }
};
int det(int a,int b,int c,int d){return a*d-b*c;}
int main()
{
    int T;scanf("%d",&T);
    printf("INTERSECTING LINES OUTPUT\n");
    while(T--)
    {
        Line L1,L2;   L1.Scan();L2.Scan();
        int D=det(L1.a,L1.b,L2.a,L2.b);
        int xx=det(L1.c,L1.b,L2.c,L2.b);
        int yy=det(L1.c,L1.a,L2.c,L2.a);
        if(D==0)
        {
            if((xx==0)&&(yy==0))
                printf("LINE\n");
            else
                printf("NONE\n");
        }
        else
            printf("POINT %.2f %.2f\n",-xx/(double)D,yy/(double)D);
    }
    printf("END OF OUTPUT\n");
    return 0;
}

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;
}