zercal

PKU推荐题目

posted @ 2007-10-30 15:56 zercal 阅读(571) | 评论 (0) | 编辑收藏

南京挂了

无奈啊,本来实力就不行,经验又不够,运气又差.又蒙了,想不挂都难...

第一道题是我们最善长的题目,结果题目意思理解错误,直接卡了3个小时,把我们都卡蒙了...
第2题3题都是我们最弱的高级数据结构(另一个同样弱的就是几何了),如果第一题早出,那么第2题字典树还是能出的,但是后缀数组就只好放弃了...
总的来说,拿不了银是实力问题,没拿铜就是比赛经验和人品的问题了...

posted @ 2007-10-30 15:52 zercal 阅读(203) | 评论 (0) | 编辑收藏

PKU1639最小度限制生成树

摘要: 终于AC了，大概在8月份就会做这道题了，一直没有去写（bs下自己）。拖了好久昨天下定决心说一定要把这道题AC了（pku1639），于是就开始写，结果一下从18：00wa到21：30.。。。都怨操作系统老师，我都在睡觉了她讲课还把我搞的头疼了一天… 今天起来决定重写,之前写的那个实在是太烂了. 精神好了干什么都顺利,在经过几个莫名其妙的小错误后,终于A了̷... 阅读全文

posted @ 2007-10-09 16:10 zercal 阅读(1060) | 评论 (0) | 编辑收藏

调整状态...努力...

最近状态一直很不好...乱七八糟的事情烦得要死,文艺部开学也正忙,心情也不好,搞得这半个多月都很没有动力.还有一个月就要出去比赛了,这种状态真是....
还都是要努力才行啊...

十一完了会熄灯...慢慢的把状态转过来,不去管恶心的事情(我恨死校团委了),而且文艺部的事情现在也都可以比较放心(其实还是很不放心的...),慢慢的把精力放在ACM上吧,水平那么烂,再不努力.......

恩,十月份的目标:
1,把标程都整理出来,主要是图论的,需要标程的整理出一个精简的比赛用的标程,不需要的那些经典问题也都要写一遍,压得那几道题目也都尽量过了.数论的就要好好努力把书多看看...偏偏计科还不学信安数基...搞了这么久感觉人信安的随便抓个人数论都比我强...郁闷
2,多看写论文...看一些是一些吧...
3,保证比赛量的同时自己也要做些练习题...秒杀娱乐题就不做了,毕竟在Arbiter里我不用当代码手.不过中档的题目(对于我来说就是难题了T T)要多做,争取一道题目有一道题目的收获吧,保持状态也是很重要的.
4,具体数学...看一点是一点吧...有些事情是真的勉强不来的...IQ不够那也没办法不是...
5,规范作息...一开始熄灯我估计又要开始失眠了...
6,保持好心情...这个最难...工作时要表现的有自信,不能影响别人happy...比赛时不管怎样都要冷静...其实我是实在什么都不想做...啊啊啊啊啊啊啊....真是太没心情了......

posted @ 2007-10-06 20:26 zercal 阅读(214) | 评论 (0) | 编辑收藏

单元最短路（dijkstra+堆）不是很精简

  1 #include<iostream>
  2 using namespace std;
  3 #define maxn 100000
  4 #define maxint 100000000
  5
  6 struct adj{
  7     int ed;
  8     int ll;
  9     adj *pe;
10 };
11
12 int vn,maxd;//点数需要将vn赋初值
13 int dui[maxn],d[maxn],father[maxn],hx[maxn];//点，堆从1开始
14 struct adj *node[maxn];//邻接表，要memset
15
16 int take(int x)
17 {
18     int k;
19     while(d[dui[x]]<d[dui[x/2]]&&x>1)
20     {
21         swap(hx[dui[x]],hx[dui[x/2]]);
22         swap(dui[x],dui[x/2]);
23         x=x/2;
24     }
25     while((x*2)<=maxd)
26     {
27         k=x*2;
28         if(k<maxd&&d[dui[k]]>d[dui[k+1]])
29             k++;
30         if(d[dui[x]]>d[dui[k]])
31         {
32             swap(hx[dui[x]],hx[dui[k]]);
33             swap(dui[x],dui[k]);
34             x=k;
35         }
36         else    break;
37     }
38     return 0;
39 }
40
41 int out()
42 {
43     int x,i;
44     if(maxd<1) return -1;
45     x=dui[1];
46     dui[1]=dui[maxd--];
47     take(1);
48     return x;
49 }
50
51
52 int djs(int st,int ee)
53 {
54     int i,j,k,x;
55     adj *p;
56     maxd=vn;
57     for(i=1;i<=vn;i++)
58     {
59         dui[i]=i;
60         d[i]=maxint;
61         hx[i]=i;
62     }
63     d[st]=0;
64     father[st]=st;
65     take(hx[st]);
66     x=out();
67     while(x!=-1)
68     {
69         if(x==ee) break;
70         p=node[x];
71         while(p!=NULL)
72         {
73             if(d[p->ed]>d[x]+p->ll)
74             {
75                 d[p->ed]=d[x]+p->ll;
76                 father[p->ed]=x;
77                 take(hx[p->ed]);
78             }
79             p=p->pe;
80         }
81         x=out();
82     }
83     return d[ee];
84 }
85
86 int insert(int a,int b,int c)
87 {
88     adj *p;
89     p=node[a];
90     node[a]=(adj*)malloc(sizeof(adj));
91     node[a]->ed=b;
92     node[a]->ll=c;
93     node[a]->pe=p;
94     return 0;
95 }
96
97
98
99
100
101
102

