TIOJ 1008 量杯問題

[BFS]
原來叫做"隱式圖搜索"@@

#include<algorithm>
#include<cmath>
#include<stdio.h>
#include<cstdlib>
#include<queue>
#include<set>
#include<cstring>
using namespace std;
#define min(x,y) (((x)>(y)) ? (y):(x))
#define max(x,y) (((x)>(y)) ? (x):(y))
#define LL long long int
class State
{
public:
    LL I[5];
    int Step;
    State(){I[0]=I[1]=I[2]=I[3]=I[4]=0,Step=0;}
    LL GetNum()const
    {return I[0]+I[1]*51+I[2]*51*51+I[3]*51*51*51+I[4]*51*51*51*51;}
    void Print(){printf("(%I64d %I64d %I64d %I64d %I64d)STP=%d\n",I[0],I[1],I[2],I[3],I[4],Step);}
};
queue<State> BFS;
set<LL> TB;
void Test(State IS)
{
    if(TB.count(IS.GetNum())) return;
    BFS.push(IS);
    TB.insert(IS.GetNum());
}
int main()
{
    TB.clear();
    int T;          scanf("%d",&T);
    LL Cont[5]; for(int lx=0;lx<T;lx++) scanf("%I64d",&Cont[lx]);
    LL Target;      scanf("%I64d",&Target);

    LL G=0;LL MAX=0;
    for(int lx=0;lx<T;lx++)
        G=__gcd(G,Cont[lx]);
    if(Target%G)
    {
        printf("-1\n");
        return 0;
    }
    for(int lx=0;lx<T;lx++)
        MAX=max(Cont[lx],MAX);
    if(MAX<Target)
    {
        printf("-1\n");
        return 0;
    }
    State Start;BFS.push(Start);
    bool OK=false;
    while(BFS.size()&&(OK==false))
    {
        State TMP=BFS.front();
        //TMP.Print();
        if((TMP.I[0]==Target)||(TMP.I[1]==Target)||(TMP.I[2]==Target)||
            (TMP.I[3]==Target)||(TMP.I[4]==Target))
            break;
        BFS.pop();
        for(int lx=0;lx<T;lx++)
        {
            State SA=TMP;SA.Step++;
            if(SA.I[lx]>0)
            {
                SA.I[lx]=0;
                Test(SA);
            }
            if(SA.I[lx]<Cont[lx])
            {
                SA.I[lx]=Cont[lx];
                Test(SA);
            }
            for(int ly=0;ly<T;ly++)
            {
                if(TMP.I[lx]==0) break;
                SA=TMP;
                SA.Step++;
                if(lx==ly) continue;
                LL Last=Cont[ly]-SA.I[ly];
                LL mm=min(Last,SA.I[lx]);
                SA.I[ly]+=mm,SA.I[lx]-=mm;
                Test(SA);
            }
        }
    }
    printf("%d\n",BFS.front().Step);
    return 0;
}

TIOJ 1198 8-puzzle

[BFS+狀態壓縮]
寫的有點冗:3

#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define INF 10000
#define ALP 1*2*3*4*5*6*7*8*9
#define N(x,y) (((y)-1)*3+(x)-1)
#define SWAP(x,y) x^=y^=x^=y
using namespace std;
int Mts[10]={1,1,2,2*3,2*3*4,
               2*3*4*5,2*3*4*5*6,2*3*4*5*6*7,
               2*3*4*5*6*7*8,2*3*4*5*6*7*8*9};
