自动搬运

查看原文

来自洛谷，原作者为

	yummy 这个人是时代的眼泪，什么也没有留下

搬运于2025-08-24 22:43:44，当前版本为作者最后更新于2022-12-31 20:34:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Subtasks 1 and 2

Subtask 1 直接枚举每条消息是否撤回，然后 $O(m)$ 判断一下，时间复杂度 $O(m2^m)$。

首先我们考虑一件事，撤回别人的消息好还是自己的消息好。

如果你撤回一条别人的消息 $A$，在 $A$ 之后第一条自己的消息是 $B$，那么：

• 如果撤回 $A$，那么消息 $B$ 排名减 $1$，还可能导致惩罚；同时 $B$ 之后的消息排名减 $1$。
• 如果撤回 $B$，那么它不可能造成惩罚，之后的消息排名仍然减 $1$。

因此，撤回别人的消息总是不优于撤回自己的。

枚举每条自己的消息是否撤回，然后判断一下，时间复杂度 $O(n2^n+m)$。

Subtask 3

我们发现，是否撤回后面的消息，不影响前面消息的排名。

因此，如果前面的消息都已经决定是否撤回，那么当前消息如果会导致惩罚就删掉，否则不删掉。

如果删掉一条消息，那么之后的消息排名要全部减 $1$，时间复杂度 $O(n^2+m)$。

Subtask 4

每条消息都是小 A 发的。不管他删多少条消息，总是占据消息记录的前若干条。

因此，最多留几条消息，相当于 $f$ 有几个前缀 $0$。

Subtasks 5 and 6

在 Subtask 3 基础上，不实时更新每条消息的排名，而是需要决策时，它之前撤回几条消息，排名就减去几。

时间复杂度 $O(n+m)$，常数极小。

参考代码（C++）：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005];
char f[1000005];
int main()
{
	int withdrawn=0; 
	scanf("%d%d%s",&n,&m,f+1);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(f[a[i]-withdrawn]=='1')
			withdrawn++;
	}
	printf("%d",withdrawn);
	return 0;
}

参考代码（Python 3）：

input()
f="0"+input()
cnt=0
for i in map(int,input().split()):
	cnt+=f[i-cnt]=='1'
print(cnt)