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 ;
}

最新文章

  1. 读书笔记-you-don&#39;t-konw-js
  2. 乐够GO应用源码完整版
  3. mysql 大表 Sharding [转]
  4. Windows Server 2003 SP2 R2 企业版/标准版/32与64位 CD-KEY
  5. Visual Studio 必备神器---转
  6. 在线预览pdf、xlsx、docx、ppt等文档
  7. $_FILES详解
  8. ABP PUT、DELETE请求错误405.0 - Method Not Allowed 因为使用了无效方法(HTTP 谓词) 引发客户端错误 No &#39;Access-Control-Allow-Origin&#39; header is present on the requested resource
  9. ASP.NET MVC2未能加载类型“System.Web.Mvc.ViewPage的解決方法
  10. pytest 12 函数传参和fixture传参数request
  11. Java笔记----字节流与字符的常见类型
  12. codeforces534B
  13. cmd代码:查端口占用,查进程号,杀进程
  14. 学习笔记之Python爬虫
  15. python的__mro__与__slot__
  16. Delphi IDHTTP控件:GET/POST 请求
  17. 表示层设计模式:Intercepting Filter(截取筛选器)模式
  18. springboot的interceptor(拦截器)的应用
  19. c语言打印uint64, int64
  20. mysql DCl语句

热门文章

  1. PD生成兼容Oracle、Mysql脚本
  2. 《C++ Primer Plus》学习笔记11
  3. Java数组List换算方法
  4. 2017 JavaScript 开发者的学习图谱
  5. iphone开发技巧整合
  6. WPF中的资源(一) - 静态资源和动态资源
  7. linq中不能准确按拼音排序
  8. Windows 10 UWP开发:如何去掉ListView默认的选中效果
  9. ThinkPHP 提供Auth 权限管理、支付宝、微信支付、阿里oss、友盟推送、融云即时通讯、云通讯短信、Email、Excel、PDF 等等
  10. Visual studio调试Web发生未能正常启动IIS express