[Topcoder SRM 467]均匀字符串Next…

题目: http://cogs.pro/cogs/problem/problem.php?pid=1906 我们称一个字符串是“均匀的”,如果它每个长度为n的连续子串都包含不超过d个不同的字符。对于一个字符串seed和一个长整型整数k,定义k大均匀字符串为:所有和seed长度相同且字典序大于等于seed的均匀字符串中,按字典序从小到大,从0开始数的第k个。这里所说的字符串只包含小写字母。给出n,d,seed,k,你需要计算并输出k大均匀字符串。如果合法的字符串少于k+1个,输出空字符串。1... 查看更多

WC2015总结&解题报告(伪)

这次三道题:k小割,混淆与破解,未来程序。 先看“k小割”:啥啥啥这都是啥…… 然后看“混淆与破解”:范浩强居然真敢把讲课内容出出来……但是问题①GL算法的后半部分完全没听懂②即使听懂了算法显然也做不出来,不过没准前40分(m=1)的可做 “未来程序”:去年是给程序和输出凑输入,今年直接给程序(源代码都给了)和输入求输出? 不管了第一题10分暴力走你┏ (゜ω゜)=☞,方法是2^m枚举边集然后O(n+m)判断是否是割集 然后玩提答。 program1:这难道是传说中的快速乘?然后愉快地码了一个出来,用计算器验算正确 program2:让它算了几个小数据,发现是……Fibonac... 查看更多

几道pb_ds模板题

冬令营上有人讲了这个,看上去很省事的样子,所以来学习一个 1:COGS 2.旅行计划 题目地址: http://cogs.pro/cogs/problem/problem.php?pid=2 求起点到所有点的最短路,可以用pb_ds中的priority_queue优化Dijkstra 代码: http://cogs.pro/cogs/submit/code.php?id=149462 tips: ①声明格式必须是__gnu_pbds::priority_queue,因为STL里还有另一个priority_queue ②pb_ds包含的这些堆的迭代器是point_iterator而非ite... 查看更多

[国家集训队2012]电子对撞机 解题…

国家集训队2012 电子对撞机(刘洪轩)解题报告 题目: 见http://cogs.pro/cogs/problem/problem.php?pid=1784 Q国最近科学技术不断进步,经过不懈努力,Q国主席QQ终于在质子对撞机的基础上研发了新一代能量供给装置:电子对撞机。 这个设备呈长条状且对外封闭,设备内部有N个带有一定能量的电子。长条状的外形使得这些电子只能沿条形走向左右运动。设备长度为L,左端位置为0,右端位置为L。内部的电子速率恒定,每一个单位时间在左右方向上移动一个单位长度,而方向可能是向左或向右。当两个电子相遇即运动到同一个点时,它们之间会发生对撞,对撞后它们的速率不变... 查看更多

[国家集训队2011]stone解题报告

题目: http://cogs.pro/cogs/problem/problem.php?pid=1847 话说Nan在海边等人,预计还要等上M分钟。为了打发时间,他玩起了石子。 Nan搬来了N堆石子,编号为1到N,每堆包含Ai颗石子。 每1分钟,Nan会在编号在之间的石堆中挑出任意Ki颗扔向大海(好疼的玩法),如果剩下石子不够Ki颗,则取尽量地多。 为了保留扔石子的新鲜感,Nan保证任意两个区间和 ,不会存在Li... 查看更多

[国家集训队2011]拆迁队 解题报告

题目: http://cogs.pro/cogs/problem/problem.php?pid=1859 lanxisi带领着他的拆迁队来整治一个街道。这个街道由N个旧房子组成,从左到右编号为1..N。每个旧房子i有一个正整数的美观度Ai。 lanxisi希望整个街道从左到右美观度严格递增,也就是保证Aij(i 现在,请你求出lanxisi最多能保留多少旧房子和整治这个街道所需要的最少总花费(当然是在保留旧房子最多这个前提下的)。 分析: 首先这种题一看要么贪心要么DP,对吧……贪心估计不靠谱,所以往DP上想。 因为需要尽可能保留旧房子,所以先考虑一个问题:假设我们保留的房子中,有两... 查看更多

[国家集训队2011]种树 解题报告

题目: http://cogs.pro/cogs/problem/problem.php?pid=1862 A城市有一个巨大的圆形广场,为了绿化环境和净化空气,市政府决定沿圆形广场外圈种一圈树。园林部门得到指令后,初步规划出n个种树的位置,顺时针编号1到n。并且每个位置都有一个美观度Ai,如果在这里种树就可以得到这Ai的美观度。但由于A城市土壤肥力欠佳,两棵树决不能种在相邻的位置(i号位置和i+1号位置叫相邻位置。值得注意的是1号和n号也算相邻位置!)。 最终市政府给园林部门提供了m棵树苗并要求全部种上,请你帮忙设计种树方案使得美观度总和最大。如果无法将m棵树苗全部种上,给出无解信息。 ... 查看更多

[国家集训队2011]happiness(吴确)…

题目: http://cogs.pro/cogs/problem/problem.php?pid=1873 高一一班的座位表是个n*m的矩阵,经过一个学期的相处,每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了,每个同学对于选择文科与理科有着自己的喜悦值,而一对好朋友如果能同时选文科或者理科,那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板,想知道如何分配可以使得全班的喜悦值总和最大。 分析: 首先不用想,这肯定是个最小割……不妨将其解题过程记录下来,以作为一个典型的最小割模型题。 “最小割”求的是一个“最小”的值,而本题需要最大化喜悦值之和,所以很显然... 查看更多

[国家集训队2011]公交路线 解题报…

题目: http://cogs.pro/cogs/problem/problem.php?pid=1877 Z市交通不发达,所有公交路线覆盖的边竟然一个环也不包含,甚至该市的公交路线有可能会分为几个互不连通的块,这可真是不可思议。有一天,你突然听到一条消息,说你的M个同学被困在了Z市里,他们分别要从他们当前所在的点ai移动到他们想去的点bi.于是你立刻调集资料,了解了Z市的形状和公交路线的分布,现在你要算出每个人到达目的地最少要换多少次车,或者告知那个人不能仅用公交车达到目的地。 分析: 先考虑一个询问。假设我们想要从A走到B,像这样: 很显然,如果没有越过LCA,就可以尽量一直走。就像... 查看更多