数据结构 - Page 3

「NOI考前欢乐赛」[BZOJ3648] 小奇泛舟
「题目背景」微露点滴沾衿落袖丽日绰约轻解莲舟蒹葭荣茂燕雀啁啾白石溪畔斜阳逐流——《白石溪》「问题描述」小奇喜欢在斜阳下的白石溪上泛舟。白石溪风光奇美，名花异石甚多，小奇在地图上标记了n处景观（标号从1到n），有些景观通过溪流连接，这样的溪流有m段。小奇想知道，有多少种泛舟的路径，经过的景观数大于等于K呢？（小奇不喜欢一次泛舟重复经过一个景观）「输入格式」第一行包括3个整数，n，m，K。接下来m行，每行2个整...
72016年6月26日6,772点分治,树状数组

「NOI考前欢乐赛」小奇遐想
「题目背景」撷来一缕清风飘渺方知今日书信未到窗外三月天霁垂柳新长枝条风中鸟啼犹带欢笑——《清风醉梦》「问题描述」小奇望着青天中的悠悠白云，开始了无限的遐想，在它的视野中，恰好有n朵高度不同的白云排成一排，他想从左到右选出四朵白云a，b，c，d，使得h_a<h_b<h_d<h_c，即看起来像是彩虹的形状！它想知道有多少种方案数。「输入格式」第一行包括1个整数n。第二行包括n个整数，第i个正数表示h_i，保证这n个整数是...
02016年6月26日4,842树状数组
「STL练习」丑数
题目描述丑数是指不能被2，3，5以外的其他素数整除的数。把丑数从小到大排列起来，结果如下：1,2,3,4,5,6,8,9,10,12,15,......请编写一个程序，求第k个丑数。输入一个整数k(k<=1500)。输出仅有一个整数为第k大丑数。样例输入[crayon-67a332c8ae9f3452346535/]样例输出[crayon-67a332c8ae9fa552346083/]题解STL练习，每次从数据结构中取出最小值x，加入2x，3x，5xpriority_queue[crayon-67a332c8ae9fe612505482/]priority_que...
12016年6月15日4,327STL
「BZOJ1208」[HNOI2004] 宠物收养所
Description最近，阿Q开了一间宠物收养所。收养所提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。每个领养者都希望领养到自己满意的宠物，阿Q根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值a（a是一个正整数，a<2^31），而他也给每个处在收养所的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了，宠物收养所总是会有两种情况发生：被遗弃的宠物过多或者...
82016年6月14日19,373STL,splay
「二叉搜索树 / set / 朝鲜树 / 替罪羊树」快速排序
本文上接http://hzwer.com/8009.htmlhttps://www.contesthunter.org/contest/%E5%B9%B3%E8%A1%A1%E6%A0%91%E8%AE%B2%E8%A7%A3/%E6%8E%92%E5%BA%8F这题当然可以直接调用sort[crayon-67a332c8afaca329224363/]用set实现排序[crayon-67a332c8afad5469630513/]用二叉搜索树来排序，不能通过已经排序好的大数据点[crayon-67a332c8afad9570278211/]可以打乱输入的数据实现深度期望[crayon-67a332c8afade910660853/]...
32016年6月13日5,822替罪羊树
二叉搜索树 / set入门
仅列出纲要二叉树结点，叶结点，分支结点，结点的度左右孩子树的深度，大小二叉树类型满二叉树完全二叉树平衡二叉树二叉搜索树性质1.前驱后继2.如何查找？构建1.对已经排序的数快速构建二叉搜索树2.如何顺序插入？效率讨论STL-set顾名思义的操作什么是Iterator？如何遍历set？用法示例[crayon-67a332c8b0512677307108/] 替罪羊树阅读http://pan.baidu.com/share/link?shareid=318543&a...
02016年6月12日5,083STL,树
「CODEVS2875」RY哥查字典
题目描述DescriptionRY哥最近新买了一本字典,他十分高兴,因为这上面的单词都十分的和谐,他天天查字典。输入描述InputDescription1个整数N,表示字典里面的单词数量。接下来N行,每行一个字符串,表示一个单词。然后第N+2行,一个整数M,表示要查的单词数。接下来M行,每行一个字符串,表示一个要查的单词。输出描述OutputDescription对于每一个要查的单词,如果在字典里面,就输出'Yes',否则输出'No',一行一个。样例输入Sa...
02016年6月12日3,440哈希表
「CODEVS1004」四子连棋
题目描述 Description在一个4*4的棋盘上摆放了14颗棋子，其中有7颗白色棋子，7颗黑色棋子，有两个空白地带，任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格，这叫行棋一步，黑白双方交替走棋，任意一方可以先走，如果某个时刻使得任意一种颜色的棋子形成四个一线（包括斜线），这样的状态为目标棋局。●○●○●○●●○●○○●○ 输入描述 InputDescription[crayon-67a332c8cc20c923465237/]输出描述 Ou...
02016年6月12日8,784广度搜索,哈希表
「CODEVS1230」元素查找
题目描述Description给出n个正整数，然后有m个询问，每个询问一个整数，询问该整数是否在n个正整数中出现过。输入描述InputDescription第一行两个整数n和m。第二行n个正整数（1<=n<=100000）第三行m个整数(1<=m<=100000)输出描述OutputDescription一共m行，若出现则输出YES，否则输出NO样例输入SampleInput42213419样例输出SampleOutputYESNO数据范围及提示DataSize&Hint所有数据都不超过10...
12016年6月11日5,439STL,哈希表
「小奇模拟赛2」小奇的危机
「题目背景」小奇驾驶飞船来到了一个奇怪的星球，这个星球的所以城市都在地下，而且由于环境不断恶化，星球上发生了可怕的生化危机。「问题描述」星球上有n个城市，标号为1-n，用n-1条双向通道连接，保证任意两个城市能互相到达。生化危机爆发了！但由于政府安全能力有限，安全区只包括在标号l到r的城市，小奇现在在城市x，它想知道最近的安全城市的距离。「输入格式」第一行有1个整数n。接下来n-1行，每行3个整数u，v，l，表示u，...
02016年5月22日6,259STL,dijkstra,分块
「小奇模拟赛2」[BZOJ3784] 小奇的树
「题目背景」小奇在研究树时，遇到了一个难题。「问题描述」给定一棵n个节点的树，求前m条最长路径的长度。「输入格式」第1行2个整数n，m。接下来n-1行，每行3个整数u，v，l，表示u，v之间有一条长度为l的边。「输出格式」m行如题，从大到小输出。「样例输入」42121132143「样例输出」54「数据范围」序号nm数据类型1103暴力223323333暴力32000300000暴力42000300000暴力5500001随机生成6779817798随机生成7779827798随机生成877983...
22016年5月22日8,005ST表,STL,点分治
「小奇模拟赛」小奇的自动机
「题目背景」小奇在研究后缀自动机时遇到了一个难题。「问题描述」定义：如果字符串A是字符串B的后缀，那么称B是A的XQ串。小奇有n个只包含小写字母的字符串，编号为1-n，表示为Si。接下来对于每个串Si，小奇想知道：对于小奇拥有的n个字符串，所有是Si的XQ串的编号集合(包括i）中第Ki小的编号。「输入格式」第1行1个整数n。接下来n行，第i+1行包括1个字符串Si。再接下来n行，第n+1+i行的整数表示Ki。「输出格式」输出...
02016年5月21日5,098字典树,线段树