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