更差的閱讀體驗

首先，我們預處理出 \(f_i\) 表示當進攻能力為 \(i\) 時防守能力最大能有多少。

對于一組詢問，假設我們派出的進攻、防守兵力分別為 \(a,d\)，對方分別為 \(a',d'\)。那么我們考慮己方和對方進球 \(\max(0, a-d')\) 和 \(\max(0, a'-d)\)。由于我們只需要考慮自己贏或打平的情況，因此可以分以下三種情況考慮：

• \(a-d' \le 0\)。則此時不妨直接讓 \(a = 0\)，這樣 \(d\) 盡可能大，可以讓 \(a' - d\) 盡可能小。如果 \(a' - d \le 0\)，則有可能打平。
• \(a-d' > 0, a' -d\le 0\)。則把 \(d\) 換成 \(f_{a}\)，有 \(a' - f_a \le 0\)。我們預處理出 \(f\) 的后綴最大值就能判斷。
• \(a-d' > 0, a' -d> 0\)。則還是把 \(d\) 換成 \(f_{a}\)，有 \(a-d' > a'-f_a, a+f_a > a' + d'\)。因此只要預處理出 \(f_a + a\) 的后綴最大值就能判斷。

預處理 \(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;
}