bool step[ALP+1];
class Status
{
public:
    int I[9];int x,y;int Step;
    Status()
    {
        for(int lx=0;lx<9;lx++)
            I[lx]=9-lx;
        Step=0;
        x=3,y=3;
    }
    int CountPrm()const
    {
        int RE=0;
        for(int lx=0;lx<9;lx++)
        {
            int sum=0;
            for(int ly=lx+1;ly<9;ly++)
                sum+=(I[ly]<I[lx]);
            RE+=sum*Mts[9-lx-1];
        }
        return RE+1;
    }
};
istream& operator>>(istream &in,Status &ss)
{
    for(int lx=0;lx<9;lx++)
        in >> ss.I[lx];
    for(int lx=0;lx<9;lx++)
        if(ss.I[lx]==0)
        {
            ss.y=lx/3+1;
            ss.x=lx%3+1;
            ss.I[lx]=9;
        }
    return in;
}
ostream& operator<<(ostream &out,Status &ss)
{
    for(int lx=0;lx<9;lx++)
    {
        out << ss.I[lx] << " ";
        if(lx%3==2) out << endl;
    }
    out << endl;
    out << "x=" << ss.x << " y=" << ss.y << endl;
    return out;
}
bool operator==(const Status &a1,const Status &b1)
{
    for(int lx=0;lx<9;lx++)
        if(a1.I[lx]!=b1.I[lx]) return false;
    return true;
}
queue<Status> BFS;
int main()
{
    //Initializing
    memset(step,false,sizeof(step));

    Status SStart,SEnd;
    cin >> SStart >> SEnd;
    //cout << SStart;
    BFS.push(SStart);
    if(SStart==SEnd){printf("0\n");return 0;}
    while(BFS.size())
    {
        if(BFS.front()==SEnd) break;
        Status SS=BFS.front();BFS.pop();
        //cout << SS;
        //getchar();
        if(SS.x>=2)
        {
            Status Sa;
            Sa=SS;Sa.Step++;
            SWAP(Sa.I[N(Sa.x-1,Sa.y)],Sa.I[N(Sa.x,Sa.y)]);
            Sa.x--;
            if(step[Sa.CountPrm()]==false)
            {
                step[Sa.CountPrm()]=true;
                BFS.push(Sa);
            }

        }
        if(SS.x<=2)
        {
            Status Sa;
            Sa=SS;Sa.Step++;
            SWAP(Sa.I[N(Sa.x+1,Sa.y)],Sa.I[N(Sa.x,Sa.y)]);
            Sa.x++;
            if(step[Sa.CountPrm()]==false)
            {
                step[Sa.CountPrm()]=true;
                BFS.push(Sa);
            }
        }
        if(SS.y>=2)
        {
            Status Sa;
            Sa=SS;Sa.Step++;
            SWAP(Sa.I[N(Sa.x,Sa.y-1)],Sa.I[N(Sa.x,Sa.y)]);
            Sa.y--;
            if(step[Sa.CountPrm()]==false)
            {
                step[Sa.CountPrm()]=true;
                BFS.push(Sa);
            }
        }
        if(SS.y<=2)
        {
            Status Sa;
            Sa=SS;Sa.Step++;
            SWAP(Sa.I[N(Sa.x,Sa.y+1)],Sa.I[N(Sa.x,Sa.y)]);
            Sa.y++;
            if(step[Sa.CountPrm()]==false)
            {
                step[Sa.CountPrm()]=true;
                BFS.push(Sa);
            }
        }
    }
    printf("%d\n",BFS.front().Step);
    return 0;
}

TIOJ 1011 Edit Distance In Numbers

[IMPLEMENT]

#include<stdio.h>
#include<stdlib.h>
#define LL unsigned long long int
#define min(a,b) (((a)>(b)) ?  (b):(a))
int dcret(LL I,bool aa[40])
{
    int lx;
    for(lx=0;I;I>>=1,lx++)
        aa[lx]=I&1;
    return lx;
}
int main()
{
    LL a,b;
    while(scanf("%I64u %I64u",&a,&b)==2)
    {
        bool aa[40],bb[40];
        int alen,blen,cc;
        int lx;
        alen=dcret(a,aa);
        blen=dcret(b,bb);
        cc=min(alen,blen);
        for(lx=0;lx<cc;lx++)
            if(aa[alen-lx-1]^bb[blen-lx-1])break;
        printf("%d\n",alen+blen-2*lx);
    }
    return 0;
}

TIOJ 1046 B.陷阱

[爆搜]
:3

