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

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

@krydom6天前

09/24
16:44
最小割

[bzoj 3894] 文理分科

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

文理分科是一件很纠结的事情!(虽然看到这个题目的人肯定都没有纠结过)
 小P所在的班级要进行文理分科。他的班级可以用一个n*m的矩阵进行描述,每个格子代表一个同学的座位。每位同学必须从文科和理科中选择一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式得到:
1.如果第i行第秒J的同学选择了文科,则他将获得art[i][j]的满意值,如果选择理科,将得到science[i][j]的满意值。
2.如果第i行第J列的同学选择了文科,并且他相邻(两个格子相邻当且仅当它们拥有一条相同的边)的同学全部选择了文科,则他会更开心,所以会增加same_art[i][j]的满意值。
3.如果第i行第j列的同学选择了理科,并且他相邻的同学全部选择了理科,则增加same_science[i]j[]的满意值。
小P想知道,大家应该如何选择,才能使所有人的满意值之和最大。请告诉他这个最大值。

Read More →

[bzoj 3894] 文理分科

@krydom7天前

09/24
10:15
分块 莫队算法

[bzoj 3809] Gty的二逼妹子序列

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

Autumn和Bakser又在研究Gty的妹子序列了!但他们遇到了一个难题。
对于一段妹子们,他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数。
为了方便,我们规定妹子们的美丽度全都在[1,n]中。
给定一个长度为n(1<=n<=100000)的正整数序列s(1<=si<=n),对于m(1<=m<=1000000)次询问“l,r,a,b”,每次输出sl…sr中,权值∈[a,b]的权值的种类数。

Read More →

[bzoj 3809] Gty的二逼妹子序列

@krydom7天前

09/24
09:33
dijkstra 最大流

[bzoj 3931] [CQOI2015]网络吞吐量

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

 路由是指通过计算机网络把信息从源地址传输到目的地址的活动,也是计算机网络设计中的重点和难点。网络中实现路由转发的硬件设备称为路由器。为了使数据包最快的到达目的地,路由器需要选择最优的路径转发数据包。例如在常用的路由算法OSPF(开放式最短路径优先)中,路由器会使用经典的Dijkstra算法计算最短路径,然后尽量沿最短路径转发数据包。现在,若已知一个计算机网络中各路由器间的连接情况,以及各个路由器的最大吞吐量(即每秒能转发的数据包数量),假设所有数据包一定沿最短路径转发,试计算从路由器1到路由器n的网络的最大吞吐量。计算中忽略转发及传输的时间开销,不考虑链路的带宽限制,即认为数据包可以瞬间通过网络。路由器1到路由器n作为起点和终点,自身的吞吐量不用考虑,网络上也不存在将1和n直接相连的链路。

Read More →

[bzoj 3931] [CQOI2015]网络吞吐量

@krydom3周前

09/11
14:33
树链剖分 线段树

[bzoj 4448] [Scoi2015]情报传递

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

奈特公司是一个巨大的情报公司,它有着庞大的情报网络。情报网络中共有n名情报员。每名情报员口J-能有若T名(可能没有)下线,除1名大头日外其余n-1名情报员有且仅有1名上线。奈特公司纪律森严,每名情报员只能与自己的上、下线联系,同时,情报网络中仟意两名情报员一定能够通过情报网络传递情报。
奈特公司每天会派发以下两种任务中的一个任务:
1.搜集情报:指派T号情报员搜集情报
2.传递情报:将一条情报从X号情报员传递给Y号情报员
情报员最初处于潜伏阶段,他们是相对安全的,我们认为此时所有情报员的危险值为0;-旦某个情报员开始搜集情报,他的危险值就会持续增加,每天增加1点危险值(开始搜集情报的当天危险值仍为0,第2天危险值为1,第3天危险值为2,以此类推)。传递情报并不会使情报员的危险值增加。为了保证传递情报的过程相对安全,每条情报都有一个风险控制值C。余特公司认为,参与传递这条情报的所有情报员中,危险值大于C的情报员将对该条情报构成威胁。现在,奈特公司希望知道,对于每个传递情报任务,参与传递的情报员有多少个,其中对该条情报构成威胁的情报员有多少个。

Read More →

