scturtle's 渣代码集散地

编译原理实验一 PL/0语言词法分析

2010年10月02日 23:21

代码冗长但不恶心，自我感觉良好~

有问题再改，电脑准备拿去修，贴上来备份

hdu 3532 极角排序

2010年9月26日 02:57

今天的D题，才知道极角排序。。。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define pi 3.141592653

double jijiao(double x,double y)
{
    return atan2(x,y)*180/pi;
}

double p[1001][2];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
#endif
    vector<double> jj;
    int n,i,j,k;
    double maxj,minj,nowj;
    while(scanf("%d",&n)&&n>0)
    {
        for(i=0;i<n;i++)
            scanf("%lf%lf",&p[i][0],&p[i][1]);

        maxj=0;
        for(i=0;i<n;i++)
        {
            minj=180;jj.clear();
            for(j=0;j<n;j++) if(i!=j)
                jj.push_back(jijiao(p[j][0]-p[i][0],p[j][1]-p[i][1]));
            sort(jj.begin(),jj.end());
            for(j=0;j<jj.size()-1;j++)
            {
                nowj=jj[j+1]-jj[j];
                if(nowj+1e-8>180) nowj=360-nowj;
                minj=min(minj,nowj);
                //printf("%f\n",nowj);
            }
            nowj=jj[0]-jj[jj.size()-1]+360;
            if(nowj+1e-8>180) nowj=360-nowj;
            minj=min(minj,nowj);
            //printf("%f\n",nowj);
            maxj=max(maxj,minj);
        }
        printf("%.4f\n",maxj);
    }
}

评论(0) 阅读(2148)

poj 3630 trie

2010年9月22日 17:53

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

Trie（from维基百科）

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

性质它有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) 阅读(2179)

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) 阅读(2735)

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) 阅读(2314)

« 上一页 1 2 … 11 12 13 14 15 16 17 18 19 … 27 28 下一页 »