算法 - Page 79 - hzwer.com

「BZOJ3689」「FJ2014集训」异或之
「题目描述」给定n个非负整数A[1],A[2],……,A[n]。对于每对(i,j)满足1<=i<j<=n，得到一个新的数A[i]xorA[j]，这样共有n*(n-1)/2个新的数。求这些数（不包含A[i]）中前k小的数。注：xor对应于pascal中的“xor”，C++中的“^”。「输入格式」第一行2个正整数n,k，如题所述。以下n行，每行一个非负整数表示A[i]。「输出格式」共一行k个数，表示前k小的数。「样例输入」451134「样例输出」02255「样例解释」1xor1=0(...
02014年7月13日5,099模拟

「BZOJ3688」「FJ2014集训」折线统计
「题目描述」二维平面上有n个点(xi,yi)，现在这些点中取若干点构成一个集合S，对它们按照x坐标排序，顺次连接，将会构成一些连续上升、下降的折线，设其数量为f(S)。如下图中，1->2,2->3,3->5,5->6（数字为下图中从左到右的点编号），将折线分为了4部分，每部分连续上升、下降。现给定k，求满足f(S)=k的S集合个数。「输入格式」第一行两个整数n和k，以下n行每行两个数(xi,yi)表示第i个点的坐标。所有点的坐标值都在...
02014年7月13日4,913递推与动规,树状数组
「FJ互测」「BZOJ3704」昊昊的机油之GRST
题目描述(grst.c/cpp/pas)昊昊有个好机油，他就是传说中的着力点。现在昊昊获得了一份长度为n的GRST牌（mod4意义下），打算作为送给好机油的生日礼物（不是在2月的么）。但是，昊昊深知他的机油是个神犇，作为数字控的他，只会喜欢特定的序列。但是昊昊不怕，他可以使用一次菲亚特（他的机油最喜欢的大招），将一段区间内的数字全部+1，若某个数字为3，则+1后变为0。但昊昊的神力是有限的，问从初始序列a到达最终序列b，最少需...
02014年7月12日3,763递推与动规,贪心
「BZOJ1806」[IOI2007] Miners 矿工配餐
Description现有两个煤矿，每个煤矿都雇用一组矿工。采煤工作很辛苦，所以矿工们需要良好饮食。每当一辆食品车到达煤矿时，矿工们便会产出一定数量的煤。有三种类型的食品车：肉车，鱼车和面包车。矿工们喜欢变化的食谱。如果提供的食品能够不断变化，他们的产煤量将会增加。每当一个新的食品车到达煤矿时，矿工们就会比较这种新的食品和前两次（或者少于两次，如果前面运送食品的次数不足两次）的食品，并且：•如果这几次食品车...
02014年7月10日4,155递推与动规
「BZOJ3396」[Usaco2009 Jan] Total flow 水流
DescriptionInput第1行输入N，之后N行每行描述一条水管，前两个英文字母表示水管的两端（大小写字母是不一样的），后一个整数表示水管的流量，流量不会超过1000.Output一个整数，表示总流量．SampleInput5AB3BC3CD5DZ4BZ6SampleOutput3题解直接上网络流模板。。。似乎有小写字母[crayon-694fc9ae41bc6778454962/] ...
02014年7月10日4,258最大流
「BZOJ1754」[Usaco2005 qua] Bull Math
DescriptionBullsaresomuchbetteratmaththanthecows.Theycanmultiplyhugeintegerstogetherandgetperfectlypreciseanswers...orsotheysay.FarmerJohnwondersiftheiranswersarecorrect.Helphimcheckthebulls'answers.Readintwopositiveintegers(nomorethan40digitseach)andcomputetheirproduct.Outputitasanormalnumber(withnoextraleadingzeros).FJasksthatyoudothisyourself;don'tuseaspeciallibraryfunctionforthemulti...
02014年7月10日3,496高精度
「BZOJ1574」[Usaco2009 Jan] 地震损坏Damage
Description农夫John的农场遭受了一场地震.有一些牛棚遭到了损坏,但幸运地,所有牛棚间的路经都还能使用.FJ的农场有P(1<=P<=30,000)个牛棚,编号1..P.C(1<=C<=100,000)条双向路经联接这些牛棚,编号为1..C.路经i连接牛棚a_i和b_i(1<=a_i<=P;1<=b_i<=P).路经可能连接a_i到它自己,两个牛棚之间可能有多条路经.农庄在编号为1的牛棚.N(1<=N<=P)头在不同牛棚的牛通过手机短信report_j(2<=...
02014年7月10日3,994深度搜索
「NOIP模拟赛」合唱队形
「问题描述」学校要进行合唱比赛了，于是班主任小刘准备给大家排个队形。他首先尝试排成m1行，发现最后多出来a1个同学；接着他尝试排成m2行，发现最后多出来a2个同学，……，他尝试了n种排队方案，但每次都不能让同学们正好排成mi行。于是小刘寻求同事小明的帮助，以便给同学们排好队形。但小刘来去太匆忙，忘记告诉小明他们班有多少人了。没办法，现在只能根据上述信息求个满足要求的最小的数字来作为人数了。虽然小明年轻时是理科...
02014年7月10日4,326扩展欧几里得算法
「NOIP模拟赛」秘密文件
「问题描述」某天，情报局得到了一份秘密文件。文件的内容是加密后的全部由大写字母组成字符串。情报局局长小明想将其发送给远在东方神秘的xx大陆上的老朋友小刘来解密。然而若字符串太长，则需要很长的发送时间，太不安全了，因此小明想尽量将其缩短。于是小明制定了这样一个缩短规则：若一个字符串t连续出现k次，则可以用k(t)进行说明。如ABABAB可以缩成3(AB)。当然，重复缩短是允许的，如ABABABAAAAAAARA...
02014年7月10日4,215区间动规
「NOIP模拟赛」hash函数
「问题描述」明明觉得hash是个好算法，代码短、效率高。某天，他碰到了一个求正方形个数的问题，于是很淡定地枚举对角线，然后用hash判存在，妥妥的搞定，但是提交后却wa了几个点。仔细观察其hash函数为：h=x*y+x+y。为了让明明知道这个函数存在什么问题，对于给出一个h值，请你来告诉他有多少对(x，y)满足上述式子(max(x,y)≤h；h，x，y都为非负整数)?「输入格式」多组测试数据，第一行为测试点的个数T，接下来每一行一个整数h，...
02014年7月10日3,288筛法
「NOIP模拟赛」聪明的打字员
聪明的打字员(typer)阿兰是某机密部门的打字员，她现在接到一个任务：需要在一天之内输入几百个长度固定为6的密码。当然，她希望输入的过程中敲击键盘的总次数越少越好。不幸的是，出于保密的需要，该部门用于输入密码的键盘是特殊设计的，键盘上没有数字键，而只有以下六个键：Swap0，Swap1，Up，Down，Left，Right。为了说明这6个键的用，我们先定义录入区的6个位置的编号，从左至右依次为l，2，3，4，5，6。下面列出每个键...
32014年7月8日3,016广度搜索
「NOIP模拟赛」笨笨的电话网络
多年以后，笨笨长大了，成为了电话线布置师。由于地震使得某市的电话线全部损坏，笨笨是负责接到震中市的负责人。该市周围分布着N(1≤N≤1000)根据1…n顺序编号的废弃的电话线杆，任意两根线杆之间没有电话线连接，一共有p(0≤p≤10000)对电话杆可以拉电话线。其他的由于地震使得无法连接。第i对电线杆的两个端点分别是ai，bi，它们的距离为li(1≤li≤1000000)。数据中每对(ai，bi)只出现一次。编号为1的电话杆已经接入了全国的电...
02014年7月8日4,582spfa,二分法