学习ACM

PKU 3625

hujixiang — 2009-11-24 19:51:00

本题是最小生成树，用prim 比较方便，用kruskal的话，我超时了，看了discuss 后才知道要用优先队列优化。而且这题 prim 效率应该效率更高。 kruskal +优先队列 Memory: 8032K Time: 125MS Language: C++ Result: Accepted #include#include#includeusing namespace std;int N,M,set[1021],need,num;double vx[1001],vy[1001];struct edge{ int x,y; double w;}e[555555];int find (int x){ int i,j,r; r=x; while(set[r]!=r) r=set[r]; j=x; while(j!=r) { i=set[j]; set[j]=r; j=i; } return r;}void merge(int x,int y){ if(x>y) set[x]=y; else set[y]=x;}void insert(edge a){ int i; num++; e[num]=a; i=num; while(i>1 &

zoj 3010

hujixiang — 2009-08-09 11:21:00

DFS，规模很小，直接搜过#includeusing namespace std;int n;double sum,m;bool mark[11],escape;struct vex{ int num,count[11]; double per;}a[12];void dfs(int si,int num,double max){ int total=0,i; double temp; if(num==n) { if(max>sum)sum=max; escape=1; return; } if(si==n+1)return; for( i=1;i<=a[si].num;i++) { if(mark[a[si].count[i]]){mark[a[si].count[i]]=0;total++;} else {mark[a[si].count[i]]=1;total--;}

寻找必败态:博弈问题的快速解法

hujixiang — 2009-08-04 19:26:00

寻找必败态:博弈问题的快速解法http://www.mydrs.org 2005-1-9 大榕树博弈是信息学和数学试题中常会出现的一种类型，算法灵活多变是其最大特点，而其中有一类试题更是完全无法用常见的博弈树来进行解答。寻找必败态即为针对此类试题给出一种解题思路。此类问题一般有如下特点： 1、博弈模型为两人轮流决策的非合作博弈。即两人轮流进行决策，并且两人都使用最优策略来获取胜利。 2、博弈是有限的。即无论两人怎样决策，都会在有限步后决出胜负。 3、公平博弈。即两人进行决策所遵循的规则相同。以下题目都属于这一类： POJ1740 A New Stone Game MIPT100 Nim Game -- who is the winner? POJ1704 Georgia and Bob POJ1067 取石子游戏本着先理论后实践的原则，本文先对“寻找必败态”做出理论上的解释：要理解这种思想，首先要明白什么叫必败态。说简单点，必败态就是“在对方使用最优策略时，无论做出什么决策都会导致失败的局面”。其他的局面称为胜态，值得注意的是在胜态下做出错误的决策也有可能导致失败。此类博弈问题的精髓就是让对手永远面对必败态。必败态和胜态有着如下性质： 1、若面临末状态者为获胜则末状态为胜态否则末状态为必败态。 2、一个局面是胜态的充要条件是该局面进行某种决策后会成为必败态。 3、一个局面是必败态的充要条件是该局面无论进行何种决策均会成为胜态这三条性质正是博弈树的原理，但博弈树是通过计算每一个局面是胜态还是必败态来解题，这样在局面数很多的情况下是很难做到的，此时，我们可以利用人脑的推演归纳能力找到必败态的共性，就可以比较好的解决此类问题了。下面就通过实际题目来做一些分析：例1 POJ1740 A New Stone Game 题目大意是：有N堆石子，两人轮流进行操作，每一次为“操作者指定一堆石子，先从中扔掉一部分（至少一颗，可以全部扔掉），然后可以将该堆剩下的石子中的任意多颗任意移到其他未取完的堆中”，操作者无法完成操作时为负。分析：只有一堆时先手必胜。有两堆时若两堆相等则后手只用和先手一样决策即可保证胜

最小生成树问题的拓展

hujixiang — 2009-07-31 21:42:00

