Codeforces Round #423 (Div. 1, rated, based on VK Cup Finals)
2024-09-01 19:27:15
Codeforces Round #423 (Div. 1, rated, based on VK Cup Finals)
B. High Load
题意：给定一个只包含A,T,C,G的字符串S,有如下两种操作
1）修改一个点的字母.
2）给定一个字符串e ($\left | e \right |\leq 10$)，生成一个由e重复组成的新串，eee...，问$S_{l..r}$中有几个字母跟这个新的字符串一一对应。
SOL：对于每个字母，用BIT[x][y][L]表示$S_{1..L}$中，所有$\equiv x\left (mod \, y \right )$的位置出现了该字母几次。然后复杂度大概就是$O(100*mlogn)$。
然而比赛的时候由于没有想到树状数组动态更新前缀和，而是用了一个静态数组，强行用定期重构过去了。。复杂度$O(10 * m*\sqrt{n})$，略微有些暴力。
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int LEN = 1e5 + ;
int i, j, k, n, m, s, t, ans, S, top;
char c[LEN], a[LEN], d[LEN];
int f[LEN][][];
set <int> st;
typedef set <int> :: iterator iter;
const char to[] = {'A', 'C', 'G', 'T'};
int get(char x) {
if (x == 'A') {
return ;
} else if (x == 'C') {
return ;
} else if (x == 'G') {
return ;
} else {
return ;
}
}
void init() {
for (int i = n; i >= ; i--) {
for (int j = ; j <= ; j++) {
for (int k = ; k < ; k++) {
if (get(c[i]) == k) {
f[i][j][k] = ;
} else {
f[i][j][k] = ;
}
if (i + j <= n) {
f[i][j][k] += f[i + j][j][k];
}
}
}
}
}
int ask(int l, int r, int L) {
int ans = ;
if (r - l + <= L) {
for (int i = l; i <= r; i++) {
if (c[i] == a[i - l + ]) {
ans++;
}
}
} else {
for (int i = ; i <= L; i++) {
int t = get(a[i]);
ans += f[l + i - ][L][t];
int k = (r - l + - i) / L + ;
if (k >= && l + i - + k * L <= n) {
ans -= f[l + i - + k * L][L][t];
}
}
}
for (iter it = st.begin(); it != st.end(); it++) {
int x = *it, t = get(d[x]);
if (l <= x && x <= r) {
int p = (x - l) % L + ;
if (get(c[x]) == get(a[p]) && get(a[p]) != t) {
ans--;
}
if (get(c[x]) != get(a[p]) && get(a[p]) == t) {
ans++;
}
}
}
return ans;
}
void rebuild() {
for (iter p = st.begin(); p != st.end(); p++) {
int x = *p;
c[x] = d[x];
}
init();
st.clear();
}
int main() {
scanf("%s", c + );
n = strlen(c + );
S = sqrt(n) + ;
init();
scanf("%d", &m);
while (m--) {
int op, l, r;
scanf("%d", &op);
if (op == ) {
scanf("%d %d", &l, &r);
scanf("%s", a + );
int L = strlen(a + );
printf("%d\n", ask(l, r, L));
} else {
scanf("%d %s", &l, a + );
st.insert(l);
d[l] = a[];
if (st.size() >= S) {
rebuild();
}
}
}
return ;
}
最新文章
- ABAP 上传文件到内表
- Authentication和Authorization的区别
- Response响应请求操作
- linux vim用法总结
- Java Portlet 规范概述
- JSP版（utf8编码）的Ueditor百度文章编辑器配置以及使用说明
- Homebrew -- Mac软件管家（套件管理yun……）
- Qt多工程多目录的编译案例
- i++与++i陷阱
- 学习Identity Server 4的预备知识
- 咸鱼入门到放弃13--监听器（Listener）
- DevExpress 之 GridControl 自定义列
- PHP chdir函数：改变当前的目录
- Hibernate常见面试题(转)
- C# 根据类名创建类的实例对象
- Eclipse的下载及安装
- L2tp协议简单解析
- JS判断时特殊值与boolean类型的转换
- JSON特殊字符的处理
- Autofac构建