假如战争明天爆发

发表于 |
字数统计: 269 | 阅读时长 ≈ 1
  • Code Level:
  • Thinking Level: ※

Description

N个站点，J在1站，R在N站，每个站带有权值，经过即可增权；J先手，轮到每个人时可选择让J向右走或者让R向左走；交互选择知道两人相遇（同一格子）

Solution

对于N为奇数：
因为具有操作可具有对称性，所有J可以将答案控制在中间三格中，而R可选择让J停在中间或者两边

对于N为偶数：
选择第一次即可使局面变为奇数，而J成了后手，推导过程相似

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int nn=10005;
int n,a[nn],ans,t; ll sum[nn];
int chk(int x){ return sum[x]-sum[n]+sum[x-1]; }
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
        if(n&1) ans=min(chk(n/2+1),max(chk(n/2+2),chk(n/2)));
        else ans=max(chk(n/2),chk(n/2+1));
        if(ans==0) printf("tie\n"); else if(ans>0) printf("win\n"); else printf("lose\n");   
    }
    return 0;
}