第十九届浙江省 I. Barbecue

第十九届浙江省 I. Barbecue

题意： 两个同学Putata和Budada在玩一个游戏，一开始给定一个固定长度的字符串，接下去有$m$次询问，每次询问给定一个范围$[l,r]$，即从原字符串中截取$[l,r]$的部分。从第一个同学Putata开始操作，每次操作必须从字串开头或末尾移除一个字符，如果操作前后字串变成回文串那么操作的同学判负，问每次询问哪个同学会赢？

Tip:

• 如果一开始第一个同学拿到的就是回文串，那么必定输掉比赛。
• 否则第一个同学拿到的就是非回文串，由于如果操作后子串变成回文串那么也算操作的同学输，那么在操作的同学最好的方案就是 非回文$⟹$非回文
• 这就说明如果游戏没结束即上一次操作的同学结束操作后字串变成 非回文，那么意味着游戏如果始终持续进行除去 第一次操作 ，操作的同学拿到的 始终是非回文串 。那么通过不断操作，最终拿到长度为 $2$ 的同学 必败 ，因为无论怎么操作，剩下的 $1$ 个字符必定是 回文 。
• 那么显然有如果第一次操作的同学拿到的是 非回文 并且长度为偶数那么第一次操作的同学必败。如果是 非回文 并且长度为奇数，那么第一次操作的同学必胜。 当然非回文偶数字串有一种特殊情况为$abababab$，不管拿掉首个字符还是末尾字符都是操作者输，所以同样归类至第一种情况。
• 接下去就是如果判定区间$[l,r]$内的字串为回文串，由于题目给到的查询有$10^6$，所以支持的复杂度即为$O(1)$查询。那么我们可以通过字符串$hash$和$Manachar$算法来进行处理。此处给出字符串$hash$做法(学习地址)。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,q;
const int P = 131;
const int N = 1e6+10;
unsigned long long p[N],t[N],t1[N];
unsigned long long query1(int l,int r){
    return t[r]-t[l-1]*p[r-l+1];
}
unsigned long long query2(int l,int r){
    return t1[l]-t1[r+1]*p[r-l+1];
}
char s[N];
int main(){
    scanf("%d%d",&n,&q);
    scanf("%s",s+1);
    p[0]=1;
    t[0]=0;
    t1[n+1]=0;
    for(int i=1;i<=n;i++){
        p[i]=p[i-1]*P;
        t[i]=t[i-1]*P+s[i];
    }
    for(int i=n;i>=1;i--){
        t1[i]=t1[i+1]*P+s[i];
    }
    while(q--){
        int l,r;
        scanf("%d%d",&l,&r);
        if(query1(l,r)==query2(l,r)){
            printf("Budada\n");
        }
        else{
            if((r-l+1)%2==0)printf("Budada\n");
            else printf("Putata\n");
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39