CF edu 56 & AT Grand 029 游记

今天 AT 和 CF 刚好连上了，于是就都打了一下。

关于模板

今天心血来潮把用于在线比赛的模板换了一下，加了点东西，然后发现 rep(1,l,r) 写起来非常不顺手..保留了部分比较好用的。

测试的时候忘记开数组了（都是些什么sb错误），然后以为 ll 不能作下标，于是没有 #define long long，然后 CF 挂惨了..

AtCoder

上一场打的 Beginner，这场难度正常多了。

A 是个值域为 $2$ 的逆序对..

B 用 multiset 乱搞了一下，对于每个数枚举组成的数，然后从大到小匹配，不知道是不是正解，反正过了，而且是 $log^2$ 的。

C 感觉挺可做的..可能有细节没调出来，赶着回酒店打 CF 就没有继续调了..

D 一开始还在想博弈论完全不会..然后仔细看了一眼，如果 A 不走，B 就会不走，就结束了；所以 A 一定能走则走。然后就随便做了。

只不过 AT 的 rating 真的涨的好快..

Codeforces

ABC 三道 spj ？？？

都是随便构造就能做的..

然而 C 一开始忘开 ll 了…..

D 黑白染色一下，连通块内两种节点分别有 $a$ 个和 $b$ 个答案就是 $2^a+2^b$ ，把每个连通块的答案加起来就好了。

由于 $O(nq)$ memset 会爆掉，不能 memset 整个数组，于是愉快地在开了 ll 的情况下 memset(…sizeof(int)…)；发现了之后不小心把开 int 的另一个数组也改成 memset(…sizeof(long long)..) 了.. 开场 $40$ 分钟的时候这 $3$ 个关于 ll 的罚时让我排名翻了三倍…

于是，A 了 D 之后我就在板子里加上了 #define int long long。

看了会儿 E 不会做，然后一看 standing，惊奇地发现 G 有一堆（$15$ 个，当时 E $7$ F $1$）人 A 了，然后一看，就是POJ 2926+动态RMQ…

感觉自己几年没有写过普通线段树了（最近写的全是平衡树/动态开点线段树），写了半个多小时还写错了..毕竟是 CF，应该去复制个模板才对的…一交，MLE 了，woc我好不容易#define int long long了就是这个结果？？改成 int，跑了 $5.4s$，巨方，于是手动开了 O3，$4.8s$ ，但重交竟然没有罚时。应该去找个 BIT 动态求 RMQ 的模板的…

看到 halyavin 参赛了，感觉自己要 fst ，赶紧把博客写了睡觉去。

UPD

halyavin 竟然没有 hack…然而 D 有一堆 memset 整个数组的，我也去 hack 了一个（edu hack $\sqrt{}$）。

没有 fst，第一次 A $5$ 题，上 $2k$ 了，感觉海星。

UUPD

题解 CF1093D 【Beautiful Graph】

题解 CF1093G 【Multidimensional Queries】