刚开始学图论的时候写的...没有精简长度也没有刻意省时间...

posted @ 2007-10-06 20:04 zercal 阅读(387) | 评论 (0) | 编辑收藏

匈牙利算法求二分图最大匹配

#include <stdio.h>

#include <cstring>

//匈牙利算法

int xv=5,yv=5,n=5; // 顶点数（数字5认你定）

int g[5][5]; // g[i][j]=1 表示 xi与yj相邻

int sy[5]; // 辅助：当轮被搜过的y点都是1

int cnt,xm[5],ym[5]; // 输出

void init()

{

cnt=0 ;

memset(g, 0 ,sizeof(g));

memset(xm,-1,sizeof(xm));

memset(ym,-1,sizeof(ym));

}

int path(int u) // 返回是否找到增广路（递归，时间复杂度O（n*n））

{

int v;

for(v=0;v<yv;v++)

{

if((g[u][v]==1)&&(sy[v]==0))

{

sy[v]=1;

if((ym[v]==-1)||(path(ym[v])==1))

{

xm[u]=v;ym[v]=u;

return 1;

}

return 0;

}

void main()

{

int i,j;

//初始化

init();

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{

scanf("%d",&g[i][j]);

}

//核心

for(i=0;i<xv;i++)

{

if(xm[i]==-1)

{

memset(sy,0,sizeof(sy));

cnt+=path(i);

}

//打印

printf("sum=%d",cnt);

}

posted @ 2007-10-06 19:57 zercal 阅读(374) | 评论 (0) | 编辑收藏

拓扑排序求逆序对

#include<iostream>

using namespace std;

int a[110000],b[110000],res;//res需要赋初值0

int merge(int st,int mid,int ed)

{

int sa,ea,sb,eb,i,j;

sa=st,ea=mid,sb=mid+1,eb=ed;i=j=0;

while(sa<=ea&&sb<=eb)

{

if(a[sa]<=b[sb])

b[i++]=a[sa++];

else{

b[i++]=a[sb++];

res+=mid+1-sa;

}

while(sa<=ea)

b[i++]=a[sa++];

while(sb<=eb)

b[i++]=b[sb++];

for(j=0;j<i;j++)

a[st+j]=b[j];

return 0;

}

int mst(int st,int ed)

{

int mid,i,j,k;

if(st<ed)

{

mid=(st+ed)/2;

mst(st,mid);

mst(mid+1,ed);

merge(st,mid,ed);

}

return 0;

}

posted @ 2007-10-06 19:48 zercal 阅读(351) | 评论 (0) | 编辑收藏

中国剩余定理（菜鸟版，勉强能用）

#include<iostream>

using namespace std;

#define maxn 10000 //数的数量

int num[maxn],lef[maxn]; //除数和余数

long long mm[maxn],use[maxn];

//扩展欧几里德求逆元

int extended_euclid(int a,int b,int &x,int &y)

{

if(b==0)

{

x=1;y=0;

return a;

}

int t,d;

d=extended_euclid(b,a%b,x,y);

t=x;

x=y;

y=t-(a/b)*y;

return d;

}

//返回第一个正的解 n为数的数量

long long chinaleft(int n)

{

int i,j,k,x,y;

long long pm,res;

for(i=0,pm=1;i<n;i++)

pm*=num[i];

for(i=0;i<n;i++)

{

mm[i]=pm/num[i];

extended_euclid(mm[i],num[i],x,y);

use[i]=mm[i]*x;

}

for(i=0,res=0;i<n;i++)

res=(res+lef[i]*use[i])%pm;

if(res<0) res+=pm;

return res;

}

这一阵子在狂啃数论,真是不喜欢这种纯数学的东西...马上都要比赛了才刚刚会中国剩余定理...真是丢脸...

posted @ 2007-10-06 19:43 zercal 阅读(229) | 评论 (0) | 编辑收藏

扩展欧几里德

int extended_euclid(int a,int b,int &x,int &y)
{
       if(b==0)
   {
           x=1;y=0;
           return a;
       }
       int t,d;
       d=extended_euclid(b,a%b,x,y);
       t=x;
           x=y;
           y=t-(a/b)*y;
    return d;
}

输出x*a+y*b=gcd(a,b)的一个特解

posted @ 2007-10-06 19:40 zercal 阅读(281) | 评论 (0) | 编辑收藏

又开博了

这次的博客主要是贴些自己的代码(不过本人水平有限~大牛们就不要bs哈)还有其他的资料什么的，私人的事情就不写了（再说我现在也没啥爆点了）.

posted @ 2007-10-06 19:13 zercal 阅读(175) | 评论 (0) | 编辑收藏

常用链接

留言簿(1)

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