UVALive 7325 Book Borders
2024-10-07 11:10:57
-------------------------------------------------------------------------------------------------------------
我们可以预处理除长度为L的区间能存下的从第一个单词开始的单词的次数
然后枚举区间长度从a到b 每次从一个区间最后一个单词结尾跳到另一个区间最后一个单词结尾
这样相邻两次跳跃的总长度至少为一个区间长度
设单词总长为$len$ 对于长度为$x$的区间 总的跳跃次数不超 $len\ /\ x * 2$
因此整个问题的复杂度根据调和级数分析发现是 $O(lenlog{len})$
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = ;
int a[N], pre[N], sum[N];
char s[N];
int len, n;
int main()
{
while(gets(s) != NULL)
{
n = ;
len = strlen(s) + ;
for(int i = ; i < len; ++i)
{
if(s[i] < 'a' || s[i] > 'z')
{
++n;
a[n] = i + - sum[n - ];
sum[n] = sum[n - ] + a[n];
}
pre[i + ] = n;
}
int L, R, ans, now;
scanf("%d%d", &L, &R);
getchar();
++L;
++R;
for(int i = L; i <= R; ++i)
{
ans = -;
now = ;
while(now != len)
{
ans += a[pre[now] + ];
now = sum[pre[min(now + i, len)]];
}
printf("%d\n", ans);
}
}
return ;
}
最新文章
- 手动实现jQuery Tools里面tab功能
- 众人口中的JAVASCRIPT
- Linux命令中特殊符号
- Android 手机卫士15--程序锁
- java 面向对象编程--第十章 接口
- hdu 3397 Sequence operation(很有意思的线段树题)
- C++ CopyFile
- C++:运算符重载函数之成员运算符重载函数
- ubuntu中文实训手册
- DevExpress ASP.NET 使用经验谈(7)-ASPxTreeList控件使用
- STL之queue(单向队列)
- [Android] Activity 重复使用
- 如何用.reg文件操作注册表
- libaio.so.1()(64bit) is needed by MySQL-server 问题解决办法
- VMware下liunx虚拟机仅主机模式上网
- 小学四则运算APP 第二阶段冲刺
- 小程序点击事件改变样式(普通js鼠标点击事件)
- Java_按位与&;,按位或,取反,左移,右移运算符
- rest api上传和下载文件
- IT系统故障引起的一个事故的思考
热门文章
- 题解 AT2684 【K-City】
- python文件打包/导入 .so 文件
- 08: mysql主从原理
- angularJS(二):作用域$scope、控制器、过滤器
- ISC2016训练赛 phrackCTF--Smali
- install python+twisted+mysqldb+django on mac
- AFNetworking2.0源码解析<;一>;
- 05.Linux系统-WCP知识共享平台安装部署(旗舰版)
- IsDate(expression)函数
- TensorFlow机器学习实战指南之第二章2