20连测1 赛后总结

赛时

T1

赛时没想出正解，打了一个 \(O\left(n^2\right)\) 的暴力。得了 \(50\space \texttt{pts}\) 。其实赛后想想还挺简单的，公式就是： \[ \sum_{i=1}^n\left(n-1\right){a_i}^2-\sum_{i=1}^{n}\left(-2a_i\cdot\sum_{j=i+1}^{n}a_j\right) \]

T2

差一点就想出正解来了，把 \(\mod 2\) 写成了 \(\mod 3\) ，结果爆零了。

T3

这个题是全场最简单的一道题，画一画图就满分了。

T4

赛时写了个 DFS ，赛时样例过了，但是交上去爆零了。

预估分数

\(50+30+100+50=230\space\left(\texttt{pts}\right)\)

实际分数

\(50+0+100+0=150\space\left(\texttt{pts}\right)\)

---

不足之处

• T1推公式推的并不仔细，就算错了也没有认真查错，否则拿个 \(50\space\texttt{pts}\) 还是没有什么问题的。

• T2并没有认真思考，就是一个进制转换问题，其实赛后看了题解觉得比T1还简单。

• T4真是吃了大亏，连这种基本算法都能写错，说明对算法的熟练度不高，平时还是要多刷题才行。

---

solution

T1

上面都有公式，没什么好说的。

T2

假设 \(m\) 代表这个数在二进制下非零的位数，如果 \(m\leq k\) 且奇偶性相同的话，可以，否则不行。

T3

没什么好说的。

T4

一道 BFS 分层最短路，在加上一些 DP ，就可以算出最小的字典序。

---