模拟17 题解

2019-08-11

模拟17 题解

T1[A. 入阵曲]

60%算法

维护一下某一列的从第一行到这一行和二维前缀和

然后枚举上下左右边界,$O(n^4)$

100%算法

省掉左右边界的枚举,改为从左向右扫一边,记录总和%k的余数,并放入桶中,可以发现,如果这个值出现过,那说明这个位置的总和减去那个位置的差(即这个区间)是k的正倍数

 

T2

又是个贪心。。

对于一个节点,它要被覆盖,驻扎点只有是它的第k级父亲节点时可以最优,越往上越优,因为这样覆盖的就会更广,根节点特判

实现,bfs倒序枚举每个点,up找到其父节点,并且向下标记

 

模拟17 题解

模拟17 题解

原文地址:https://www.cnblogs.com/casun547/p/11336903.html