zercal

C++博客 首页 新随笔 联系 聚合 管理
  10 Posts :: 0 Stories :: 0 Comments :: 0 Trackbacks

2007年10月30日 #

POJ上一些题目在
http://162.105.81.202/course/problemSolving/
可以找到解题报告。
《算法艺术与信息学竞赛》的习题提示在网上可搜到

一.动态规划
参考资料:
刘汝佳《算法艺术与信息学竞赛》
《算法导论》

推荐题目:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1141
简单

http://acm.pku.edu.cn/JudgeOnline/problem?id=2288
中等,经典TSP问题

http://acm.pku.edu.cn/JudgeOnline/problem?id=2411
中等,状态压缩DP

http://acm.pku.edu.cn/JudgeOnline/problem?id=1112
中等

http://acm.pku.edu.cn/JudgeOnline/problem?id=1848
中等,树形DP。
可参考《算法艺术与信息学竞赛》动态规划一节的树状模型

http://acm.zju.edu.cn/show_problem.php?pid=1234
中等,《算法艺术与信息学竞赛》中的习题

http://acm.pku.edu.cn/JudgeOnline/problem?id=1947
中等,《算法艺术与信息学竞赛》中的习题

http://acm.pku.edu.cn/JudgeOnline/problem?id=1946
中等,《算法艺术与信息学竞赛》中的习题

http://acm.pku.edu.cn/JudgeOnline/problem?id=1737
中等,递推

http://acm.pku.edu.cn/JudgeOnline/problem?id=1821
中等,需要减少冗余计算

http://acm.zju.edu.cn/show_problem.php?pid=2561
中等,四边形不等式的简单应用

http://acm.pku.edu.cn/JudgeOnline/problem?id=1038
较难,状态压缩DP,《算法艺术与信息学竞赛》中有解答

http://acm.pku.edu.cn/JudgeOnline/problem?id=1390
较难,《算法艺术与信息学竞赛》中有解答

http://acm.pku.edu.cn/JudgeOnline/problem?id=3017
较难,需要配合数据结构优化(我的题目^_^)

http://acm.pku.edu.cn/JudgeOnline/problem?id=1682
较难,写起来比较麻烦

http://acm.pku.edu.cn/JudgeOnline/problem?id=2047
较难

http://acm.pku.edu.cn/JudgeOnline/problem?id=2152
难,树形DP

http://acm.pku.edu.cn/JudgeOnline/problem?id=3028
难,状态压缩DP,题目很有意思

http://acm.pku.edu.cn/JudgeOnline/problem?id=3124


http://acm.pku.edu.cn/JudgeOnline/problem?id=2915
非常难


二.搜索
参考资料:
刘汝佳《算法艺术与信息学竞赛》
推荐题目:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1011
简单,深搜入门题

http://acm.pku.edu.cn/JudgeOnline/problem?id=1324
中等,广搜

http://acm.pku.edu.cn/JudgeOnline/problem?id=2044
中等,广搜

http://acm.pku.edu.cn/JudgeOnline/problem?id=2286
较难,广搜

http://acm.pku.edu.cn/JudgeOnline/problem?id=1945
难,IDA*,迭代加深搜索,需要较好的启发函数

http://acm.pku.edu.cn/JudgeOnline/problem?id=2449
难,可重复K最短路,A*。
可参考解题报告:
http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1144

http://acm.pku.edu.cn/JudgeOnline/problem?id=1190
难,深搜剪枝,《算法艺术与信息学竞赛》中有解答

http://acm.pku.edu.cn/JudgeOnline/problem?id=1084
难,《算法艺术与信息学竞赛》习题

http://acm.pku.edu.cn/JudgeOnline/problem?id=2989
难,深搜

http://acm.pku.edu.cn/JudgeOnline/problem?id=1167
较难,《算法艺术与信息学竞赛》中有解答

http://acm.pku.edu.cn/JudgeOnline/problem?id=1069
很难


三. 常用数据结构
参考资料:
刘汝佳《算法艺术与信息学竞赛》
《算法导论》
线段树资料:
http://home.ustc.edu.cn/~zhuhcheng/ACM/segment_tree.pdf
树状数组资料
http://home.ustc.edu.cn/~zhuhcheng/ACM/tree.ppt
关于线段树和树状数组更多相关内容可在网上搜到
后缀数组资料
http://home.ustc.edu.cn/~zhuhcheng/ACM/suffix_array.pdf
http://home.ustc.edu.cn/~zhuhcheng/ACM/linear_suffix.pdf

推荐题目
http://acm.pku.edu.cn/JudgeOnline/problem?id=2482
较难,线段树应用,《算法艺术与信息学竞赛》中有解答

http://acm.pku.edu.cn/JudgeOnline/problem?id=1151
简单,线段树应用矩形面积并,《算法艺术与信息学竞赛》中有解答

http://acm.pku.edu.cn/JudgeOnline/problem?id=3225
较难,线段树应用,可参考解题报告
http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1233

http://acm.pku.edu.cn/JudgeOnline/problem?id=2155
难,二维树状数组。

