多校NOIP31

本文主要是介绍多校NOIP31，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

T1：

　　考场上认为是简单题

　　首先的思路为容斥原理，考虑钦定行或列满足条件

用总情况数减去不合法情况数即可，考虑的是反演，问

题如下：不合法方案数的计算公式，于是考虑二维反演

暴力容斥，然而仍然无法解决本质问题

　　于是考虑问题的形式，这也是计数问题我遇到不多

的一种套路，发现可以归纳成上下两峰的形式，于是考

虑对于这一类图形的计数，我的问题在于一边考虑计数

一边考虑如何不重复，导致无法继续进行思考，事实上

对于图形计数一般抽象为数学模型，考虑一种方法为将

其抽象为插板法，转化为严格形式进行插板，每个板代

表一个数，另一种方法为转化为轮廓线计数。

　　于是将问题分为两种情况，水平线分割与垂直线分

割枚举线位置，枚举两峰坐标即可，前缀和优化即可做

到O(nm)

T2：

　　原题没有做出来，考虑问题形式：求最远点，实际

上等价于求树的直径，于是发现利用类似的方法可以证

明答案一定为树的直径两端点之一，于是考虑动态维护

树的直径，容易想到离线操作倒叙进行，将删边转化为

加边，那么形成的联通快的直径一定为原联通快四个直

径端点中的两个，最后直接求两点距离即可

　　由于删边加边本质上没有改变树的结构，而每次查

询距离的两点一定在同一联通快，因此可以采用树链剖

分进行维护

　　注意思考问题的形式

T3：

　　考场用二维差分+二分降低的复杂度，然而瓶颈在于

二维差分

　　考虑本质上是求若干矩形在每个点的覆盖次数，考

虑扫描线，从上往下扫描，将矩形做差分处理即可，发

现统计出现次数大于k的并不容易，考虑k很小，于是维

护小于k的情况，于是线段树上开桶维护前k小的数即可

　　注意观察数据范围

这篇关于多校NOIP31的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！