poj 3630 trie

2010年9月22日 17:53

刚接触trie树,试着做做,写的好挫。。。

Trie(from维基百科)

Trie 又称单词查找树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。

性质 它有3个基本性质:

  1. 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
  2. 根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
  3. 每个节点的所有子节点包含的字符都不相同。
#include <cstdio>
#include <cstring>

#define NODEMAX 100005
struct node
{
    int next[10];
    int key;
} trie[NODEMAX];
int nodeindex=1;

bool search(char word[])
{
    int i=0,t,in=0;//root
    while(word[i]!='\0')
    {
        t=word[i]-'0';
        if(trie[in].next[t]==0)
        {
            memset(trie[nodeindex].next,0,sizeof(trie[nodeindex].next));
            trie[nodeindex].key=0;
            trie[in].next[t]=nodeindex++;
        }
        in=trie[in].next[t];
        if(word[i+1]=='\0'&&trie[in].key>0)
            return true;
        if(word[i+1]!='\0'&&trie[in].key==2)
            return true;
        trie[in].key=1;
        i++;
    }
    trie[in].key=2;
    return false;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int cas;scanf("%d",&cas);
    int n,i;
    char num[11];
    bool failed;
    while(cas--)
    {
        scanf("%d",&n);
        memset(trie[0].next,0,sizeof(trie[0].next));
        trie[0].key=0;
        failed=0;nodeindex=1;
        for(i=0;i<n;i++)
        {
            scanf("%s",num);
            if(!failed&&search(num)) failed=1;
        }
        if(!failed) puts("YES");
        else puts("NO");
    }
}

评论(0) 阅读(1789)

hdu 1573

2010年9月19日 05:18

http://acm.hdu.edu.cn/showproblem.php?pid=1573

不互质的中国剩余定理,一开始还只以为是中国剩余定理了,长时间没做过了

翻笔记,没找到,搜一搜,点开发现是两个月前的自己的blog,汗一个

数据有trick,多谢wr大牛

#include <cstdio>
typedef long long lld;
#define maxn 12
int r[maxn];
int m[maxn];

lld gcd(lld a,lld b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}
lld x, y, t;
lld egcd(lld a, lld b)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    else
    {
        lld e = egcd(b, a % b);
        t = x; x = y; y = t - a / b * y;
        return e;
    }
}

lld exChnRnd(int len)
{
    int i;
    lld d,c,t,mm=m[0],rr=r[0];
    for(i=1;i<len;i++)
    {
        d=egcd(mm,m[i]);
        c=r[i]-rr;
        if(c%d)
            return -1;
        t=m[i]/d;
        x=(c/d*x%t+t)%t;
        rr=mm*x+rr;
        mm=mm*m[i]/d;
    }
        return rr;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int n,i,M;
    lld t,sum;
    int cas;scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d%d",&M,&n);
        sum=1;
        for(i=0;i<n;i++)
        {
            scanf("%d",m+i);
            sum=sum/gcd(sum,m[i])*m[i];
        }
        for(i=0;i<n;i++)
        {
            scanf("%d",r+i);
            r[i]%=m[i];
        }
        t=exChnRnd(n);
        //printf("t:%lld\n",t);
        //printf("sum:%lld\n",sum);
        if(t==-1)
        {
            printf("0\n");
            continue;
        }
        i=0;
        if(t<=M) i=1+(M-t)/sum;
        if(t==0&&i)//这里...
            --i;
        printf("%d\n",i);
    }
}

评论(0) 阅读(2305)

poj 1228 凸包

2010年9月17日 04:40

