Linux Stuff

看完并查集，做个题目巩固一下，解题报告还没有写，占个位置先，代码粘贴如下： /* ZJU1789The Suspects 【问题描述】 Severe acute respiratory syndrome (SARS), an atypical pneumonia of unknown aetiology, was recognized as a global threat in mid-March 2003. To minimize transmission to others, the best strategy is to separate the suspects from others. In the Not-Spreading-Your-Sickness University (NSYSU), there are many student groups. Students in the same group intercommunicate with each other frequently, and a student may join several groups. To prevent the possible transmissions of SARS, the NSYSU collects the member lists of all student groups, and makes the following rule in their standard operation procedure (SOP). Once a member in a group is a suspect, all members in the group are suspects. However, they find that it is not easy to identify all the suspects when a student is recognized as a suspect. Your job is to write a program which finds all the suspects. Input The input contains several cases. Each test case begins with two

对并查集的理解： 1、树的深度最多是2 2、一般set结构体都需要有一个rank[]来记录有多少孩子，孩子多的，以后还是父亲 3、并查集： 不相交集合，这个概念一定得搞清楚！ 欢迎拍砖！

(union-find sets) 是一种简单的用途广泛的集合 . 并查集是若干个不相交集合，能够实现较快的合并和判断元素所在集合的操作，应用很多。一般采取树形结构来存储并查集，并利用一个 rank 数组 来存储集合的深度下界，在查找操作时进行路径压缩使后续的查找操作加速。这样优化实现的并查集，空间复杂度为 O(N) ，建立一个集合的时间复杂度为 O(1) ， N 次合并 M 查找的时间复杂度为 O(M Alpha(N)) ，这里 Alpha 是 Ackerman 函数的某个反函数，在很大的范围内（人类目前观测到的宇宙范围估算有 10 的 80 次方个原子，这小于前面所说的范围）这个函数的值可以看成是不大于 4 的，所以并查集的操作可以看作是线性的。它支持以下三中种操作 : 　　－ Union (Root1, Root2) // 并操作；把子集合 Root2 并入集合 Root1 中 . 要求： Root1 和 Root2 互不相交 , 否则不执行操作 . 　　－ Find (x) // 搜索操作；搜索单元素 x 所在的集合 , 并返回该集合的名字 . 　　－ UFSets (s) // 构造函数。将并查集中 s 个元素初始化为 s 个只有一个单元素的子集合 . 　　－对于并查集来说，每个集合用一棵树表示。 　　－集合中每个元素的元素名分别存放在树的结点中，此外，树的每一个结点还有一个指向其双亲结点的指针。 　　－设 S1= {0, 6, 7, 8 } ， S2= { 1, 4, 9 } ， S3= { 2, 3, 5 } 并查集： －为简化讨论，忽略实际的集合名，仅用表示集合的树的根来标识集合。 　　－为此，采用树的双亲表示作为集合存储表示。集合元素的编号从 0 到 n-1 。其中 n 是最大元素个数。在双亲表示中，第 i 个数组元素代表包含集合元素 i 的树结点。根结点的双亲为 -1 ，表示集合中的元素个数。为了区别双亲指针信息 ( ≥ 0 ) ，集合元素个数信息用负数表示。 　　　 / 元素个数用负数表示 ？这个题目可是没有这样呀？ 数值： parent      索引：下标 集合 S1, S2 和 S3 的双亲表示 :                   　　 　          S1 ∪ S2 的可能的表示方法

来自： richardhuang 对 ACM World Finals 1999－－ " Trade on Verweggistan" 的解决 acm world finals 1999 解题报告 #include <stdio.h> #include <iostream.h> #include <string.h> main() {          int u,n,i,j,k,max,s,total,t,all;          int a[60][30];          int b[2000],c[2000];          int e[300];          scanf("%d",&n);          u=0;          while (n>0)          {                          u++;                          total=0;                          memset(a,0,sizeof(a));                          memset(b,0,sizeof(b));                          b[0]=1;                          all=0;                          for (i=1;i<=n;i++)                          {                                         scanf("%d",&a[i][0]);                                         all+=a[i][0];                                         for (j=1;j<=a[i][0];j++)                                         {

1015 Jury Compromise 1029 False coin 1036 Gangsters 1037 A decorative fence 1038 Bugs Integrated, Inc. 1042 Gone Fishing 1050 To the Max 1062 昂贵的聘礼 1074 Parallel Expectations 1080 Human Gene Functions 1088 滑雪 1093 Formatting Text 1112 Team Them Up! 1141 Brackets Sequence 1143 Number Game 1157 LITTLE SHOP OF FLOWERS 1159 Palindrome 1160 Post Office 1163 The Triangle 1170 Shopping Offers 1178 Camelot 1179 Polygon 1180 Batch Scheduling 1185 炮兵阵地 1187 陨石的秘密 1189 钉子和小球 1191 棋盘分割 1192 最优连通子集 1208 The Blocks Problem 1239 Increasing Sequences 1240 Pre-Post-erous! 1276 Cash Machine 1293 Duty Free Shop 1322 Chocolate 1323 Game Prediction 1338 Ugly Numbers 1390 Blocks 1414 Life Line 1432 Decoding Morse Sequences 1456 Supermarket 1458 Common Subsequence 1475 Pushing Boxes 1485 Fast Food 1505 Copying Books 1513 Scheduling Lectures 1579 Function Run Fun 1609 Tiling Up Blocks 1631 Bridging signals 1633 Gladiators 1635 Subway tree systems 1636 Prison rearrangement 1644 To Bet or Not To Bet 1649 Market

昨天把1011AC了，不过还没有来得及写结题报告，占个位置先～ Source Code Problem: 1011 User: omycle Memory: 264K Time: 32MS Language: C++ Result: Accepted Source Code #include <iostream> #include <time.h> #include <stdlib.h> #include <string.h> using namespace std ; //#define GS 64 //#define GS 64//根数 //bool stt=false; int GS ; int stick_length [ 50 ]; //50就足够用了 int stick_count = 0 ; //每一种可能的值对应的长棍的根数--是一个全局变量 int stick_length_count = 0 ; // 有几种可能的长度值 int Len = 0 ; //长度值的全局变量，利于递归访问 int * sticks_length ; //int sticks_length[10]={7,1,7,1,7,1,2,2,2,2}; /* int sticks_length[64]={40,40,30,35,35,\ 26,15,40,40,40,\ 40,40,40,40,40,\ 40,40,40,40,40,\ 40,40,40,43,42,\ 42,41,10,4,40,\ 40,40,40,40,40,\ 40,40,40,40,40,\ 40,40,40,25,39,\ 46,40,10,4,40,\ 40,37,18,17,16,\ 15,40,40,40,40,\ 40,40,40,40}; */ //bool flag[GS]={true};//全部可以用 bool * flag ; bool stick ( int g_st , int length_ing , int next_gun ); //初始化flag[] void Init_flag ( int g ) { memset ( flag , true , sizeof (

