QBXT七月D1

待我称王封你为后i 2021-12-03 11:41 273阅读 0赞

今天是lyd神仙讲课的第一天，可以感觉到的是这位神仙有着不同于他人的气质，比如他的表情包（雾）

![1606141-20190713195542989-1445428559.png][]

好了来讲正经的）

今天讲的比较多的是模拟算法和一些比赛中的好习惯

# high-level #

这个名词的大体意思就是，你要明白自己在写什么，要现在脑海里构造出代码的答题思路，其实和我前一阵在搞的模块化码风比较像，我们不能看见一个题就开始写输入输出，而是应该理清思路，争取一次a掉。

这个思想会在这几天的讲课当中逐渐渗透

# 模拟 #

模拟这个东西是很水的一种算法了吧，它本身其实就是将人类语言翻译成代码，更准确的说就是：讲一个用日常大白话用计算机语言抽象的表达出来。

所以想要良好的掌握模拟算法，就要做到以下两点

1.优秀的读题能力

2.优秀的代码能力

##  例题 ##

斗地主

![1606141-20190714075924671-296603629.png][]

斗地主，当然我懒得写（惆怅，但是还是借着这个讲一讲

开始high-level

## 这他妈是个啥？？？？？？？？？？？？？？ ##

恶心死了

手里有n张牌

有k个规则(k<?)，每个规则可以打出一定的牌

请问最少要打出多少次牌

显然是个明显的深搜

大体的代码是这么写（但是lyd把所有重要的都去掉了（惆怅）

void dfs(剩下多少张牌没打last，打了多少次牌ans)
    {
        if(last==0)
    
        规则1
        规则2
        ......
        规则k
    }

总之这就使是hgih-level的一个良好体现，其实就是让你的代码思路更加清晰

![1606141-20190714152841624-787556725.png][]

我们要尽量保证写完每一个小段都能保证写对，也就是尽量保证一次写对代码，写出来就能编译。

还有就是爆零问题，这个问题就在于平时的做题习惯好不好，其实noip和平时的考试没什么关系，但是问题就是你不是在oj上测评，一大问题就是你得不到数据，平时写题能不能一遍AC，正确做法是每一次交之前都当做考试，用尽可能少的提交次数换来尽可能高的代码质量

还有一个问题就是要去写对拍并且自己造数据

因为很多时候下我们是拿不了全分的，按照常理说30分是可以用暴力写出来的，正常的时候会先写正解再写暴力，然后进行对拍

按理说noip两天的t1都写对，然后就开始写剩下的暴力，就能得省一（大雾

## 贪心（其实就是捞 ##

贪心算法的数学原理是局部最优解得到全局最优解，在每一个状态下，都选择当前的最优解而不考虑全局的影响。

爬山算法是能够较好的体现贪心的思想的，其实所有程序都可以看做一个函数，可以知道的是，一般贪心问的话都是让你求最优解。

![1606141-20190714153225512-1716708429.png][]

我可以在走到波峰的时候来判断我是最优解，但是如果这样呢？

![1606141-20190714153322410-413315910.png][]

像这样的函数，，如果我走到了b点，我会成为局部最优，但是并不是全局最优。我们就会说他陷入了局部最优解，这种的就没法用贪心解

### 贪心算法要满足的两个条件 ###

1.决策没有后效性

2.不会陷入局部最优解

根据贪心的数学背景我们在做贪心题目时一般有两种策略

1.把一个问题划分成很多子问题，对每个子问题直接求最优解，然后合成一个最优解

2.对于当前局面，搜索所有可能的临近局面，选择最优的局面进行转移

贪心与其说是一个算法，不如说是一种思想。

贪心一般都用于求解最优化问题，但是最优化问题还有很多算法，不如动规和搜索。

其实没有很好的方法去一下子区分一个最优化的题究竟是搜索加剪枝还是dp还是贪心，其实吧，我们可以枚举一下状态数，比如说搜索问题，dfs下第一维是放的第几个数，第二维是放的是什么数，数据范围大用贪心，数据范围中等用dp，数据范围小勇n^2的话就得用搜索

要主要的是，贪心最重要的一点就是要去找反例，当你找到三个以上的反例之后，你就最好不要用这个贪心策略了

贪心最重要的一点就是反例。一般做题过程就是在思考规律->寻找反例->找到算法或者是重新思考的循环种度过

所以要多做题积累经验和感觉

# 看看例题 #

![1606141-20190714155931850-1534179466.png][]

N  <= 1e5, m <= 1e18

一般这种数据范围特大的，首先要保证

贪心策略是，把巧克力价格升序排列，对于每种巧克力我们只有两种情况，当前开心的牛已经足够了，并且钱还够买别的，或者是这种的还没够，

至于证明的话。。。。。。大胆猜想，无需证明（雾

其实就是说如果我们不一直买最便宜的话，最后的解一定能够找到一种方法得到一个更加实惠的方法来使奶牛高兴

![1606141-20190714181359447-81734907.png][]

首先考虑前缀和

然后这个题如果不取模是很好做的，加上取模则有两种情况

1.x-y(y<=x)

2.X+M-y(y>x)

第一种情况，y越接近0越好

第二种情况，y越接近x越好

用set+upper\_bound就ok

其实当我们发现mod是一个输入的值的时候，就应该猜想是不是有规律可循了，因为在模意义下数值是可以循环的，所以就可以通过一些玄学操作a掉某些题