最小生成树问题的拓展安徽省芜湖一中汪汀摘要本文主要论述最小生成树问题中的两类拓展——最小度限制生成树和次小生成树。首先分别介绍了这两类拓展问题的模型，然后提出了求解这两类问题的算法，最后，通过一些例子分析其在实际问题中的应用。关键字生成树拓展度限制正文最小生成树是信息学竞赛中的经典问题，但近年来，竞赛中的题目不再局限于这类经典模型，难度大大增加。为解决这些问题，我们必须对这些经典模型加以拓展。拓展的类型很多，本文主要论述其中的两类——最小度限制生成树和次小生成树。1 最小生成树1.1最小生成树的定义设 G=(V,E,ω)是连通的无向图，G 中权值和最小的生成树称为最小生成树。1.2求解最小生成树的算法求最小生成树，比较常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使复杂度降为O(Vlog2V+E)，后者一般应用于稀疏图，其时间复杂度为O(Elog2V)。2、最小度限制生成树2.1、最小度限制生成树的定义对于一个加权的无向图，存在一些满足下面性质的生成树：某个特殊的结点的度等于一个指定的数值。最小度限制生成树就是满足此性质且权值和最小的一棵生成树。把它抽象成数学模型就是：设 G=(V,E,ω)是连通的无向图，v0 ∈V是特别指定的一个顶点,k为给定的一个正整数。IOI2004国家集训队论文汪汀第 2 页共 7 页如果 T是G的一个生成树且dT(v0)=k，则称T为G的k度限制生成树。G中权值和最小的k度限制生成树称为G的最小k度生成树。2.2、求解最小度限制生成树的算法约定：T为图G 的一个生成树，T+a-b 记作(+a,-b)，如果T+a-b 仍然是一个生成树，则称(+a,-b)是T的一个可行交换。引理 1：设T1,T2是图G 的两个不同的生成树，E(T1)\E(T2)={a1,a2,……,an},E(T2)\E(T1)={b1,b2,……,bn},则存在一个排序bi1,bi2,……,bin,使得T2+ej-fij (j=1,2,……,n)仍然是G 的生成树。定理 1：设T 是G的k 度限制生成树，则T是G的最小k 度限制生成树当且仅当下面三个条件同时成立：Ⅰ 对于 G中任何两条与v0关联的边所产生的T的可行交换都是不可改进的。Ⅱ 对于 G中任何两条与v0不关联的边所产生的T的可行交换都是不可改进的。Ⅲ

SPFA模板

hujixiang — 2009-07-28 18:57:00

