彩虹糖

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

Description

两人分别持有两个操作序列A和B（长tota和totb），其中无相同元素（元素属于1~m）；
和一长为n的待操作序列S
两人轮流操作：
选择S中一元素x，x须属于自己操作序列，可将x分为y和x-y。（0<y<x）
无法操作的人输
先手若获胜输出Pomegranate，否则输出Orange

Solution

不同于一般的平等博弈，此题先手后手的选择域是不同的
因此我们引入f(x)来计入x能造成的贡献，即能多幸存几回合

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
const int nn=1000005;
const int mn=10005;
int n,m,f[mn],tota,totb,a[mn],b[mn];
int main(){
    scanf("%d%d",&n,&m);

    int i,j,x;
    scanf("%d",&tota); for(i=1;i<=tota;i++) scanf("%d",&x),a[x]=1;
    scanf("%d",&totb); for(i=1;i<=totb;i++) scanf("%d",&x),b[x]=1;

    f[1]=0;
    for(i=2;i<=m;i++){
        f[i]=0;
        if(a[i]) for(j=1;j*2<=i;j++) f[i]=max(f[i],f[j]+f[i-j]+1);
        if(b[i]) for(j=1;j*2<=i;j++) f[i]=min(f[i],f[j]+f[i-j]-1);
    }

    for(i=1;i<=n;i++) scanf("%d",&x),f[0]+=f[x];
    if(f[0]>0) printf("Pomegranate\n");
    else printf("Orange\n");
    return 0;
}