UVA 112 - Tree Summing

[有限狀態自動機?]
原本寫了一個建樹的@@

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define NONE -1
enum TYPE
{
TYPE_NULL=-1,
TYPE_NUM,
TYPE_LEFTQ,
TYPE_RIGHTQ
};
class Token
{
public:
TYPE Type;
int val;
Token():Type(TYPE_NULL),val(0){};
void Set(char *I)
{
if(I[0]==')') Type=TYPE_RIGHTQ;
else if(I[0]=='(') Type=TYPE_LEFTQ;
else if(I[0]=='\0') Type=TYPE_NULL;
else
{
val=0;
Type=TYPE_NUM;
int sgn=1;
if(I[0]=='-') sgn=-1;
for(int lx=(sgn==-1);I[lx]!='\0';lx++)
val=val*10+(I[lx]-'0');
val*=sgn;
}
}
};

Token Line[10000];int Tokcnt=0,Tokptr=0;

void NextToken()
{
Tokptr++;
}
void AddToken(char *I)
{
if(I[0]=='\0') return ;
// printf("Add [%s]\n",I);
Line[Tokcnt].Set(I);
Tokcnt++;
}
bool judge;
bool Tree(int n,int k) // TREE自動機
{
// printf("%d\n",Line[Tokptr].Type);
NextToken();
if(Line[Tokptr].Type==TYPE_RIGHTQ)
{
NextToken();
return true;
}
else
{
int vv=Line[Tokptr].val;
NextToken();
bool bleft=Tree(n+vv,k);
bool bright=Tree(n+vv,k);
NextToken();
if((bleft&&bright))
judge=(judge||((n+vv)==k));
return false;
}
}
void ReadData()
{
Tokcnt=0;
Tokptr=0;
judge=false;
int flag=1;
char c=getchar();
while(c!='(')
c=getchar();
AddToken("(");
char TOK[100];
int TOKlen=0;
while(flag)
{
c=getchar();
if((c==' ')||(c=='\n')||(c=='\t'))
{
TOK[TOKlen]='\0';
AddToken(TOK);
TOKlen=0;
}
else if(c=='(')
{
TOK[TOKlen]='\0';
AddToken(TOK);
TOKlen=0;
AddToken("(");
flag++;
}
else if(c==')')
{
TOK[TOKlen]='\0';
AddToken(TOK);
TOKlen=0;
AddToken(")");
flag--;
}
else
TOK[TOKlen++]=c;
}
}
int main()
{
int k;
while(scanf("%d",&k)!=EOF)
{
ReadData();
Tree(0,k);
if(judge)
printf("yes\n");
else
printf("no\n");
}
return 0;
}

UVA 136 - Ugly Numbers

基本上，這題應該算水題，但背後隱含的概念比較特別。

比如說：

任一個多項式可以被無限個質數整除

這就說明，若將

2^a*3^b*5^c 所有數蒐集起來排序，成長速度將會大於多項式成長

這讓我滿擔心若直接蒐的話，會不會很慢，不過看來不會XD

UVA 147 - Dollars

[DP]

空間尚可省

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<cstring>
#include<vector>
#define min(x,y) (((x)>(y)) ? (y):(x))
#define max(x,y) (((x)>(y)) ? (x):(y))
using namespace std;
#define DOL 11
#define LL long long int
int dollars[DOL]={5,10,20,50,100,200,500,1000,2000,5000,10000};
LL Table[DOL][30010];
LL getTable(int type,int money)
{
    if(money<0) return 0;
    if(money==0) return 1;
    if(type<0) return 0;
    return Table[type][money];
}
int main()
{
    memset(Table,0,sizeof(Table));
    for(int lx=0;lx<DOL;lx++)
        for(int ly=1;ly<=30000;ly++)
            Table[lx][ly]=getTable(lx-1,ly)+getTable(lx,ly-dollars[lx]);
/*  for(int ly=0;ly<=30;ly++)
    {
        for(int lx=0;lx<5;lx++)
            printf("%lld\t",getTable(lx,ly));
        printf("\n");
    }*/
    int m1,m2;
    while((scanf("%d.%d",&m1,&m2)!=EOF)&&(m1+m2))
        printf("%3d.%02d%17lld\n",m1,m2,getTable(DOL-1,m1*100+m2));
    return 0;
}

