容易的多元拉格朗日反演练习题

你说得对，但确实和题目没有一点关系。

模拟赛记录下午出。

题面

看到 Alice 和 Bob 就知道是什么题了。

思路

这个题开始先胡乱想想，发现按照博弈论的思路，那么每次 Bob 行动一步后，Alice 需要有对应的策略，也就是说，若 Alice 必胜，这次行动应该是固定的最优策略步。

然后再代入一下，如果你是 Alice，每次肯定是优先拿去较小的数，这样才能获得更大的操作空间。

然后 Bob 为了阻止你胜利，同样也会拿较小的数，这样就得到了我一开始的错误的想法：把数按非降序排列后，若奇数位的和满足属于区间 \(\left[l,r\right]\)，则 Alice 必胜。

但思考一下就能知道这是个错解，例：

4 5 6
1 3 5 6

这种情况下，Alice 只有拿到 \(1\) 和 \(5\) 才能胜利，而它们恰好都在奇数位上，所以按如上思路答案是 Alice，但只要 Bob 拿到其中一个 Alice 就不可能赢了。

于是考虑转换思路。我们发现，\(n\) 为偶数时没有什么突破口，比如上面的例子中 Bob 的最优策略就不再是固定于某几个位置上的数。那么尝试考虑 \(n\) 为奇数时，Alice 赢，Bob 先行动的情况，那么此时主动权就来到了 Bob 手上，他每次行动后，Alice 会有一个最优策略来应对 Bob 的行动。

这样的话，整个数列会被分成若干个数对和一个剩余的数。不难发现，数列中相邻的两个数配对是 Alice 赢的最好策略。那么再结合上面假了的猜想，Bob 每次取任意一个数，那么Alice 的最优策略就是选与 Bob 配对的另一个数。

现在的局面是，Bob 具有主动权（先手），而最后剩余的数是 Alice 决定的，因此我们可以枚举最后剩余的数，这样 Alice 所选数之和的上下边界就确定了，因而可以得出在该情况下，Alice 是否必胜的结论。

分别求出奇数位和偶数位上的和，枚举每次最后剩余的数，由于它可能会影响数位上的数的变化，我们对于每类数位要开两个变量，在这里先统称为 \(A\) 与 \(B\)，表示奇数位和与偶数位和，那么显然 \(SumAlice\) 只能取到这个范围内的值，因此若 \(l\le A\) 并且 \(B\le r\)，那么 Alice 是必胜的。

现在已经得到了 \(n\) 为奇数，Bob 先手的做法。迁移到 \(n\) 为偶数上，我们只要先排去 Alice 先手的那一步不就可以了吗。所以先枚举 Alice 先手所选的数，（当然超过 \(r\) 的数选了直接就寄了，这时候结束枚举就行了），再枚举最后剩下的那个数，求出奇偶数位上值的和，按上述方法判断即可，这里判断要加上开始枚举的 Alice 首选的那个值。复杂度是 \(\mathcal{O(n^2)}\) 的，\(n\le 5000\)，显然能过。

还有，注意 \(a_i\) 的值域是 \(10^9\) 级别的，计算和的时候要开 long long。

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Ratio=0;
const int N=5005;
int T,n;
ll l,r,a[N],b[N];
namespace Wisadel
{
	short main()
	{
		scanf("%d",&T);
		while(T--)
		{
			scanf("%d%lld%lld",&n,&l,&r);
			bool Alicewin=0;
			for(int i=1;i<=n;i++) scanf("%d",&a[i]);
			sort(a+1,a+1+n);
			for(int i=1;i<=n;i++)
			{// 先枚举 Alice 首选
				if(a[i]>r) break;
				ll jied=a[i],oued=a[i],ji=0,ou=0;
				// 分别表示枚举过和未枚举的奇偶数位之和，这里提前就把 a[i] 加上了
				// 这里枚举与否取决于最下面循环的进行程度，感性理解一下
				for(int j=1;j<=n;j++)
					if(i!=j) b[(j>i?j-1:j)]=a[j];
				for(int j=1;j<n;j++)
					if(j&1) ji+=b[j];
					else ou+=b[j];
				for(int j=1;j<n;j++)
				{// 枚举最后剩下的数
					if(j&1) ji-=b[j];
					else ou-=b[j];
					if(l<=jied+ou&&oued+ji<=r)
					{
						Alicewin=1;
						break;
					}
					if(j&1) jied+=b[j];
					else oued+=b[j];
				}
				if(Alicewin) break;
			}
			if(Alicewin) printf("Alice\n");
			else printf("Bob\n");
		}
		return Ratio;
	}
}
int main(){return Wisadel::main();}

代码中有一句 if(l<=jied+ou&&oued+ji<=r)，赛时调了好一会才改出来。如果你枚举的这个数是奇数位上的，那么之后的奇数位数之和其实是开始的偶数位数之和，偶数位上的数同理。无论如何，二者上下界关系没有变。