题解：P14011 [POCamp 2023] 珿求 / bootfall

dyc2022 · 2025-09-10 18:00:58 · 题解

更好的阅读体验

首先，我们预处理出 f_i 表示当进攻能力为 i 时防守能力最大能有多少。

对于一组询问，假设我们派出的进攻、防守兵力分别为 a,d，对方分别为 a',d'。那么我们考虑己方和对方进球 \max(0, a-d') 和 \max(0, a'-d)。由于我们只需要考虑自己赢或打平的情况，因此可以分以下三种情况考虑：

预处理 f 直接背包。那么这道题就做完了，复杂度 O(n^3 + q)。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 406
using namespace std;
int n,q,a[N],b[N],f[2][N*N],g[N*N],h[N*N],sa,sb;
int win,lose,draw;
main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&a[i],&b[i]),sa+=a[i];
    memset(f,-0x3f,sizeof(f)),f[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        f[i&1][0]=(sb+=b[i]);
        for(int j=0;j<=sa;j++)
        {
            f[i&1][j]=f[(i&1)^1][j]+b[i];
            if(a[i]<=j)f[i&1][j]=max(f[i&1][j],f[(i&1)^1][j-a[i]]);
        }
    }
    for(int i=0;i<=sa;i++)g[i]=i+f[n&1][i];
    for(int i=sa;~i;i--)
        h[i]=max(h[i+1],f[n&1][i]),g[i]=max(g[i+1],g[i]);
    scanf("%lld",&q);
    while(q--)
    {
        int x,y;scanf("%lld%lld",&x,&y);
        int w=0,d=0;
        if(x-f[n&1][0]<=0)d++;
        if(h[y+1]>x)w++;
        else {
            if(h[y+1]==x)d++;
            if(g[y+1]>x+y)w++;
            else if(g[y+1]==x+y)d++;
        }
        if(w)win++;
        else if(d)draw++;
        else lose++;
    }
    printf("%lld %lld %lld\n",win,draw,lose);
    return 0;
}