void SPFA(int s) { for(int i=1;i<=n;i++) { d[i] = MAX; } int queue[N*N] = {0}; bool visit[N] = {false}; int front = 0, rear = 1; //int path[N]; queue[front] = s; visit[s] = true; d[s] = 0; while(frontd[u]+ edges[u][i]) {

北大ACM分类

hujixiang — 2009-07-28 18:51:00

1.搜索　//回溯2.DP（动态规划）　3.贪心　北大ACM题分类2009-01-27 14.图论　//Dijkstra、最小生成树、网络流5.数论　//解模线性方程6.计算几何　//凸壳、同等安置矩形的并的面积与周长sp; 7.组合数学　//Polya定理8.模拟　9.数据结构　//并查集、堆sp; 10.博弈论　 1、排序 sp; 1423, 1694, 1723, 1727, 1763, 1788, 1828, 1838, 1840, 2201, 2376, 2377, 2380, 1318, 1877, 1928, 1971, 1974, 1990, 2001, 2002, 2092, 2379, 1002（需要字符处理，排序用快排即可） 1007（稳定的排序） 2159（题意较难懂） 2231 2371（简单排序） 2388（顺序统计算法） 2418（ nbsp; 1.搜索　回溯二叉排序树） 2、搜索、回溯、遍历 1022 1111d 1118 1129 1190 1562 1564 1573 1655 2184 2225 2243 2312 2362 2378 2386 sp; 1010,1011,1018,1020,1054,1062,1256,1321,1363,1501，1650,1659,1664,1753,2078,2083,2303,2310,2329 简单：1128, 1166, 1176, 1231, 1256, 1270, 1321, 1543, 1606, 1664, 1731, 1742, 1745, 1847, 1915, 1950, 2038, 2157, 2182, 2183, sp; 2381, 2386, 2426,不易：1024, 1054, 1117, 1167, 1708, 1746, 1775, 1878, 1903, 1966, 2046, 2197, 2349,推荐：1011, 1190, 1191, 1416, 1579, 1632, 1639, 1659, 1680, 1683, 1691, 1709, 1714, 1753, 1771, 1826, 1855, 1856, 1890, 1924, 8:33主流算法： &nb 1935, 19

ACM网址大全

hujixiang — 2009-04-09 19:10:00

ACM网址大全来自http://hi.baidu.com/dizemmm/blog/item/8b520f0901d7d4c83ac7633b.html 浙江大学 http://acm.zju.edu.cn 北京大学 http://acm.pku.edu.cn/JudgeOnline 天津大学 http://acm.tju.edu.cn 厦门大学 http://acm.xmu.edu.cn/JudgeOnline 福州大学 http://acm.fzu.edu.cn 华中科技 http://acm.hust.edu.cn/JudgeOnline 宁波理工 http://acm.nit.net.cn 合肥工大 http://acm.tdzl.net:83/JudgeOnline 汕头大学 http://acm.stu.edu.cn 北大内部 http://ai.pku.cn/JudgeOnline 中国科大 http://acm.ustc.edu.cn 暨南大学 http://202.116.24.78/JudgeOnline 浙江工业 http://acm.zjut.edu.cn 中山大学 http://202.116.77.69/sicily 福建师范 http://acm.fjnu.edu.cn 哈工业大 http://acm.hit.edu.cn/ojs/ojs.php 杭电科大 http://acm.hziee.edu.cn 四川大学 http://acm.scu.edu.cn/soj 哈工程大 http://acm.hrbeu.edu.cn 武汉大学 http://acm.whu.edu.cn/noah 同济大学 http://acm.tongji.edu.cn 湖南大学 http://acm.hnu.cn:8080/online/ 上海大学 http://pc.shu.edu.cn/openjudge/problemlist.php 兰州大学 http://acm.sundayclub.cn/JudgeOnline/problemlist 最新、最全的 ACM ONLINE JUDGE 网站集合2007-02-11 18:21中国：浙江大学（ZJU）：http://acm.zj

新人向导

hujixiang — 2009-04-01 21:14:00

原创：怒火之袍 2003年4月29日我们学校的计算机学院从去年起开始组织学生参加世界上最具权威性的大学生程序设计竞赛——ACM/ICPC。从这学期开始，学院计划有组织地进行训练和讲座，以帮助大家在有限的时间内尽可能多地提高自己的能力，这对有兴趣投入数据结构与算法研究的同学来说无疑是一件好事。但是，刚刚接触信息学领域的同学往往存在很多困惑，不知道从何入手学习，在这篇文章里，我希望能将自己不多的经验与大家分享，希望对各位有所帮助。一、语言是最重要的基本功无论侧重于什么方面，只要是通过计算机程序去最终实现的竞赛，语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与JAVA。笔者首先说说JAVA，众所周知，作为面向对象的王牌语言，JAVA在大型工程的组织与安全性方面有着自己独特的优势，但是对于信息学比赛的具体场合，JAVA则显得不那么合适，它对于输入输出流的操作相比于C++要繁杂很多，更为重要的是JAVA程序的运行速度要比C++慢10倍以上，而竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽，这无疑对算法设计提出了更高的要求，是相当不利的。其实，笔者并不主张大家在这种场合过多地运用面向对象的程序设计思维，因为对于小程序来说这不旦需要花费更多的时间去编写代码，也会降低程序的执行效率。接着说C和C++。许多现在参加讲座的同学还在上大一，C的基础知识刚刚学完，还没有接触过C++，其实在赛场上使用纯C的选手还是大有人在的，它们主要是看重了纯C在效率上的优势，所以这部分同学如果时间有限，并不需要急着去学习新的语言，只要提高了自己在算法设计上的造诣，纯C一样能发挥巨大的威力。而C++相对于C，在输入输出流上的封装大大方便了我们的操作，同时降低了出错的可能性，并且能够很好地实现标准流与文件流的切换，方便了调试的工作。如果有些同学比较在意这点，可以尝试C和C++的混编，毕竟仅仅学习C++的流操作还是不花什么时间的。 C++的另一个支持来源于标准模版库（STL），库中提供的对于基本数据结构的统一接口操作和基

acm竞赛要掌握的知识

hujixiang — 2009-04-01 21:13:00

图论路径问题 0/1边权最短路径 BFS 非负边权最短路径（Dijkstra）可以用Dijkstra解决问题的特征负边权最短路径 Bellman-Ford Bellman-Ford的Yen-氏优化差分约束系统 Floyd 广义路径问题传递闭包极小极大距离 / 极大极小距离 Euler Path / Tour