题意
有(N)个点，每个点有一个点权(w_i)（有正有负）
现在有两个人甲，乙，分别站在位置(1)与位置(n)，此时它们身上的金钱分别为(w_1)与(w_n)
在两个人行进的过程中，每经过一个点(x)，它们身上的金钱就加上(w_x)
当两个人在都到达同一点时，两个人都停止移动，此时若甲身上的前比乙多，则甲胜；如果比乙少，则甲负；否则甲乙平局
现在两个人都采取最优策略，求最后甲是输，赢还是平
(N leq 1e4,T=10,|a_i|leq1e4)
解法
(O(N^2))做法
这个题还算良心
有一档部分分(Nleq 100)，能获得(90pts)
然而愚蠢如我当然是没有拿到的
考虑(DP/)记忆化搜索
设一个状态(f[l][r][0/1])为甲在(l)，乙在(r)，对于甲(/)乙是胜，负还是平（用(1,-1,0)分别表示）
考虑对于一个点(x)，如果两个人最终在点(x)相遇，我们能够很方便的判断输赢情况：
这样，我们可以(O(n))预处理出所有的(f[x][x])
思考转移
对于一段区间(l...r)，我们可以发现：
如果(f[l+1][r][1])与(f[l][r-1][1])中有一个为必败态，那么(f[l][r][0])必胜
因为甲为先手，它可以控制当前这个状态走向(f[l+1][r])还是(f[l][r-1])让乙失败，因此总能走向一个必胜态
如果(f[l+1][r][1])与(f[l][r-1][1])均为必胜态，那么即使先手甲也无法逆转局势，只能败
否则为平局
这样转移是(O(N^2))的
(O(N))做法
考虑(N)为偶数的情况：
我们可以发现，整场游戏的结局只与点(frac{N}{2})与(frac{N}{2}+1)有关
对于每个状态，双方都有唯一的必胜策略：
设(f(x))为(x)点的状态，我们可以进行如下的讨论：
如果(f(frac{N}{2})=1)或者(f(frac{N}{2}+1)=1)，甲必胜
对于这种情况，有如下的必胜策略：
如果(f(frac{N}{2})=1)，甲把乙向左移一格，此时甲与乙关于(frac{N}{2})对称
否则甲自己向右移一格，甲乙关于(frac{N}{2}+1)对称
设对称点为(x)
接下来是乙进行移动：我们可以发现，无论乙选择哪种方式移动，甲总可以(lfloor)模仿( ceil)乙的操作，让每一轮操作甲乙始终关于点(x)对称
我们会发现最后两个人一定回来到点(x)，并且最后一个进行操作的一定是甲
所以此时甲必胜
如果(f(frac{N}{2})=f(frac{N}{2}+1)=0)，乙有唯一的必胜策略
同样，(lfloor)模仿( ceil)甲的操作，最后一定能使甲来到必败点
否则两者平局
对于(N)为奇数的情况，我们可以枚举分别判断甲进行操作(1)与操作(2)的情况：
由于甲进行一次操作以后，问题转化为偶数的情况，只不过此时的先手是乙
只要判断乙的胜负状态就可以判断甲的胜负状态了
代码
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
int t, n;
int a[N], l[N], r[N];
int main() {
freopen("come.in", "r", stdin);
freopen("come.out", "w", stdout);
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", a + i);
l[0] = r[n + 1] = 0;
for (int i = 1; i <= n; ++i) l[i] = l[i - 1] + a[i];
for (int i = n; i >= 1; --i) r[i] = r[i + 1] + a[i];
if (n & 1) {
int x = n / 2, y = n / 2 + 1, z = n / 2 + 2;
if ((l[x] > r[x] && l[y] > r[y]) || (l[y] > r[y] && l[z] > r[z]))
puts("win");
else if ((l[x] >= r[x] && l[y] >= r[y]) || (l[y] >= r[y] && l[z] >= r[z]))
puts("tie");
else
puts("lose");
} else {
int x = n / 2, y = n / 2 + 1;
if (l[x] > r[x] || l[y] > r[y])
puts("win");
else if (l[x] >= r[x] || l[y] >= r[y])
puts("tie");
else
puts("lose");
}
}
return 0;
}