[bzoj 4448] [Scoi2015]情报传递

@krydom3周前

09/11
13:54
数学相关

[bzoj 4459] [Jsoi2013]丢番图

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

 丢番图是亚历山大时期埃及著名的数学家。他是最早研究整数系数不定方程的数学家之一。
为了纪念他,这些方程一般被称作丢番图方程。最著名的丢番图方程之一是x^N+y^n=z^N。费马提出,对于N>2,x,y,z没有正整数解。这被称为“费马大定理”,它的证明直到最近才被安德鲁·怀尔斯(AndrewWiles)证明。
考虑如下的丢番图方程:
1/x+1/y=1/n(x,y,n属于N+)                      (1)
小G对下面这个问题十分感兴趣:对于一个给定的正整数n,有多少种本质不同的解满足方程(1)?例如n=4,有三种本质不同(x≤y)的解:
1/5+1/20=1/4
1/6+1/12=1/4
1/8+1/8=1/4
显然,对于更大的n,没有意义去列举所有本质不同的解。你能否帮助小G快速地求出对于给定n,满足方程(1)的本质不同的解的个数?

Read More →

[bzoj 4459] [Jsoi2013]丢番图

@krydom3周前

09/11
13:38
最小割

[bzoj 4485] [Jsoi2015]圈地

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

 【故事背景】
JYY在火星买了一大块矩形的地皮做房地产开发。由于地皮实在是太大了,JYY把这块地皮划分成了N行M列的小方格,并在每一格中建造一栋房子。历时若干年,开发终于宣告结束,JYY也可以把这些房子挂牌出售了。现在他找到了两位非同寻常的土豪买家:南南和强强。
麻烦的是,南南和强强是水火不容的。为了保证他们俩不发生矛盾,JYY需要把卖给他们俩的房子用墙隔开。不过造墙是需要钱的,JYY作为倒卖地皮的专家,自然想挣尽可能多的钱,因此他邀请到你帮他设计最优的出售方案。
【问题描述】
JYY把这块地皮划分成了N行M列的矩形,且矩形的每一格中建造一栋房子。现在,南南和强强已经将他们的购买意见提交给了JYY。对于每一栋房子,南南和强强已经给定了他们的出价(不想购买,或愿意以一定价格购买),并且由于他们已经协商好了各自的势力范围,因此不存在两个人同时想买一栋房子的情况。JYY可以选择每一栋房子是否出售(因为不存在两个人同时想买一栋房子的情况,若JYY选择出售一栋房子,它的买家就是确定的)。房子卖给强强和南南以后,JYY就能获得卖出房子出价的总和。
不过,作为售后服务,JYY需要通过造墙(将两栋相邻的房子用一堵墙隔开)把两个人的房子完全隔开。所谓完全隔开,就是指造出的墙以及四周的边界将整个区域划分成若干个不连通的部分,每个部分里面只有一个人的房子。当然,造墙也是需要钱的,而且价格不菲。不过JYY当初在宣传时声称造墙完全免费,所以这部分钱只好由JYY自己出了。
JYY请你为他规划每幢房子是否要卖出以及建造哪些围墙,才能使得卖房子的收益减去造围墙的花费最大。另外一个好消息是整个地皮的四周已经建好了墙,因此JYY可以利用这些建好的墙达到目的。下图就是用墙将区域划分成3个不连通的部分的例子。格子中的数字代表出价(数字的含义参考输入格式),边上的数值代表造墙的价格。四周的墙(边界)本来就有,不需要JYY花额外的代价去建造。
4

Read More →

[bzoj 4485] [Jsoi2015]圈地

@krydom3周前

09/11
13:05
主席树

[bzoj 4408] [Fjoi 2016]神秘数

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

 一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。例如S={1,1,1,4,13},
1 = 1
2 = 1+1
3 = 1+1+1
4 = 4
5 = 4+1
6 = 4+1+1
7 = 4+1+1+1
8无法表示为集合S的子集的和,故集合S的神秘数为8。
现给定n个正整数a[1]..a[n],m个询问,每次询问给定一个区间[l,r](l<=r),求由a[l],a[l+1],…,a[r]所构成的可重复数字集合的神秘数。

Read More →

[bzoj 4408] [Fjoi 2016]神秘数