http://acm.pku.edu.cn/JudgeOnline/problem?id=2777
中等,线段树应用。

http://acm.pku.edu.cn/JudgeOnline/problem?id=2274
难,堆的应用,《算法艺术与信息学竞赛》中有解答

http://acm.zju.edu.cn/show_problem.php?pid=2334
中等,左偏树,二项式堆或其他可合并堆的应用。
左偏树参考http://www.nist.gov/dads/HTML/leftisttree.html
二项式堆参见《算法导论》相关章节

http://acm.pku.edu.cn/JudgeOnline/problem?id=1182
中等,并查集

http://acm.pku.edu.cn/JudgeOnline/problem?id=1816
中等,字典树

http://acm.pku.edu.cn/JudgeOnline/problem?id=2778
较难,多串匹配树
参考:http://home.ustc.edu.cn/~zhuhcheng/ACM/zzy2004.pdf

http://acm.pku.edu.cn/JudgeOnline/problem?id=1743
难,后缀数组

http://acm.pku.edu.cn/JudgeOnline/problem?id=2774
较难,最长公共子串,经典问题,后缀数组

http://acm.pku.edu.cn/JudgeOnline/problem?id=2758
很难,后缀数组
可参考解题报告
http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1178

http://acm.pku.edu.cn/JudgeOnline/problem?id=2448
很难,数据结构综合运用

四.图论基础
参考资料:
刘汝佳《算法艺术与信息学竞赛》
《算法导论》
《网络算法与复杂性理论》谢政

推荐题目: 
http://acm.pku.edu.cn/JudgeOnline/problem?id=2337
简单,欧拉路

http://acm.pku.edu.cn/JudgeOnline/problem?id=3177
中等,无向图割边

http://acm.pku.edu.cn/JudgeOnline/problem?id=2942
较难,无向图双连通分支

http://acm.pku.edu.cn/JudgeOnline/problem?id=1639
中等,最小度限制生成树,《算法艺术与信息学竞赛》中有解答

http://acm.pku.edu.cn/JudgeOnline/problem?id=2728
中等,最小比率生成树,《算法艺术与信息学竞赛》中有解答

http://acm.pku.edu.cn/JudgeOnline/problem?id=3013
简单,最短路问题

http://acm.pku.edu.cn/JudgeOnline/problem?id=1275
中等,差分约束系统,Bellman-Ford求解,《算法艺术与信息学竞赛》中有解答

http://acm.pku.edu.cn/JudgeOnline/problem?id=1252
简单,Bellman-Ford

http://acm.pku.edu.cn/JudgeOnline/problem?id=1459
中等,网络流

http://acm.pku.edu.cn/JudgeOnline/problem?id=2391
较难,网络流

http://acm.pku.edu.cn/JudgeOnline/problem?id=1325
中等,二部图最大匹配

http://acm.pku.edu.cn/JudgeOnline/problem?id=2226
较难,二部图最大匹配

http://acm.pku.edu.cn/JudgeOnline/problem?id=2195
中等,二部图最大权匹配
KM算法参考《网络算法与复杂性理论》

http://acm.pku.edu.cn/JudgeOnline/problem?id=2516
较难,二部图最大权匹配

http://acm.pku.edu.cn/JudgeOnline/problem?id=1986
中等,LCA(最近公共祖先)问题
参考Tarjan's LCA algorithm 《算法导论》第21章习题

http://acm.pku.edu.cn/JudgeOnline/problem?id=2723
较难,2-SAT问题
参考:http://home.ustc.edu.cn/~zhuhcheng/ACM/2-SAT.PPT

http://acm.pku.edu.cn/JudgeOnline/problem?id=2749
较难,2-SAT问题

http://acm.pku.edu.cn/JudgeOnline/problem?id=3164
较难,最小树形图
参考《网络算法与复杂性理论》中朱-刘算法

五.数论及组合计数基础
http://acm.pku.edu.cn/JudgeOnline/problem?id=1811
简单,素数判定,大数分解
参考算法导论相关章节

http://acm.pku.edu.cn/JudgeOnline/problem?id=2888
较难,Burnside引理

http://acm.pku.edu.cn/JudgeOnline/problem?id=2891
中等,解模方程组

http://acm.pku.edu.cn/JudgeOnline/problem?id=2154
中等,经典问题,波利亚定理

http://cs.scu.edu.cn/soj/problem.action?id=2703
难,极好的题目,Burnside引理+模线性方程组

http://acm.pku.edu.cn/JudgeOnline/problem?id=2764
较难,需要数学方法,该方法在《具体数学》第七章有讲

http://acm.pku.edu.cn/JudgeOnline/problem?id=1977
简单,矩阵快速乘法


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

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

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

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

2007年10月9日 #

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

2007年10月6日 #

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

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

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

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

  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<1return -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 阅读(281) | 评论 (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 阅读(251) | 评论 (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 阅读(209) | 评论 (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 阅读(129) | 评论 (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 阅读(184) | 评论 (0)编辑 收藏

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

 

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

仅列出标题