题目描述
题解没什么好发的,我要说的重点是模拟,一定要自己模拟一遍
先自己想一遍,想到要转化进制来解决问题.
然后就去解决进制了,结果卡在进制了,想不出来就去看代码,
就解决了卡住自己的问题,然后自然就写出来了.
当然,2h搞定可能跟我前面的积淀有关系,不过也慢了
样例
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
char str[N];
int l1, r1, l2, r2;
int jinzhi[N], h[N], p = 131;//第一个数组用来存放辅助进制,第二个数组存放具体的数
int get(int l, int r)
{
return h[r] - h[l - 1] * jinzhi[r - l + 1];
}
void solve()
{
cin >> l1 >> r1 >> l2 >> r2;
if (get(l1, r1) == get(l2, r2)) cout << "Yes" << endl;
else cout << "No" << endl;
}
int main()
{
int n, m; cin >> n >> m;
cin >> str + 1;
//字符串的每个数用进制转化
jinzhi[0] = 1;
for (int i = 1; i <= n; i++)
{
h[i] = h[i - 1] * p + str[i];
jinzhi[i] = jinzhi[i - 1] * p;
}
while (m--)
{
solve();
}
return 0;
}