F - Kirei and the Linear Function（前缀和，哈希，暴力）
题目：
有一个长度为(2e5)的字符串和一个长度(w)。进行(2e5)次询问，每次给出(l_i,r_i,k_i)，询问是否存在(v(l, r)*v(L_1,L_1+w-1)+v(L_2,L_2+w-1) bmod 9 == k_i)。
思路：
(l,r)是指定好的，无法更改，但是(L_1,L_2)是可以自由选择的。如果选择去枚举(L)的话，时间复杂度会非常大。我们可以对全部要查询的区间初始化后取模，进行前缀和+哈希处理。那么我们每次查询只需要枚举10^2就可以求解。
实现：
题目提到，当有多个方案时，输出最小字典序的(L)的答案。在预处理的时候，我们只存储(L)位置最靠前的两个。最后我们用一个(PII)来更新我们的(L_1, L_2)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;
const int N = 200005;
int n;
char str[N];
int s[N];
int zero[N];
int w, m;
int calc(int l, int r) //用前缀哈希法 求v(l, r) % 9
{
return ((s[r] - s[l - 1] * zero[r - l]) % 9 + 9) % 9;
}
void init() //为了求v(l, r)做的初始化
{
zero[0] = 1;
for(int i = 1; i <= n; i ++)
{
zero[i] = (zero[i - 1] * 10) % 9;
s[i] = (s[i - 1] * 10 + str[i] - '0') % 9;
}
}
void solve()
{
scanf("%s", str + 1);
n = strlen(str + 1);
init();
scanf("%d%d", &w, &m);
vector<int> v[11];
for(int l = 1; l + w - 1 <= n; l ++) //预处理所有v(l, l + w - 1) % 9
{
int r = l + w - 1;
int tmp = calc(l, r);
if(v[tmp].size() < 2)
v[tmp].push_back(l);
}
while(m --)
{
PII res = {inf, inf};
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
int tmp = calc(l, r);
for(int i = 0; i <= 9; i ++)
{
if(!v[i].size()) continue;
for(int j = 0; j <= 9; j ++)
{
if(!v[j].size()) continue;
if((tmp * i + j) % 9 == k)
{
if(i == j && v[i].size() > 1)
res = min(res, {v[i][0], v[i][1]});
else if(i != j)
res = min(res, {v[i][0], v[j][0]});
}
}
}
if(res.first == inf) res = {-1, -1};
printf("%d %dn", res.first, res.second);
}
}
signed main()
{
int _;
scanf("%d", &_);
while(_--)
solve();
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
