BZOJ1010【HNOI2008】玩具装箱toy <斜率优化>
Problem
【HNOI2008】玩具装箱toy
TimeLimit:10Sec
MemoryLimit:162MB
Description
P教授要去看奥运,但是他舍不下他的玩具,于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩,其可以将任意物品变成一堆,再放到一种特殊的一维容器中。P教授有编号为1∼N的N件玩具,第i件玩具经过压缩后变成一维长度为Ci.为了方便整理,P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具,那么两件玩具之间要加入一个单位长度的填充物,形式地说如果将第i件玩具到第j个玩具放到一个容器中,那么容器的长度将为 x=j−i+∑k=ijCk制作容器的费用与容器的长度有关,根据教授研究,如果容器长度为X,其制作费用为(X−L)2.其中L是一个常量。P教授不关心容器的数目,他可以制作出任意长度的容器,甚至超过L。但他希望费用最小.
Input
第一行输入两个整数N,L.接下来N行输入Ci.
1≤N≤50000,1≤L,Ci≤107
Output
输出最小费用.
BZOJ1096【ZJOI2007】仓库建设 <斜率优化>
Problem
【ZJOI2007】仓库建设
TimeLimit:10Sec
MemoryLimit:162MB
Description
L公司有N个工厂,由高到底分布在一座山上。如图所示,工厂1在山顶,工厂N在山脚。由于这座山处于高原内陆地区(干燥少雨),L公司一般把产品直接堆放在露天,以节省费用。突然有一天,L公司的总裁L先生接到气象部门的电话,被告知三天之后将有一场暴雨,于是L先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。由于地形的不同,在不同工厂建立仓库的费用可能是不同的。第i个工厂目前已有成品Pi件,在第i个工厂位置建立仓库的费用是Ci。对于没有建立仓库的工厂,其产品应被运往其他的仓库进行储藏,而由于L公司产品的对外销售处设置在山脚的工厂N,故产品只能往山下运(即只能运往编号更大的工厂的仓库),当然运送产品也是需要费用的,假设一件产品运送1个单位距离的费用是1。假设建立的仓库容量都都是足够大的,可以容下所有的产品。你将得到以下数据:
- 工厂i距离工厂1的距离Xi(其中X1=0)
- 工厂i目前已有成品数量Pi
- 在工厂i建立仓库的费用Ci
请你帮助L公司寻找一个仓库建设的方案,使得总的费用(建造费用+运输费用)最小。
Input
第一行包含一个整数N,表示工厂的个数。接下来N行每行包含两个整数Xi,Pi,Ci, 意义如题中所述。
Output
仅包含一个整数,为可以找到最优方案的费用。
HDU4560 我是歌手 <二分+网络流>
Problem
我是歌手
TimeLimit:2000MS
MemoryLimit:32768KB
Description
2013年一开始,一档音乐节目“我是歌手”就惊艳了大家一回。闲话少说,现在,你成为了这档节目的总导演,你的任务很简单,安排每一期节目的内容。
现在有N个歌手,M种歌曲流派(Rock,Pop之类),每个歌手都有自己擅长的流派领域,这些资料都已整理。你的工作是,安排尽可能多场的演唱比赛。每一场比赛所有歌手都必须上场,为了提高收视率,每个人演唱的歌曲类型不能相同,即便一些歌手要被迫选择一些他们不擅长的。同时,为了展现全面性,在不同的演唱比赛上,每个歌手都会安排不同的歌曲流派。
但是问题是,对于任何一个歌曲流派的歌迷,如果超过K个不擅长的歌手演唱了这种歌曲,他们就会表示不满,比如,发一些宣泄不满的帖子微博,为了表示观点挑起事端等等。你当然不希望这些事情与你的节目有关,在这个前提下,你可以任意安排尽可能多的比赛场次。
Input
输入第一行为T,表示有T组测试数据。
每组数据以四个数字N,M,L,K开始。L表示有L组擅长关系,接下来的L行,每一行有两个数字Ai,Bi,表示歌手Ai擅长Bi类型的歌曲。
Output
对每组数据,先输出为第几组数据,然后输出最多比赛场次。
CF446C DZY Loves Fibonacci Numbers <线段树>
Problem
DZY Loves Fibonacci Numbers
Timelimit:4Sec
Memorylimit:256MB
Description
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation F1 = 1,F2 = 1,F3=F1+F2=3,⋯Fn = Fn−1+Fn−2.
DZY loves Fibonacci numbers very much. Today DZY gives you an array consisting of n integers: a1, a2,⋯,an. Moreover, there are m queries, each query has one of the two types:
- Format of the query “1 l r”. In reply to the query, you need to add Fi−l+1 to each element ai, where l≤ i≤ r.
- Format of the query “2 l r”. In reply to the query you should output the value of ∑i=lrai modulo 109+9.
Help DZY reply to all the queries.
Input
The first line of the input contains two integers n and m (1 ≤n, m ≤ 3×105). The second line contains n integers a1, a2, ⋯, an(1 ≤ ai ≤109) — initial array a.
Then, m lines follow. A single line describes a single query in the format given in the statement. It is guaranteed that for each query inequality 1 ≤ l ≤ r ≤ n holds.
Output
For each query of the second type, print the value of the sum on a single line.
BZOJ2671 Calc <莫比乌斯反演>
BZOJ2339【HNOI2011】卡农 <计数DP+组合数学>
BZOJ4334【JSOI2012】铁拳 <上下界网络流>
Problem
【JSOI2012】铁拳
TimeLimit:10Sec
MemoryLimit:256MB
Description
经过了可怕的第三次世界大战后,国家政府崩溃,各大财团趁机夺取掌控世界。长年战争后,八大财团幸存并割据一方,其中最强的当属掌控北美的铁拳。
在铁拳财团所维护的文明区域中,有一项最为光荣、重要的赛事——IronFist,也就是铁拳大赛。IF中云集了世界各地各财团鼎力资助的世外高手,只为了赢得IFChampion,得到无上的荣耀,当然还有随之而来的权力。本来一切秩序井然,但一个来自贫民窟的少年风间仁意外地在海选中赢了IF正式选手,获得了决赛资格,从此格局被打乱……
为了应对这突如其来的变数,IF管理层决定先对联盟中所有的选手进行评估,以更好地掌握大局。
知最近m届比赛出现过的n位选手,背后都有着各自财团的资助,并且签下了合同。由于这是各财团的高度机密,合同的具体细节无从得知,但铁拳财团的间谍们通过各种渠道得知了每个选手的薪金范围(显然薪金是非负数)。
对于最近m届的IF比赛(从1开始编号),每一届联盟都会进行清算,通过国际金融手段准确计算出这一届联盟选手身价总和的变化。每一届中,会有一些新选手加入,也会有部分选手在比赛中丧失了战斗能力,而被踢出联盟,流放到贫民窟。
现在给出联盟中n位选手的身价范围,以及他们 进入联盟的届数(0表示在m+1届以前就已经是联盟选手) 和 离开联盟的届数(0表示是现役选手)。同时给出最近m届中,每一届联盟选手身价总和减去上一届的值。
请你根据现有信息,尽可能准确地给出每个选手可能的薪金范围。各选手之间的薪金范围可以不同时成立,但对于一位选手的范围中的每一个数,都必须至少存在一种合法方案使该选手能得到相应薪金,而且这个范围跨度要尽可能大。
如果输入信息有误,请输出−1,表示无解。
Input
第一行一个正整数m,意义见上(下同)。
第二行包含m个整数,第i个表示第i届中 选手身价总和 的变化情况。
第三行一个正整数n。
接下来n行,每行包含四个整数,分别表示 身价下限 、 身价上限 、 出道届数 、 退役届数,细节请参照上文。
保证出道时间严格比退役时间小(0除外)。
Output
一行,输出最小的答案。