基础数据结构 - Page 2

「省选模拟赛」小奇的糖果
原题：EAST!模拟赛RoundXV呓语「题目背景」小奇不小心让糖果散落到了地上，它对着满地的彩色糖果胡思乱想。「问题描述」有N个彩色糖果在平面上。小奇想在平面上取一条水平的线段,并拾起它上方或下方的所有糖果。求出最多能够拾起多少糖果,使得获得的糖果并不包含所有的颜色。「输入格式」包含多组测试数据,第一行输入一个正整数T表示测试数据组数。接下来T组测试数据,对于每组测试数据,第一行输入两个正整数N、K,分别表...
02015年11月22日4,537链表,树状数组

「BZOJ3535」[Usaco2014 Open] Fair Photography
DescriptionFJ'sNcows(1<=N<=100,000)arestandingatvariouspositionsalongalongone-dimensionalfence.Theithcowisstandingatpositionx_i(anintegerintherange0...1,000,000,000)andhasbreedb_i(anintegerintherange1..8).Notwocowsoccupythesameposition.FJwantstotakeaphotoofacontiguousintervalofcowsforthecountyfair,butwewantsallofhisbreedstobefairlyrepresentedinthephoto.Therefore,hewantstoensurethat...
12015年7月12日5,884哈希表
「BZOJ3483 / 4212」SGU505 Prefixes and suffixes(询问在线版)
DescriptionGAL发现了N个特殊的字母序列，由小写字母组成。小L认为，对于两个字符串s1,s2，若s1是某个特殊序列的前缀，s2是该特殊序列的后缀，则称s1,s2被这个序列拥有。现在小L给出M对s1,s2，对于每对字符串，问它们被几个特殊序列拥有。Input第1行一个整数N。接下来N行，每行一个字符串，代表N个特殊序列。第N+2行一个整数M。接下来M行每行一对s1,s2用空格隔开。S1,s2是经过加密的。设上一问的答案为lastans。解...
32015年7月7日4,469STL,哈希表
「BZOJ2118」墨墨的等式
Description墨墨突然对等式很感兴趣，他正在研究a1x1+a2y2+…+anxn=B存在非负整数解的条件，他要求你编写一个程序，给定N、{an}、以及B的取值范围，求出有多少B可以使等式存在非负整数解。Input输入的第一行包含3个正整数，分别表示N、BMin、BMax分别表示数列的长度、B的下界、B的上界。输入的第二行包含N个整数，即数列{an}的值。Output输出一个整数，表示有多少b可以使等式存在非负整数解。SampleInput251035S...
02015年7月5日7,637STL,堆,dijkstra
NOI2005瑰丽华尔兹
Description你跳过华尔兹吗？当音乐响起，当你随着旋律滑动舞步，是不是有一种漫步仙境的惬意？众所周知，跳华尔兹时，最重要的是有好的音乐。但是很少有几个人知道，世界上最伟大的钢琴家一生都漂泊在大海上，他的名字叫丹尼•布德曼•T.D.•柠檬•1900，朋友们都叫他1900。1900在20世纪的第一年出生在往返于欧美的邮轮弗吉尼亚号上，很不幸他刚出生就被抛弃了，成了孤儿。1900孤独的成长在弗吉尼亚号上，从未离开过这个摇晃的...
02015年6月29日8,044递推与动规,单调队列
「CF332X」Codeforces Round #193 (Div. 2)
A.DowntheHatch!阅读+模拟题[crayon-69e6a20be2e18874193271/]B.MaximumAbsurdity每K个的和求出来以后，就是找距离超过K的两个数相加的最大值[crayon-69e6a20be2e25141495806/]C.Students'Revengehttp://m.blog.csdn.net/blog/u010638776/10044315[crayon-69e6a20be2e2f215761047/]D.TheftofBlueprintswmd神犇：http://blog.csdn.net/wmdcstdio/article/details/44755115[crayon-69e6a20be2e38460168239/]E.Binary...
02015年6月25日3,782模拟,递推与动规,贪心,堆,记忆化搜索
「CF551X」Codeforces Round #307 (Div. 2)
A.GukiZandContest排序[crayon-69e6a20be4096210494761/]B.ZgukistringZ统计每个串每个字母的使用次数，枚举串b出现次数，计算c最大出现次数，更新答案我不知道为什么写太挫还能T[crayon-69e6a20be40a4892584853/]C.GukiZhatesBoxes感受一下可以发现，比较远的箱子堆去的人越少越好所以二分答案后，从后往前贪心check即可[crayon-69e6a20be40b0024694787/]D.GukiZandBinaryOperations按位考虑，给定K以后，每一位...
12015年6月17日6,049模拟,贪心,分块,二分法,快速幂,矩阵乘法
POJ训练记录3
1379.RunAway模拟退火裸题[crayon-69e6a20be5956551863325/]2758.CheckingtheText暴力+哈希[crayon-69e6a20be5965704132227/]poj3156.Interconnect由于状态是满足拓扑序的，所以直接dp上，再用个hash记忆化[crayon-69e6a20be5970562869680/]1837.Balancef(i,j)前i个力矩为j的方案,dp[crayon-69e6a20be597f707479812/]3609.ResetSequence状压+bfs初始集合是0-n-1每个指令会使得集合中的一些元素消失，目标状态是只有一个0[c...
02015年5月19日5,356递推与动规,哈希表,广度搜索,状压动规,几何,记忆化搜索,概率与期望
PKUSC 2013 #1
poj2245.Lotto裸搜索[crayon-69e6a20c36453805623163/]poj2601.Simplecalculations推公式麻烦。。直接二分[crayon-69e6a20c36462612930437/]poj1635.Subwaytreesystems树的同构，哈希[crayon-69e6a20c3646b018443388/]poj2419.Forests暴力即可[crayon-69e6a20c36475790130794/]poj1717.Dominoesdp水题[crayon-69e6a20c36480747657538/]poj2949.WordRings建图+分数规划[crayon-69e6a20c3648b218874043/] ...
02015年5月14日4,684递推与动规,spfa,深度搜索,并查集,二分法,哈希表
「BZOJ3207」花神的嘲讽计划Ⅰ
Description背景花神是神，一大癖好就是嘲讽大J，举例如下： “哎你傻不傻的！「hqz：大笨J」” “这道题又被J屎过了！！” “J这程序怎么跑这么快！J要逆袭了！” ……描述这一天DJ在给吾等众蒟蒻讲题，花神在一边做题无聊，就跑到了一边跟吾等众蒟蒻一起听。以下是部分摘录： 1.“J你在讲什么！” “我在讲XXX！” “哎你傻不傻的！这么麻烦，直接XXX再XXX就好了！” “……” 2. “J你XXX讲...
22015年4月22日7,228可持久化线段树,哈希表
「BZOJ3238」[Ahoi2013] 差异
DescriptionInput一行，一个字符串SOutput一行，一个整数，表示所求值SampleInputcacaoSampleOutput54HINT2<=N<=500000,S由小写英文字母组成题解显然后缀数组不是正确姿势。。。不过还是说说后缀数组的做法吧，bzoj总时限20s是能过的SA+rmq求lcp应该烂大街了，这题还不用rmq。。。首先求出h数组考虑h[i]在哪些区间内会成为最小值，这个用两次单调栈很容易就能解决还要处理一下由于h[i]可能相同造成的重复计数...
62015年4月9日6,649后缀数组,单调栈
「ch57」凯撒密码
[Description]Gemini最近喜欢上了历史，他了解到历史上有一种神奇的加密方法叫做凯撒密码。凯撒密码非常的简单，就是把每个字母向后移动m位（z的后一位是a）。例如，当m=1，abcd加密后就是bcde，当m=5，xyz加密后会变成cde。Gemini对学会一种加密方法表示非常兴奋，于是，他构造了大量长度为5的纯英文小写密文（为什么是5？我也不知道）。然后……，然后他把哪个明文对应哪个密文搞混了。（-_-|||）幸运的是，经过分析，还是可以...
02015年4月9日4,864哈希表