2019CCPC秦皇岛赛区(重现赛)- J
2024-09-04 22:20:14
链接:
http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1010&cid=872
题意:
鉴纯夏是一名成绩不太好的高中生。一天她在数学考试中碰到了一道求某条线段长度的问题。因为她并不会做这道题,所以她准确地作图后用尺子量出了这条线段的长度。不幸的是,答案在10进制下为一个无限小数,纯夏只量出了这个无限小数在10进制表示下的前若干位。
纯夏猜测问题的答案为一个有理数,所以答案为一个无限循环小数,如13=0.333⋯,3635=1.0285714285714⋯。纯夏希望从这个无限小数的前n位猜出原本的数字。纯夏意识到,猜测的循环节太长或循环节已经开始出现的部分长度太短是不可信的。举个例子,若她量出的小数为1.0285714285714,显然假设循环节为0285714285714(长度为13)或假设循环节为428571(已经开始出现的部分长度为7)都不如假设循环节为285714(长度为6,已经开始出现的部分长度为12)可靠。因此她定义一个循环节的可靠程度为a×循环节已经开始出现的部分长度−b×循环节长度。请你帮她求出最可靠的循环节的可靠程度为多少。
思路:
小数部分逆序, KMP, 求所有后缀的最小循环节.
注意答案初始化为len时情况.
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e7+10;
int Next[MAXN];
char l[MAXN], r[MAXN];
void GetNext(char *s)
{
int j = 0, k = -1;
int len = strlen(s);
Next[0] = -1;
while (j < len)
{
if (k == -1 || s[j] == s[k])
{
++j;
++k;
Next[j] = k;
}
else
k = Next[k];
}
}
int main()
{
LL a, b;
while (~scanf("%lld%lld", &a, &b))
{
memset(Next, 0, sizeof(Next));
memset(l, 0, sizeof(l));
memset(r, 0, sizeof(r));
scanf("%s", l);
int i = 0;
int len = strlen(l);
for (i = 0;i < len;i++)
{
if (l[i] == '.')
break;
}
strcpy(r, l+i+1);
len = strlen(r);
reverse(r, r+len);
GetNext(r);
LL ans = a*len-b*len;
for (int j = 1;j <= len;j++)
{
LL le = j-Next[j];
LL tmp = a*j-b*le;
ans = max(ans, tmp);
}
printf("%lld\n", ans);
}
return 0;
}
最新文章
- android 自定义控件——(一)圆角按钮
- WCF初探文章列表
- JDBC详解
- springmvc请求参数异常处理
- Python核心编程第三版第二章学习笔记
- Spring中@Async注解实现“方法”的异步调用
- 如何设置table的border-radius?
- Atom 插件安装
- hdu 3586 Information Disturbing(树形dp + 二分)
- Python:标准数据类型6种
- CodeForces463C Gargari and Bishops(贪心)
- 解决ListView 和ScroolView 共存 listItem.measure(0, 0) 空指针
- mac OSx 安装 mysqlclient
- JVM垃圾回收(四)- GC算法:实现(1)
- xmltodict 模块
- pip的更新问题
- Promise的实现原理
- 用PNChart绘制饼状图简介
- Mysql 查看定时器 打开定时器 设置定时器时间
- vue的项目优化---回顾