\(\mathcal{Preface}\)
分数 \(100+100+100+25=325\)。
菜死了。
\(\mathcal{Problem \space{} A}\)
Tag:循环,暴力枚举。
送分题,由于 \(1 \le l \le r \le 3000\) 且 \(1 \le nn \le 3000\),由此可知平方级别的时间复杂度是完全可以接受的,因此直接枚举除数 \(k\) 然后挨个算出值取 \(\min\) 就好了,注意如果有相同的取最小一个。
\(\mathcal{Problem \space{} B}\)
Tag:因数,循环。
定 \(ans=10^{k}\),然后看看,\(n\) 中有 \(x\) 个 \(2\) 的因子,就让 \(ans \to ans \div 2^x\),有 \(y\) 个 \(5\) 的因子,又让 \(ans \to ans \div 5^y\),最终的 \(ans\) 便是答案。
\(\mathcal{Problem \space{} C}\)
Tag:完全二叉树的性质,二叉树。
记录以每个点为根的子树包含的字母的情况。
如果这个包含字母情况中,只有至多 \(1\) 种字母的数量为奇数,才可以形成回文。
一开始先预处理最初的情况,算出答案输出。
然后考虑修改的情况,如果节点 \(u\) 上的字母被改动了,受影响的子树只有以自己的祖先节点为根的子树才会受到影响(自己以及父亲算作特殊的祖先)。而又由于题目给定的是一棵完全二叉树,因此深度只有 \(\log n\),暴力修改没有问题。
先判断之前有没有,之前有的话先让答案减一,然后再看改变之后有没有,改变之后有的话就让答案加一。
\(\mathcal{Problem \space{} D}\)
Tag:构造,思维,逆序对。
好神的题目,好神的做法!
由于要求逆序对和顺序对的数量相同,不难算出逆序对和顺序对的数量都是 \(\frac{n \times (n-1)}{4}\)。可以先让 \(sum = \frac{n \times (n-1)}{4}\)。
首先考虑构造足够的顺序对。如果在序列前面放进一个 \(1\),那么会贡献 \(n-1\) 个顺序对,而不会出现逆序对;如果接着放进一个 \(2\),那么又会再贡献 \(n-2\) 个顺序对,同样不会出现逆序对;以此类推,如果顺着来的话,放一个 \(x\),就会贡献 \(n-x\) 个顺序对。
那么考虑依次枚举 \(i\) 从 \(1\) 到 \(n\),如果当前的顺序对数量 \(cnt\) 加上这一轮新加的 \(n-i\) 个之后还没有够到 \(sum\),也就是说当 \(cnt+(n-i) < sum\) 的情况下,直接让 \(a_i = i\),标记 \(i\) 数字已经填写,然后让 \(cnt \to cnt+(n-i)\)。但是如果超过了,就要往后找到一个恰好的 \(x\),使得 \(cnt + (n-x) = sum\),并让 \(a_i = x\),标记 \(x\) 已经填写;标记完了之后,顺序对的数量也就已经达标了,这个时候只要填入足够多的逆序对就可以了,很简单,把还剩下没填的数字全部倒序挨个填进 \(a\) 里就行了。
最后输出即可,代码很简单。
\(\mathcal{Summary}\)
T4 的构造方法确实挺厉害的,构造也确实不是强项,之后继续加油吧。正好又多知道一个构造的方法了,不断累积经验肯定也是有帮助的!