STEP5 0051 Ch特別篇-5.數學作業2

[MATH]

分解成質數的冪次後就AC了XDD

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<cstring>
#include<vector>
#define min(x,y) (((x)>(y)) ? (y):(x))
#define max(x,y) (((x)>(y)) ? (x):(y))
using namespace std;
#define NN 1000010
#define LL long long int
bool seive[NN+10];
vector<LL> PRIME;
vector<LL> Conds;
vector<LL> Ins;
void maketable()
{
memset(seive,false,sizeof(seive));
for(int lx=2;lx<=NN;lx++)
{
if(seive[lx]==false)
{
PRIME.push_back((LL)lx);
for(int ly=2;ly*lx<=NN;ly++)
seive[ly*lx]=true;
}
}
}
void add(LL II)
{
bool Exist=false;
for(int lx=0;lx<Conds.size();lx++)
if(Conds[lx]%II==0)
return;
else if(II%Conds[lx]==0)
{
Conds.erase(Conds.begin()+lx);
Conds.push_back(II);
return;
}
Conds.push_back(II);
}
int main()
{
maketable();
int N;scanf("%d",&N);
for(int lx=0;lx<N;lx++)
{
LL I;scanf("%I64d",&I);
Ins.push_back(I);
for(int lx=0;(lx<PRIME.size())&&(PRIME[lx]<I);lx++)
{
if(I%PRIME[lx]==0)
{
//printf("PRIME=%I64d\n",PRIME[lx]);
LL a=1;
while(I%PRIME[lx]==0)
{
a*=PRIME[lx];
I/=PRIME[lx];
}
add(a);
}
}
if(I>1)
add(I);
}
#ifdef DEBUG
for(int lx=0;lx<Conds.size();lx++)
printf("%I64d ",Conds[lx]);
#endif
LL match[1000];
for(int lx=0;lx<N;lx++)
match[lx]=1;
for(int lx=0;lx<Conds.size();lx++)
{
for(int ly=0;ly<Ins.size();ly++)
if(Ins[ly]%Conds[lx]==0)
{
match[ly]*=Conds[lx];
break;
}
}
for(int lx=0;lx<N;lx++)
printf("%I64d ",match[lx]);
return 0;
}

UVAOJ 151 - Power Crisis

[IMPLEMENT]



#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define min(x,y) (((x)>(y)) ? (y):(x))
#define max(x,y) (((x)>(y)) ? (x):(y))
using namespace std;
bool check(int n,int k)
{
queue<int>Que;
for(int lx=1;lx<=n;lx++)
Que.push(lx);
int prck=0;
while(Que.size())
{
int a=Que.front();
Que.pop();
if(prck!=0)
Que.push(a);
else
{
//printf("kill %d\n",a);
if(a==13) break;
}

prck=(prck+1)%k;
}
return (Que.size()==0);
}
int main()
{
int I;
while(scanf("%d",&I)&&I)
{
for(int lx=1;lx<=I-1;lx++)
{
//printf("check(%d):\n",lx);
if(check(I,lx))
{
printf("%d\n",lx);
break;
}
}

}
return 0;
}

UVAOJ 105 - The Skyline Problem

[Heap]

恩 MlogN
是說最近懶得幫他著色了= =

