第5章
百度之星2017
5.1资格赛
5.1资格赛
度度熊保护村庄
时间限制:2000/1000毫秒(Java/其他)
空间限制:32768/32768KB(Java/其他)
题目
哗啦啦村袭击了喵哈哈村！
度度熊为了拯救喵哈哈村，带着自己的伙伴去救援喵哈哈村去了！度度熊与伙伴们很快的就过来占据了喵哈哈村的各个军事要地，牢牢守住了喵哈哈村。但是度度熊发现，这是一场旷日持久的战斗，所以度度熊决定要以逸待劳，保存尽量多的体力，去迎战哗啦啦村的战士。于是度度熊决定派尽量多的人去休息，但是同时也不能松懈对喵哈哈村的保护。换句话而言，度度熊希望尽量多的人休息，而且存在一个包围圈由剩下的人组成，且能够恰好包围住喵哈哈村的所有住房(包括边界)。
请问最多能让多少个人休息呢?
输入
本题包含若干组测试数据。
第一行一个整数n，表示喵哈哈村的住房数量。
接下来n行，每行两个整数(x1[i]，y1[i])，表示喵哈哈村的住房坐标。
第n+1行一个整数m，表示度度熊的士兵数量。
接下来m行，每行两个整数(x2[i]，y2[i])，表示度度熊伙伴的坐标。
满足:1≤n,m≤500,-10000≤x1[i],x2[i],y1[i],y2[i]≤10000。
输出
请输出最多的人员休息的数目。如果无法保护整个村庄的话，输出ToT。
输入样例
2
11
146百度之星题集(2005-2021年)
22
4
00
04
42
40
1
11
2
00
01
输出样例
1
ToT
关键思路
特判掉n=1和n=2的情况。
然后做一个由n个点组成的凸包，找到所有在凸包外面的边(由士兵组成)。
假设由第i个点和第j个点组成的边在凸包外的话，令mpi
度度熊的王国战略
时间限制:40000/20000毫秒(Java/其他)
空间限制:32768/132768KB(Java/其他)
题目
度度熊国王率领着喵哈哈族的勇士，准备进攻哗啦啦族。哗啦啦族是一个强悍的民族，里面有充满智慧的谋士，拥有无穷力量的战士。所以这一场战争，将会十分艰难。为了更好地进攻哗啦啦族，度度熊决定首先从内部瓦解哗啦啦族。第一步就是使得哗啦啦族内部不能齐心协力，需要内部有间隙。哗啦啦族一共有n个将领，他们一共有m个强关系，摧毁每一个强关系都需要一定的代价。
现在度度熊命令你摧毁一些强关系，使得内部的将领，不能通过这些强关系，连成一个完整的连通块，以保证战争的顺利进行。
请问最少应该付出多少的代价。
输入
本题包含若干组测试数据。
第一行两个整数n，m，表示有n个将领，m个关系。
接下来m行，每行三个整数u，v，w。表示u将领和v将领之间存在一个强关系，摧毁这个强关系需要代价w。
数据范围:2≤n≤3000,1≤m≤100000,1≤u,v≤n,1≤w≤1000
输出
对于每组测试数据，输出最小需要的代价。
第5章
输入样例
21
121
33
125
124
233
输出样例
1
3
关键思路
这道题是一个经典题了，是无向图的最小割。
采用Stoer-Wagner算法,再用堆优化,就可以将复杂度优化到n^2logn。
度度熊与邪恶大魔王
时间限制:2000/1000毫秒(Java/其他)
空间限制:32768/32768KB(Java/其他)
题目
度度熊为了拯救可爱的公主，于是与邪恶大魔王战斗起来。邪恶大魔王的麾下有n个怪兽，每个怪兽有a[i]的生命值，以及b[i]的防御力。度度熊一共拥有m种攻击方式，第i种攻击方式，需要消耗k[i]的晶石,造成p[i]点伤害。
如果度度熊使用第i个技能打在第j个怪兽上面的话，会使得第j个怪兽的生命值减少p[i]-b[j]，如果伤害小于防御，那么攻击就不会奏效。如果怪兽的生命值降为0或以下，那么怪兽就会被消灭。当然每个技能都可以使用无限次。
请问度度熊最少携带多少品石，就可以消灭所有的怪兽。
输入
本题包含若干组测试数据。
第一行两个整数n.m，表示有n个怪兽，m种技能。
接下来n行，每行两个整数，a[i]，b[i]，分别表示怪兽的生命值和防御力。
再接下来m行，每行两个整数k[i]和p[i]，分别表示技能的消耗晶石数目和技能的伤害值。
数据范围：
≤slan
0≤k[i]≤100000,0≤p[i]≤1000
输出
对于每组测试数据，输出最小的晶石消耗数量，如果不能击败所有的怪兽，输出-1输入样例
12
35
710
148百度之星题集(2005—2021年)
68
12
35
107
86
输出样例
6
18
关键思路
仔细观察，防御力实际上只有11种情况，对于每一种防御力，我们都做一次背包DP，预处理出DP状态。然后对于每一个怪兽，我们O(1)的进行回答即可。
度度熊的午饭时光
时间限制:2000/