链表（chain table）是我们最常使用的一种数据结构。在信息学竞赛中，经常需要使用链表作为遍历等操作使用的数据结构参与解题过程。这是因为链表具有自己的优点。用数组模拟链表，可以简化链表的使用，从而使链表更好的为我们服务。如果您已经知道链表数据结构的原理，可以跳过第一部分直接查看与数组模拟链表有关的内容。
[...]
| ||||||
有向图的强连通分量 深度优先遍历是求有向图的强连通分量的一个有效方法，具体求解步骤如下： ⑴ 在有向图中，从某个顶点出发进行深度优先遍历，并按其所有邻接点的访问都完成（即出栈）的顺序将顶点排列起来。 ⑵ 在该有向图中，从最后完成访问的顶点出发，沿着以该顶点为头的弧作逆向的深度优先遍历，若此次遍历不能访问到有向图中所有顶点，则从余下的顶点中最后完成访问的那个顶点出发，继续作逆向的深度优先遍历，依次类推，直至有向图中所有顶点都被访问到为止。 ⑶ 每一次逆向深度优先遍历所访问到的顶点集便是该有向图的一个强连通分量的顶点集，若仅作一次逆向深度优先遍历就能访问到图的所有顶点，则该有向图是强连通图。 例如对图6-3(a)所示有向图，从顶点v1出发作深度优先遍历，在访问顶点v2后，顶点v2不存在未访问的邻接点从而成为一个“死结点”，如图(b) 所示。将v2从栈顶弹出后，再从顶点v1出发，在访问顶点v3 v4后，顶点v4不存在未访问的邻接点从而也成为“死结点”，如图(c)所示。将v4从栈顶弹出后，顶点v3不存在未访问的邻接点从而也成为“死结点”， 将v3从栈顶弹出后，顶点v1不存在未访问的邻接点从而也成为“死结点”，将v1从栈顶弹出，所以，得到出栈的顶点序列为v2, v4, v3, v1；再从最后一个出栈的顶点v1出发作逆向的深度优先遍历（逆着有向边的箭头方向），得到一个顶点集{ v1, v3, v4}，如图(d)所示；再从顶点v2出发作逆向的深度优先遍历，得到一个顶点集{v2}，如图(e)所示。这就是该有向图的两个强连通分量的顶点集。 本解题报告非本人原创，程序为本人原创。转载请注明出处并保留本注释。 题目描述 Polygons 两个做游戏的人在玩一种多边形游戏。一个有n个顶点的凸多边形需要由 n－3条对角线划分成n－2个三角形。这些对角线只会相交在顶点。划分后的三角形中有一个是黑色的，其余的都是白色。两个选手轮流取，每一个选手每一次要从多边形中切下一个三角形。每个选手只允许沿着一条对角线切下一个三角形。切下黑色三角形的选手获得比赛的胜利。 注意：我们称一个多边形是凸多边形当且仅当任意两个顶点的连线都被包含在多边形的内部。 任务：编写程序， 1、从文本文件gra.in中读入关于凸多边形的描述。 2、判断是否先取的选手有一种必胜的策略。 3、将结果写入文件gra.out。 输入： 输入文件gra.in的第一行包含一个整数n，4 <= n <= 50000，表示多边形的顶点数。顶点按顺时针编号为0至n－1。 以下的n－2行描述该多变形划分成的三角形。第i＋1行（1≤i≤n－2）包含三个非负整数，表示第i个三角形的三个顶点的编号。第一个描述的三角形是黑色的。 输出： 输出文件gra.out包含一个单词： ‘TAK’(在波兰文中表示“是”)，如果先走的选手有必胜策略。 ‘NIE’(在波兰文中表示“否”)，如果先走的选手没有必胜策略。 样例输入： 6 0 1 2 2 4 3 4 2 0 0 5 4 样例输出： TAK 《Polygons》解题报告 一、分析。 为了描述方便，我们用三角形的三个顶点的编号来表示三角形，如下图中的黑色三角形为（1，3，6）。 在 下图中，要切下黑色三角形（1，3，6），就必须切下三角形集合{(0,1,6)},{(1,2,3)},{(3,5,6),(3,4,5)}中的两个。 同样，对于任何一个凸多边形，要切下黑色三角形都必须切下三个三角形集合中的两个。切下一个三角形集合所需的步数是一定的，而与切的顺序无关，所以对于任 何一个三角形集合中我们只需考虑集合中三角形的个数而不必考虑分别是哪几个三角形。 设三个三角形集合的元素个数分别为a，b，c。下面的问题就是如何从状态(a,b,c)判断是否有必胜状态。 先分析必胜状态，首先（0,0,1）一定是必胜状态。若初始状态不是（0，0，n）则状态（0,0,c），c>1，实际是不可能出现的。 证明：(1)、状态（0，0，n）不存在。 (2)、若（0，0，c）n>＝c>＝2不存在，由于（0，0，c－1）只能从（0，0，c）和（0，1，c－1）中得到。 状态（0，0，c）不存在，而从（0，1，c－1）出发可以得到比（0，0，c－1）更优的（0，1，c－2），所以不可能选择（0，0，c－1）。 因此，若状态（0，0，（0，0，c－1）也不存在。 所以（0，0，c）,c>1不存在，则（0，0，c－1）也是不存在的。 ∴ 若初始状态不是（0，0，n），则不可能出现（0，0，c），c>1。因此必胜状态只有一个（0，0，1）。 接 着，分析状态（a，b，c），a≠0,令s＝a+b+c，称s为奇数的状态为奇状态，s为偶数的状态为偶状态。由于每一步只能将a，b，c中的一个数减 [...] 本解题报告版权归 Ceeji，转载请保留出处和本注释。 问题描述 原始生物的遗传密码是一个自然数的序列K=(a1,…,an)。原始生物的特征是指在遗传密码中连续出现的数对（l,r），即存在自然数i使得l=ai且r=ai+1。在原始生物的遗传密码中不存在(p，p)形式的特征。 求解任务： 请设计一个程序： •从文件PIE.IN中读入一系列的特征。 •计算包含这些特征的最短的遗传密码。 •将结果写到文件PIE.OUT中。 输入： 在输入文件PIE.IN的第一行是一个整数n ，表示特征的总数。在接下来的n行里，每行都是一对由空格分隔的自然数l 和r ，1 <= l，r <= 1000。数对（l， r）是原始生物的特征之一。输入文件中的特征不会有重复。 输出： 输出文件PIE.OUT的唯一一行应该包含一个整数，等于包含了PIE.IN中所有特征的遗传密码的最小长度。 样例输入： 12 2 3 3 9 9 6 8 5 5 7 7 6 4 5 5 1 1 4 4 2 2 8 8 6 样例输出： 15 注： PIE.IN中的所有特征都包含在以下遗传密码中： (8, 5, 1, 4, [...] 欧拉回路 【定义】 图G的一个回路，若它恰通过G中每条边一次,则称该回路为欧拉(Euler)回路。 具有欧拉回路的图称为欧拉图（简称E图）。 【相关结论】 定理： 一个无向图是欧拉图，当且仅当该图所有顶点度数都是偶数或只有两个定点的度数为奇。 一个有向图是欧拉图，当且仅当该图所有顶点度数都是0。 求欧拉回路的一种解法 下面是无向图的欧拉回路输出代码：注意输出的前提是已经判断图确实是欧拉回路。 int num = 0;//标记输出队列 int match[MAX];//标志节点的度，无向图，不区分入度和出度 void solve(int x) { if(match[x] == 0) Record[num++] = x; else { for(int k =0;k<=500;k++) { if(Array[x][k] !=0 ) { Array[x][k]–; Array[k][x]–; match[x]–; match[k]–; solve(k); } } Record[num++] = x; } } 注意record中的点的排列是输出的到序，因此，如果要输出欧拉路径，需要将record倒过来输出。 求欧拉回路的思路： 循环的找到出发点。从某个节点开始，然后查出一个从这个出发回到这个点的环路径。这种方法保证每个边都被遍历。如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。这样，整个图就被连接到一起了。 具体步骤： 1。如果此时与该点无相连的点，那么就加入路径中 2。如果该点有相连的点，那马就列一张表，遍历这些点，知道没有相连的点。 3。处理当前的点，删除走过的这条边，并在其相邻的点上进行同样的操作，并把删除的点加入到路径中去。 [...] | ||||||
Copyright © 2012 笃志以砺，决起而飞 - All Rights Reserved. LOVE YOU FOREVER. Powered by WordPress & Atahualpa 40 queries. 0.294 seconds. |
||||||
近期评论