#include<stdio.h>
#include<algorithm>
#include<queue>
#define CM 10010
using namespace std;
class BuildLine
{
public:
    int L,R;
    int H;
    BuildLine():L(0),R(0),H(0){}
    void set(int a,int b,int c)
    {
        L=a,R=b,H=c;
    }
    void Print()const
    {
        printf("Building: (%d %d)=(%d)\n",L,R,H);
    }
};
bool operator< (BuildLine a,BuildLine b)
{
    return (a.H<b.H);
}
bool sortfunc(BuildLine a,BuildLine b)
{
    return (a.L<b.L);
}
priority_queue<BuildLine>Heap;
BuildLine Builds[5050];
int BuildCnt;
int Height[CM+1];
int main()
{
    int a,b,c;
    int Rm=0;
    while(Heap.size())
        Heap.pop();
    BuildCnt=0;
    while(scanf("%d %d %d",&a,&b,&c)!=EOF)
    {
        Builds[BuildCnt++].set(a,c,b);
        if(c>=Rm) Rm=c;
    }
     
    sort(Builds,Builds+BuildCnt,sortfunc);
    int ptr=0;
    for(int lx=1;lx<=CM;lx++)
    {
        while((lx>=Builds[ptr].L)&&(ptr<BuildCnt))
        {
            //Builds[ptr].Print();
            Heap.push(Builds[ptr]);
            ptr++;
        }
        while((Heap.size())&&(lx>=Heap.top().R))
            Heap.pop();
        if(Heap.size())
            Height[lx]=Heap.top().H;
        else
            Height[lx]=0;
        //printf("%d:%d\n",lx,Height[lx]);
    }
    int prev = 0;
    for (int lx=1; lx<Rm; lx++) {
        if (prev==Height[lx]) continue;
        printf("%d %d ",lx,Height[lx]);
        prev = Height[lx];
    }
    printf("%d %d\n",Rm, 0);
    return 0;
}

Codeforce 366C. Dima and Salad

[DP]
第一次用Custom test AC題目 XDD
這應該是NP問題："子集合和=0"

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define BASE 100000
int jz[BASE+20000];
int tmp[BASE+20000];
void set(int a,int v)
{
    //printf("set(%d %d),jz[%d]=%d\n",a,v,a,jz[a]);
    if(v>jz[a+BASE])
        jz[a+BASE]=v;
}
int get(int a)
{
    return jz[a+BASE];
}
void setmp(int a,int v)
{
    //printf("set(%d %d),jz[%d]=%d\n",a,v,a,jz[a]);
    if(v>tmp[a+BASE])
        tmp[a+BASE]=v;
}
int getmp(int a)
{
    return tmp[a+BASE];
}
void resetmp()
{
    for(int lx=0;lx<BASE+20000;lx++)
        tmp[lx]=-1;
}
void write()
{
    for(int lx=0;lx<BASE+20000;lx++)
        jz[lx]=tmp[lx];
}
int main()
{
    int n,k;
    resetmp();
    for(int lx=0;lx<BASE+20000;lx++)
        jz[lx]=-1;
    scanf("%d %d",&n,&k);
    set(0,0);
    int a[110],b[110];
    for(int lx=0;lx<n;lx++)
        scanf("%d",a+lx);
    for(int lx=0;lx<n;lx++)
    {
        scanf("%d",b+lx);
        b[lx]*=k;
    }
    for(int lx=0;lx<n;lx++)
    {
        for(int ly=-BASE;ly<=10010;ly++)
        {
           int v=get(ly);
           setmp(ly,v);
           if(v>=0)
           {
               setmp(ly+a[lx]-b[lx],v+a[lx]);
               //printf("visit(%d)\n",ly);
           }   
        }
        write();
        resetmp();
    }
    if(get(0)==0)
        printf("-1\n");
    else
        printf("%d\n",get(0));
    return 0;
}

POJ 3723 Conscription

[PRIM]

存圖好麻煩= =

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define min(x,y) (((x)>(y)) ? (y):(x))
#define max(x,y) (((x)>(y)) ? (x):(y))
#define R 50000
#define N 20020
#define INF -1
using namespace std;
class Edge
{
public:
    int a,b,w;
    Edge():a(0),b(0),w(0){}
    void Print()const