题意给出一个凸包,问是否唯一。若某边上仅有由两个点,则易见可以加一个点扩充,形成另一个凸包。对数据无语。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int sig(double d) { return fabs(d) < 1E-6 ? 0 : d < 0 ? -1 : 1; }
struct Point{double x,y;
	bool operator < (const Point &p) const {
		return sig(x-p.x) != 0 ? x < p.x : sig(y-p.y) < 0;
	}
};
double dis(Point a, Point b) {
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double cross(Point o, Point a, Point b) {
	return (a.x - o.x)*(b.y - o.y)-(b.x - o.x)*(a.y - o.y);
}
int graham(Point*p, int n, int*ch) {
#define push(x)     ch[len ++]=x
#define pop()		len --
sort(p, p+n);
	int len = 0, len0 = 1, i;
	for(i = 0; i < n; i ++) {
		while(len > len0 && sig(cross(p[ch[len-1]], p[ch[len-2]], p[i]))<=0)
			pop();
		push(i);
	}
	len0 = len;
	for(i = n-2; i >= 0; i --) {
		while(len > len0 && sig(cross(p[ch[len-1]], p[ch[len-2]], p[i]))<=0)
			pop();
		push(i);
	}
	return len-1;
}


#define maxn 1001
Point p[maxn]; 
int ch[maxn];
bool flag[maxn];
int flag2[maxn];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int cas,i,j,n,m;
    scanf("%d",&cas);
    bool ok;
    while(cas--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%lf%lf",&p[i].x,&p[i].y);
        m=graham(p,n,ch);
        if(n<=5) {puts("NO");continue;}//加了这句才过……
        memset(flag,0,sizeof(flag));
        memset(flag2,0,sizeof(flag2));
        for(i=0;i<m;i++)
            flag[ch[i]]=1;
        for(i=0;i<n;i++) if(!flag[i])
        {
            for(j=1;j<m;j++)
                if(sig(cross(p[i],p[ch[j-1]],p[ch[j]]))==0)
                {flag2[j-1]|=2;flag2[j]|=1;}
            if(sig(cross(p[i],p[ch[m-1]],p[ch[0]]))==0)
            {flag2[m-1]|=2;flag2[0]|=1;}
        }
        ok=1;
        for(i=0;i<m;i++)
            if(flag2[i]<3) {ok=0;break;}
        if(ok)
            puts("YES");
        else
            puts("NO");
    }
}

评论(0) 阅读(1944)

poj 2425 博弈 SG函数

2010年9月10日 03:26

#include <cstdio>
#include <cstring>
#include <vector>
std::vector<int> adj[1000];
int f[1000];
int n;

int mex(int v)
{
    bool g[1000]={0};
    int i,w;
    for(i=0;i<adj[v].size();i++)
    {
        w=adj[v][i];
        if(f[w]==-1)
            f[w]=mex(w);
        g[f[w]]=1;
    }
    for(i=0;;i++)
        if(!g[i]) return i;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int m,v,w,sum;
    while(scanf("%d",&n)!=EOF)
    {
        for(v=0;v<n;v++)
        {
            adj[v].clear();
            scanf("%d",&m);
            while(m--)
            {
                scanf("%d",&w);
                adj[v].push_back(w);
            }
        }
        memset(f,-1,sizeof(f));
        while(scanf("%d",&m)!=EOF&&m)
        {
            sum=0;
            while(m--)
            {
                scanf("%d",&v);
                if(f[v]==-1)
                    f[v]=mex(v);
                sum^=f[v];
            }
            if(sum)
                puts("WIN");
            else
                puts("LOSE");
        }
    }
    return 0;
}

评论(0) 阅读(1980)

poj 1201 第一道差分约束

2010年9月08日 03:22

差分约束系统介绍 http://imlazy.ycool.com/post.1702305.html

设S[i]为数组Z在[0,i)上包含的数的个数,则对每一组a b c有,S[b+1]-S[a]>=c 即 S[a]-S[b+1]<=-c,建图时对应从S[b+1]到S[a]的一条权为-c的边.同时有隐含条件0<=S[i+1]-S[i]<=1即S[i+1]-S[i]<=1和S[i]-S[i+1]<=0,对应建图.

因为本题求的是可行解组中最小的,所以用最长路径求法.

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
#define maxn 50001
#define inf 0x3f3f3f3f
int n,m,tot;
struct Edge{int w,wt,next;}e[4*maxn];
int start[maxn];
int d[maxn];//单源距离

void add(int v,int w,int wt)
{
    e[tot].w=w;e[tot].wt=wt;
    e[tot].next=start[v];start[v]=tot++;
}

void spfa(int s)
{
    int i,v,N=0;
    deque<int> dq;
    for(v=0;v<n;v++) d[v]=inf;
    d[s]=0;
    dq.push_back(s);dq.push_back(n);
    while(!dq.empty())
    {
        v=dq.front();dq.pop_front();
        if(v==n)
        {if(N++>n) return;dq.push_back(n);}
        else
            for(i=start[v];i!=-1;i=e[i].next)
            {
                if(d[e[i].w]>d[v]+e[i].wt)
                {
                    d[e[i].w]=d[v]+e[i].wt;
                    dq.push_back(e[i].w);
                }
            }
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int m,i,a,b,c,maxnum=0;
    scanf("%d",&m);
    tot=0;for(i=0;i<maxn;i++) start[i]=-1;
    for(i=0;i<m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        add(b+1,a,-c);
        if(b+1>maxnum) maxnum=b+1;
    }
    for(i=0;i<maxnum;i++)
    {
        add(i,i+1,1);
        add(i+1,i,0);
    }
    n=maxnum+1;
    spfa(maxnum);
    printf("%d",d[maxnum]-d[0]);
    return 0;
}

评论(0) 阅读(2032)