Day 05/19/2020 div2training

E题也补了


前排提醒,还未补E
场上写了ABC1C2 补了D

A题脑补题。
B题二分搜索找一个串包含字母ABC
C1:给出一个n=2 x的正多边形,x是偶数。问包围他的最小正方形,比划可知,正方形最小的情况就是贴合四条边。
C2:给出一个n=2
x的正多边形,x是奇数。问包围他的最小正方形,原以为和上一题一样,结果这题要考虑的东西挺多的。首先是特例,六边形的时候我直接特判Y4bDVf.th.png
然后看十边形,Y4bcGQ.md.png大概长这个样子。
奇数的时候不再是边对边相连,而是顶对顶,这样更优。通过画图和不断缩放可知,边要和最外面的那个顶点相切,而最外面的切点,就是最中间的那个点。找到规律之后,所有东西都迎刃而解了。剩下的就是简单几何问题了。
D:在28兆空间内,有什么办法可以模拟n=1e6,且元素均<n 的multiset吗,操作有:插入一个元素,删除第x大的元素。经过这些步骤之后,随便返回一个multiset内的元素。
1、树状数组:

int lowbit[1000005];

void update(int i,int k){
    while(i0){
        res += c[i];
        i -= lowbit[i];
    }
    return res;
}
    for(int i=0;i

先贴一个树状数组的板子。一开始我是用的树状数组来写的。结果发现tle了。百思不得其解之后,我把cin改成了scanf,再把变量声明定义在外面,再把其他乱七八糟的预处理定义在外面,最终t13. 然后改成C++11过了。玄学过题发

最终的复杂度是Nloglog,换算过来就是NsqrtN n=1e6,所以刚好卡住。能过就意味着常数非常的小。

然后第二种做法是线段树:区别就在于线段树有个树上query的过程,这样就能直接找到对应的地方,再进行update,以至于最后的复杂度是Nlog,少了一个log,就能完美通关。

差个第三种写法,待补


第三种写法:
因为是任意输出一个即可,那么有没有可能直接输出最小的那个呢?这样,我们先假设数x是剩下的set里面最小的那个数。
然后On算一下小于等于x的有多少个,On模拟insert和delete的过程算一下最后小于等于x的有多少个。
如果最后cnt大于0.那么意味着最后的set是存在元素小于等于x的。但至于是不是x,不得而知,所以得进行二分查找。
不断的逼近x的最小值。


E题:给一个无向图标号(1,2,3),要求是相邻两个数的绝对值得是1.意味着唯一的偶数2十分的重要。
1和3是可以任意放的,所以问题不大。
然后的话,解法分为两步:
1、找到所有联通块,每一个联通块分两部分。
2、dp所有情况,即可。

您可能还喜欢...

发表评论

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