    {
        printf("%d------%d   %d\n",a,b,w);
    }
};

int Girl,Boy,egcnt=0;
Edge Edges[2*R+2*N];
int Startptr[N];
int Endptr[N];
bool IsVis[N];
priority_queue<Edge, deque<Edge>, greater<Edge> > BFS;
void Connect(int Gind,int Bind,int w)
{
    Edges[egcnt].a=Bind;
    Edges[egcnt].b=Gind;
    Edges[egcnt].w=10000-w;
    egcnt++;
    Edges[egcnt].a=Gind;
    Edges[egcnt].b=Bind;
    Edges[egcnt].w=10000-w;
    egcnt++;
}
void Reprc()
{
    sort(Edges,Edges+egcnt);
    for(int lx=0;lx<=Boy+Girl;lx++)
        Startptr[lx]=-1,Endptr[lx]=-1;
    for(int lx=0;lx<egcnt;lx++)
    {
        if(Startptr[Edges[lx].a]==-1)
            Startptr[Edges[lx].a]=lx;
        Endptr[Edges[lx].a]=lx;
    }
}
void Add(int I)
{
    IsVis[I]=true;
    if(Startptr[I]==-1) return;
    for(int lx=Startptr[I];lx<=Endptr[I];lx++)
        if(IsVis[Edges[lx].b]==false)
            BFS.push(Edges[lx]);
    return;
}
void Clear()
{
    memset(IsVis,false,sizeof(IsVis));
    egcnt=0;
    while(BFS.size())
        BFS.pop();
}
bool operator<(Edge a1,Edge a2)
{
    if(a1.a<a2.a)
        return true;
    else if(a1.a==a2.a)
        return (a1.b<a2.b);
    return false;
}
bool operator>(Edge a1,Edge a2)
{
    return (a1.w>a2.w);
}

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        Clear();
        int _ES;
        scanf("%d %d %d",&Girl,&Boy,&_ES);
        for(int lx=1;lx<=Girl+Boy;lx++)
            Connect(0,lx,0);
        while(_ES--)
        {
            int x,y,w;scanf("%d %d %d",&x,&y,&w);
            Connect(x+1,y+Girl+1,w);
        }
        Reprc();
        Add(0);
        long long int Cost=0;
        while(BFS.size())
        {
            Edge pp=BFS.top();
            BFS.pop();
            if(IsVis[pp.b]) continue;
            Cost+=(long long int)pp.w;
            Add(pp.b);
        }
        printf("%I64d\n",Cost);
    }
    return 0;
}

TIOJ 1290 F.不定向邊

