“分层图思想”及其在信息学竞赛中的应用 天津市南开中学肖天 【摘要】本文通过对几道信息学竞赛题的解决，提出了一种解决问题的建模思想——分层图思想。该思想通过挖掘问题性质，将原问题抽象得出的图复 制为若干层并连接形成更大的图，使本来难以用数学语言表达得图论模 型变得简明严谨，为进一步解决问题打下了良好的基础。 【关键字】分层图思想图论数学模型最短路信息学竞赛 【正文】 1 引论 人们在借助计算机解决一个实际问题时，无非就是详细地告诉计算机应该怎么做，使它能通过人们给定的输入得到人们想要的输出。由于一般的计算机只能处理数字信号，所以只有把实际问题转化为数学问题，计算机才能帮助我们。这一步就是建立数学模型。 数学模型的建立在通过计算机解决问题的过程中非常重要。它把计算机无法理解的问题加以转化，使一切事物量化，最终变为只含数学过程的问题。它是人脑与计算机沟通的桥梁。不仅如此，数学模型的好坏直接影响着人与计算机之间的信息交流，影响着计算机对问题的“理解”。好的数学模型能够抓住问题的本质，表述简捷明了，易于人们找到有效的解决方法，并通过编制程序的方式将解决方法告诉计算机；相反，对于同一个问题，如果数学模型不能抓住问题本质，人们就可能无法解决问题，或者找不到有效的方法，更不用提告诉计算机如何做了。 由于建立数学模型是为了解决问题，所以人们在做这项工作时往往希望把问题归结为已经很好解决的经典问题或若干这样问题的有机结合。这样，只要应用前人的研究成果就可以了。比如，排序、求图的单源最短路、网络流等等都是经典问题，前人不仅给出一般解法，而且对各种特殊情况和变形作了深入的研究。但事情并不总像人们希望的那样，有的问题即使可以归结为已有问题，在其中加入一些干扰因素后，原有性质就会发生改变，原来建立起的数学模型难以再用严谨的数学语言表达。这样问题中的部分图论问题可以用本文提出的“分层图思想”解决。 该思想注重对原问题性质的挖掘，通过对原问题数学模型的扩展，将干扰因素融入新的数学模型之中，恢复了模型的严谨性，进而与已解决问题产生联系，得到有效算法。
摘抄自C博客 组合数学 计数与统计 2001 - 符文杰：《Pólya原理及其应用》 2003 - 许智磊：《浅谈补集转化思想在统计问题中的应用》 2007 - 周冬：《生成树的计数及其应用》 2008 - 陈瑜希《Pólya计数法的应用》 数位问题 2009 - 高逸涵《数位计数问题解法研究》 2009 - 刘聪《浅谈数位类统计问题》 动态统计 2004 - 薛矛：《解决动态统计问题的两把利刃》 2007 - 余江伟：《如何解决动态统计问题》 博弈 2002 - 张一飞：《由感性认识到理性认识——透析一类搏弈游戏的解答过程》2007 - 王晓珂：《解析一类组合游戏》 2009 - 曹钦翔《从“k倍动态减法游戏”出发探究一类组合游戏问题》 2009 - 方展鹏《浅谈如何解决不平等博弈问题》 2009 - 贾志豪《组合游戏略述——浅谈SG游戏的若干拓展及变形》 母函数 2009 - 毛杰明《母函数的性质及应用》 拟阵 2007 - 刘雨辰：《对拟阵的初步研究》 线性规划 2007 - 李宇骞：《浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》 置换群 2005 - 潘震皓：《置换群快速幂运算研究与探讨》 问答交互 2003 - 高正宇：《答案只有一个——浅谈问答式交互问题》 猜数问题 2003 - 张宁：《猜数问题的研究:<聪明的学生>一题的推广》
2006 - 龙凡：《一类猜数问题的研究》 数据结构 数据结构 2005 - 何林：《数据关系的简化》 2006 - 朱晨光：《基本数据结构在信息学竞赛中的应用》 2007 - 何森：《浅谈数据的合理组织》 2008 - 曹钦翔《数据结构的提炼与压缩》 结构联合 2001 - 高寒蕊：《从圆桌问题谈数据结构的综合运用》 2005 - 黄刚：《数据结构的联合》 块状链表 2005 - 蒋炎岩：《数据结构的联合——块状链表》 2008 - 苏煜《对块状链表的一点研究》 动态树 2006 - 陈首元：《维护森林连通性——动态树》 2007 - 袁昕颢：《动态树及其应用》 左偏树 2005 - 黄源河：《左偏树的特点及其应用》 跳表 2005 - 魏冉：《让算法的效率“跳起来”！——浅谈“跳跃表”的相关操作及其应用》 2009 - 李骥扬《线段跳表——跳表的一个拓展》 SBT 2007 - 陈启峰：《Size Balance Tree》 线段树 2004 - 林涛：《线段树的应用》 单调队列 2006 - 汤泽：《浅析队列在一类单调性问题中的应用》 哈希表 2005 - 李羽修：《Hash函数的设计优化》 2007 - 杨弋：《Hash在信息学竞赛中的一类应用》 Splay 2004 - 杨思雨：《伸展树的基本操作与应用》
字符串可以用字符数组与字符串变量两种方式来存储，效果类似。 一、用字符数组来存储字符串： char st1[100],st2[100] ; //字符数组说明 cin>>st1>>st2; long a,b; 输入：hello, world 则st1={…h?,?e?,?l?,?l?,?o?,?,?,?\0?} st2={…w?,?o?,?r?,?l?,?d?,?\0} 字符?\0?为字符串结束标志 1. 字符数组长度 strlen(st1); //如a=strlen(st1);b=strlen(st2); 则a=6,b=5 2. 字符数组比较 不能直接比较，st1>st2是错误的，要用strcmp（）函数 strcmp(st1,st2); //st1=st2相等则输出0，st1
动态规划算法的优化技巧 福州第三中学毛子青 [关键词] 动态规划、时间复杂度、优化、状态 [摘要] 动态规划是信息学竞赛中一种常用的程序设计方法，本文着重讨论了运用动态规划思想解题时时间效率的优化。全文分为四个部分，首先讨论了动态规划时间效率优化的可行性和必要性，接着给出了动态规划时间复杂度的决定因素，然后分别阐述了对各个决定因素的优化方法，最后总结全文。 [正文] 一、引言 动态规划是一种重要的程序设计方法，在信息学竞赛中具有广泛的应用。 使用动态规划方法解题，对于不少问题具有空间耗费大、时间效率高的特点，因此人们在研究动态规划解题时更多的注意空间复杂度的优化，运用各种技巧将空间需求控制在软硬件可以承受的范围之内。但是，也有一部分问题在使用动态规划思想解题时，时间效率并不能满足要求，而且算法仍然存在优化的余地，这时，就需要考虑时间效率的优化。 本文讨论的是在确定使用动态规划思想解题的情况下，对原有的动态规划解法的优化，以求降低算法的时间复杂度，使其能够适用于更大的规模。 二、动态规划时间复杂度的分析 使用动态规划方法解题，对于不少问题之所以具有较高的时间效率，关键在于它减少了“冗余”。所谓“冗余”，就是指不必要的计算或重复计算部分，算法的冗余程度是决定算法效率的关键。动态规划在将问题规模不断缩小的同时，记录已经求解过的子问题的解，充分利用求解结果，避免了反复求解同一子问题的现象，从而减少了冗余。 但是，动态规划求解问题时，仍然存在冗余。它主要包括：求解无用的子问题，对结果无意义的引用等等。 下面给出动态规划时间复杂度的决定因素： 时间复杂度=状态总数*每个状态转移的状态数*每次状态转移的时间[1] 下文就将分别讨论对这三个因素的优化。这里需要指出的是：这三者之间不是相互独立的，而是相互联系，矛盾而统一的。有时，实现了某个因素的优化，另外两个因素也随之得到了优化；有时，实现某个因素的优化却要以增大另一因素为代价。因此，这就要求我们在优化时，坚持“全局观”，实现三者的平衡。 三、动态规划时间效率的优化 3.1 减少状态总数 我们知道，动态规划的求解过程实际上就是计算所有状态值的过程，因此状态的规模直接影响到算法的时间效率。所以，减少状态总数是动态规划优化的重要部分，本节将讨论减少状态总数的一些方法。
左偏树的特点及其应用 广东省中山市第一中学黄源河 【摘要】 本文较详细地介绍了左偏树的特点以及它的各种操作。 第一部分提出可并堆的概念，指出二叉堆的不足，并引出左偏树。第二部分主要介绍了左偏树的定义和性质。第三部分详细地介绍了左偏树的各种操作，并给出时间复杂度分析。第四部分通过一道例题，说明左偏树在当今信息学竞赛中的应用。第五部分对各种可并堆作了一番比较。最后总结出左偏树的特点以及应用前景。 【关键字】左偏树可并堆优先队列 【目录】 一、引言 (2) 二、左偏树的定义和性质 (2) 2.1 优先队列，可并堆 (2) 2.1.1 优先队列的定义 (2) 2.1.2 可并堆的定义 (2) 2.2 左偏树的定义 (3) 2.3 左偏树的性质 (4) 三、左偏树的操作 (5) 3.1 左偏树的合并 (5) 3.2 插入新节点 (7) 3.3 删除最小节点 (8) 3.4 左偏树的构建 (8) 3.5 删除任意已知节点 (9) 3.6 小结 (12) 四、左偏树的应用 (13) 4.1 例——数字序列（Baltic 2004） (13) 五、左偏树与各种可并堆的比较 (15) 5.1 左偏树的变种——斜堆 (15) 5.2 左偏树与二叉堆的比较 (16) 5.3 左偏树与其他可并堆的比较 (16) 六、总结 (18)
【正文】 一、引言 优先队列在信息学竞赛中十分常见，在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中，优先队列都有着广泛的应用。二叉堆是一种常用的优先队列，它编程简单，效率高，但如果问题需要对两个优先队列进行合并，二叉堆的效率就无法令人满意了。本文介绍的左偏树，可以很好地解决这类问题。 二、左偏树的定义和性质 在介绍左偏树之前，我们先来明确一下优先队列和可并堆的概念。 2.1优先队列，可并堆 2.1.1优先队列的定义 优先队列(Priority Queue)是一种抽象数据类型(ADT)，它是一种容器，里面有一些元素，这些元素也称为队列中的节点(node)。优先队列的节点至少要包含一种性质：有序性，也就是说任意两个节点可以比较大小。为了具体起见我们假设这些节点中都包含一个键值(key)，节点的大小通过比较它们的键值而定。优先队列有三个基本的操作：插入节点(Insert)，取得最小节点(Minimum) 和删除最小节点(Delete-Min)。 2.1.2可并堆的定义 可并堆(Mergeable Heap)也是一种抽象数据类型，它除了支持优先队列的三个基本操作(Insert, Minimum, Delete-Min)，还支持一个额外的操作——合并操作： H ← Merge(H1,H2) Merge( ) 构造并返回一个包含H1和H2所有元素的新堆H。 前面已经说过，如果我们不需要合并操作，则二叉堆是理想的选择。可惜合并二叉堆的时间复杂度为O(n)，用它来实现可并堆，则合并操作必然成为算法的瓶颈。左偏树(Leftist Tree)、二项堆(Binomial Heap) 和Fibonacci堆(Fibonacci Heap) 都是十分优秀的可并堆。本文讨论的是左偏树，在后面我们将看到各种可并堆的比较。
【字符数组转化成string类型】 Char ch[]=”ABCDEFG” String str(ch);//也可string str=ch; 或者 Char ch[]=”ABCDEFG” String str; Str=ch;//在原有基础上添加可以用str+=ch; 【string类型转换为字符数组】 Char buf[10] String str(“ABCDEFG”); Length=str.copy(buf,9); Buf[length]=’\0’; 或者 Char buf[10]; String str1(“ABCDEFG”); strcpy（buf,str1.c_str());//strncpy(buf,str1.c_str(),10); 【字符串拼接】 一、string类字符串 重点：函数append的用法： (1)向s1-string的后面加s2-string （1个参数）
s.append(s2); 或s1+=s2; 也可直接将字符串拼接：如 string s=“hello”; s.append(" world");//“hello"后面拼接”world" (2)（2个参数） 1.向s1-string的后面加s2-string的一部分 s1.append(s2,n); // 把字符串s2的前n个字符连接到当前字符串结尾 2.向string后面加多个字符 string s1 = "hello "; s1.append(4,’!’); //在当前字符串结尾添加4个字符! s1 = “hello !!!”; (3).向string的后面加string的一部分（3个参数） 1.string s1 = "hello ", s2 = "beautiful world "; s1.append(s2, 11, 5); //把字符串s2中从11开始的5个字符连接到当前字符串的结尾得s1 = “hello world”; 2.string s1 = "hello ", s2 = “beautiful world”; s1.append(s2.begin()+11, s2.end()); //把s2的迭代器begin()+11和end()之间的部分连接到当前字符串的结尾得“hello world”; 二、char数组类字符串 重点：strcat()函数，该函数接受两个字符串作为参数，该函数把第2个字符串
字符数组与字符串类型 字符型变量:VAR CH :CHAR ; 一、字符数组:数组基类型(元素的类型为字符型。 VAR A:ARRAY [ 1. . N ] OF CHAR ; 输入、输出也与普通数组一样,只能用循环结构,逐个元素地给它赋值,即: FOR I:= 1 TO N DO READ(A[ I ] ; 或者: A[I]:=‘ X ’ ; 不能用:A :=‘ IT IS A PEN ’ ; 例一:判断从键盘输入的字符串是否为回文(从左到右和从右到左读一串字符的值是一样的, 如 ABCDCBA , 1234321, 11, 1 ,串长 < 100 ,且以点号‘. ’结束。 2000年竞赛题:判断一个数是否为回文数。 VAR LETTER:ARRAY [ 1. . 100 ] OF CHAR ; I, J :0. . 100 ; CH:CHAR ; BEGIN WRITELN(‘ INPUT A STRING :’ ; I := O ; READ (CH ; WHILE CH < > ‘. ’ DO BEGIN
I:=I+1 ; LETTER[ I ] := CH ; READ (CH ; END ; J :=1 ; { I 指向数组的尾部, J 指向数组的头部 ,逐个比较 } WHILE (J < I AND (LETTER[ J ]= LETTER[ I ] DO BEGIN I:= I – 1 ; J :=J + 1 END ; IF J > = I THEN WRITELN(‘ YES ’ ELSE WRITELN(‘ NO ’ ; END . 二、字符串类型:针对 TURBO PASCAL 1、字符串常量:CONST STR=‘ THIS IS A BOOK。’ ; 我们经常在 WRITE 语句中用到字符串,也可以 WRITE (STR ;语句输出 STR 的值。 2、字符串类型:也是一种构造类型。 定义形式:TYPE 字符串类型名 = STRING[ N ];
1999年 陈宏- 数据结构的选择与算法效率——从IOI98试题PICTURE谈起 来煜坤- 把握本质，灵活运用——动态规划的深入探讨 齐鑫- 搜索方法中的剪枝优化 邵铮- 数学模型的建立、比较和应用 石润婷- 隐蔽化、多维化、开放化──论当今信息学竞赛中数学建模的灵活性睢》?- 准确性、全面性、美观性——测试数据设计中的三要素 周咏基- 论随机化算法的原理与设计 2000年 陈彧- 信息学竞赛中的思维方法 方奇- 动态规划 高寒蕊- 递推关系的建立及在信息学竞赛中的应用 郭一- 数学模型及其在信息学竞赛中的应用 江鹏- 探索构造法解题模式 李刚- 动态规划的深入讨论 龙翀- 解决空间规模问题的几种常用的存储结构 骆骥- 数学模型的建立和选择 施遥- 人工智能在围棋程序中的应用 肖洲- 数据结构的在程序设计中的应用 谢婧- 规模化问题的解题策略 徐串- 论程序的调试技巧 徐静- 图论模型的建立与转化 杨江明- 论数学策略在信息学问题中的应用 杨培- 非最优化算法初探 张辰- 动态规划的特点及其应用 张力- 类比思想在解题中的应用 张一飞- 冗繁削尽留清瘦——浅谈信息的充分利用 2001年 高寒蕊- 从圆桌问题谈数据结构的综合运用 符文杰- Pólya原理及其应用 高岳- 中等硬度解题报告 江鹏- 从一道题目的解法试谈网络流的构造与算法 刘汝佳- 搬运工问题的启示 李益明- 计算几何的相关问题 李源- 树的枚举 骆骥- 由“汽车问题”浅谈深度搜索的一个方面——搜索对象与策略的重要性毛子青- 动态规划算法的优化技巧 俞玮- 基本动态规划问题的扩展 张一飞- 求N!的高精度算法 2002年 戴德承- 退一步海阔天空——“目标转化思想”的若干应用
字符串和字符数组之间的转换 2010-11-02 16:53:00| 分类： |举报|字号订阅 字符串类提供了一个void ToCharArray() 方法，该方法可以实现字符串到字符数组的转换。如下例： private void TestStringChars() { string str = "mytest"; char[] chars = (); = ""; "Length of \"mytest\" is " + + "\n"); "Length of char array is " + + "\n"); "char[2] = " + chars[2] + "\n"); } 例中以对转换转换到的字符数组长度和它的一个元素进行了测试，结果如下： Length of "mytest" is 6 Length of char array is 6 char[2] = t 可以看出，结果完全正确，这说明转换成功。那么反过来，要把字符数组转换成字符串又该如何呢？ 我们可以使用类的构造函数来解决这个问题。类有两个构造函数是通过字符数组来构造的，即 String(char[]) 和String[char[], int, int)。后者之所以多两个参数，是因为可以指定用字符数组中的哪一部分来构造字符串。而前者则是用字符数组的全部元素来构造字符串。我们以前者为例， 在 TestStringChars() 函数中输入如下语句： char[] tcs = {'t', 'e', 's', 't', ' ', 'm', 'e'}; string tstr = new String(tcs); "tstr = \"" + tstr + "\"\n"); 运行结果输入 tstr = "test me"，测试说明转换成功。 实际上，我们在很多时候需要把字符串转换成字符数组只是为了得到该字符串中的某个字符。如果只是为了这个目的，那大可不必兴师动众的去进行转换，我们
字符数组与字符串 <1>定义 Char数组名[常量表达式] 数组中每一个元素的值为一个字符。 系统在内存为字符数组分配若干连续的存储单元，每个储存单元为一个字节。 <2>初始化 逐个元素初始化，如char c[8]={‘b’,’o’,’y’};（要记得加单引号） 用字符串初始化，如char c[11]={“I am a boy”};初始化后在末尾自动添加’0’ 如果初值个数<数组长度，则只将这些字符赋给数组中前面元素，其余元素自动定为空字符（即’0’） <3>输入输出 ①用格式”%c”逐个输入输出，如scanf(“%c”,&a[0]); ②用格式符”%s”整个字符串输入输出，如scanf(“%s”,a) 用”%s”格式输出字符数组时，遇’\0’结束输出，且输出字符中不含’\0’，用scanf及”%s”输入时，数组名前不能再加”&”符号。 字符串的末尾必须有’\0’字符，且字符串只能存放在字符数组中。 scanf中%s输入时遇空格或回车结束。 ③用函数gets实现输入 gets（字符数组），如gets(a) 调用函数时，回车键作为输入结束标志；然后将接收到的字符依
次赋给数组各个元素，并自动在字符串末尾加字符串结束标记’\0’ ④用字符串输出函数puts实现输出 puts(字符串/字符数组)，如puts(a); 输出一个字符串，并在输出后自动换行。 <4>字符串处理函数 ①字符串拷贝函数 格式strcpy(字符数组1,字符串2) 将字符串2拷贝到字符数组1中去，要求字符数组1必须足够大，拷贝时’\0’一同拷贝，不能使用赋值语句为一个字符数组赋值。字符数组1应写成数组名的形式，比如char a[0]; strcpy(a,…) ②字符串连接函数 格式strcat(字符数组1,字符数组2) 将字符数组2连到字符数组1后面，要求字符数组1必须足够大，连接前，两串均以’\0’结束；连接后，串1的’0’取消，新串最后加’\0’。 ③计算字符串长度的函数 strlen(字符数组); 求出字符串或字符数组中实际字符个数，不包括’\0’，并且遇到’\0’结束。 ④字符串比较函数 格式strcmp(字符数组1,字符数组2)
NOI国家集训队论文分类（至2008） 摘抄自C博客 组合数学 计数与统计 2001 - 符文杰：《Polya原理及其应用》 2003 -许智磊：《浅谈补集转化思想在统计问题中的应用》 2007 -周冬：《生成树的计数及其应用》 2008 - 陈瑜希《Polya计数法的应用》 数位问题 2009 -高逸涵《数位计数问题解法研究》 2009 -刘聪《浅谈数位类统计问题》 动态统计 2004 -薛矛：《解决动态统计问题的两把利刃》 2007 -余江伟：《如何解决动态统计问题》 博弈 2002 -张一飞：《由感性认识到理性认识一一透析一类搏弈游戏的解答过程》2007 -王晓珂：《解析一类组合游戏》 2009 -曹钦翔《从“k倍动态减法游戏”出发探究一类组合游戏问题》 2009 -方展鹏《浅谈如何解决不平等博弈问题》 2009 -贾志豪《组合游戏略述一一浅谈SG游戏的若干拓展及变形》母函数 2009 -毛杰明《母函数的性质及应用》 拟阵 2007 -刘雨辰：《对拟阵的初步研究》 线性规划 2007 -李宇骞：《浅谈信息学竞赛中的线性规划一一简洁高效的单纯形法实现与应用》 置换群 2005 -潘震皓：《置换群快速幕运算研究与探讨》 问答交互 2003 -高正宇：《答案只有一个一一浅谈问答式交互问题》 猜数问题 2003 -张宁：《猜数问题的研究：< 聪明的学生> 一题的推广》
2006 -龙凡：《一类猜数问题的研究》 数据结构 数据结构 2005 -何林：《数据关系的简化》 2006 -朱辰光:《基本数据结构在信息学竞赛中的应 用》 2007 -何森：《浅谈数据的合理组织》 2008 -曹钦翔《数据结构的提炼与压缩》 结构联合 2001 -高寒蕊：《从圆桌问题谈数据结构的综合运用》 2005 -黄刚：《数据结构的联合》 块状链表 2005 -蒋炎岩：《数据结构的联合——块状链表》 2008 -苏煜《对块状链表的一点研究》 动态树 2006 -陈首元：《维护森林连通性——动态树》 2007 -袁昕颢：《动态树及其应用》 左偏树 2005 -黄源河：《左偏树的特点及其应用》 跳表 2005 -魏冉：《让算法的效率跳起来”——浅谈跳跃表”的相关操作及其应用》2009 -李骥扬《线段跳表——跳表的一个拓展》 SBT 2007 - 陈启峰：《Size Bala nee Tree 》 线段树 2004 -林涛：《线段树的应用》 单调队列 2006 -汤泽：《浅析队列在一类单调性问题中的应用》 哈希表 2005 - 李羽修：《Hash函数的设计优化》 2007 - 杨弋：《Hash在信息学竞赛中的一类应用》 Splay 2004 -杨思雨：《伸展树的基本操作与应用》
置换群快速幂运算 研究与探讨 江苏省苏州中学 潘震皓 [关键词] 置换 循环 分裂 合并 [摘要] 群是一个古老的数学分支，近几年来在程序设计中置换群得到了一定的应用。本文针对置换群的特点提出了线性时间的幂运算算法，并举例说明了优化后算法的效果。 [正文] 一、引言 置换群是一种优秀的结构，在程序设计中，它的大部分基本操作，时间和空间复杂度都是线性的，甚至有的还是常数的。所以一个问题如果能够抽象归结为一个置换群模型的话，往往能够在程序设计中轻松地解决。但是对于整幂运算来说，似乎只能通过反复做乘法来获得O(k*乘法)或是O(logk*乘法)的算法；而对于分数幂运算，则找不到较好的方法实现。 二、置换群的整幂运算 2.1 整幂运算的一个转化 在置换群中有一个定理：设e T k =， （T 为一置换，e 为单位置换（映射函数为x x f =)(的置换）），那么k 的最小正整数解是T 的拆分的所有循环长度的最小公倍数。 或者有个更一般的结论：设e T k =， （T 为一循环，e 为单位置换），那么k 的最小正整数解为T 的长度。 我们知道，单位置换就是若干个只含单个元素的循环．．．．．．．．．的并。也就是说，长度为l 的循环，l 次的幂，把所有元素都完全分裂了。这是为什么呢？ 我们来做一个试验：(下面的置换均以循环的连接表示) 设n=6，那么3 26 )(T T =。任取一T=(1 3 5 2 4 6)，来做一遍乘法： ()() 36 2 45 1 34 126565432134 1 2 6 51265431265436543211265436543211265436543212 =???? ??=???? ?????? ??=???? ?????? ??=T 分裂成了2份！而且这2份恰好是T 的奇数项和偶数项！（注意可以写成(1 5 4)(3 2 6)）
实验06 数组、指针与字符串（4学时） （第6章数组、指针与字符串） 一、实验目的 二、实验任务 6_1（习题6-25）编写并测试3×3矩阵转置函数，使用数组保存3×3矩阵。 6_2（习题6-26）使用动态内存分配生成动态数组来重新完成上题（n阶方阵），使用指针实现函数的功能。 6_3 编程实现两字符串的连接。要求使用字符数组保存字符串，不要使用系统函数。
6_4 使用string类声明字符串对象，重新实现上一小题。 6_5（习题6-27）声明一个Employee类。 其中包括姓名、街道地址、城市和邮编等属性，以及change_name()和display()等函数。display()显示姓名、街道地址、城市和邮编等属性，change_name()改变对象的姓名属性，实现并测试这个类。 6_6（习题6-27）声明包含5个元素的对象数组，每个元素都是Employee 类型的对象。 6_7 修改实验4中的people（人员）类。 具有的属性如下：姓名char name[11]、编号char number[7]、性别char sex[3]、生日birthday、身份证号char id[16]。其中“出生日期”声明为一个“日期”类内嵌子对象。 用成员函数实现对人员信息的录入和显示。 要求包括：构造函数和析构函数、拷贝构造函数、内联成员函数、聚集。 在测试程序中声明people类的对象数组，录入数据并显示。 三、实验步骤 1.（编程，习题6-25）编写矩阵转置函数，输入参数为3×3整型数组。 使用循环语句实现矩阵元素的行列对调，注意在循环语句中究竟需要对哪些元素进行操作，编写main()函数实现输入输出。程序名：lab6_1.cpp。 参考运行结果：
C语言中字符变量字符串和字符数组应用 字符变量(type｀char｀?字符串(string)和字符数组(type｀char｀arrary)是C语言中非常重要的结构成分,也是应用编程中常发生混淆?导致错误发生的成分?一?注意区别字符数组中的字符和字符串C语言中无字符串变量,但提供了字符数组character arrary) 用于存储字符串,例如: char str[]="Hello"; 同时,字符数组亦用于存储字符或字符变量,例如: /*存放字符例*/ char Chars[]={｀H｀｀e｀,｀1｀｀1｀,｀o｀}; /*存放字符变量例*/ char ch=getch(); char CharVar[]=ch; str和Chars的内容尽管由相同字母构成,但前者是字符串(str)后者为一列字符(Chars)?两者在内存中的结构不同,即字符串结尾有NULL 0(字符串终止符)?在应用编程实践中,常常需要从键盘获取字符,依次存入字符数组中,再以字符串输出函数输出到屏幕等,譬如,在中文环境?图形模式下中文字符的键盘输入和屏幕显示?如混淆字符数组中字符组与字符串的差别,则可能得到奇怪的结果?如例: CharStr() { int i,CharNum=5; unsigned char str[80]; for(i=0;i 字符数组，字符指针，字符串 char a[]="hello world"; char* b="hello world"; string c="hello wolrd"; cout< 浅谈数位类统计问题 山东省青岛第二中学刘聪 【摘要】 在信息学竞赛中，有一类与数位有关的区间统计问题。这类问题往往具有比较浓厚的数学味道，无法暴力求解，需要在数位上进行递推等操作。本文通过几个例子，简要介绍了解决此类问题的基本思想和方法。 【关键字】 数位区间统计递推树二进制 【正文】 在信息学竞赛中，有这样一类问题：求给定区间中，满足给定条件的某个D进制数或此类数的数量。所求的限定条件往往与数位有关，例如数位之和、指定数码个数、数的大小顺序分组等等。题目给定的区间往往很大，无法采用朴素的方法求解。此时，我们就需要利用数位的性质，设计log(n)级别复杂度的算法。解决这类问题最基本的思想就是“逐位确定”的方法。下面就让我们通过几道例题来具体了解一下这类问题及其思考方法。 【例题1】Amount of degrees (ural 1057) 题目大意： 求给定区间[X,Y]中满足下列条件的整数个数：这个数恰好等于K个互不相等的B的整数次幂之和。例如，设X=15，Y=20，K=2，B=2，则有且仅有下列三个数满足题意： 17 = 24+20， 18 = 24+21， 20 = 24+22。 输入：第一行包含两个整数X和Y。接下来两行包含整数K和B。 输出：只包含一个整数，表示满足条件的数的个数。 数据规模：1 ≤ X ≤ Y ≤ 231?1，1 ≤ K ≤ 20，2 ≤ B ≤ 10。 分析： 所求的数为互不相等的幂之和，亦即其B进制表示的各位数字都只能是0和1。因此，我们只需讨论二进制的情况，其他进制都可以转化为二进制求解。 很显然，数据范围较大，不可能采用枚举法，算法复杂度必须是log(n)级别，因此我们要从数位上下手。 线段树的应用 广西柳铁一中林涛 【摘要】 在竞赛解题中，常遇到与区间有关的操作，比如统计若干矩形并的面积，记录一个区间的最值、总量，并在区间的插入、删除和修改中维护这些最值、总量。 线段树拥有良好的树形二分结构，能够高效的完成这些操作，本文将介绍线段树的各种操作以及一些推广。 本文通过3个例子：《蛇》、《空心长方体》、《战场统计系统》，讲述线段树中基本的插入、删除、查找操作，和不规则的修改和删除操作，以及到二维的推广。 关键字：线段树二分子树收缩叶子释放面积树 【正文】 1. 线段树的定义及特征 定义1：线段树 一棵二叉树，记为T (a,b)，参数a,b表示该节点表示区间[a,b]。区间的长度b-a记为L。递归定义T[a,b]： 若L>1 ：[a, (a+b) div 2]为T的左儿子 [(a+b) div 2,b]为T的右儿子。 若L=1 ：T为一个叶子节点。 表示区间[1, 10]的线段树表示如下： (以下取对数后均向上取整) 定理1：线段树把区间上的任意一条线段都分成不超过2log L条线段 证明：(1)在区间(a，b)中，对于线段(c，d)，如果(c<=a) 或(d>=b)，那么线段在(a，b)中被分为不超过log(b-a)。 用归纳法证明，如果是单位区间，最多被分为一段，成立。 如果区间(a，b)的左儿子与右儿子成立，那么如果当c<=a时， 1．若d<=(a+b)div2那么相当与其左儿子分该线段，所分该线段数树不超过log((a+b)div 2-a)，即不超过log(b-a),成立。 2．若d>(a+b) div 2那么相当于该线段被分为它左儿子表示的线段，加上右儿子分该线段，线段数不超过1+log(b-(a+b) div 2),也不超过 log(b-a)，成立。 对于d>=b的情况证明类似，不再赘述。 (2)在区间(a,b)中，对于任意线段也用归纳法证明。 对于单位区间，最多分为一段，成立。 若(a，b)的左儿子与右儿子均成立，则对于线段(c，d) 1．若d<=(a+b)div 2 则该区间所分该线段等于其左儿子区间所分该线段，线段数小于log((a+b) div 2-a)<2log(b-a)，成立。 2．若c>(a+b) div 2 则该区间所分该线段等于其右儿子区间所分该线段，线段数小于log(b-(a+b) div 2)<2log(b-a)，成立。 3．若1、2均不成立，则此线段在左儿子区间分该线段满足d>V.Lson.b,分该线段数不超过log(b-(a+b) div 2)，而在右儿子区间分该线段满 足c<=V.Rson.a,分该线段不超过log((a+b) div 2-1)，所以在该区间 分该线段不超过2log(b-a)，成立。 这个结论为线段树能在O(log L)的时间内完成一条线段的插入、删除、查找等工作，提供了理论依据。 【例题一】蛇1 在平面上有N个点，现在要求一些线段，使其满足以下要求： a．这些线段必须闭合 b．线段的端点只能是这N个点 c．交于一点的两条线段成90度角 d．线段都必须平行于坐标轴 e．所有线段除在这N个点外不自交 f．所有线段的长度之和必须最短 如果存在这样的线段，则输出最小长度，否则输出0。 【问题分析】 从该题的要求入手，先构出符合要求的图，再解决线段长度之和最小的问题。1．题目显然要求一个以给定的N个点为顶点的N多边形。所有线段都要和坐标轴平行，所以每个点只能与上下左右四个点相连。由于与一个点相连的两条线段成90度，每个顶点必须与一条平行于X轴和一条平行于Y轴的线段相连。 2．将所有点排序后发现，在同一水平线上的点中，设这些点为P1，P2，P3，P4……Pn，P1要有一条平行于X轴的线段与其相连，就必须连它右边的点——P2，而P3如果再连P2，P2就有两条平行于X轴的线段和它相连，所以P3只能连P4，P5只能连P6……，同一垂直线上的点也是如此，所以线段的构造是唯一的，那么最小长度的问题就解决了。 3．由于解是唯一的，而是否相连只要广度扩展就可以判断了，所以关键在于判断由上述方法所构出线段是否合法——满足线段不在N个点之外自交： 1Saratov State University Problem Archive, 1028, Snake. 本题考查了基本的插入、删除和查找 NOI 国家集训队论文分类（至2008） 摘抄自 C 博客 组合数学 计数与统计 2001- 符文杰：《Pólya 原理及其应用》 2003- 许智磊：《浅谈补集转化思想在统计问题中的应用》 2007- 周冬：《生成树的计数及其应用》 2008- 陈瑜希《Pólya 计数法的应用》 数位问题 2009- 高逸涵《数位计数问题解法研究》 2009 - 刘聪《浅谈数位类统计问题》 动态统计 2004- 薛矛：《解决动态统计问题的两把利刃》 2007- 余江伟：《如何解决动态统计问题》博弈 2002- 张一飞：《由感性认识到理性认识——透析一类搏弈游戏的解答过程》 2007- 王晓珂：《解析一类组合游戏》 2009 - 曹钦翔《从“k倍动态减法游戏”出发探究一类组合游戏问题》 2009 - 方展鹏《浅谈如何解决不平等博弈问题》 2009 - 贾志豪《组合游戏略述——浅谈SG 游戏的若干拓展及变形》母函数 2009 - 毛杰明《母函数的性质及应用》 拟阵 2007- 刘雨辰：《对拟阵的初步研究》 线性规划 2007 - 李宇骞：《浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》 置换群 2005- 潘震皓：《置换群快速幂运算研究与探讨》 问答交互 2003- 高正宇：《答案只有一个——浅谈问答式交互问题》 猜数问题 2003- 张宁：《猜数问题的研究:< 聪明的学生> 一题的推广》2006 - 龙《一类猜数问题的研究》 数据结 构 数据结 构 2005 - 何 林：《数据关系的简化》 2006 - 朱晨 光：《基本数据结构在信息学竞赛中的应用》 2007 - 何 森：《浅谈数据的合理组织》 2008 - 曹钦翔《数据结构的提炼与压缩》 结构联合 2001- 高寒蕊：《从圆桌问题谈数据结构的综合运用》 2005- 黄刚：《数据结构的联合》 块状链表 2005- 蒋炎岩：《数据结构的联合——块状链表》 2008- 苏煜《对块状链表的一点研究》动态树 2006- 陈首元：《维护森林连通性——动态树》 2007- 袁昕颢：《动态树及其应用》左偏树 2005- 黄源河：《左偏树的特点及其应用》 跳表 2005- 魏冉：《让算法的效率“跳起来”！——浅谈“跳跃表”的相关操作及其应用》 2009- 李骥扬《线段跳表——跳表的一个拓展》 SBT 2007 - 陈启峰：《Size Balance Tree 》线段树 2004- 林涛：《线段树的应用》 单调队列 2006- 汤泽：《浅析队列在一类单调性问题中的应用》哈希表2005- 李羽修：《Hash 函数的设计优化》 2007- 杨弋：《Hash 在信息学竞赛中的一类应用》 Splay 2004- 杨思雨：《伸展树的基本操作与应用》 图论 图论 2005- 任恺：《图论的基本思想及方法》字符串,字符数组,字符指针
国家集训队2009论文集浅谈数位类统计问题
国家集训队2004论文集_林涛
NOI国家集训队论文分类(至2008)(摘抄自C博客)
相关主题
文本预览