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

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

@krydom4月前

04/6
09:11
prufer序列 快速幂

[bzoj 4766] 文艺计算姬

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

"奋战三星期,造台计算机"。小W响应号召,花了三星期造了台文艺计算姬。文艺计算姬比普通计算机有更多的艺术细胞。普通计算机能计算一个带标号完全图的生成树个数,而文艺计算姬能计算一个带标号完全二分图的生成树个数。更具体地,给定一个一边点数为n,另一边点数为m,共有n*m条边的带标号完全二分图K_{n,m},计算姬能快速算出其生成树个数。小W不知道计算姬算的对不对,你能帮助他吗?

Read More →

[bzoj 4766] 文艺计算姬

@krydom4月前

04/6
08:58
倍增 矩阵乘法

[bzoj 4773] 负环

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

在忘记考虑负环之后,黎瑟的算法又出错了。对于边带权的有向图 G = (V, E),请找出一个点数最小的环,使得环上的边权和为负数。保证图中不包含重边和自环。

Read More →

[bzoj 4773] 负环

@krydom4月前

04/5
20:53
STL 莫队算法

[bzoj 4810] [Ynoi2017]由乃的玉米田

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

由乃在自己的农田边散步,她突然发现田里的一排玉米非常的不美。这排玉米一共有N株,它们的高度参差不齐。
由乃认为玉米田不美,所以她决定出个数据结构题
这个题是这样的:
给你一个序列a,长度为n,有m次操作,每次询问一个区间是否可以选出两个数它们的差为x,或者询问一个区间是否可以选出两个数它们的和为x,或者询问一个区间是否可以选出两个数它们的乘积为x ,这三个操作分别为操作1,2,3选出的这两个数可以是同一个位置的数

Read More →

[bzoj 4810] [Ynoi2017]由乃的玉米田

@krydom4月前

04/5
18:56
搜索

[bzoj 4809] 皇后

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

众所不知,rly现在不会玩国际象棋。但是,作为一个OIer,rly当然做过八皇后问题。这里再啰嗦几句,皇后可以攻击到同行同列同对角线,在n*n的方格中摆n个皇后使其互不攻击到,求不同的解的数量,这就是经典的n皇后问题。现在问题推广到n皇后问题,这个问题对于你而言实在是小菜一叠。但因为上一次rly把棋盘弄破了,又拿不出新的,所以rly打算难一点点,问题就是破棋盘上的n皇后问题。他想知道……(你们懂的)。
棋子都是相同的。

Read More →

[bzoj 4809] 皇后

@krydom4月前

04/5
15:37
二分图匹配 网络流

[bzoj 4808] 马

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

众所周知,马后炮是中国象棋中很厉害的一招必杀技。"马走日字"。本来,如果在要去的方向有别的棋子挡住(俗称"蹩马腿"),则不允许走过去。为了简化问题,我们不考虑这一点。马跟马显然不能在一起打起来,于是rly在一天再次借来了许多许多的马在棋盘上摆了起来……但这次,他实在没兴趣算方案数了,所以他只想知道在N×M的矩形方格中摆马使其互不吃到的情况下的最多个数。但是,有一个很不幸的消息,rly由于玩得太Happy,质量本来就不好的棋盘被rly弄坏了,不过幸好只是破了其中的一些格子(即不能再放子了),问题还是可以继续解决的。

Read More →

[bzoj 4808] 马

@krydom4月前

04/5
15:16
组合数/lucas 高精度

[bzoj 4807] 車

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

众所周知,車是中国象棋中最厉害的一子之一,它能吃到同一行或同一列中的其他棋子。車跟車显然不能在一起打起来,于是rly一天又借来了许多许多的車在棋盘上摆了起来……他想知道,在N×M的矩形方格中摆最多个数的車使其互不吃到的情况下方案数有几种。但是,由于上次摆炮摆得实在太累,他为了偷懒,打算增加一个条件:对于任何一个車A,如果有其他一个車B在它的上面(車B行号小于車A),那么車A必须在車B的右边(車A列号大于車B)。
棋子都是相同的。

Read More →

[bzoj 4807] 車

@krydom5月前

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

[bzoj 4806] 炮

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

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

Read More →

[bzoj 4806] 炮

@krydom5月前

04/5
14:41
树形动规

[bzoj 4726] [POI2017]Sabota?

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

某个公司有n个人, 上下级关系构成了一个有根树。其中有个人是叛徒(这个人不知道是谁)。对于一个人, 如果他下属(直接或者间接, 不包括他自己)中叛徒占的比例超过x,那么这个人也会变成叛徒,并且他的所有下属都会变成叛徒。你要求出一个最小的x,使得最坏情况下,叛徒的个数不会超过k。

Read More →

[bzoj 4726] [POI2017]Sabota?