BearChild's Blog

免费道路 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 ...

Sensor Network Time Limit: 2 Sec Memory Limit: 128 MB Description 魔法炮来到了帝都，除了吃特色菜之外，还准备去尝一尝著名的北京烤鸭。 　　帝都一共有n个烤鸭店，可以看成是二维平面内的点。 　　不过由于魔法炮在吃烤鸭之前没有带钱，所以吃完烤鸭之后只能留下刷盘子。 　　刷完盘子之后，魔法炮除了不用付饭费之外，老板还会奖励他d元钱。 　　魔法炮是一个特么喜欢吃烤鸭的孩子，所以在去过一家烤鸭店之后，魔法炮还准备去其他的烤鸭店。 　　但是由于帝都路费较贵，每单位长度需要花费1元钱，所以魔法炮可能去不了所有其他的烤鸭店。 　　在到达下一家烤鸭店之前，魔法炮会花掉手里所有钱，以便于下一次接着吃霸王餐。 　　另外，魔法炮对于自己刷过盘子的烤鸭店有着特殊的感情，所以他要求在某一家烤鸭店吃完烤鸭后，可以到达全部已经吃过去过的烤鸭店。 　　那么问题来了，魔法炮想知道自己最多能去多少家烤鸭店，以及这些烤鸭店都是哪些。你能帮帮他吗？ Input 第一行两个整数n和d，分别表示烤鸭店数和老板给魔法炮的路费。 　　接下来n行，每行两个整数x,y，表示 ...