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

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

@krydom9月前

12/6
19:29
dfs

[bzoj 3990] [SDOI2015]排序

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

小A有一个1-2^N的排列A[1..2^N],他希望将A数组从小到大排序,小A可以执行的操作有N种,每种操作最多可以执行一次,对于所有的i(1<=i<=N),第i中操作为将序列从左到右划分为2^{N-i+1}段,每段恰好包括2^{i-1}个数,然后整体交换其中两段.小A想知道可以将数组A从小到大排序的不同的操作序列有多少个,小A认为两个操作序列不同,当且仅当操作个数不同,或者至少一个操作不同(种类不同或者操作位置不同).

  下面是一个操作事例:
  N=3,A[1..8]=[3,6,1,2,7,8,5,4].
  第一次操作,执行第3种操作,交换A[1..4]和A[5..8],交换后的A[1..8]为[7,8,5,4,3,6,1,2].
  第二次操作,执行第1种操作,交换A[3]和A[5],交换后的A[1..8]为[7,8,3,4,5,6,1,2].
  第三次操作,执行第2中操作,交换A[1..2]和A[7..8],交换后的A[1..8]为[1,2,3,4,5,6,7,8].

Read More →

[bzoj 3990] [SDOI2015]排序

@krydom10月前

10/15
13:56
dfs

[bzoj 3391] [Usaco2004 Dec]Tree Cutting网络破坏

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

 约翰意识到贝茜建设网络花费了他巨额的经费,就把她解雇了.贝茜很愤怒,打算狠狠报复.她打算破坏刚建成的约翰的网络.    约翰的网络是树形的,连接着N(1≤N≤10000)个牛棚.她打算切断某一个牛棚的电源,使和这个牛棚相连的所有电缆全部中断.之后,就会存在若干子网络.为保证破坏够大,每一个子网的牛棚数不得超过总牛棚数的一半,那哪些牛棚值得破坏呢?

Read More →

[bzoj 3391] [Usaco2004 Dec]Tree Cutting网络破坏

@krydom10月前

10/11
15:38
dfs 最大团

[bzoj 3632] 外太空旅行

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

在人类的触角伸向银河系的边缘之际,普通人上太空旅行已经变得稀松平常了。某理科试验班有n个人,现在班主任要从中选出尽量多的人去参加一次太空旅行活动。
可是n名同学并不是和平相处的。有的人,比如小A和小B整天狼狈为奸,是好朋友;但还有的人,比如杜鲁门和赫鲁晓夫就水火不相容。这n名同学,由于是理科生,都非常的理性,所以“朋友的朋友就是朋友”和“敌人的朋友就是敌人”这两句话对这些同学无效。换句话说,有可能小A和小B是朋友,小B和小C是朋友,但是小A和小C两人势如水火。
任意两个人之间要不就是敌人,要不就是朋友。
因为在太空船上发生人员斗殴事件是很恶劣也很危险的,因此选出来参加旅行活动的同学必须互相之间都是朋友。你的任务就是确定最多可以选多少人参加旅行。

Read More →

[bzoj 3632] 外太空旅行

@krydom11月前

09/11
12:33
dfs 暴力

[bzoj 4401] 块的计数

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

 小Y最近从同学那里听说了一个十分牛B的高级数据结构——块状树。听说这种数据结构能在sqrt(N)的时间内维护树上的各种信息,十分的高效。当然,无聊的小Y对这种事情毫无兴趣,只是对把树分块这个操作感到十分好奇。他想,假如能把一棵树分成几块,使得每个块中的点数都相同该有多优美啊!小Y很想知道,能有几种分割方法使得一棵树变得优美。小Y每次会画出一棵树,但由于手速太快,有时候小Y画出来的树会异常地庞大,令小Y感到十分的苦恼。但是小Y实在是太想知道答案了,于是他找到了你,一个天才的程序员,来帮助他完成这件事。

Read More →

[bzoj 4401] 块的计数

@krydom1年前

06/9
08:29
bfs dfs

[bzoj 2435] [Noi2011]道路修建

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

 在 W 星球上有 n 个国家。为了各自国家的经济发展,他们决定在各个国家
之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬,他们只愿
意修建恰好 n – 1条双向道路。 每条道路的修建都要付出一定的费用, 这个费用等于道路长度乘以道路两端的国家个数之差的绝对值。例如,在下图中,虚线所示道路两端分别有 2 个、4个国家,如果该道路长度为 1,则费用为1×|2 – 4|=2。图中圆圈里的数字表示国家的编号。1(2)
由于国家的数量十分庞大,道路的建造方案有很多种,同时每种方案的修建
费用难以用人工计算,国王们决定找人设计一个软件,对于给定的建造方案,计
算出所需要的费用。请你帮助国王们设计一个这样的软件。
[萌漫乡]东方project 470

Read More →

[bzoj 2435] [Noi2011]道路修建

@krydom1年前

05/29
08:25
dfs

[bzoj 4500] 矩阵

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

有一个n*m的矩阵,初始每个格子的权值都为0,可以对矩阵执行两种操作:
1. 选择一行, 该行每个格子的权值加1或减1。
2. 选择一列, 该列每个格子的权值加1或减1。
现在有K个限制,每个限制为一个三元组(x,y,c),代表格子(x,y)权值等于c。问是否存在一个操作序列,使得操作完后的矩阵满足所有的限制。如果存在输出”Yes”,否则输出”No”。

Read More →

[bzoj 4500] 矩阵

@krydom1年前

03/8
19:30
dfs

[bzoj 1016] JSOI2008 最小生成树计数

00:00/00:00

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

 现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树,而希望知道这个图中有多少个不同的最小生成树。(如果两颗最小生成树中至少有一条边不同,则这两个最小生成树就是不同的)。由于不同的最小生成树可能很多,所以你只需要输出方案数对31011的模就可以了。

Read More →

[bzoj 1016] JSOI2008 最小生成树计数

@krydom2年前

01/4
19:14
dfs

[bzoj 1053] HAOI2007 反素数ant

00:00/00:00

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

 对于任何正整数x,其约数的个数记作g(x)。例如g(1)=1、g(6)=4。
如果某个正整数x满足:g(x)>g(i) 0<i<x,则称x为反质数。例如,整数1,2,4,6等都是反质数。
现在给定一个数N,你能求出不超过N的最大的反质数么?

Read More →

[bzoj 1053] HAOI2007 反素数ant

@krydom2年前

12/27
13:31
dfs

[bzoj 4325] NOIP2015 斗地主

00:00/00:00

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

 牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的A到K加上大小王的共54张牌来进行的扑克牌游戏。在斗地主中,牌的大小关系根据牌的数码表示如下:3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王,而花色并不对牌的大小产生影响。每一局游戏中,一副手牌由n张牌组成。游戏者每次可以根据规定的牌型进行出牌,首先打光自己的手牌一方取得游戏的胜利。现在,牛牛只想知道,对于自己的若干组手牌,分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。需要注意的是,本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。具体规则如下:

Read More →

[bzoj 4325] NOIP2015 斗地主