![1606141-20190714182302785-1028866946.png][]

经典题，直接按照右端点排序，然后找左端点较小的就OK了

这个题蓝书上有，也算是个经典题目，我们具体分析一下

因为圆覆盖矩形是覆盖不全的，所以我们要切掉一部分，其实也就是说从圆变成了矩形（雾

![1606141-20190714182843156-199851689.png][]

然后变成了线段覆盖问题

将所有的区间按左端点从小到大排序，依次处理每一个区间，每次选择覆盖点s的区间中右端点最大的一个，直到区间已经包含了这个区间内所有的点为止

还有一个经典题

![1606141-20190714183024845-865848110.png][]

这个题读完，我们会发现在x轴上放雷达太傻了，所以我们考虑在每一个点画圆，这样的话，每一个雷达就能通过垂径定理啥的变成线段，这个题就成了线段覆盖啦

![1606141-20190714202117697-1092045086.png][]

这个题很玄学

首先，先把杀掉能回血的先杀了

显然杀的顺序按照消耗升序

杀完以后，不管用什么顺序杀掉剩下的怪，最后体力last是确定的

倒序来看，相当于将血药吐出来然后返还杀怪的消耗，那么显然也是按照损失体力（即血药回血量）升序，正回来即是降序。

为什么要倒序来看呢？因为倒序保证了一定不会死

即分为两部分，杀完能回血的按照消耗升序，剩余按血药回血量降序，然后模拟一遍判断是否合法即可

![1606141-20190715171106919-1493010668.png][]

这个题的想法是，你要尽量减最大的阶乘，能减多大减多大，然后就是说和求lca跳有点像，或者说是把十进制转化为二进制

![1606141-20190715171158190-248549508.png][]

贪心思路就是把前k个数最大的放到最前面去

![1606141-20190715171228581-597279337.png][]

这个题就是按照左右手乘积从小到大排序就可以了

证明：考虑只交换相邻两个i，i+1，则他们之前和之后的大臣拿到的金币都不变，我们只需考虑这两个大臣本身

首先我们设这两个大臣一个为i，另一个为i+1，且l\[i\]\*r\[i\]<l\[i+1\]\*r\[i+1\]

交换之前i大臣拿到的金币：S/r\[i\]，i+1大臣拿到的金币：S\*l\[i\]/r\[i+1\]，两个取max

即max(S/r\[i\],S\*l\[i\]/r\[i+1\])

交换之后i+1大臣变成了i，他拿到的金币：S/r\[i+1\]

第i大臣变成了i+1大臣，他拿到的金币S\*l\[i+1\]/r\[i\]，两个取max

即max(S/r\[i+1\],S\*l\[i+1\]/r\[i\])

我们要求的是两者的最小值，即min(max(S/r\[i\],S\*l\[i\]/r\[i+1\])，max(S/r\[i+1\],S\*l\[i+1\]/r\[i\]) )

提出S，即S\*min( max(1/r\[i\],l\[i\]/r\[i+1\])，max(1/r\[i+1\],l\[i+1\]/r\[i\]) )

然后我们显然有1/r\[i\]<l\[i+1\]/r\[i\]，l\[i\]/r\[i+1\]>1/r\[i+1\]

如果我们想要max(1/r\[i+1\],l\[i+1\]/r\[i\])<max(1/r\[i\],l\[i\]/r\[i+1\])，则必然有l\[i+1\]/r\[i\]<l\[i\]/r\[i+1\]，乘过去之后即得l\[i\]\*r\[i\]>l\[i+1\]\*r\[i+1\]，与题目矛盾，故乘积大的一定在前面

转载于:https://www.cnblogs.com/this-is-M/p/11180425.html

[1606141-20190713195542989-1445428559.png]: /images/20211203/32a2ec48e74441a78afe2c69f2328f29.png
[1606141-20190714075924671-296603629.png]: /images/20211203/6bff2f8c3b1144a2b8161f1a88f49240.png
[1606141-20190714152841624-787556725.png]: /images/20211203/c499c99ba3364008838597d0843061de.png
[1606141-20190714153225512-1716708429.png]: /images/20211203/4cda66919db7425fa54417ce605ac8d7.png
[1606141-20190714153322410-413315910.png]: /images/20211203/d65c11259527428c82911d2d246aa58b.png
[1606141-20190714155931850-1534179466.png]: /images/20211203/0c8099ae731d45c49052ca2c5b3447b8.png
[1606141-20190714181359447-81734907.png]: /images/20211203/88666387646a455cb484932bf1f909f7.png
[1606141-20190714182302785-1028866946.png]: /images/20211203/216af248a6b04a7d8a55aebf82e14ef4.png
[1606141-20190714182843156-199851689.png]: /images/20211203/b6982fee7066417f984ebe6bc09d32f8.png
[1606141-20190714183024845-865848110.png]: /images/20211203/4fff132a7740470ca2a4f3a2f52b2438.png
[1606141-20190714202117697-1092045086.png]: /images/20211203/c16fd2b771864e1eb60a0757b020f465.png
[1606141-20190715171106919-1493010668.png]: /images/20211203/e7fb4831085249f98e37280bcc0367cf.png
[1606141-20190715171158190-248549508.png]: /images/20211203/5f89668eabf04c01a46998d1cec51324.png
[1606141-20190715171228581-597279337.png]: /images/20211203/d9cb06dc09fb4c349759289f07da5ac6.png