UOJ Logo qmqmqm的博客

博客

BJOI 2018 day1 题解

2018-05-11 21:28:20 By qmqmqm

题目背景来自于 Codeforces 的 rating 四人组。

毒瘤.jpg

#2491. 「BJOI2018」求和

可以发现答案是由连续的一段或两段 $k$ 次方和组成的。由于 $1 \leq k \leq 50$, 可以直接 $O(nk)$ 预处理,然后每个询问找出最近公共祖先,使用单次 $O(\log n)$ 的算法即可通过。代码难度和思维难度都很小,现场有接近一半的选手 AC 了这个题目。

原本这个题目是有树形态修改的操作的,但感觉这样一来这场比赛对刚接触省选的选手就太不友好了,就改成了一个 NOIP 难度题。

#2492.「BJOI2018」二进制

首先很容易注意到一个区间能否重排成 $3$ 的倍数只与其中 $0$ 和 $1$ 的个数有关。

如果其中有偶数个 $1$ ,那么将所有 $0$ 放于高位,这个数就是 $2$ 的偶数幂次减一,是 $3$ 的倍数;如果其中只有一个 $1$,那么总是一个 $2$ 的幂次,无法排列成 $3$ 的倍数。如果有奇数个 $1$ 且没有 $0$ , 是 $2$ 的奇数幂次减一,不是 $3$ 的倍数;有奇数个 $1$ 且只有一个 $0$ , 是 $2$ 的偶数幂次减一再减去一个$2$ 的幂次,不是 $3$ 的倍数;如果有至少三个 $1$ 且有至少两个 $0$,可以组成 $10101_{(2)}$,然后将所有其余 $1$ 放到低位,所有其余 $0$ 放到高位,形成 $3$ 的倍数。综上,不能重排的情况只有两种: 奇数个 $1$ 和不超过一个 $0$,只有一个 $1$。观察到这些区间要么只有一个 $1$ 要么只有一个 $0$ 用两个set维护所有 $0$ 和 $1$ 的位置然后查询前驱后继,用树状数组维护即可,复杂度 $O(n\log n)$(认为 $m$ 和 $n$ 同阶)。这个题目现场每个部分分都有不少人,有五六个高水平的选手 AC 了,是比赛的主要区分度题。

#2493. 「BJOI2018」染色

我们现在把自己当做 master,考虑如何构造集合卡掉 pupil。

明显只要所有点的集合相同就能卡掉不是二分图的情况,而且不同的连通块互不影响,度不超过 $1$ 的节点也可以去掉。所以现在我们只考虑所有节点均有至少两条边的二分图。

对于完全二分图 $K_{3,3}$, 样例已经给出了构造;对于完全二分图 $K_{2,4}$,只要一边是 $(A,B)$ 和 $(C,D)$,另一边是 $(A,C)$ ,$(A,D)$,$(B,C)$,$(B,D)$ 即可。然后如果图中有两个偶环有不超过一个公共点,可以使用一个限制偶环点染色的方法卡掉,即一个点是 $(A,B)$,与它相邻的两个是 $(A,C)$ 和 $(C,B)$ ,这样之后的点就不能染 $C$ 了。

现在我们的图只有两种情况了:偶环和两个度为 $3$ 的节点,其中有三条不相交的路径。对于偶环,如果其中两个相邻节点的集合不同,则可以一个节点染一个另一个集合没有的颜色,然后顺着环染即可,所以答案为 YES;三条不相交的路径,只有长度为 $ 2-2- $ 偶数才为 YES,因为对于 $ 2-4-4,1-3-3$ 均有卡掉的方法,而如果相邻两个度为 $ 2 $ 的节点,可以他们和某一边选相同的颜色集合,这样颜色交替变化,相交部分还是相同的。

现在我们只需要使用类似最短路或类似拓扑排序的方法去掉度不超过 $1$ 的节点,然后对每个联通分量判断是否是偶环或 $ 2-2- $ 偶数即可。复杂度 $O(m)$。

这个题目现场有一个人使用奇怪的双连通分量方法 AC 了本题,另有人判断了一部分情况获得了 60 分,少数人写了 20 分暴力,大部分人写了 10 分的判断二分图。

论毒瘤

2018-02-12 14:02:13 By qmqmqm

卡常题目万口传,至今已觉不新鲜。江山代有OJ出,各领风骚一两年。

拯救NOI分身术

2018-01-10 08:59:25 By qmqmqm

目前上的分身术题目,std在官方数据用时平均只是其他代码的一半思考熊,但仍然出现了TLE的情况炸弹熊,而其他代码又因为错在了一些特殊情况上导致97捂脸熊,所以寻求能够ac这个题的代码作为std。

NOI2017四题出锅

2017-08-19 08:21:34 By qmqmqm

NOI2017的六道题目中,居然有四道题目出现了问题,并且day2的三个题目全部出现问题:

day1t1在数据范围中$|a|=1$的数据中,出现了$a=0$的情况,数据不符合范围;

day2t1的spj当选手输出了多余内容时,仍然将选手输出判为正确;

day2t2的std出现了爆int导致答案错误

day2t3的std出现了爆int导致运行时错误

【CTSC2017】投影 应该开放hack

2017-06-05 20:08:39 By qmqmqm

【CTSC2017】投影是一道随机化的题目,但其前30%的数据不是随机生成的,可以通过val来判断是否合法,std也使用了专门的确定性算法来进行解决。

但在这部分数据范围上,通过特殊构造的数据,如果仍然使用后70分的随机算法,可能找不到最优解。所以我认为应该开放这个题目的hack。

qmqmqm Avatar