【2023NOI模拟赛13】sequence 做题记录

有⼀个⻓度为 $n$ 的序列 $s$，每⼀位为 * 或 +，你需要选择⼀个 $s$ 的⼦序列 $t$，使得 $f(t) \mod 2^k$ 最⼤。

$f(t)$ 表示依次遍历 $t$ 中元素后的 $x$ 值：$i$ 从 $1$ 开始，如果 $t_i$ 为 * 则 $x$ 乘 $2$ ，如果 $t_i$ 为 + 则 $x$ 加 $1$ ，$x$ 初始为 $0$。

注意：⼀个序列 $t$ 为 $s$ 的⼦序列，当且仅当 $t$ 可以通过删除 $s$ 中⼀些位置的元素得到。

$1\le n,k\le 10^6$。

先维护出一个数组 $a$，求出每个 + 后面 * 的个数 $x$，即这个 + 最多可以贡献到 $2^x$，然后让 $a_x\to a_x+1$。

接下来贪心的进位，按 $i$ 从小到大遍历 $a$，若 $a_i\ge 3$ 则让 $a_{i+1}\to a_{i+1}+1$，$a_i\to a_i-2$，注意到这样可以让来自相邻两个 * 的 + 在 $a$ 上留下连续的一段 $1$ 或者 $2$，并且可以避免进了不需要进的位的情况。

然后就可以求出答案了，从高位往低位贪心，设当前是第 $i$ 位，那么：

• 存在 $j\ge i$ 满足 $a_j\not=0$：那么直接让这一位的 $1$ 贡献给第 $i$ 位，$ans_i=1$，并且让 $a_j=0$。注意到由于来自相邻两个 * 的 + 在 $a$ 上留下连续的一段 $1$ 或者 $2$，这些 + 会在答案中留下连续的一段 $1$，所以这样”强扯“过来是可行的，相当于把最后一个 * 从子序列中删去；
• 不存在 $j\ge i$ 满足 $a_j\not=0$：那么要么 $ans_i=0$，要么找到 $1111112$ 这样的一段 $a$ 进位到 $a_i$，由于进位之后这些位置都会变成 $0$，所以直接暴力找即可；

由于高位为 $1$ 一定更优，所以这样贪心是对的，时间复杂度 $O(n)$。

代码如下：

// Problem: #A. sequence
// Contest: Hydro
// URL: http://oiclass.com/d/AKNOI/p/185?tid=63fd6c6355e89e02d91afefd
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>

using namespace std;

const int S=1000005;

int n,k;
char str[S];
int sum[S],a[S*2];
int ans[S];

int main()
{
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
	scanf("%d%d",&n,&k);
	k--;
	scanf("%s",str+1);
	sum[n]=str[n]=='*';
	for(int i=n-1;i>=1;i--) sum[i]=sum[i+1]+(str[i]=='*');
	for(int i=1;i<=n;i++) if(str[i]=='+') a[sum[i]]++;
	for(int i=0;i<=n*2;i++)
	{
		if(a[i]>=3)
		{
			a[i+1]+=a[i]/2-(a[i]&1^1);
			a[i]=1+(a[i]&1^1);
		}
	}
	for(int i=k,j=n*2;i>=0;i--)
	{
		while(j>=i&&a[j]==0) j--;
		if(j>=i) a[j]=0,ans[i]=1;
		else
		{
			int res=-1;
			for(int l=i-1;l>=0;l--)
			{
				if(a[l]==0) break;
				if(a[l]==2)
				{
					res=l;
					break;
				}
			}
			if(res!=-1)
			{
				for(int l=res;l<=i-1;l++) a[l]=0;
				ans[i]=1;
			}
		}
	}
	bool flg=false;
	for(int i=k;i>=0;i--)
	{
		if(ans[i]==1) flg=true;
		if(flg) printf("%d",ans[i]);
	}
	if(!flg) puts("0");
	else printf("\n");
	return 0;
}