\(\texttt{2024.10.4 赛后总结}\)
比赛记录
成绩： \(100+100+20+0=220\space\texttt{pts}\)
补题：\(100+100+100+0=300\texttt{pts}\)
难度：\(\textcolor{orange}{\texttt{橙}}\space\textcolor{orange}{\texttt{橙}}\space\textcolor{yellow}{\texttt{黄}}\space\textcolor{green}{\texttt{绿}}\)
反思
骗分一定不要输固定值！
骗分一定不要输固定值！
骗分一定不要输固定值！
重要的事情说三遍。
题目
A
题面
在 \(l,r\) 之间选一个数 \(x\) ，求 \(x\) 质因子个数的最大值。
思路
可以证明，当 \(x=2^n\) 答案最优，而 \(2l\leq r\) ，那么在区间中一定有 \(x=2^n\) ，答案就是正整数 \(n\) 。
代码重点
输出记得下取整。
B
题面
给定 \(l,r\) ，求 \(l|(l+1)|(l+2)|\ldots|r\) 。
多组数据。
思路
按位拆分，如果区间里有一个数在这个位上的值为 \(1\) ，就加上这个位在十进制中代表的值，总复杂度 \(\Theta(T \log^2 r)\) ，可以接受。
代码要点
对于多组数据记得清空。
C
题面
找出没有重复元素的，最长的，字典序最小的子序列，其中奇数位的字典序要乘 \(-1\) 。
思路
用 set
维护每个数最后出现的位置，每次取最前面的就是答案。
代码要点
这样做可能超时，要用单调队列优化算法。
D
题面
抽象的题面。
思路
一道DP好题。
令 \(dp_{i,j}\) 表示到了 \(i\) 划分为 \(j\) 段，第二层枚举到 \(k+1\) ，然后加上一些前缀和优惠，可以接受。
代码要点
记得取模。