#include<cstring>
#include<stdlib.h>
#include<stdio.h>
#define INF 100
#define min(a,b) ((a)>(b)) ? (b):(a)
bool Field[7][7];
bool Test[10][10];
int Rowcnt=0;
int RowLen=0;
int dfs(int x,int y,bool k)
{
    if(x==RowLen+1)
    {
        for(int ly=2;ly<=Rowcnt;ly++)
            for(int lx=1;lx<=RowLen;lx++)
                Test[ly][lx]=Test[ly-1][lx]^Test[ly-1][lx+1]^Test[ly-1][lx-1]^Test[ly-2][lx]^Field[ly-1][lx];
        for(int ly=1;ly<=Rowcnt;ly++)
            for(int lx=1;lx<=RowLen;lx++)
                if((Field[ly][lx])!=
                    (Test[ly][lx-1]^Test[ly][lx+1]^Test[ly][lx]^Test[ly-1][lx]^Test[ly+1][lx])) return INF;
        int sum=0;
        for(int ly=1;ly<=Rowcnt;ly++)
            for(int lx=1;lx<=RowLen;lx++)
                sum+=Test[ly][lx];
        return sum;
    }
    else if(y==1)
    {
        Test[y][x]=k;
        int a=dfs(x+1,y,false);
        int b=dfs(x+1,y,true);
        return min(a,b);
    }
}
int main()
{
    while(1)
    {
        char I[8];gets(I);
        Rowcnt=0;
        if(I[0]=='#')
            break;
        for(int lx=0;I[lx]!='\0';lx++)
            RowLen=lx+1;
        while(strlen(I)>0)
        {
            for(int lx=0;I[lx]!='\0';lx++)
                Field[Rowcnt+1][lx+1]=(I[lx]=='O');
            Rowcnt++;
            gets(I);
        }
        memset(Test,false,sizeof(Test));
        int a=dfs(1,1,false),b=dfs(1,1,true);
        int c=min(a,b);
        if(c>=INF)
            printf("Another Skeleton in the Ancient Tomb!\n");
        else
            printf("Minimum Steps : %d\n",c);
    }
    return 0;
}

TIOJ 1155 4.經濟編碼

[HEAP]
第一次用STL :3  

#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
priority_queue<double> minheap;
int main()
{
    int n;scanf("%d",&n);
    while(n--)
    {
        char a[5];double b;
        scanf("%s %lf",a,&b);
        minheap.push(-b);
    }
    double penalty=0;
    while(minheap.size()>=2)
    {
        double a,b;
        a=minheap.top(); minheap.pop();
        b=minheap.top(); minheap.pop();
        penalty+=a+b;
        minheap.push(a+b);
    }
    printf("%.2f",-penalty);
    return 0;
}

POJ 2492 A Bug's Life

[DISJIONT SET]

#include<stdio.h>
#include<cstring>
#define BUGN 2000
class Node
{
public:
    int Fat;
    int Rank;
};
Node ptr[2*BUGN];
void Init(int n)
{
    for(int lx=0;lx<2*n;lx++)
        ptr[lx].Fat=lx,ptr[lx].Rank=1;
}
int Getfather(int I)
{
    if(ptr[I].Fat==I)
        return I;
    ptr[I].Fat=Getfather(ptr[I].Fat);
    return ptr[I].Fat;
}
void Union(int a,int b)
{
    int af=Getfather(a);
    int bf=Getfather(b);
    if(ptr[af].Rank>ptr[bf].Rank)
        ptr[bf].Fat=af;
    else if(ptr[af].Rank<ptr[bf].Rank)
        ptr[af].Fat=bf;
    else
    {
        ptr[af].Fat=bf;
        ptr[bf].Rank++;
    }
}
int main()
{
    int T,lx=1;scanf("%d",&T);
    while(T--)
    {
        printf("Scenario #%d:\n",lx);
        int n,s;scanf("%d %d",&n,&s);
        Init(n);
        int pa,pb;
        while(s--)
        {
            scanf("%d %d",&pa,&pb);
            Union(pa-1,n+pb-1);
            Union(pb-1,n+pa-1);
        }
        int Check=true;
        for(int lx=0;(lx<n)&&Check;lx++)
            Check=(Getfather(lx)!=Getfather(n+lx));
        if(!Check)
            printf("Suspicious bugs found!\n\n");
        else
            printf("No suspicious bugs found!\n\n");
        lx++;
    }
    return 0;
}

