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

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

@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:49
杂题

[bzoj 4874] 筐子放球

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

小N最近在研究NP完全问题,小O看小N研究得热火朝天,便给他出了一道这样的题目:
有 n 个球,用整数 1 到 n 编号。还有 m 个筐子,用整数1到m编号。
每个球只能放进特定的两个筐子之一,第 i 个球可以放进的筐子记为 Ai 和 Bi 。
每个球都必须放进一个筐子中。
如果一个筐子内有奇数个球,那么我们称这样的筐子为半空的。
求半空的筐子最少有多少个。
小N看到题目后瞬间没了思路,站在旁边看热闹的小I嘿嘿一笑:"水题!"
然后三言两语道出了一个多项式算法。
小N瞬间就惊呆了,三秒钟后他回过神来一拍桌子:
"不对!这个问题显然是NP完全问题,你算法肯定有错!"
小I浅笑:"所以,等我领图灵奖吧!"
小O只会出题不会做题,所以找到了你--请你对这个问题进行探究,并写一个程序解决此题。

Read More →

[bzoj 4874] 筐子放球

@krydom1月前

05/17
20:46
杂题

[bzoj 4895] 项链分赃(增强版)

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

你和你的1个同伙偷了一串长度为n的项链,它上面有m种颜色的珠子,我们假设项链为链状的,并且每一颗珠子都是随机分布,现在我想知道,对于给定的n,m你在最坏情况下最少需要切多少刀 才能使得你们可以通过每人获得一些切完之后的项链,并且满足每个人得到的每种宝石的数量刚好相同,我们假设珠子的数目一定是偶数。也就是说对于每种情况都一定存在一种解决方案。然而这才是这个问题的真正形式。

Read More →

[bzoj 4895] 项链分赃(增强版)

@krydom1月前

05/17
20:42
kruskal

[bzoj 4883] [Lydsy2017年5月月赛]棋盘上的守卫

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

在一个n*m的棋盘上要放置若干个守卫。对于n行来说,每行必须恰好放置一个横向守卫;同理对于m列来说,每列必须恰好放置一个纵向守卫。每个位置放置守卫的代价是不一样的,且每个位置最多只能放置一个守卫,一个守卫不能同时兼顾行列的防御。请计算控制整个棋盘的最小代价。

Read More →

[bzoj 4883] [Lydsy2017年5月月赛]棋盘上的守卫

@krydom1月前

05/17
20:39
二分图 并查集

[bzoj 4881] [Lydsy2017年5月月赛]线段游戏

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

quailty和tangjz正在玩一个关于线段的游戏。在平面上有n条线段,编号依次为1到n。其中第i条线段的两端点坐标分别为(0,i)和(1,p_i),其中p_1,p_2,...,p_n构成了1到n的一个排列。quailty先手,他可以选择一些互不相交的线段,将它们拿走,当然他也可以一条线段也不选。然后tangjz必须拿走所有剩下的线段,若有两条线段相交,那么他就输了,否则他就赢了。注意若quailty拿走了全部线段,那么tangjz也会胜利。quailty深深喜欢着tangjz,所以他不希望tangjz输掉游戏,请计算他有多少种选择线段的方式,使得tangjz可以赢得游戏。

Read More →

[bzoj 4881] [Lydsy2017年5月月赛]线段游戏

@krydom1月前

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

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

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

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

Read More →

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