B Solution

yummy · 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)