算法 - Page 94 - hzwer.com

「NOIP模拟赛」虫洞
「题目描述」N个虫洞，M条单向跃迁路径。从一个虫洞沿跃迁路径到另一个虫洞需要消耗一定量的燃料和1单位时间。虫洞有白洞和黑洞之分。设一条跃迁路径两端的虫洞质量差为delta。从白洞跃迁到黑洞，消耗的燃料值减少delta，若该条路径消耗的燃料值变为负数的话，取为0。从黑洞跃迁到白洞，消耗的燃料值增加delta。路径两端均为黑洞或白洞，消耗的燃料值不变化。作为压轴题，自然不会是如此简单的最短路问题，所以每过1单位时间黑洞...
02014年5月10日5,751spfa

「BZOJ1458」士兵占领
Description有一个M*N的棋盘，有的格子是障碍。现在你要选择一些格子来放置一些士兵，一个格子里最多可以放置一个士兵，障碍格里不能放置士兵。我们称这些士兵占领了整个棋盘当满足第i行至少放置了Li个士兵,第j列至少放置了Cj个士兵。现在你的任务是要求使用最少个数的士兵来占领整个棋盘。Input第一行两个数M,N,K分别表示棋盘的行数，列数以及士兵的个数。第二行有M个数表示Li。第三行有N个数表示Ci。接下来有K行，...
02014年5月10日4,953最大流
「BZOJ1009」[HNOI2008] GT考试
Description阿申准备报名参加GT考试，准考证号为N位数X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。他的不吉利数学A1A2...Am(0<=Ai<=9)有M位，不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am.A1和X1可以为0Input第一行输入N,M,K.接下来一行输入M位的数。100%数据N<=10^9,M<=20,K<=100040%数据N<=100010%数据N<=6Output阿申想知道不出现不吉利数字的号...
62014年5月9日15,825递推与动规,KMP,矩阵乘法
「BZOJ1854」[SCOI2010] 游戏
Descriptionlxhgww最近迷上了一款游戏，在游戏里，他拥有很多的装备，每种装备都有2个属性，这些属性的值用[1,10000]之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。游戏进行到最后，lxhgww遇到了终极boss，这个终极boss很奇怪，攻击他的装备所使用的属性值必须从1开始连续递增地攻击，才能对boss产生伤害。也就是说一开始的时候，lxhgww只能使用某个属性值为1的装备攻击boss，...
82014年5月8日9,701并查集
「BZOJ1800」[Ahoi2009] fly 飞行棋
Description给出圆周上的若干个点，已知点与点之间的弧长，其值均为正整数，并依圆周顺序排列。请找出这些点中有没有可以围成矩形的，并希望在最短时间内找出所有不重复矩形。Input第一行为正整数N，表示点的个数，接下来N行分别为这N个点所分割的各个圆弧长度Output所构成不重复矩形的个数SampleInput812231133SampleOutput3HINTN<=20题解20的数据范围直接使其变成水题[crayon-687f20f1b5af7529127963/] ...
02014年5月8日3,629模拟
「BZOJ3280」小R的烦恼
Description小R最近遇上了大麻烦，他的程序设计挂科了。于是他只好找程设老师求情。善良的程设老师答应不挂他，但是要求小R帮助他一起解决一个难题。问题是这样的，程设老师最近要进行一项邪恶的实验来证明P=NP，这个实验一共持续n天，第i天需要a[i]个研究生来给他搬砖。研究生毕竟也是人，所以雇佣研究生是需要钱的，机智的程设老师已经联系好了m所大学，第j所大学共有l[j]个研究生，同时雇佣这所大学的一个研究生需要p[j]元...
02014年5月8日4,359费用流
「BZOJ3293」[CQOI2011] 分金币
Description圆桌上坐着n个人，每人有一定数量的金币，金币总数能被n整除。每个人可以给他左右相邻的人一些金币，最终使得每个人的金币数目相等。你的任务是求出被转手的金币数量的最小值。Input第一行为整数n（n>=3），以下n行每行一个正整数，按逆时针顺序给出每个人拥有的金币数。Output输出被转手金币数量的最小值。SampleInput41254SampleOutput4样例解释设四个人编号为1,2,3,4。第3个人给第2个人2个金币（变成1,4,3...
02014年5月8日4,158其它
「BZOJ2697」特技飞行
Description神犇航空开展了一项载客特技飞行业务。每次飞行长N个单位时间，每个单位时间可以进行一项特技动作，可选的动作有K种，每种动作有一个刺激程度Ci。如果连续进行相同的动作，乘客会感到厌倦，所以定义某次动作的价值为(距上次该动作的时间)*Ci，若为第一次进行该动作，价值为0。安排一种方案，使得总价值最大。Input　　第一行，两个数，N和K，如上所述；第二行，K个正整数，表示K种动作的Ci值。Output　　仅...
02014年5月8日4,086贪心
「BZOJ1787」[Ahoi2008] Meet 紧急集合
DescriptionInputOutputSampleInput641223244556456631244666SampleOutput52254160HINT题解忘记换行搞半天我擦咧求三个结点到一个结点距离之和最小的结点以及距离和求出两两lca，其中有两个相同，答案则为另一个，画画图就可以理解[crayon-687f20f1b691a790279860/]或者将三个lca分别计算取最优[crayon-687f20f1b6927756417707/] ...
22014年5月7日5,710最近公共祖先
「POJ2356」Find a multiple
DescriptionTheinputcontainsNnatural(i.e.positiveinteger)numbers(N<=10000).Eachofthatnumbersisnotgreaterthan15000.Thisnumbersarenotnecessarilydifferent(soitmayhappenthattwoormoreofthemwillbeequal).Yourtaskistochooseafewofgivennumbers(1<=few<=N)sothatthesumofchosennumbersismultipleforN(i.e.N*k=(sumofchosennumbers)forsomenaturalnumberk).InputThefirstlineoftheinputcontainsthesingl...
12014年5月7日3,164其它
「BZOJ1150」[CTSC2007] 数据备份Backup
Description Input输入的第一行包含整数n和k，其中n（2≤n≤100000）表示办公楼的数目，k（1≤k≤n/2）表示可利用的网络电缆的数目。接下来的n行每行仅包含一个整数（0≤s≤1000000000）,表示每个办公楼到大街起点处的距离。这些整数将按照从小到大的顺序依次出现。Output输出应由一个正整数组成，给出将2K个相异的办公楼连成k对所需的网络电缆的最小总长度。SampleInput52134612SampleOutput4HINT上面的样例输入给出...
02014年5月7日8,017贪心,堆,链表
「BZOJ2288」「POJ Challenge」生日礼物
Descriptionftiasch18岁生日的时候，lqp18_31给她看了一个神奇的序列 A1, A2,..., AN.她被允许选择不超过 M 个连续的部分作为自己的生日礼物。自然地，ftiasch想要知道选择元素之和的最大值。你能帮助她吗？Input第1行，两个整数 N (1≤ N ≤105)和 M (0≤ M ≤105),序列的长度和可以选择的部分。第2行， N 个整数 A1, A2,..., AN (0≤|Ai|≤104),序列。Output一个整数，最大的和。SampleI...
12014年5月7日8,067贪心,堆,链表