Loading... # Barbecue-字符串hash > **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 **s_1s_2\dots s_n** of length ***n* is considered to be a palindrome if for all integers i*i* from 11 to *n*, **s_i=s_{n-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 ** s_l s_{l+1}\dots s_r .** **Input** > **The first line contains two integers n, **q\ (1\leq n, q\leq 1\,000\,000)*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\leq l\leq r\leq 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".** **Sample 1** | Input | Outpu | | --------------------------------------------- | -------------------------------- | | 7 3<br />potatop<br />1 3<br />3 5<br />1 6 | Putata<br />Budada<br />Budada | **题目** > 普塔塔和布达达正在玩一个新游戏。一开始，普塔塔有一个由小写字母组成的字符串。在每一轮中，拥有纸条的玩家必须从纸条的开头或结尾撕下一个角色，然后将纸条传递给其他玩家。如果在任何时候，音符上的字符串是回文，那么拥有这个音符的玩家就输了。注意，不管是在玩家从纸条上撕下角色之前还是之后，玩家都被认为拥有这张纸条。一个长度为*n*的字符串$s_1s_2\dots s_n$ 被认为是一个回文，如果从1到*n*的所有整数*i*， $s_i=s_{n-i+1}$ > 然而，当普塔发现这个音符时，他发现以前有人玩过这个音符。因为普塔塔和布达都很聪明，总是会选择让自己获胜的最佳方式，他们想知道谁会赢得游戏，所以他们向你寻求帮助。正式地，你被给了一个长度为*n*的字符串，你必须回答*q*查询，每个查询由两个整数*l*和*r*描述，这意味着你必须决定谁将赢得如果puata和Budada玩上面描述的字符串 $s_l s_{l+1}\dots s_r .$ **输入** > 第一行包含两个整数n， $q\ (1\leq n, q\leq 1000000)$,表示字符串的长度和查询的数量。 > 第二行包含一个长度为*n*的字符串*s*，由小写英文字母组成。 > 下面的每一个*q*行包含两个整数*l*和$r\ (1\leq l\leq r\leq n)$，描述一个查询。 **输出** > 对于每个查询，打印一行。如果puata在一个查询中获胜，输出“puata”(不带引号)。否则输出“Budada”。 **说明：** 这题我刚开始写的是用dp将回文串记录下来，后来发现数组不能开这么大，后面经同学提醒用字符串hash 刚开始写的代码： ``` #include <iostream> #include <cstring> #include <string> using namespace std; const int maxn = 1e4 + 5; bool vis[maxn][maxn]; int main(void) { int n, q; char str[maxn]; scanf("%d %d %s", &n, &q, str); memset(vis, false, sizeof(vis)); for (int i = 0; i < n; ++i) { vis[i][i] = true; if (i < n - 1 && str[i] == str[i + 1]) vis[i][i+1] = true; } for (int k = 2; k < n; ++ k) { for (int i = 0; i + k < n; ++i) { if (str[i] == str[i + k] && vis[i + 1][i + k - 1]) { vis[i][i + k] = true; } } } int l, r; for (int i = 0; i < q; ++i) { scanf("%d %d", &l, &r); -- l, --r; if (vis[l][r] || (l - r + 1) % 2 == 0) { puts("Budada"); } else { puts("Putata"); } } return 0; } ``` 下面的代码是正确的： ``` #include <iostream> #include <cstring> using namespace std; typedef long long ll; const int maxn = 1e6 + 5; const int m = 27; ll hash1[maxn], hash2[maxn], p[maxn]; int main(void) { int n, q; char str[maxn]; scanf("%d %d %s", &n, &q, str + 1); p[0] = 1; hash1[0] = 0; for (int i = 1; i <= n; ++i) { p[i] = p[i - 1] * m; hash1[i] = hash1[i - 1] * m + str[i] - 'a'; } hash2[n + 1] = 0; for (int i = n; i >= 1; --i) { hash2[i] = hash2[i + 1] * m + str[i] - 'a'; } for (int i = 1; i <= q; ++i) { int l, r; scanf("%d %d", &l, &r); ll h1 = hash1[r] - hash1[l - 1] * p[r - l + 1]; ll h2 = hash2[l] - hash2[r + 1] * p[r - l + 1]; if (h1 == h2 || (r - l + 1) % 2 == 0) { puts("Budada"); } else { puts("Putata"); } } return 0; } ``` 最后修改：2022 年 07 月 17 日 © 允许规范转载 赞 1 如果觉得我的文章对你有用，请随意赞赏
