POJ 2887:Big String(分块)
2024-10-02 03:02:19
http://poj.org/problem?id=2887
题意:给出一个字符串,还有n个询问,第一种询问是给出一个位置p和字符c,要在位置p的前面插入c(如果p超过字符串长度,自动插在最后),第二种询问是给出一个位置p,查找第p个位置的字符(p保证合法)。
思路:暴力分块。一开始建成块之后,每次插入就在每个块的字符串插入字符,因为询问最多只有2000个,所以就算极端情况也不会超时。
注意:sz和cnt其中一个要向上取整。用string类会超时。
#include <cstring>
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
using namespace std;
char s[][];
char str[];
int n, block[], sz, cnt; void Build() {
sz = sqrt(n);
cnt = (n + sz - ) / sz; // 记得向上取整, 因为这WA了一次
for(int i = ; i < n; i++) s[i / sz + ][block[i / sz + ]++] = str[i];
} void Insert(char c, int p) {
int i;
for(i = ; i <= cnt; i++) {
if(p - block[i] <= ) break;
p -= block[i];
}
if(i == cnt + ) { s[cnt][block[cnt]++] = c; return ; }
block[i]++;
int len = strlen(s[i]);
for(int j = len - ; j >= p - ; j--) s[i][j+] = s[i][j];
s[i][p-] = c;
} void Query(int p) {
int i;
for(i = ; i <= cnt; i++) {
if(p - block[i] <= ) break;
p -= block[i];
}
printf("%c\n", s[i][p-]);
} int main() {
scanf("%s", str); n = strlen(str);
int q; scanf("%d", &q);
Build();
while(q--) {
char op[], c[]; int num;
scanf("%s", op);
if(op[] == 'I') {
scanf("%s%d", c, &num);
Insert(c[], num);
} else {
scanf("%d", &num);
Query(num);
}
}
return ;
}
最新文章
- 读书笔记-you-don&#39;t-konw-js
- 乐够GO应用源码完整版
- mysql 大表 Sharding [转]
- Windows Server 2003 SP2 R2 企业版/标准版/32与64位 CD-KEY
- Visual Studio 必备神器---转
- 在线预览pdf、xlsx、docx、ppt等文档
- $_FILES详解
- ABP PUT、DELETE请求错误405.0 - Method Not Allowed 因为使用了无效方法(HTTP 谓词) 引发客户端错误 No &#39;Access-Control-Allow-Origin&#39; header is present on the requested resource
- ASP.NET MVC2未能加载类型“System.Web.Mvc.ViewPage的解決方法
- pytest 12 函数传参和fixture传参数request
- Java笔记----字节流与字符的常见类型
- codeforces534B
- cmd代码:查端口占用,查进程号,杀进程
- 学习笔记之Python爬虫
- python的__mro__与__slot__
- Delphi IDHTTP控件:GET/POST 请求
- 表示层设计模式:Intercepting Filter(截取筛选器)模式
- springboot的interceptor(拦截器)的应用
- c语言打印uint64, int64
- mysql DCl语句