[Dijkstra]
第一次CODE Dijkstra
有點冗長 尚有進步空間

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define min(x,y) (((x)>(y)) ? (y):(x))
#define max(x,y) (((x)>(y)) ? (x):(y))
using namespace std;
#define LL long long int
LL _INF=100000*100000;
class Edge
{
public:
    int a,b;
    LL w;
    Edge(){}
    void Print()const
    {
        printf("[%d--%d %I64d]\n",a,b,w);
    }
};
bool operator<(Edge e1,Edge e2)
{
    if(e1.a<e2.a)
        return true;
    else if(e1.a==e2.a)
        return (e1.b<e1.b);
    return false;
}
bool operator>(Edge e1,Edge e2)
{
    return e1.w>e2.w;
}
Edge newEdge(int a,int b,LL w)
{
    Edge RE;RE.a=a;RE.b=b;RE.w=w;
    return RE;
}
priority_queue<Edge,deque<Edge>,greater<Edge> >Heap;
vector<Edge>edges;
int BgTab[1010];
int EdTab[1010];
LL Table[1010];
void BuildTable()
{
    sort(edges.begin(),edges.end());
    for(int lx=0;lx<edges.size();lx++)
    {
        if(BgTab[edges[lx].a]==-1)
            BgTab[edges[lx].a]=lx;
        EdTab[edges[lx].a]=lx;
        //edges[lx].Print();
    }
}
void insert(int a)
{
    if(BgTab[a]<0) return;
    for(int lx=BgTab[a];lx<=EdTab[a];lx++)
    {
        if(Table[edges[lx].b]<_INF)
            continue;
        Edge nn=edges[lx];
        nn.w+=Table[a];
        Heap.push(nn);
    }
}
int main()
{
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        edges.clear();
        while(Heap.size()) Heap.pop();

        for(int lx=1;lx<=n;lx++)
        {
            Table[lx]=_INF;
            BgTab[lx]=-1;
        }
        int Start,End;scanf("%d %d",&Start,&End);
        for(int lx=0;lx<m;lx++)
        {
            int a,b;
            LL w;
            scanf("%d %d %I64d",&a,&b,&w);
            if(a==b) continue;
            edges.push_back(newEdge(a,b,w));
            edges.push_back(newEdge(b,a,w));
        }
        BuildTable();
        Table[Start]=0;
        insert(Start);
        //printf("Prc:\n");

        while(Heap.size()>0)
        {
            if(Table[End]<_INF) break;
            Edge out=Heap.top();
            Heap.pop();
            //printf("Do on:\n");
            //out.Print();
            if(Table[out.b]<_INF) continue;
            Table[out.b]=out.w;
            insert(out.b);
        }
        if(Table[End]==_INF)
            printf("He is very hot\n");
        else
            printf("%I64d\n",Table[End]);

    }
    return 0;
}

TIOJ 1045 A.細菌培養

[離散暴力]

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#define LL long long int
using namespace std;
struct step
{
    LL ax,ay;
    LL bx,by;
    int x1,x2;
    int y1,y2;
}Steps[400];
int n;
void Print(LL *I,int cnt,const char *CC)
{
    printf("%s:",CC);
    for(int lx=0;lx<cnt;lx++)
        printf("%I64d ",I[lx]);
    printf("\n");
}
int Cut(LL *I,int cnt)
{
    sort(I,I+cnt);
    int re=1;
    for(int lx=1;lx<cnt;lx++)
        if(I[lx]!=I[lx-1])
            I[re++]=I[lx];
    return re;
}
LL field[440][440];
LL xax[1000],yax[1000];
int xpc,ypc;
void PrintField()
{
    for(int lx=0;lx<xpc-1;lx++)
    {
        for(int ly=0;ly<ypc-1;ly++)
            printf("%I64d ",field[lx][ly]);
        printf("\n");
    }
    printf("===============================\n");
}
int main()
{
    while(scanf("%d",&n)&&n)
    {
        int xcnt=0,ycnt=0;
        xax[xcnt++]=0;xax[xcnt++]=10000;
        yax[ycnt++]=0;yax[ycnt++]=10000;
        for(int lx=0;lx<n;lx++)
        {
            scanf("%I64d %I64d %I64d %I64d",&Steps[lx].ax,&Steps[lx].ay,&Steps[lx].bx,&Steps[lx].by);
            xax[xcnt++]=Steps[lx].ax;xax[xcnt++]=Steps[lx].bx;
            yax[ycnt++]=Steps[lx].ay;yax[ycnt++]=Steps[lx].by;
        }
        xpc=Cut(xax,xcnt);
        ypc=Cut(yax,ycnt);
        //Print(xax,xpc,"XAX:");
        //Print(yax,ypc,"YAX:");
        for(int lx=0;lx<n;lx++)
        {
            for(int ly=0;ly<xpc;ly++)
            {
                if(xax[ly]==Steps[lx].ax)
                    Steps[lx].x1=ly;
                else if(xax[ly]==Steps[lx].bx)
                    Steps[lx].x2=ly-1;
            }
            for(int ly=0;ly<ypc;ly++)
            {
                if(yax[ly]==Steps[lx].ay)
                    Steps[lx].y1=ly;
                else if(yax[ly]==Steps[lx].by)
                    Steps[lx].y2=ly-1;
            }
        }
        for(int lx=0;lx<xpc-1;lx++)
            for(int ly=0;ly<ypc-1;ly++)
                field[lx][ly]=(xax[lx+1]-xax[lx])*(yax[ly+1]-yax[ly]);
        //PrintField();
        //for(int lx=0;lx<n;lx++)
        //  printf("[%d %d %d %d]\n",Steps[lx].x1,Steps[lx].x2,Steps[lx].y1,Steps[lx].y2);
        for(int lp=0;lp<n;lp++)
        {
            for(int lx=Steps[lp].x1;lx<=Steps[lp].x2;lx++)
                for(int ly=Steps[lp].y1;ly<=Steps[lp].y2;ly++)
                    field[lx][ly]*=2;
            //PrintField();
        }

        LL ANS=0;
        for(int lx=0;lx<xpc-1;lx++)
            for(int ly=0;ly<ypc-1;ly++)
                ANS+=field[lx][ly];
        printf("%I64d\n",ANS);
    }

    return 0;
}

