称霸 题解

· · 个人记录

做法一

全部输出 -l，由于出题人凉心，本做法能得 10 分。

做法二

对于每名选手只暴露一次弱点的情况，我们可以直接循环处理。遇到 0 则积累力量，遇到非零的数直接进行挑战，判断力量是否合适即可。期望得分 20。

做法三

每个回合最多只有两种状态，即积攒力量或者发起挑战。我们可以枚举每个回合的操作，找遍所有可能的状态，选回合数最少的。时间复杂度 \rm O(2^{\it n})，期望得分 40。

#include<cstdio>
int n,m,a[10001],ans,cp,cm,b[10001];
bool f[10001];
void dfs(int day) {
    if(ans<=day-1)return;
    else if(cm==m) {
        ans=day-1;
        return;
    }
    else if(a[day]&&(!f[a[day]])&&cp>=b[a[day]]) {
        f[a[day]]=1;
        cp-=b[a[day]];
        ++cm;
        dfs(day+1);
        cp+=b[a[day]];
        f[a[day]]=0;
        --cm;
    }
    ++cp;
    dfs(day+1);
    --cp;
}
int main() {
    scanf("%d%d",&n,&m);
    ans=n+1;
    for(int i=1; i<=n; ++i)scanf("%d",&a[i]);
    for(int i=1; i<=m; i++)scanf("%d",&b[i]);
    dfs(1);
    if(ans==n+1)puts("-l");
    else printf("%d",ans);
}

做法四

发现答案是有单调性的，我们可以二分答案，然后判断是否合法。

判断使用贪心思路：在有限回合内，我们必然尽可能后挑战所有人，因为我们只需判断答案是否合法，则越后挑战，力量越大，成功的可能越高。

即对每个人，我们选他在特定回合数内，出现的最后一次作为挑战回合，其余积累力量就好。

经过分析，二分复杂度 \rm O(\log{\it n})，检验函数复杂度约 \rm O\it(m\log{n})，期望得分 100。

#include <bits/stdc++.h>
using namespace std;

const int maxn=1111111;
int A[maxn],B[maxn],C[maxn],N,M;
bool vis[maxn];

bool check(int n)
{
    memset(vis,0,sizeof(vis));
    for(int i=n;i>=1;--i)
    {
        if(vis[A[i]]) C[i]=0;
        else vis[A[i]]=true,C[i]=A[i];
    }
    int nw=0,cnt=0;
    for(int i=1;i<=n;++i)
    {
        if(C[i]) nw-=B[A[i]],++cnt;
        else ++nw;
        if(nw<0) return false;
    }
    return cnt==M;
}

int main()
{
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;++i) scanf("%d",A+i);
    for(int i=1;i<=M;++i) scanf("%d",B+i);
    int l=1,r=N,ans=-1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    if(ans!=-1) printf("%d\n",ans);
    else puts("-l");
    return 0;
}