Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1月前

05/19
21:29
一般动规与递推

[bzoj 4897] [Thu Summer Camp2016]成绩单

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

期末考试结束了,班主任L老师要将成绩单分发到每位同学手中。L老师共有n份成绩单,按照编号从1到n的顺序叠放在桌子上,其中编号为i的成绩单分数为w_i。成绩单是按照批次发放的。发放成绩单时,L老师会从当前的一叠成绩单中抽取连续的一段,让这些同学来领取自己的成绩单。当这批同学领取完毕后,L老师再从剩余的成绩单中抽取连续的一段,供下一批同学领取。经过若干批次的领取后,成绩单将被全部发放到同学手中。然而,分发成绩单是一件令人头痛的事情,一方面要照顾同学们的心理情绪,不能让分数相差太远的同学在同一批领取成绩单;另一方面要考虑时间成本,尽量减少领取成绩单的批次数。对于一个分发成绩单的方案,我们定义其代价为:
其中,k是方案中分发成绩单的批次数,对于第i批分发的成绩单,〖max〗_i是最高分数,〖min〗_i是最低分数。a,b是给定的评估参数。现在,请你帮助L老师找到代价最小的分发成绩单的方案,并将这个最小的代价告诉L老师。当然,分发成绩单的批次数k是由你决定的。

Read More →

[bzoj 4897] [Thu Summer Camp2016]成绩单

@krydom1月前

05/17
20:58
一般动规与递推 容斥原理 数学其他 组合数/lucas

[bzoj 4767] 两双手

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

老W是个棋艺高超的棋手,他最喜欢的棋子是马,更具体地,他更加喜欢马所行走的方式。老W下棋时觉得无聊,便决定加强马所行走的方式,更具体地,他有两双手,其中一双手能让马从(u,v)移动到(u+Ax,v+Ay)而另一双手能让马从(u,v)移动到(u+Bx,v+By)。小W看见老W的下棋方式,觉得非常有趣,他开始思考一个问题:假设棋盘是个无限大的二维平面,一开始马在原点(0,0)上,若用老W的两种方式进行移动,他有多少种不同的移动方法到达点(Ex,Ey)呢?两种移动方法不同当且仅当移动步数不同或某一步所到达的点不同。老W听了这个问题,觉得还不够有趣,他在平面上又设立了n个禁止点,表示马不能走到这些点上,现在他们想知道,这种情况下马有多少种不同的移动方法呢?答案数可能很大,你只要告诉他们答案模(10^9+7)的值就行。

Read More →

[bzoj 4767] 两双手

@krydom1月前

05/17
20:54
一般动规与递推 中国剩余定理 容斥原理 组合数/lucas

[bzoj 3782] 上学路线

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 小C所在的城市的道路构成了一个方形网格,它的西南角为(0,0),东北角为(N,M)。小C家住在西南角,学校在东北角。现在有T个路口进行施工,小C不能通过这些路口。小C喜欢走最短的路径到达目的地,因此他每天上学时都只会向东或北行走;而小C又喜欢走不同的路径,因此他问你按照他走最短路径的规则,他可以选择的不同的上学路线有多少条。由于答案可能很大,所以小C只需要让你求出路径数mod P的值。

Read More →

[bzoj 3782] 上学路线

@krydom1月前

05/17
20:35
一般动规与递推

[bzoj 4884] [Lydsy2017年5月月赛]太空猫

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

太空猫(SpaceCat)是一款画面精致、玩法有趣的休闲游戏,你需要控制一只坐在迷你飞碟上的猫咪在太空里不断探索,让大家看看你能飞得多远。游戏地图可以看成一个二维的网格图,上下是两段障碍物。在游戏的一开始,太空猫位于地图最左边的下边界之上,且重力方向向下。
在每个时刻,你可以用手指点击屏幕,翻转重力的方向,或者通过遥感控制太空猫往左或往右移动。每次翻转重力方向时,你需要消耗的能量值等于上下底边之间的高度差。在左右移动的时候,太空猫可以下降到对应重力方向更低的位置,但不能往上爬。当然,太空猫也不能穿墙而过。在重力翻转的过程中,直到碰到地面之前,你都不能操控太空猫左右移动。太空猫的终点位于地图的最右端的下底边之上,请计算为了让太空猫到达终点,需要消耗能量的最小值。

