Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

一次NOIPACM模拟赛(内含bzoj3477 poj3040 真假奶牛 赞助学费)

第一题——POJ3040 奶牛工资

题目链接

传送门

想说的话

挺烧脑的

题解

诠释贪心思想的好题
对于硬币的面值 我们可以分为两类
第一类是面值大于需要的工资的 这些东西我们不用管 直接加上个数就好了
第二类的时候我们就要贪心了
从大到小选出最接近工资的面值 然后再从小到大去补 这样让浪费的最少 支付的就是最多
我们用一个bool变量记录当前这次选出的总面值够不够工资 然后再记录每个面值用了多少次
最后算出总的天数

代码

第二题——bzoj3477 破坏阴谋

题目链接

传送门

想说的话

这个题其实想明白很简单 一句话题解
但是代码的实现就很费劲了
最重要的是
这个思路根本想不到啊

题解

我们二分平均数答案的方式算
对于每个平均数 我们计算当前的和够不够
然后我们用dp算出当前这台机器破坏与不破坏对于平均数造成的影响
最后二分验证就行了
注意精度问题

代码

第三题——赞助学费

题目链接

没找到qaq

题目描述

人类可以上大学,而奶牛们却没学可上。为解决这个问题,贝西和她的伙伴们创立了一所奶牛大学,取名为哞哞大学。今年,共有 C 头奶牛申请入学,第 i 头奶牛的考试分数为 S i ,没有两头奶牛的分数是一样的。奶牛们必须依赖奖学金才能进入大学学习,第 i 头奶牛申请的奖学金为 Q i 元。贝西负责选拔新生的工作。首先,今年只能招 N 头奶牛,N 是个奇数。本着一个都不能少的原则,不能让入学的奶牛数量少于 N。其次,由于学校的助学基金只能支付 F 元,所以她选拔的新生所申请的奖学金数量之和不能超过 F。在满足这两个条件的前提下,贝西希望新生的考试分数的中位数越高越好。所谓中位数,就是按大小排序后处在中间位置的分数,比如{3,8,9,7,5} 的中位数是 7。请帮助贝西确定接受哪些奶牛的申请才可以使学校新生的考试分数的中位数达到最大。

输入

第一行:三个整数 N,C 和 F,1 ≤ N ≤ 19999 ≤ C ≤ 10 5
第二行到第 C + 1 行:第 i + 1 行有两个整数 S i 和 Q i ,0 ≤ S i ≤ 2 × 10 9 ,0 ≤ Q i ≤ 10 5

输出

单个整数:表示考试分数的最大中位数,如果预算不够资助任意 N 头奶牛的组合,输出 −1

样例输入

3 5 70
30 25
50 21
20 20
5 18
35 30

样例输出

35

提示

贝西接受分数为 5,35,50 的奶牛,中位数为35,需支付的奖学金总额为 18 + 30 + 21 = 69,在预算范围之内

想说的话

这题也是思路很重要

题解

小根堆加上优先队列
维护两个数组
前一半需要最少的钱和后面需要最少的钱
最后我们从最大可能的中位数向前枚举
前一半的钱加上他自己的钱加上后一半的钱
如果可以的话这就是最大的方案

代码

第四题——真假奶牛

题目链接

还是没找到

题目描述

约翰有 N 头奶牛,有一部分奶牛是真话奶牛,它们只说真话,而剩下的是假话奶牛,只说假话。
有一天,约翰从奶牛的闲谈中陆续得到了 M 句话,第 i 句话出自第 X i 头奶牛,它会告诉约翰第 Y i 头
是一头真话奶牛还是假话奶牛。然而,约翰记性不好,他可能把这些话的内容记错了。请检查一下约翰的记录是否会有矛盾,帮助他找到一个尽量大的 K,使得约翰记下的前 K 句话不矛盾。

输入

• 第一行:两个整数 N 和 M,1 ≤ N ≤ 1000,1 ≤ M ≤ 10000
• 第二行到 M + 1 行:第 i + 1 行有两个整数:X i 和 Y i ,1 ≤ X i ,Y i ≤ N,接下来有一个字符:
– 如果是 T,表示 X i 说 Y i 是真话奶牛;
– 如果是 L,表示 X i 说 Y i 是假话奶牛;

输出

单个整数,即表示题目描述中的 K

样例输入

4 3
1 4 L
2 3 T
4 1 T

样例输出

2

提示

前两句没有矛盾, 但第一句和第三句存在矛盾

想说的话

注意是问的前K句话
不是最多K句话

题解

我觉得看不出是并查集的大概就需要重新学习OI了
这个题有两种思路
第一种就是对于奶牛们无非两种关系 真假话
那大概就是朋友和敌人的想法
并查集经典题目
第二种思路就是对于所有的假话 我们把对应的序号加上n
这样我们对于一个奶牛只对应了一个编号
并查集搞起来更简单

题解I代码

题解II代码

写在最后

就是这样

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