1001解题报告： 1、每一次提交前，先核对一下是否真正粘贴了应该粘的正确的程序。 2、在提交前，请把system("PAUSE")或者clock()-start之类测试时间的代码给注释掉。 3、严格按照题目所给的输出格式输出，例如，如果题目要求循环录入，那么谨记，用while(cin>>){}的格式或者其他的只要能够符合循环录入即可。 4、请不要试图把软件工程之类的东西给随意套进来，因为可能会增加问题的规模。造成自己测试的复杂度－－－（这一条还有待考究啊，毕竟自己才是菜鸟，也只是对软件工程的东西稍微懂一点。） 5、把每一次测试的数据，给保存下来，最好给每一个程序项目都专门建一个测试数据.txt文档。 6、每当拿到一个复杂的问题，不要慌张，先概要设计在详细设计，呵呵，又扯到了软件工程的东西了。不过这一点是应该提倡的－－－即从抽象到具体，逐步求精。呵呵。 解题代码： Source Code Problem: 1001 User: omycle Memory: 256K Time: 16MS Language: C++ Result: Accepted Source Code #include <iostream> #include <string.h> //#include <time.h> #include <stdlib.h> using namespace std ; void add ( char * a , char * c , int offset ) { char ab [ 255 ]; memset ( ab , ' \0 ' , sizeof ( char )* 255 ); //这一步很有必要 for ( unsigned int i_ = 0 ; i_ < strlen ( a ); i_ ++) ab [ i_ ]= a [ strlen ( a )- i_ -1 ]; char cd [ 255 ]; memset ( cd , ' \0 ' , sizeof ( char )* 255 ); // for ( unsigned int j = 0 ; j < s