[虚树][树形DP]消耗战
消耗战
Time Limit: 20 Sec Memory Limit: 512 MB
Description
在一场战争中,战场由n个岛屿和n-1个桥梁组成,保证每两个岛屿间有且仅有一条路径可达。现在,我军已经侦查到敌军的总部在编号为1的岛屿,而且他们已经没有足够多的能源维系战斗,我军胜利在望。已知在其他k个岛屿上有丰富能源,为了防止敌军获取能源,我军的任务是炸毁一些桥梁,使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同,所以炸毁不同的桥梁有不同的代价,我军希望在满足目标的同时使得总代价最小。
侦查部门还发现,敌军有一台神秘机器。即使我军切断所有能源之后,他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁,而且会重新随机资源分布(但可以保证的是,资源不会分布到1号岛屿上)。不过侦查部门还发现了这台机器只能够使用m次,所以我们只需要把每次任务完成即可。
Input
第一行一个整数n,代表岛屿数量。
接下来n-1行,每行三个整数u,v,w,代表u号岛屿和v号岛屿由一条代价为c的桥梁直接相连,保证1<=u,v<=n且1<=c<=100 ...
[计算几何]下落的圆盘
下落的圆盘
Time Limit: 10 Sec Memory Limit: 162 MB
Description
有n个圆盘从天而降,后面落下的可以盖住前面的。求最后形成的封闭区域的周长。
看下面这副图, 所有的红色线条的总长度即为所求。
Input
第一行为1个整数n
接下来n行每行3个实数,ri,xi,yi,表示下落时第i个圆盘的半径和圆心坐标.
Output
最后的周长,保留三位小数
Sample Input
2
1 0 0
1 1 0
Sample Output
10.472
HINT
n <= 1000
Solution
显然是一道计算几何题。
考虑一个圆对于答案的贡献,显然是这个圆的周长 - 后面的圆把它覆盖掉的周长的并。那么我们就考虑怎么求这个并。
先考虑怎样记录下一个答案,显然直接扣掉单个圆对它的覆盖是不可行的,要减去重叠的情况。
既然边不可行,我们就用角度。显然,若我们求出 两圆交点的角度 即可解决这题。
我们考虑求圆A被圆B覆盖的角度:现在我们有两个圆的半径、圆心距。我们就可以得到 圆A与圆B的圆心连线 与 圆A半径 的夹角。
我们也可以知道 圆A与 ...
[计算几何]数矩形
数矩形
Time Limit: 20 Sec Memory Limit: 128 MB
Description
最近某歌手在研究自己的全国巡回演出,他将所有心仪的城市都用平面上一个点来表示,并打算从中挑选出4个城市作为这次巡回演出的地点。
为了显示自己与众不同,他要求存在一个矩形使得挑选出的4个点恰好是这个矩形的4个顶点,并且希望这个矩形的面积最大。
这可急坏了经纪人,于是他向全球歌迷征集方案,当然你这位歌迷一定不会错过这个机会。
Input
第一行是一个正整数N,表示平面上点的个数(即某歌手心仪的城市数)。
接下来N行,每行是两个整数Xi,Yi,表示对应点的坐标。
Output
输出一个数,表示最大矩形面积。
Sample Input
8
-2 3
-2 -1
0 3
0 -1
1 -1
2 1
-3 1
-2 1
Sample Output
10
HINT
1<=N<=1500 , -10^8<=Xi,Yi<=10^8
Main idea
给出平面上的若干个点,求出可由这些点作为顶点构成的矩形的最大面积。
Solu ...
[贪心]生日礼物
生日礼物
Time Limit: 10 Sec Memory Limit: 128 MB
Description
ftiasch 18岁生日的时候,lqp18_31给她看了一个神奇的序列 A1, A2, …, AN. 她被允许选择不超过 M 个连续的部分作为自己的生日礼物。
自然地,ftiasch想要知道选择元素之和的最大值。你能帮助她吗?
Input
第1行,两个整数 N 和 M , 序列的长度和可以选择的部分。
第2行, N 个整数 A1, A2, …, AN , 序列。
Output
一个整数,最大的和。
Sample Input
5 2
2 -3 2 -1 2
Sample Output
5
HINT
1 ≤ N ≤ 105, 0 ≤ M ≤ 105, 0 ≤ |Ai| ≤ 104
Solution
首先,我们可以把权值正负相同的连续的一段合并起来。Ans+=(所有正数),块数++。
然后把每一段的绝对值加入到小根堆里面。每次贪心取出最小的来,块数减去 1 直到满足题目要求为止。
为什么这样可以对呢?我们来讨论一下:
1. 如果删去的段是正数, 那么相当于不取这个。
2. 如 ...
[贪心]免费道路
免费道路
Time Limit: 2 Sec Memory Limit: 128 MB
Description
Input
Output
Sample Input
5 7 2
1 3 0
4 5 1
3 2 0
5 3 1
4 3 0
1 2 1
4 2 1
Sample Output
3 2 0
4 3 0
5 3 1
1 2 1
HINT
1<=n<=20000,1<=m<=100000,0<=k<=n-1
Main idea
一种0边,一种1边,求一棵最小生成树并且正好有K条0边,输出其中一种方案。
Solution
显然要搞一棵符合题目的生成树。
每次要加入0边或者1边,直接做肯定不可行,考虑有什么0边是一定要加入的。
只需要输出一种方案,所以我们先加入所有可加的1边,如果图不联通则加入可加入的0边,那么这几条0边在我们所求的方案中是一定需要加入的。
这时候判断一下,如果此时加入的0边数量>K,或者图还是无法联通的话则无解。然后处理完毕前半部分,考虑接下来如何实现。
因为我们要使得图为树并且正好有K条0边,运用 ...
[费用流][分数规划]新生舞会
新生舞会
Time Limit: 10 Sec Memory Limit: 128 MB
Description
学校组织了一次新生舞会,Cathy作为经验丰富的老学姐,负责为同学们安排舞伴。有n个男生和n个女生参加舞会买一个男生和一个女生一起跳舞,互为舞伴。
Cathy收集了这些同学之间的关系,比如两个人之前认识没计算得出 a[i][j] ,表示第i个男生和第j个女生一起跳舞时他们的喜悦程度。
Cathy还需要考虑两个人一起跳舞是否方便,比如身高体重差别会不会太大,计算得出 b[i][j],表示第i个男生和第j个女生一起跳舞时的不协调程度。
当然,还需要考虑很多其他问题。Cathy想先用一个程序通过a[i][j]和b[i][j]求出一种方案,再手动对方案进行微调。
Cathy找到你,希望你帮她写那个程序。
一个方案中有n对舞伴,假设没对舞伴的喜悦程度分别是a’1,a’2,…,a’n,
假设每对舞伴的不协调程度分别是b’1,b’2,…,b’n。
令C=(a’1+a’2+…+a’n)/(b’1+b’2+…+b’n),Cathy希望C值最大。
Input
第一行一个整数n。
接下来n行,每 ...
[费用流]数字配对
数字配对
Time Limit: 10 Sec Memory Limit: 128 MB
Description
有 n 种数字,第 i 种数字是 ai、有 bi 个,权值是 ci。
若两个数字 ai、aj 满足,ai 是 aj 的倍数,且 ai/aj 是一个质数,
那么这两个数字可以配对,并获得 ci×cj 的价值。
一个数字只能参与一次配对,可以不参与配对。
在获得的价值总和不小于 0 的前提下,求最多进行多少次配对。
Input
第一行一个整数 n。
第二行 n 个整数 a1、a2、……、an。
第三行 n 个整数 b1、b2、……、bn。
第四行 n 个整数 c1、c2、……、cn。
Output
一行一个数,最多进行多少次配对
Sample Input
3
2 4 8
2 200 7
-1 -2 1
Sample Output
4
HINT
n≤200,ai≤10^9,bi≤10^5,∣ci∣≤10^5
Solution
显然是一个费用流,并且这可以是一个二分图,由于 ai/aj 要是质数,那显然可以根据质因子个数的奇偶分类。
然后跑一跑最大费用最大流。判断一下值要&g ...
[费用流]猜测
猜测
Time Limit: 10 Sec Memory Limit: 256 MB
Description
Input
Output
Sample Input
3
1 1
1 2
2 1
Sample Output
3
explain:
(1,1),(1,1),(2,2)不是一个合法猜测(有相同的格子),因此不管怎么猜总是能全部猜中。
HINT
Main idea
给定了若干个标准点,用这些点的横纵坐标分为x集和y集,定义猜点表示从x集和y集中各选一个,不能猜出重复的点,问在所有合法方案中最少包含上述几个标准点。
Solution
我们看到了这道题目,考虑从费用流的方法下手。
我们从S->x集:容量为数字出现次数,费用为0;y集->T:容量为数字出现次数,费用为0;x集->y集:容量为1,若组合成了标准点则费用为1,否则为0。
然后我们这样连边,又由于题目要的是最少包含几个点,那么显然最小费用最大流就是答案了。
Code
12345678910111213141516171819202122232425262728293031323334 ...
[费用流]球队预算
球队预算
Time Limit: 10 Sec Memory Limit: 256 MB
Description
在一个篮球联赛里,有n支球队,
球队的支出是和他们的胜负场次有关系的,具体来说,第i支球队的赛季总支出是Cix^2+Diy^2,Di<=Ci。(赢得多,给球员的奖金就多嘛)
其中x,y分别表示这只球队本赛季的胜负场次。
现在赛季进行到了一半,每只球队分别取得了a[i]场胜利和b[i]场失利。
而接下来还有m场比赛要进行。
问联盟球队的最小总支出是多少。
Input
第一行n,m
接下来n行每行4个整数a[i],b[i],Ci,Di
再接下来m行每行两个整数s,t表示第s支队伍和第t支队伍之间将有一场比赛,注意两只队间可能有多场比赛。
Output
输出总值的最小值。
Sample Input
3 3
1 0 2 1
1 1 10 1
0 1 3 3
1 2
2 3
3 1
Sample Output
43
HINT
2<=n<=5000,0<=m<=1000,0<=di<=ci<=10,0< ...
[费用流]软件开发
软件开发
Time Limit: 10 Sec Memory Limit: 162 MB
Description
某软件公司正在规划一项n天的软件开发计划,根据开发计划第i天需要ni个软件开发人员,为了提高软件开发人员的效率,公司给软件人员提供了很多的服务,其中一项服务就是要为每个开发人员每天提供一块消毒毛巾,这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种,A种方式的消毒需要a天时间,B种方式的消毒需要b天(b>a),A种消毒方式的费用为每块毛巾fA, B种消毒方式的费用为每块毛巾fB,而买一块新毛巾的费用为f(新毛巾是已消毒的,当天可以使用);而且f>fA>fB。公司经理正在规划在这n天中,每天买多少块新毛巾、每天送多少块毛巾进行A种消毒和每天送多少块毛巾进行B种消毒。当然,公司经理希望费用最低。你的任务就是:为该软件公司计划每天买多少块毛巾、每天多少块毛巾进行A种消毒和多少毛巾进行B种消毒,使公司在这项n天的软件开发中,提供毛巾服务的总费用最低。
Input
第1行为n,a,b,f,fA,fB. 第2行为n1,n2,……,nn.
Output
...