NOIP2018游记

命运的钟摆已经开始摆动了,谁也无法阻止这一切的发生,唯能紧握住自己的命运,让他不在时光之中暗淡,即使命运待你不公,也要勇敢的面对,即使这是一件困难的事情,也要去追逐,去拼搏,为了,曾经没有实现的诺言,为了自己的梦想。
NOIP2018加油! ......  查看更多

[SCOI2005]最大子矩阵

[SCOI2005]最大子矩阵
DP就好

[POI2015]Wilcze doły

[POI2015]Wilcze doły

枚举右区间,维护一个长度为d的区间使其区间和单调递减并且顺序是从左到右

[POI2006]Szk-Schools

[POI2006]Szk-Schools
最小费用最大流,拆点建边跑一次就可以了。

[POI2012]Letters

[POI2012]Letters
树状数组求逆序对

[JSOI2016]最佳团体

[JSOI2016]最佳团体
树形DP+二分,二分答案,DP验证答案是否正确。

[ZJOI2007]时态同步

[ZJOI2007]时态同步
贪心。

很明显最后每个叶节点的到达时间应该是一开始的到叶节点的时间的最大值。所以每个点增加的时间之和是确定的。越靠近根,使用一次增加的贡献就越大,所以贪心即可

[APIO2010]特别行动队

[APIO2010]特别行动队
简单的斜率优化题目【其实推公式推了我一个多小时】

[USACO2018]Out of Sorts

[USACO2018]Out of Sorts
神仙数论题,重点是分析一下他排序的分割点。膜了题解还是觉得这题很神仙。

题解考虑的是对于每一个数他会被算多少次,也就是他递归的层数
这个我也想过,但是我完全没有思路啊TAT
然后一个数,他的递归层数是多少呢?
显然地,就是剩下他一个的时候
也就是他左边的出现了分隔符,右边也出现了分隔符
于是,问题就转化为,某一个分隔符出现的时间
然后一个点的答案就是两个分隔符取max
考虑一个数i前面的分隔符怎么得到
其实就是所有比i−1i−1小的数,位置的最大值减去i−1i−1
至于为什么,你结合一下我上文说的  ......  查看更多

[POI2018]Prawnicy

[POI2018]Prawnicy
这题可以采用贪心策略,假如我们已经确定了最终区间的左端点L,那么我们选择的区间一定是左端点在L左边,且右端点最右的K个点。所以我们将所有区间按左端点排序,用小根堆维护左端点在左边,且右端点最大的K个点。每次用第K大值更新答案即可。 ......  查看更多