Codeforce 369D. Valera and Fools

[BFS、dijkstra]
反正狀態只長醬子
[有].....[有.....有]
N^2狀態

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#define min(x,y) (((x)>(y)) ? (y):(x))
#define max(x,y) (((x)>(y)) ? (x):(y))
using namespace std;
#define NN 3010
#define INF 4000
int prob[NN];
int Status[NN][NN];
struct ST{int x,y;};
ST newST(int a,int b)
{
    ST re;re.x=a,re.y=b;
    return re;
}
deque<ST> BFS;
bool vempty=false;
int cnt=1;
void visit(int a,int b,int k)
{
    //printf("visit(%d,%d)\n",a,b);
    //if(b<=-1) return;
    if(Status[a][b]>k)
    {
        //printf("PP");
        if(Status[a][b]==INF)
            cnt++;
        Status[a][b]=k;
        BFS.push_back(newST(a,b));
    }
}
int main()
{
    BFS.clear();
    int n,k;
    int Dead_ptr,Undead_ptr;
    scanf("%d %d",&n,&k);
    for(int lx=0;lx<=n;lx++)
        for(int ly=0;ly<=n;ly++)
            Status[lx][ly]=INF;
    Dead_ptr=0;
    Undead_ptr=n+1;
    for(int lx=1;lx<=n;lx++)
    {
        scanf("%d",prob+lx);
        if(prob[lx]==100)
            Dead_ptr=lx;
    }
    for(int lx=n;(prob[lx]==0)&&lx;lx--)
        Undead_ptr=lx;
    BFS.push_back(newST(n,n-1));
    Status[n][n-1]=0;
    while(BFS.size())
    {
        ST out=BFS.front();
        BFS.pop_front();
         int ptr1=n-out.x+1;
        if(Status[out.x][out.y]>=k) break;
        if((n-out.y+1)>=Undead_ptr)
        {
            if(prob[ptr1]>0)
                visit(out.x,out.y-1,Status[out.x][out.y]+1);
            continue;
        }
        if(out.y==0) continue;

        if(prob[ptr1]>0)    //兩隻同時死掉
        {
            if(out.y==1)
                vempty=true;
            else
                visit(out.y-1,out.y-2,Status[out.x][out.y]+1);
        }
        if(prob[ptr1]<100)
            visit(out.y,out.y-1,Status[out.x][out.y]+1);
        if(n-out.x+1<Dead_ptr) continue;
        if(prob[ptr1]>0)
            visit(out.x,out.y-1,Status[out.x][out.y]+1);
    }
    printf("%d\n",cnt+vempty);
    return 0;
}