STEP5 0035 蘿莉不同色問題

[數論]
先備：1. 指數原根 2. Baby step-Giant step

這題真不是普通的好玩XDD

總之，照題意，要解x：

先抓p的原根g

然後對兩邊取index：

然後解Linear方程。

/*      LANG:C++
**  http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0035
**      NUMBER THEORY
**      2013-11-8
*/
#include<cstring>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<math.h>
#include<assert.h>
#include<vector>
#define PMAX 100000
#define Mid(a,b) ((a+b)>>1)
#define LL long long int
#define PS printf("PS[%d]\n",step++);
using namespace std;
int step=0;
///Set up Prime Table
vector<LL> PRIME;
bool seive[PMAX+1];

void BuildPrimeTable()
{
    memset(seive,true,sizeof(seive));
    seive[1]=false;
    PRIME.clear();
    for(LL lx=2;lx<=PMAX;lx++)
    {
        if(seive[lx])
        {
            PRIME.push_back(lx);
            for(LL ly=2;ly*lx<=PMAX;ly++)
                seive[lx*ly]=false;
        }
    }
}

///Get the primitive root of P
LL P;
vector<LL> Drc;
LL _Pow(LL a,LL n,LL _PP)
{
    if(n==0) return 1;
    if(n==1) return a%_PP;
    LL k=_Pow(a%_PP,n/2,_PP);
    if(n%2)
        return (((k*k)%_PP)*a)%_PP;
    else
        return (k*k)%_PP;
}
LL _Pow(LL a,LL n)
{
    return _Pow(a,n,P);
}
//536877277
void DrcPrime()
{

    LL prc=P-1;
    Drc.clear();
    //printf("a1");
    for(int lx=0;(PRIME.size()>lx)&&(PRIME[lx]<prc);lx++)
    {
        if(prc%PRIME[lx]==0)
        {
            Drc.push_back(PRIME[lx]);
            while(prc%PRIME[lx]==0)
                prc/=PRIME[lx];
            //printf("%I64d\n",PRIME[lx]);
        }

    }

    if(prc>1)
        Drc.push_back(prc);
    //printf("a1");
}
LL GetPrimitiveRoot()
{
    for(LL lx=2;lx<=P;lx++)
    {
        bool isRoot=true;
        for(LL ly=0;ly<Drc.size();ly++)
            if(_Pow(lx,(P-1)/Drc[ly])==1){isRoot=false;break;}
        if(isRoot)
            return lx;
    }
}
///Babystep  prt^a=r
class Data
{
public:
    LL index;
    LL cont;
    Data(){}
    void set(const LL _i,const LL _c){index=_i,cont=_c;}
};
bool operator<(Data _aa,Data _bb){return (_aa.cont<_bb.cont);}
Data* brysch(Data *I,LL c,LL m)
{
    //prLLf("SCH:%d\n",c);
    LL start=0,end=m-1;
    while((end-start)>1)
    {
        //prLLf("END=%d START=%d\n",end,start);
        if(I[start].cont==c)
            return &I[start];
        else if(I[end].cont==c)
            return &I[end];
        else if(I[Mid(start,end)].cont==c)
            return &I[Mid(start,end)];
        if(c>I[Mid(start,end)].cont)
            start=Mid(start,end);
        else
            end=Mid(start,end);
    }
    if(I[start].cont==c)
        return &I[start];
    else if(I[end].cont==c)
        return &I[end];
    else
        return NULL;
}
Data sqrtb[PMAX];
LL GetInd(LL prt,LL r)
{

    r=(r%P+P)%P;//prLLf("GetInd(%d,%d)\n",prt,r);
    LL m=ceil(sqrt(P));

    for(LL lx=0,prc=1;lx<m;lx++,prc=(prc*prt)%P)
        sqrtb[lx].set(lx,prc);
    sort(sqrtb,sqrtb+m);
    /*for(LL lx=0;lx<m;lx++)
        prLLf("%d:%d\n",sqrtb[lx].index,sqrtb[lx].cont);*/
    LL base=_Pow(prt,m*(P-2));
    //printf("base=%d\n",base);
    for(LL lx=0,prc=1;lx<m;lx++,prc=(prc*base)%P)
    {
        //printf("prc=%d\n",prc);
        Data *RES=brysch(sqrtb,(r*prc)%P,m);
        if(RES==NULL) continue;
        return (*RES).index+m*lx;
    }
    return -1;
}

