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

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

@krydom2月前

01/1
21:42
基础算法

[bzoj 4723] [POI2017]Flappy Bird

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

《飞扬的小鸟》是一款风靡的小游戏。在游戏中,小鸟一开始位于(0,0)处,它的目标是飞到横坐标为X的某个位置上。每一秒,你可以选择点击屏幕,那么小鸟会从(x,y)飞到(x+1,y+1),或者不点击,那么小鸟会飞到(x+1,y-1)。在游戏中还有n个障碍物,用三元组(x[i],a[i],b[i])描述,表示在直线x=x[i]上,y<=a[i]或者y>=b[i]的部分都是障碍物,碰到或者擦边都算游戏失败。请求出小鸟从(0,0)飞到目的地最少需要点击多少次屏幕。

Read More →

[bzoj 4723] [POI2017]Flappy Bird

@krydom2月前

01/1
21:10
主席树

[bzoj 3932] [CQOI2015]任务查询系统

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

最近实验室正在为其管理的超级计算机编制一套任务管理系统,而你被安排完成其中的查询部分。超级计算机中的任务用三元组(Si,Ei,Pi)描述,(Si,Ei,Pi)表示任务从第Si秒开始,在第Ei秒后结束(第Si秒和Ei秒任务也在运行),其优先级为Pi。同一时间可能有多个任务同时执行,它们的优先级可能相同,也可能不同。调度系统会经常向查询系统询问,第Xi秒正在运行的任务中,优先级最小的Ki个任务(即将任务按照优先级从小到大排序后取前Ki个)的优先级之和是多少。特别的,如果Ki大于第Xi秒正在运行的任务总数,则直接回答第Xi秒正在运行的任务优先级之和。上述所有参数均为整数,时间的范围在1到n之间(包含1和n)。

Read More →

[bzoj 3932] [CQOI2015]任务查询系统

@krydom2月前

12/25
17:24
乱搞

[bzoj 3444] 最后的晚餐

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

【问题背景】
高三的学长们就要离开学校,各奔东西了。某班n人在举行最后的离别晚餐时,饭店老板觉得十分纠结。因为有m名学生偷偷找他,要求和自己暗恋的同学坐在一起。
【问题描述】
饭店给这些同学提供了一个很长的桌子,除了两头的同学,每一个同学都与两个同学相邻(即坐成一排)。给出所有信息,满足所有人的要求,求安排的方案总数(这个数字可能很大,请输出方案总数取余989381的值,也可能为0)。

Read More →

[bzoj 3444] 最后的晚餐

@krydom2月前

12/25
09:13
spfa 动态规划

[bzoj 3875] [Ahoi2014]骑士游戏

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

【故事背景】
长期的宅男生活中,JYY又挖掘出了一款RPG游戏。在这个游戏中JYY会扮演一个英勇的骑士,用他手中的长剑去杀死入侵村庄的怪兽。
【问题描述】
在这个游戏中,JYY一共有两种攻击方式,一种是普通攻击,一种是法术攻击。两种攻击方式都会消耗JYY一些体力。采用普通攻击进攻怪兽并不能把怪兽彻底杀死,怪兽的尸体可以变出其他一些新的怪兽,注意一个怪兽可能经过若干次普通攻击后变回一个或更多同样的怪兽;而采用法术攻击则可以彻底将一个怪兽杀死。当然了,一般来说,相比普通攻击,法术攻击会消耗更多的体力值(但由于游戏系统bug,并不保证这一点)。
游戏世界中一共有N种不同的怪兽,分别由1到N编号,现在1号怪兽入侵村庄了,JYY想知道,最少花费多少体力值才能将所有村庄中的怪兽全部杀死呢?

Read More →

[bzoj 3875] [Ahoi2014]骑士游戏

@krydom2月前

12/24
22:51
期望动规 高斯消元

[bzoj 3143] [Hnoi2013]游走

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

一个无向连通图,顶点从1编号到N,边从1编号到M。
小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束,总分为所有获得的分数之和。
现在,请你对这M条边进行编号,使得小Z获得的总分的期望值最小。

Read More →

[bzoj 3143] [Hnoi2013]游走

@krydom2月前

12/24
21:39
期望动规 高斯消元

[bzoj 3270] 博物馆

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

有一天Petya和他的朋友Vasya在进行他们众多旅行中的一次旅行,他们决定去参观一座城堡博物馆。这座博物馆有着特别的样式。它包含由m条走廊连接的n间房间,并且满足可以从任何一间房间到任何一间别的房间。
两个人在博物馆里逛了一会儿后两人决定分头行动,去看各自感兴趣的艺术品。他们约定在下午六点到一间房间会合。然而他们忘记了一件重要的事:他们并没有选好在哪儿碰面。等时间到六点,他们开始在博物馆里到处乱跑来找到对方(他们没法给对方打电话因为电话漫游费是很贵的)
不过,尽管他们到处乱跑,但他们还没有看完足够的艺术品,因此他们每个人采取如下的行动方法:每一分钟做决定往哪里走,有Pi 的概率在这分钟内不去其他地方(即呆在房间不动),有1-Pi 的概率他会在相邻的房间中等可能的选择一间并沿着走廊过去。这里的i指的是当期所在房间的序号。在古代建造是一件花费非常大的事,因此每条走廊会连接两个不同的房间,并且任意两个房间至多被一条走廊连接。
两个男孩同时行动。由于走廊很暗,两人不可能在走廊碰面,不过他们可以从走廊的两个方向通行。(此外,两个男孩可以同时地穿过同一条走廊却不会相遇)两个男孩按照上述方法行动直到他们碰面为止。更进一步地说,当两个人在某个时刻选择前往同一间房间,那么他们就会在那个房间相遇。
两个男孩现在分别处在a,b两个房间,求两人在每间房间相遇的概率。

Read More →

[bzoj 3270] 博物馆

@krydom2月前

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

[bzoj 4282] 慎二的随机数列

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

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

Read More →

[bzoj 4282] 慎二的随机数列

@krydom2月前

12/18
10:23
可持久化trie

[bzoj 3261] 最大异或和

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

给定一个非负整数序列 {a},初始长度为 N。
有   M个操作,有以下两种操作类型:
1 、A x:添加操作,表示在序列末尾添加一个数 x,序列的长度 N+1。
2 、Q l r x:询问操作,你需要找到一个位置 p,满足 l<=p<=r,使得:
a[p] xor a[p+1] xor … xor a[N] xor x 最大,输出最大是多少。

Read More →

[bzoj 3261] 最大异或和