基础数据结构 - Page 10

「POJ2828」Buy Tickets
DescriptionRailwayticketsweredifficulttobuyaroundtheLunarNewYearinChina,sowemustgetupearlyandjoinalongqueue…TheLunarNewYearwasapproaching,butunluckilytheLittleCatstillhadschedulesgoinghereandthere.Now,hehadtotravelbytraintoMianyang,SichuanProvinceforthewintercampselectionofthenationalteamofOlympiadinInformatics.Itwasoneo’clocka.m.anddarkoutside.Chillwindfromthenorthwestdidnot...
02014年3月1日4,316线段树,离线处理

「BZOJ1054」[HAOI2008] 移动玩具
Description在一个4*4的方框内摆放了若干个相同的玩具，某人想将这些玩具重新摆放成为他心中理想的状态，规定移动时只能将玩具向上下左右四个方向移动，并且移动的位置不能有玩具，请你用最少的移动次数将初始的玩具状态移动到某人心中的目标状态。Input前4行表示玩具的初始状态，每行4个数字1或0，1表示方格中放置了玩具，0表示没有放置玩具。接着是一个空行。接下来4行表示玩具的目标状态，每行4个数字1或0，意义同上。Output...
02014年2月27日5,292广度搜索,哈希表
「BZOJ1862 / 1056」GameZ游戏排名系统
DescriptionGameZ为他们最新推出的游戏开通了一个网站。世界各地的玩家都可以将自己的游戏得分上传到网站上。这样就可以看到自己在世界上的排名。得分越高，排名就越靠前。当两个玩家的名次相同时，先上传记录者优先。由于新游戏的火爆，网站服务器已经难堪重负。为此GameZ雇用了你来帮他们重新开发一套新的核心。排名系统通常要应付三种请求：上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。当...
02014年2月25日5,978treap,哈希表
「BZOJ1015」[JSOI2008] 星球大战starwar
Description很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始不可靠起来。现在，反...
32014年2月23日8,025并查集,离线处理
「CF295B」Greg and Graph
Greghasaweigheddirectedgraph,consistingof n vertices.Inthisgraphanypairofdistinctverticeshasanedgebetweentheminbothdirections.Greglovesplayingwiththegraphandnowhehasinventedanewgame:Thegameconsistsof n steps.Onthe i-thstepGregremovesvertexnumber xi fromthegraph.AsGregremovesavertex,healsoremovesalltheedgesthatgoinandoutofthisvertex.Beforeexecutingeachstep,Gregwantstoknowthesumofle...
02014年2月14日4,333floyd,离线处理
「CODEVS1553」互斥的数
题目描述 Description有这样的一个集合，集合中的元素个数由给定的N决定，集合的元素为N个不同的正整数，一旦集合中的两个数x,y满足y = P*x，那么就认为x,y这两个数是互斥的，现在想知道给定的一个集合的最大子集满足两两之间不互斥。输入描述 InputDescription输入有多组数据，每组第一行给定两个数N和P（1<=N<=10^5, 1<=P<=10^9）。接下来一行包含N个不同正整数ai（1<=ai<=10^9）。输出描述 ...
02014年2月13日4,080哈希表
「CODEVS1229」数字游戏
题目描述DescriptionLele 最近上课的时候都很无聊，所以他发明了一个数字游戏来打发时间。这个游戏是这样的，首先，他拿出几张纸片，分别写上0到9之间的任意数字(可重复写某个数字)，然后，他叫同学随便写两个数字X和K。Lele要做的事情就是重新拼这些纸牌，组成数字 T ，并且 T + X 是 K 的正整数倍。有时候，当纸片很多的时候，Lele经常不能在一节课之内拼出来，但是他又想知道答案，所以，他想请你帮忙写...
22014年2月13日3,730深度搜索,哈希表
「usaco2002.4」Power Hungry Cows
题目描述农夫约翰的奶牛可以很快地计算整数的次方，但是需要你的帮助。因为他们将要计算很大的数的次方（还是数的很大次方……我英语，悲剧），他们只能使用两个工作变量来处存临时结果。第一个动作变量被赋值为底数（用X表示）；另一个赋值为1.牛们既能把两个变量相乘也能相除，并存储在任一工作变量中，但是所有结果都被存为整数（只能存为整数？我按这个做的AC）。例如，他们想计算X^31，一种方法是这样的[crayon-676ef88d0...
02014年2月5日3,481哈希表,广度搜索
「SWUST0433」高精度整数去位去最小问题
Description键盘输入一个高精度的正整数N，去掉其中任意M个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和M寻找一种方案使得剩下的数字组成的新数最小。输出组成的新的正整数。(不超过240位)输入数据均不需判错。如果去掉了某几个位后得到的新整数开头为0，保留0。Input本题有多组测试数据，每组测试数据占一行。一个高精度正整数N（N不超过240位）一个正整数M。(M为不大于N的长度的正整数)N,M由...
02014年1月21日3,552链表
「BZOJ3039」玉蟾宫
Description有一天，小猫rainbow和freda来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。这片土地被分成N*M个格子，每个格子里写着'R'或者'F'，R代表这块土地被赐予了rainbow，F代表这块土地被赐予了freda。现在freda要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着'F'并且面积最大。但是rainbow和freda的OI水平都弱爆了，找不出这块土地，而蓝兔也想看freda卖萌（她显...
02014年1月6日5,115单调栈
「CODEVS3185 – 3187」队列练习1, 2, 3
队列练习1http://codevs.com/problem/3185/[crayon-676ef88d1075f386508912/]队列练习2http://codevs.com/problem/3186/[crayon-676ef88d1076c778310291/]队列练习3http://codevs.com/problem/3187/[crayon-676ef88d10774271375497/] ...
82013年12月26日2,498基础数据结构
「vijos1026」毒药？解药？
描述羽毛笔和im是抽签到同一个考场的，她们突然闻到一阵刺鼻的化学试剂的气味。机灵鼠：（头都不抬）你们是考生么？还在门口磨蹭什么？快进来帮我忙！！……怎么还不进来？你们拖赛，拖赛，把你们的青春都拖掉赛……im：开…开策了>_<羽毛笔：哎呀~~机灵鼠大人要我们帮什么忙？^^机灵鼠：你们看这里的这些药，都是我研制的对付各种症状的解药。可是我一个不小心，每种药都小小地配错了一点原料，所以这些药都有可能在治愈某些...
02013年12月20日4,712哈希表,广度搜索