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

难度

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

题意

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

数据范围

$2\le N\le 262144$

样例输入

$N4$ $a_1,a_2\cdots 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 之间的数字都是 s while(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; }