///ax=b mod P-1 ,return x
LL phi(LL m)
{
    LL prc=P;
    LL ret=1;
    for(LL lx=0,prc=m;(lx<PRIME.size())&&(PRIME[lx]<=prc);lx++)
    {
        if(prc%PRIME[lx]==0)
        {
            LL nn=1;prc/=PRIME[lx];
            while(prc%PRIME[lx]==0)
                prc/=PRIME[lx],nn*=PRIME[lx];
            ret*=nn*(PRIME[lx]-1);
        }
    }
    return ret;
}
LL Linear(LL a,LL b)
{
    LL MM=P-1;
    LL gg=__gcd(a,MM);
    //printf("gg=%I64d\n",gg);
    //assert(gg);
    MM/=gg;
    a/=gg;
    b/=gg;
    //printf("{%I64d}}\n",phi(MM));
    return (b*_Pow(a,phi(MM)-1,MM))%MM;
}
int main()
{
    BuildPrimeTable();
    LL X0,X1,K,N;
    LL proot;
    long long int Kqq;
    //scanf("%d",&P);
    scanf("%I64d %I64d %I64d %I64d %I64d",&X0,&X1,&Kqq,&N,&P);
    //PS
    if(Kqq>=0)
        K=Kqq;
    else
        K=P+Kqq;
    DrcPrime();
    proot=GetPrimitiveRoot();
    LL aa,bb;//ax=b;
    LL qq=0;
    if(X1>=X0)
        qq=(X1-X0);
    else
        qq=P+X1-X0;
    aa=N-1;bb=GetInd(proot,(K*_Pow(qq,P-2))%P);
    //printf("a=%d b=%d\n",aa,bb);
    //printf("proot=%I64d\n",proot);
    //PS
    LL a,b;a=_Pow(proot,Linear(aa,bb));
    if(X1>=X0*a)
        qq=X1-X0*a;
    else
        qq=P+X1-X0*a;
    b=(qq%P+P)%P;
    //PS
    printf("%I64d %I64d\n",a,b);
    for(LL lx=0,prc=X0;lx<=N;lx++,prc=(prc*a+b)%P)
        printf("%I64d ",prc);
    printf("\n");
    return 0;
}

TIOJ 1514 Problem D. 橫掃射擊場

[數論]

#include<stdio.h>
#include<cstring>
#include<math.h>
#include<vector>
using namespace std;
#define LL long long int
#define N 1000001
LL phi[N];
LL PHI[N];
bool seive[N];
vector<int> PRIME;
int main()
{
    //BUILD PHI TABLE;
    phi[1]=1;
    for(int lx=2;lx<=N-1;lx++)
    {
        if(!seive[lx])
        {
            phi[lx]=lx-1;
            PRIME.push_back(lx);
        }
        for(int ly=0;lx*PRIME[ly]<N;ly++)
        {
            seive[lx*PRIME[ly]]=1;
            if(lx%PRIME[ly]==0)
            {
                phi[lx*PRIME[ly]]=phi[lx]*PRIME[ly];
                break;
            }
            else
                phi[lx*PRIME[ly]]=phi[lx]*(PRIME[ly]-1);
        }
    }
    PHI[1]=phi[1];
    for(int lx=2;lx<=N-1;lx++)
        PHI[lx]=PHI[lx-1]+phi[lx];
    int II;
    while(scanf("%d",&II)&&(II>0))
        printf("%I64d\n",2*PHI[II]+1);
    return 0;
}