[补题][贪心][数据结构优化][数学] Gym 101775B Scapegoat

首先可以确定要分一个trouble,那一定是等分,这一点可以从公式化简得到。

所以难的问题是,给每一个trouble分几个人。当没有什么做法/头绪的时候,想一想贪心递推的操作(贪心是因为这个题数据量不应该是dp),大问题是否可以从小问题转化过来,每次多一个人的时候,这个人应该放到哪儿?可以试着遍历每一个trouble看看放在哪里会使得变小最多,但是这样是M^2的做法,但是这时候考虑“哪里小的最多”这个条件,以及,+1之后哪里变小的最多是完全取决于trouble的数值和他当前已经有的人的,所以可以用一个优先队列来存储“哪里变小的最多”这个信息!这样的话就是M^logM的算法了,可以通过本题。

自己当时为什么想挫了?主要是一开始想的把一个划分之后可以看成两个新的数,但是事实并非如此,新分出来的和原来的是不等价的,同一个trouble分出来的可以互相组合,但是不同德trouble之间不能组合,所以这种思路可以否定。所以其实每次都要考虑所有的trouble,取变小最多的那个,想到这里又觉得是M^2的算法,又没有继续,但是这时候思路已经是对的了,就可以考虑可以用什么优化,尤其是这种最值/顺序之类的问题,可以多考虑数据结构优化。

继续阅读“[补题][贪心][数据结构优化][数学] Gym 101775B Scapegoat”

[逆向思维][差分][细节][补题] Gym-101775J Straight Master

自己思考的时候问题出在哪儿呢?还是没有挖掘和抓住问题的本质特征:要分成一段一段的,肯定是从一段一段的堆起来的过程过来的,如果能把这个过程还原,就可以判断出来是不是满足要求。一段的话,就有开头和结尾,然后开始找开头和结尾就可以了。自己的具有猜想性质的算法,如果不能及时证明,则应该换思路或者让队友去写样例试图证明,或者打样例表。

想出来差分之后,还有一个细节是如何判断3这个界限,其实有更简单的判断方法但是我这里写复杂了。但是整个题目重点还是在于逆向想到差分。

2019.7.10更新:今天翻到这个题发现自己以前写的是真诡异,写了个新的清爽版本。。。 继续阅读“[逆向思维][差分][细节][补题] Gym-101775J Straight Master”