数据结构 - Page 13

「BZOJ3653」谈笑风生
Description设T为一棵有根树，我们做如下的定义：•设a和b为T中的两个不同节点。如果a是b的祖先，那么称“a比b不知道高明到哪里去了”。•设a和b为T中的两个不同节点。如果a与b在树上的距离不超过某个给定常数x，那么称“a与b谈笑风生”。给定一棵n个节点的有根树T，节点的编号为1到n，根节点为1号节点。你需要回答q个询问，询问给定两个整数p和k，问有多少个有序三元组(a;b;c)满足：1.a、b和c为T中三个不同的点，且a为p号节...
02014年12月8日7,090dfs序,线段树

「BZOJ2802」[POI2012] Warehouse Store
Description有一家专卖一种商品的店，考虑连续的n天。第i天上午会进货Ai件商品，中午的时候会有顾客需要购买Bi件商品，可以选择满足顾客的要求，或是无视掉他。如果要满足顾客的需求，就必须要有足够的库存。问最多能够满足多少个顾客的需求。Input第一行一个正整数n(n<=250,000)。第二行n个整数A1,A2,...An(0<=Ai<=10^9)。第三行n个整数B1,B2,...Bn(0<=Bi<=10^9)。Output第一行一个正整数k，表示最多...
02014年12月7日3,174贪心,STL
NOI2011阿狸的打字机
Description 阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有28个按键，分别印有26个小写英文字母和'B'、'P'两个字母。经阿狸研究发现，这个打字机是这样工作的：l输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。l按一下印有'B'的按键，打字机凹槽中最后一个字母会消失。l按一下印有'P'的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消...
32014年12月6日10,002dfs序,AC自动机,树状数组
「BZOJ1528」[POI2005] sam – Toy Cars
DescriptionJasio是一个三岁的小男孩,他最喜欢玩玩具了,他有n个不同的玩具,它们都被放在了很高的架子上所以Jasio拿不到它们.为了让他的房间有足够的空间,在任何时刻地板上都不会有超过k个玩具.Jasio在地板上玩玩具.Jasio'的妈妈则在房间里陪他的儿子.当Jasio想玩地板上的其他玩具时,他会自己去拿,如果他想玩的玩具在架子上,他的妈妈则会帮他去拿,当她拿玩具的时候,顺便也会将一个地板上的玩具放上架子使得地板上有足够的空间...
02014年12月6日4,445贪心,堆,STL
「BZOJ1216」[HNOI2003] 操作系统
Description写一个程序来模拟操作系统的进程调度。假设该系统只有一个CPU，每一个进程的到达时间，执行时间和运行优先级都是已知的。其中运行优先级用自然数表示，数字越大，则优先级越高。如果一个进程到达的时候CPU是空闲的，则它会一直占用CPU直到该进程结束。除非在这个过程中，有一个比它优先级高的进程要运行。在这种情况下，这个新的（优先级更高的）进程会占用CPU，而老的只有等待。如果一个进程到达时，CP...
02014年12月6日4,003STL,堆
「BZOJ3289」Mato的文件管理
DescriptionMato同学从各路神犇以各种方式（你们懂的）收集了许多资料，这些资料一共有n份，每份有一个大小和一个编号。为了防止他人偷拷，这些资料都是加密过的，只能用Mato自己写的程序才能访问。Mato每天随机选一个区间[l,r]，他今天就看编号在此区间内的这些资料。Mato有一个习惯，他总是从文件大小从小到大看资料。他先把要看的文件按编号顺序依次拷贝出来，再用他写的排序程序给文件大小排序。排序程序可以在1单位时间内...
42014年12月3日7,127树状数组,莫队算法
WC2010重建计划
DescriptionInput第一行包含一个正整数N，表示X国的城市个数.第二行包含两个正整数L和U，表示政策要求的第一期重建方案中修建道路数的上下限接下来的N-1行描述重建小组的原有方案，每行三个正整数Ai,Bi,Vi分别表示道路(Ai,Bi),其价值为Vi其中城市由1..N进行标号Output输出最大平均估值，保留三位小数SampleInput423121132143SampleOutput2.500HINT20%的数据,N<=500030%的数据,N<=100000,原有方案恰...
22014年12月3日7,525点分治,二分法,单调队列
「BZOJ1145」[CTSC2008] 图腾totem
Description在完成了古越州圆盘密码的研究之后，考古学家小布来到了南美大陆的西部。相传很久以前在这片土地上生活着两个部落，一个部落崇拜闪电，另一个部落崇拜高山，他们分别用闪电和山峰的形状作为各自部落的图腾。小布的团队在山洞里发现了一幅巨大的壁画，壁画上被标记出了N个点，经测量发现这N个点的水平位置和竖直位置是两两不同的。小布认为这幅壁画所包含的信息仅与这N个点的相对位置有关，因此不妨设坐标分别为(1,y...
12014年12月2日6,200树状数组
「BZOJ2300」[HAOI2011] 防线修建
Description近来A国和B国的矛盾激化，为了预防不测，A国准备修建一条长长的防线，当然修建防线的话，肯定要把需要保护的城市修在防线内部了。可是A国上层现在还犹豫不决，到底该把哪些城市作为保护对象呢？又由于A国的经费有限，所以希望你能帮忙完成如下的一个任务：给出你所有的A国城市坐标A国上层经过讨论，考虑到经济问题，决定取消对i城市的保护，也就是说i城市不需要在防线内了A国上层询问对于剩下要保护的城市，修...
42014年12月1日5,726凸包,离线处理
WC2013糖果公园
DescriptionInputOutputSampleInputSampleOutput841312784HINT题解30分暴力。。。模拟即可第4-5个测试点由于m较小，且在链上，所以可以用前缀和水过。。。对于每个询问统计每种糖果的答案贡献满分做法带修改树上莫队。。。参见vfk的博客http://vfleaking.blog.163.com/blog/#m=0&t=1&c=fks_084070093085082071086081080095085081085075084081080064080但是vfk的这种树分块方式。。。。。。感觉[B,3B]的话把应...
52014年11月29日9,028莫队算法,最近公共祖先
「BZOJ3757」苹果树
Description神犇家门口种了一棵苹果树。苹果树作为一棵树，当然是呈树状结构，每根树枝连接两个苹果，每个苹果都可以沿着一条由树枝构成的路径连到树根，而且这样的路径只存在一条。由于这棵苹果树是神犇种的，所以苹果都发生了变异，变成了各种各样的颜色。我们用一个到n之间的正整数来表示一种颜色。树上一共有n个苹果。每个苹果都被编了号码，号码为一个1到n之间的正整数。我们用0代表树根。只会有一个苹果直接根。有许许多多的...
02014年11月28日10,073莫队算法,最近公共祖先
「BZOJ2276」[POI2011] Temperature
DescriptionTheByteotianInstituteofMeteorology(BIM)measurestheairtemperaturedaily.Themeasurementisdoneautomatically,anditsresultimmediatelyprinted.Unfortunately,theinkintheprinterhaslongdriedout...TheemployeesofBIMhoweverrealisedthefactonlyrecently,whentheByteotianOrganisationforMeteorology(BOM)requestedaccesstothatdata.AneagerinternbythenameofByteasarsavedtheday,ashesystemati...
02014年11月27日4,211单调队列