【ZJNU 组队赛四：想法题】A：262144

难度

$3.3/10$
赛后一经同学的点拨立马就懂了！(?)

题意

给你一个长度为 $N$ 的数组。每个元素的值为 $1?40$。
你每次可以选择两个相邻的相同的数字，然后把它们合并成一个比原来大一的数字。
询问你可以获得的最大数字。

数据范围

$2\le N\le 262144$

样例输入

$N4$
$a_1,a_2?a_N$
$1,1,1,2$

样例输出

$3$

解释

选择第二个和第三个$1$，合并成$1,2,2$
然后合并成 $1,3$

注意：如果选择第一个和第二个 $1$，合并成 $2,1,2$ 则无法得到 $3$了。

思路

• 合成数字肯定是要从小往大枚举，若从大到小则合完小的数字后又会生成大的数字。
• 对于偶数个相邻的相同的数字，我们可以把他们全部合成。比如 $[s,s,s,s,s,s]$我们全部合成变成了 $[s+1,s+1,s+1]$。
• 对于奇数个相邻的相同的数字，易得我们有两种选择：向左合并或者向右合并。比如 $[s,s,s,s,s]$ 我们可以合成成 $[s+1,s+1,s]$ 或者可以合并成 $[s,s+1,s+1]$
• 对于奇数相邻的情况，我们可以想到，若枚举所有的合并情况时间复杂度会爆炸，也无法写。我们想到，合并完之后，中间的 $s$ 是一定无法再合成出来的。也就是说我们合成完了就把该区域分成了左段和右段，两端相互不影响。
• 那么分析完之后，我们~~（可能会想到）~~那么我们就把所有的情况全部放进来就好了嘛！比如 $[s,s,s,s,s]$，我们就合并成 $[s+1,s+1,s,s+1,s+1]\text{[s+1,s+1,s,s+1,s+1]}[s+1,s+1,s,s+1,s+1]$
• 可以使用双数组优化，来让空间复杂度降低。

核心代码

时间复杂度 $O(58\times N)$
(为什么是58呢，可以算一下262144个40可以和出多少)

/*_ __ __ _ _ | | \ \ / / | | (_) | |__ _ _ \ V /__ _ _ __ | | ___ _ | '_ \| | | | \ // _` | '_ \| | / _ \ | | |_) | |_| | | | (_| | | | | |___| __/ | |_.__/ \__, | \_/\__,_|_| |_\_____/\___|_|__/ ||___/ */
int aa[MAX];		/// 原数组
int tp[MAX][2];		/// 双队列（双数组）
int c[2];			/// c[0] 和 c[1] 记录了双队列的数组大小
int main()
{
    int n;scanf("%d",&n);for(int i = 1;i<=n;++i)scanf("%d",&aa[i]),tp[i][1] = aa[i];c[0] = c[1] = n;int st = 1;int ans = 0;for(int s = 1;s<=58;++s){
    c[st^1] = 0;		/// 清空另一个数组的大小for(int i = 1;i<=c[st];++i){
    ans = max(ans,tp[i][st]);		/// 求较大值/// 若目前数字无法合成（不是s或者是最后一个数字了或者与之后的数字都不同）if(tp[i][st] != s || i == c[st] || tp[i][st] != tp[i+1][st])tp[++c[st^1]][st^1] = tp[i][st];	else{
    int stt = i;int edd = i;/// stt 到 edd 之间的数字都是 swhile(edd + 1 <= c[st] && tp[edd+1][st] == s)edd++;/// 偶数，我们全部合成if((edd - stt + 1)% 2 == 0){
    for(int j = 1;j <= (edd - stt + 1)/2;++j)tp[++c[st^1]][st^1] = s+1;}else{
    /// 奇数，我们两种情况都放进来，中间用 0分隔开即可for(int j = 1;j <= (edd - stt + 1)/2;++j)tp[++c[st^1]][st^1] = s+1;tp[++c[st^1]][st^1] = 0;for(int j = 1;j <= (edd - stt + 1)/2;++j)tp[++c[st^1]][st^1] = s+1;}i = edd;}}st ^= 1;		/// 换到下一个数组}printf("%d",ans);return 0;
}