xjoi noip模拟训练45

今天的题目好不清真啊.

r1:
通过暴力打表找规律可以发现一个很暴力的规律

也就是在区间T取得足够大的时候,后面的值会成比例扩展

于是我们通过人类智慧找到T的最小使得区间稳定的值为115000

然后我这么做就被卡常数了,加了O2并且优化了一下两倍常数就过了

复杂度O(T)

.

t2:

首先讲一下错误的做法:我直接把AB两个点重新构图拆成两个点跑最短路,但是一个简单的数据就被hack了.因为忘记考虑了均衡的情况

正解:

我们可以利用最小生成树的思想,首先对b进行排序(为了最小生成树的操作)

然后我们枚举所有的边,看是否可以成为答案的a

于是我们就要求b,我们可以不断地加边直到满足条件

这里的满足条件判断不是有了n-1条边,而是find(1)=find(n)

复杂度O(m \lg m+mn \alpha n)

.

t3:

首先你要会二维差分

我们定义两个状态

f[i][j]表示下三角的差分数组 g[i][j]边界为n的正方形差分数组

于是维护这个差分我们就可以做到O(nm)的预处理

然后跑两遍预处理含义分别是恢复原数组以及后缀和

这里复杂度为O(n^3)

最后再进行差分还原即可

注意在预处理的时候

我们要注意一下枚举的顺序,不能有后效性

总复杂度O(n^3+nm)

.

今天一题被卡常数了一题暴力好像都打错了..只有60..
gg

发表评论

电子邮件地址不会被公开。 必填项已用*标注