Codeforces Round #698 Div2总结——构造题专场

唉。被虐的好惨。D题数论不会做。F题连双向链表都能写挂……感觉思维能力确实是跟不上了。得集中火力大规模的康复训练才行。

一路挂成狗,全程帕金森。

A. Nezzar and Colorful Balls

就统计出现次数最多的数字就行了。没啥好说的,也没啥好题解的。

Submission #111833071 - Codeforces
Codeforces. Programming competitions and contests, programming community

B. Nezzar and Lucky Number

蛮有意思的构造题。手滑T了一发……专门看了一眼官方题解,看不懂他在干啥。感觉我的这个构造一半后暴搜比较简洁。不过只是B题,各种机智做法多了去了,不敢言勇。

Codeforces Round #698 Nezzar and Lucky Number 暴力搜索
题意给你一个d(1<=d<=9),如果数字里面包含这个d,则这个数字是幸运的。现在有q个查询,每个查询给你一个数字,问你这个数字能不能拆成若干个幸运数字的和。

C. Nezzar and Symmetric Array

思维能力不行的直接证据。几乎瞬间想到做法。然后没注意要int64结果RE一发也还自罢了,毕竟老帕金森了。WA7是因为没有判重,题目里说了,生成的数组里,不能重复。太弱了。

Codeforces Round #698 Nezzar and Symmetric Array 构造
首先观察任意两个数,$a_i$和$a_j$。根据题意立刻可知,a中存在$-a_i$和$-a_j$。所以没有必要考虑符号,直接假设$a_i>0,\ a_j>0$。考量$\mid{a_i-a_j}\mid+\mid{a_i-(-a_j)}\mid$可知:如果$a_i>a_j$则这个和为$2a_i$,反之则为$2a_j$。

D. Nezzar and Board

数论,裴蜀定理。别问,问就就是已经不知道裴蜀定理是什么了。已经加入重修队列。


E. Nezzar and Binary String

啊,线段树啥的还是能随手搞得,唯一一个比较顺手的题目。一开始想着正推,去维护区间最新一次检查的查询id。但是太麻烦了,后面想了想还是直接逆推比较舒服。

Codeforces Round #698 Nezzar and Binary String 线段树
显然是线段树。因为每天只能改不超过一半,所以从最终的f开始,每天的状态其实固定的。只需要在下一个状态查询l到r间0的个数,就能知道那天晚上改了什么。

F. Nezzar and Nice Beatmap

我是真的菜。双向链表能写挂?T7的以及WA7的全是因为双向链表挂了。而且不知道为啥挂了。后来在生成结果那加了个如果链表断了就抛异常RE才发现前面搞了半天链表都断了……

int ans = n;
Point now = last;
while (now != null) {
    now.ans = ans;
    ans--;
    now = now.pre;
}
//检查最后跑下来是不是还是n个……结果就不是……
if (ans != 0) throw new RuntimeException();
Codeforces Round #698 Nezzar and Nice Beatmap 几何
题意给你一串点。然后问你这一串点的某种排列能否使得其中任意连续的三点i, i+1, i+2满足由这三点构成的夹角为锐角。如果有这种排列,则输出这种排列。没有就输出-1.题解考量三角形。三角形最多有一个直角或锐角。那么对于任意三点,如果这三个点的排列出来的结果是钝角。那么这三个点换任意一个顺序都是锐角。

太难了。全是构造题。构造题最考思维能力和智商。但问题是这两个我似乎都没有,而且手还特别不稳。我是蒟蒻……