I. Barbecue

题目链接

I. Barbecue

Putata and Budada are playing a new game. In the beginning, Putata has a note with a string consists of lowercase letters on it. In each round, the player who has the note must rip off a character from the beginning or the end of the note, then pass it to the other player. If at any moment, the string on the note is a palindrome, then the player who has the note loses. Notice that both before or after the player ripping off a character from the note, the player is considered to have the note. A string s1s2…sn of length n is considered to be a palindrome if for all integers i from 1 to n, si=sn−i+1.

However, when Putata found the note, he found that someone have played on this note before. Since both Putata and Budada are clever and will always choose the best way to make themselves win, they wonder who will win the game, and they ask you for help. Formally, you are given a string of length n and you have to answer q queries, each query is described by two integers l and r, which means you have to determine who will win if Putata and Budada play the game described above on string slsl+1…sr .

Input
The first line contains two integers n,q (1≤n,q≤1000000), denoting the length of the string and the number of queries.

The second line contains a string s of length n, consisting of lowercase English letters.

Each of the following q lines contains two integers l and r (1≤l≤r≤n), describing a query.

Output
For each query, print a single line. If Putata wins the game in one query, output “Putata” (without quotes). Otherwise output “Budada”.

Example
input

7 3
potatop
1 3
3 5
1 6

output

Putata
Budada
Budada

题意：

给定一个长度为 n 的字符串 S，q 次询问，每次询问指定 S 的一个子串，两个人在该子串上进行博弈。
博弈双方轮流删去当前串开头或结尾的一个字符，碰到回文 串的人输。 预测两人都按最优策略操作时最终谁会获胜。

题解

首先通过 Hash 等方式 O(1) 特判起始串为回文串的情况。
对于接下来任意一个局面，先手操作前一定不是回文串。
若先手无法进行任何操作，则说明无论删去开头还是结尾都 会得到回文串。
容易发现满足条件的串只能形如 ab, abab, ababab, … .
这说明终止态的长度一定是偶数，因此输赢只和起始串长度 的奇偶性有关。
时间复杂度 O(n + q)。

总结：如果区间长度为偶数或是回文串就输出输，不是就赢。这是一道进制hash求回文串的模板题。

这里有一道类似的题,也是hash求回文串的题。
SPOJ - EPALIN - Extend to Palindrome

代码：

#include<iostream>
#include<string>
using namespace std;
typedef unsigned long long ull;   //自然溢出
const ull M = 13331;             //哈希的进制
const ull maxn=1e6+7;
ull Hash1[maxn],Hash2[maxn],power[maxn];
int n,m;
void into()
{
	power[0]=1;
	for(int i=1; i<maxn; i++)
		power[i]=power[i-1]*M;
}
ull getHash1(int l,int r)      //求顺序的区间哈希值
{
	return Hash1[r]-Hash1[l-1]*power[r-l+1];
}
ull getHash2(int l,int r)     //求逆序的区间哈希值
{
	return Hash2[l]-Hash2[r+1]*power[r-l+1];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	into();             //初始化进制
	cin>>n>>m;
	string s;
	cin>>s;
	s=" "+s;
	int lens=s.size()-1;
	Hash1[0]=Hash2[lens+1]=0;
	for(int i=1; i<s.size(); i++)
	{
		Hash1[i]=Hash1[i-1]*M+s[i]-'a';
		Hash2[lens+1-i]=Hash2[lens+2-i]*M+s[lens+1-i]-'a';
	}
	for(int i=0; i<m; i++)
	{
		int l,r;
		cin>>l>>r;
		if((r-l+1)%2==0)
			cout<<"Budada\n";
		else if(getHash1(l,r)==getHash2(l,r))
			cout<<"Budada\n";
		else
			cout<<"Putata\n";
	}
}