链表（chain table）是我们最常使用的一种数据结构。在信息学竞赛中，经常需要使用链表作为遍历等操作使用的数据结构参与解题过程。这是因为链表具有自己的优点。用数组模拟链表，可以简化链表的使用，从而使链表更好的为我们服务。如果您已经知道链表数据结构的原理，可以跳过第一部分直接查看与数组模拟链表有关的内容。
[...]
| ||||||
有点晚了，但是，USACO很能考验基础数据结构和算法的熟练度。 题目描述 对于一群要互送礼物的朋友，你要确定每个人收到的礼物比送出的多多少(and vice versa for those who view gift giving with cynicism)(,反之亦然对于那些用贪婪的眼光来看礼物的人(by John))。 在这一个问题中，每个人都准备了一些钱来送礼物，而这些钱将会被平均分给那些将收到他的礼物的人。 然而，在任何一群朋友中，有些人将送出较多的礼物(可能是因为有较多的朋友)，有些人有准备了较多的钱。 给出一群朋友， 没有人的名字会长于 14 字符，给出每个人将花在送礼上的钱，和将收到他的礼物的人的列表，请确定每个人收到的比送出的钱多的数目。 格式 PROGRAM NAME: gift1 INPUT FORMAT: (file gift1.in) 第 1 行: 人数NP,2<= NP<=10 第 2到 NP+1 行:这NP个在组里人的名字 一个名字一行 第NP＋2到最后： 这里的NP段内容是这样组织的： 第一行是将会送出礼物人的名字。 第二行包含二个数字: 第一个是原有的钱的数目（在0到2000的范围里），第二个 NGi 是将收到这个送礼者礼物的人的个数 如果 NGi 是非零的, 在下面 NGi 行列出礼物的接受者的名字，一个名字一行。 OUTPUT FORMAT: (file gift1.out) 输出 NP [...] 之所以两道题放在一起，就是因为他们很相似。 本解题报告版权归 Ceeji 所有，转载请注名出处并保留本注释。 题目一：Count 大项堆是具有如下性质的二叉树： 1.它的任意一个父亲节点的权值总是比孩子的权值要大 2.它是一颗完全二叉树 先给定这个堆的节点个数N，假如每个节点的权值都为在1—N之间的整数且各不相同，求可能的大项堆的个数。当然，这个个数可能很多，这里只要求这个个数模K即可。 输入： 两个用空格隔开的整数N和Q（N<30,Q<10^9） 输出： 可能的大项堆的个数模Q 输入样例： 3 1000 输出样例： 2 题目二：树的同构 本解题报告版权归 Ceeji 所有，转载请注名出处并保留本注释。 排序二叉树是我们熟悉的一种数据结构，这里提到的排序二叉树都是指根的关键字比左 子树上的所有点都大，比右子树上的都小（假定不存在相同的关键字）的排序二叉树。如果 给定一个输入序列，按照这个序列依次将各个结点插入，我们就得到了一棵排序二叉树。比 如输入序列 4 2 1 3 5，对应如下排序二叉树： 2 4 5 1 3 而输入序列4 5 2 1 3 以及4 2 5 1 3都对应同样的树，我们说这三个序列同构。现在给定 一个长度为N的输入序列，求与之同构的序列有多少个（包括这个序列本身）。由于问题的 答案可能比较大，只要求输出答案 mod 10,007的结果。 Input 第1行：一个正整数N，即输入序列长度。 第2行：N个1—N之间的正整数，数字相互之间不重复。 Output 仅有一行，即同构序列数 [...] 首先声明这个文章不是我原创，功劳归 Matrix67（First Published By Matrix67）但合并，整理 + 改编后效果更好，也删除和添加了一些东西，献给所有需要的人。首先还是从最基础的东西说起。 什么是位运算？ 程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了，就是直接对整数在内存中的二进制位进行操作。比如，and运算本来是一个逻辑运算 符，但整数与整数之间也可以进行and运算。举个例子，6的二进制是110，11的二进制是1011，那么6 and 11的结果就是2，它是二进制对应位进行逻辑运算的结果（0表示False，1表示True，空位都当0处理）： 110 AND 1011 ———- 0010 –> 2 由于位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。当然有人会说，这个快了有什么用，计算6 and 11没有什么实际意义啊。这一系列的文章就将告诉你，位运算到底可以干什么，有些什么经典应用，以及如何用位运算优化你的程序。 Pascal和C中的位运算符号 下面的a和b都是整数类型，则： C语言 | Pascal语言 ——-+————- a & b | a and b a | b | a or b a ^ b | a xor b ~a | not a a << b | a shl b a >> b | a shr b [...] | ||||||
Copyright © 2012 笃志以砺，决起而飞 - All Rights Reserved. LOVE YOU FOREVER. Powered by WordPress & Atahualpa 40 queries. 0.317 seconds. |
||||||
近期评论