Read More →

[bzoj 4884] [Lydsy2017年5月月赛]太空猫

@krydom3月前

04/5
14:50
一般动规与递推

[bzoj 4806] 炮

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

众所周知,双炮叠叠将是中国象棋中很厉害的一招必杀技。炮吃子时必须隔一个棋子跳吃,即俗称"炮打隔子"。
炮跟炮显然不能在一起打起来,于是rly一天借来了许多许多的炮在棋盘上摆了起来……他想知道,在N×M的矩形方格中摆若干炮(可以不摆)使其互不吃到的情况下方案数有几种。棋子都是相同的。

Read More →

[bzoj 4806] 炮

@krydom6月前

12/24
12:42
一般动规与递推

[bzoj 4282] 慎二的随机数列

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

间桐慎二是间桐家著名的废柴,有一天,他在学校随机了一组随机数列, 准备使用他那强大的人工智能求出其最长上升子序列,但是天有不测风云,人有旦夕祸福,柳洞一成路过时把间桐慎二的水杯打翻了……
现在给你一个长度为 n 的整数序列,其中有一些数已经模糊不清了,现在请你任意确定这些整数的值,使得最长上升子序列最长(为何最长呢?因为间桐慎二向来对自己的人品很有信心)。

Read More →

[bzoj 4282] 慎二的随机数列

@krydom7月前

12/7
18:24
一般动规与递推

[bzoj 3892] [Usaco2014 Dec]Marathon

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

Unhappy with the poor health of his cows, Farmer John enrolls them in an assortment of different physical fitness activities. His prize cow Bessie is enrolled in a running class, where she is eventually expected to run a marathon through the downtown area of the city near Farmer John's farm! The marathon course consists of N checkpoints (3 <= N <= 500) to be visited in sequence, where checkpoint 1 is the starting location and checkpoint N is the finish. Bessie is supposed to visit all of these checkpoints one by one, but being the lazy cow she is, she decides that she will skip up to K checkpoints (K < N) in order to shorten her total journey. She cannot skip checkpoints 1 or N, however, since that would be too noticeable. Please help Bessie find the minimum distance that she has to run if she can skip up to K checkpoints. Since the course is set in a downtown area with a grid of streets, the distance between two checkpoints at locations (x1, y1) and (x2, y2) is given by |x1-x2| + |y1-y2|.

在二维平面上有N个点,从(x1,y1)到(x2,y2)的代价为|x1-x2|+|y1-y2|。
求从1号点出发,按从1到N的顺序依次到达每个点的最小总代价。
你有K次机会可以跳过某个点,不允许跳过1号点或N号点。

Read More →

[bzoj 3892] [Usaco2014 Dec]Marathon

@krydom7月前

12/6
20:45
一般动规与递推 树状数组

[bzoj 1264] [AHOI2006]基因匹配Match

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

卡卡昨天晚上做梦梦见他和可可来到了另外一个星球,这个星球上生物的DNA序列由无数种碱基排列而成(地球上只有4种),而更奇怪的是,组成DNA序列的每一种碱基在该序列中正好出现5次!这样如果一个DNA序列有N种不同的碱基构成,那么它的长度一定是5N。 卡卡醒来后向可可叙述了这个奇怪的梦,而可可这些日子正在研究生物信息学中的基因匹配问题,于是他决定为这个奇怪星球上的生物写一个简单的DNA匹配程序。 为了描述基因匹配的原理,我们需要先定义子序列的概念:若从一个DNA序列(字符串)s中任意抽取一些碱基(字符),将它们仍按在s中的顺序排列成一个新串u,则称u是s的一个子序列。对于两个DNA序列s1和s2,如果存在一个序列u同时成为s1和s2的子序列,则称u是s1和s2的公共子序列。 卡卡已知两个DNA序列s1和s2,求s1和s2的最大匹配就是指s1和s2最长公共子序列的长度。 [任务] 编写一个程序:  从输入文件中读入两个等长的DNA序列;  计算它们的最大匹配;  向输出文件打印你得到的结果。

Read More →

[bzoj 1264] [AHOI2006]基因匹配Match