数据结构 - Page 15

「NOIP模拟赛」滑动的窗户
「题目描述」在一个包含n个元素的数组上，有一个长度为k的窗户在从左向右滑动。窗户每滑动到一个位置，我们都可以看到k个元素在窗户中。如下的例子所示，假设数组为 [1 3 -1 -3 5 3 6 7]，而k等于3:窗户位置最小值最大值[1 3 -1] -3 5 3 6 7-131 [3 -1 -3] 5 3 6 7-331 3 [-1 -3 5] 3 6 7-351 3 -1 [-3 5 3] 6 7-351 3 -1 -3 [5 3 ...
02014年11月4日3,472单调队列

「NOIP模拟赛」弱点
「题目描述」一队勇士正在向你进攻，每名勇士都有一个战斗值ai。但是这队勇士却有一个致命弱点，如果存在i<j<k使得ai>aj>ak，则会影响他们整体的战斗力。我们将这样的一组(i,j,k)称为这队勇士的一个弱点。请求出这队勇士的弱点数目。「输入」输入文件：weakness.in输入的第一行是一个整数n，表示勇士的数目。接下来一行包括n个整数，表示每个勇士的战斗值ai。「输出」输入文件：weakness.out输出为一行，包含一个整数。...
02014年11月4日3,095树状数组
「NOIP模拟赛」字符串
「题目描述」现在给一个字符串，你要做的就是当这个字符串中存在两个挨着的字符是相同的时就将这两个字符消除。需要注意的是，当把这两个字符消除后，可能又产生一对新的挨着的字符是相同的。比如，初始的字符串是abcddc，dd是两个挨着的相同的字符，当把"dd"消除后，得到的字符串是abcc，这时cc又是两个挨着的相同的字符，所以又应该把cc消除。重复以上操作直到剩下的串中不存在两个挨着的字符是相同的为止，输出最终剩下的串。另...
02014年11月4日3,765链表
「NOIP模拟赛」数字对
「题目描述」小H是个善于思考的学生，现在她又在思考一个有关序列的问题。她的面前浮现出一个长度为n的序列{ai}，她想找出一段区间[L,R](1<=L<=R<=n)。这个特殊区间满足，存在一个k(L<=k<=R)，并且对于任意的i(L<=i<=R)，ai都能被ak整除。这样的一个特殊区间[L,R]价值为R-L。小H想知道序列中所有特殊区间的最大价值是多少，而有多少个这样的区间呢？这些区间又分别是哪些呢？你能帮助她吧。「输...
02014年11月4日4,273ST表,二分法
「NOIP模拟赛」点名
「题目描述」在J班的体育课上，同学们常常会迟到几分钟，但体育老师的点名却一直很准时。老师只关心同学的身高，他会依次询问当前最矮的身高，次矮的身高，第三矮的身高，等等。在询问的过程中，会不时地有人插进队伍里。你需要回答老师每次的询问。「输入格式」第一行两个整数nm，表示先后有n个人进队，老师询问了m次第二行n个整数，第i个数Ai表示第i个进入队伍的同学的身高为Ai第三行m个整数，第j个数Bj表示老师在第Bj个同...
02014年11月2日3,362STL
「NOIP模拟赛」密码
「问题描述」哪里有压迫，哪里就有反抗。moreD的宠物在法庭的帮助下终于反抗了。作为一只聪明的宠物，他打算把魔法使moreD的魔法书盗去，夺取moreD的魔法能力。但moreD怎么会让自己的魔法书轻易地被盗取？moreD在魔法书上设置了一个密码锁，密码锁上有一个问题。施以斯卧铺魔法吧，你有M次机会，如此将得完美密码。然后是一串小写字母串。moreD的宠物斯卧铺魔法就是施法时的字符串其中相邻两位交换。而moreD对于完美密码的...
22014年11月2日5,335贪心,二分法,线段树
「NOIP模拟赛」藏宝图
背景Czy爬上黑红树，到达了一个奇怪的地方……题目描述Czy发现了一张奇怪的藏宝图。图上有n个点，m条无向边。已经标出了图中两两之间距离dist。但是czy知道，只有当图中的各个点刚好又是一颗树的节点的时候，这张藏宝图才是真的。如果藏宝图是真的，那么经过点x的边的边权平均数最大的那个x是藏着宝物的地方。请计算这是不是真的藏宝图，如果是真的藏宝之处在哪里。格式输入数据第一行一个数T,表示T组数据。对于每组数据，第一...
02014年10月31日3,869STL,prim,广度搜索
「BZOJ3417」POI2013 Tales of seafaring
DescriptionYoungBytenssonlovestohangoutintheporttavern,whereheoftenlistenstotheseadogstellingtheirtalesofseafaring.Initially,hebelievedthemall,howeverincredibletheysounded.Overtimethough,hebecamesuspicious.Hehasdecidedtowriteaprogramthatwillverifyiftheremaybeanygrainoftruthinthosetallstories.Bytenssonreasonedthatwhilehecannottellifthesailorsindeedweatheredallthosestorms,hecanatleastfindouti...
232014年10月29日4,682广度搜索,离线处理
「BZOJ1665」[Usaco2006 Open] The Climbing Wall 攀岩
DescriptionOneofthemostpopularattractionsatthecountyfairistheclimbingwall.Bessiewantstoplanhertripupthewallinadvanceandneedsyourhelp.Thewallis30,000millimeterswideandH(1001<=H<=30,000)millimetershighandhasF(1<=F<=10,000)hoof-holdsatuniqueX,Ycoordinatesexpressedinmillimeters.0,0isatthegroundlevelontheleftsideofthewall.Hoof-holdsareseparatedbyatleast300millimeterssincenocowcan...
02014年10月29日3,932STL,dijkstra
「NOIP模拟赛」花园的守护之神
题目描述看着正在被上古神兽们摧残的花园，花园的守护之神――小Bug同学泪流满面。然而，FZOI不相信眼泪，小bug与神兽们的战争将进行到底！通过google，小Bug得知，神兽们来自遥远的戈壁。为了扭转战局，小Bug决定拖延神兽增援的速度。从戈壁到达花园的路径错综复杂，由若干段双向的小路组成。神兽们通过每段小路都需要一段时间。小Bug可以通过向其中的一些小路投掷小xie来拖延神兽。她可以向任意小路投掷小Xie，而且可以...
32014年10月28日4,403最小割,STL,dijkstra
「BZOJ2709」[Violet 1] 迷宫花园
DescriptionInputOutputSampleInput22.545######S##E######211312#############S###E#####################################################################SampleOutput0.500000.21053HINTSource题解。。。。二分+最短路判定即可不知道为何读入会出现奇怪的问题让我re了一版。。。。一直检查数组。。。[crayon-674438656c0fd552988921/] ...
02014年10月27日3,971STL,dijkstra,二分法
「BZOJ2143」飞飞侠
Description飞飞国是一个传说中的国度，国家的居民叫做飞飞侠。飞飞国是一个N×M的矩形方阵，每个格子代表一个街区。然而飞飞国是没有交通工具的。飞飞侠完全靠地面的弹射装置来移动。每个街区都装有弹射装置。使用弹射装置是需要支付一定费用的。而且每个弹射装置都有自己的弹射能力。我们设第i行第j列的弹射装置有Aij的费用和Bij的弹射能力。并规定有相邻边的格子间距离是1。那么，任何飞飞侠都只需要在(i,j)支付Aij的费用...
22014年10月23日6,468STL,dijkstra