[bzoj1355][baltic2009]radiotransmission

关键词：

传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1355

Description

Input

Output

Sample Input

Sample Output

HINT

由于保证了是拼接的，所以n-fail[n]就是答案。

 1 #include<cstdio>
 2 int n,fail[1000009];
 3 char s[1000009];
 4 int main(){
 5     scanf("%d",&n);
 6     scanf("%s",s+1);
 7     for(int i=2;i<=n;i++){
 8         int k=fail[i-1];
 9         while(s[k+1]!=s[i]&&k>0)k=fail[k];
10         if(s[k+1]==s[i])fail[i]=k+1;
11     }
12     printf("%d",n-fail[n]);
13     return 0;
14 }

bzoj1355:[baltic2009]radiotransmissionkmp(代码片段)

kmp复健，答案是n-next[n]#include<iostream>#include<cstdio>usingnamespacestd;constintN=1000005;intn,ne[N];chars[N];intmain()scanf("%d%s",&n,s+1);intj=0;for(inti=2;i<=n;i++)while(s[j+1]!= 查看详情

[bzoj1355][baltic2009]radiotransmission_kmp

RadioTransmissiobzoj-1355Description　　　　给你一个字符串，它是由某个字符串不断自我连接形成的。但是这个字符串是不确定的，现在只想知道它的最短长度是多少.Input　　　　第一行给出字符串的长度,1<L≤1,000,000.第二行给出一... 查看详情

bzoj1355:[baltic2009]radiotransmission

题目大意：给出一个字符串，已知它是一个字符串S不断反复后构成的无限长的字符串的一个子串，求S的最短长度是多少。思路：利用KMP算法，答案就是n-next[n].证明例如以下：图太渣了。。。另一种情况就是next[n]<=n/2,自己画... 查看详情

1355:[baltic2009]radiotransmission

1355:[Baltic2009]RadioTransmissionTimeLimit: 10Sec  MemoryLimit: 64MBSubmit: 796  Solved: 538[Submit][Status][Discuss]Description给你一个字符串，它是由某个字符串不断自我连接形成的。但是这个字 查看详情

1355:[baltic2009]radiotransmission

TimeLimit: 10Sec  MemoryLimit: 64MBSubmit: 958  Solved: 659[Submit][Status][Discuss]Description给你一个字符串，它是由某个字符串不断自我连接形成的。但是这个字符串是不确定的，现在只想知道它的最短长度是多少.In... 查看详情

bzoj1760[baltic2009]triangulation

给定一个多边形的三角剖分(n<=1e5)，且每个三角形有其颜色，问最多可以把这个三角剖分分成几个联通的部分，使任何一种颜色不出现在多个连通块中建出三角剖分对应的树，同种颜色的点之间的路径是不能被切开的，因此将... 查看详情

bzoj1414:[zjoi2009]对称的正方形

传送门我有效率这种东西吗，那是什么，可以吃吗先对每行每列跑manacher，然后需要求出每个点可以向四周扩展的最大距离，考虑单独一行，对于每个i只需求出它前面距它最远的一个j满足i-j+1>=min(rad[j]~rad[i])这个可以用单调队... 查看详情

bzoj1367:[baltic2004]sequence

1367:[Baltic2004]sequenceTimeLimit: 20Sec  MemoryLimit: 64MBSubmit: 1476  Solved: 606[Submit][Status][Discuss]DescriptionInputOutput一个整数RSampleInput794820141518 查看详情

bzoj1367:[baltic2004]sequence

1367:[Baltic2004]sequenceTimeLimit: 20Sec  MemoryLimit: 64MBDescriptionInputOutput一个整数RSampleInput794820141518SampleOutput13HINT所求的Z序列为6,7,8,13,14,15,18.R=13 详细证明请看IOI2005国家集训 查看详情

[bzoj1367][baltic2004]sequence

传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1367[Baltic2004]sequenceTimeLimit: 20Sec  MemoryLimit: 64MBSubmit: 1304  Solved: 531[Submit][Status][Discuss 查看详情

bzoj2348[baltic2011]plagiarism*

bzoj2348[Baltic2011]Plagiarism题意：n个数，如果其中两个数fi≤fj且fi≥0.9*fj，则它们要被比较。求多少对数要被比较。n≤100000。题解：排序然后双指针法。代码：1#include<cstdio>2#include<cstring>3#include<algorithm>4#defineinc(i,j, 查看详情

bzoj1367[baltic2004]sequence左偏树

【BZOJ1367】[Baltic2004]sequenceDescriptionInputOutput一个整数RSampleInput794820141518SampleOutput13HINT所求的Z序列为6,7,8,13,14,15,18.R=13题解：详见论文然而本题要求z[i]严格递增，那就让所有t[i]-=i就好了#include<cstdio>#include<cs 查看详情

bzoj31363136:[baltic2013]brunhilda（数论？）

3136:[Baltic2013]brunhildaTimeLimit: 40Sec  MemoryLimit: 128MBSubmit: 238  Solved: 73[Submit][Status][Discuss]Description给定m个素数和Q个询问。每个询问有n个人，每次操作可以任意选择其中的一个素数p 查看详情

bzoj1385[baltic2000]divisionexpression

题目链接首先，X2必定会作为分母而其他的都可以甩到分子上去如果其他的数可以把X2约成1就可以是结果变为整数1#include<algorithm>2#include<iostream>3#include<cstdlib>4#include<cstring>5#include<cstdio>6#include<string>7# 查看详情

bzoj31333133:[baltic2013]ballmachine（线段树+倍增）

3133:[Baltic2013]ballmachineTimeLimit: 20Sec  MemoryLimit: 128MBSubmit: 148  Solved: 66Description有一个装球机器，构造可以看作是一棵树。有下面两种操作：从根放入一个球，只要下方有空位，球会沿着树滚下。如果同... 查看详情

bzoj1345[baltic2007]序列问题sequence*

bzoj1345[Baltic2007]序列问题Sequence题意：n个数，合并ai和ai+1可以得到max(ai,ai+1)，代价为max(ai,ai+1)。问合并n-1次最小代价为多少。n≤1000000。题解：（来自题解，因为我不知道为什么这样做）维护一个单调递减栈。对于每个加入的元... 查看详情

[baltic2009]radiotransmission

TimeLimit:10Sec  MemoryLimit:64MBSubmit:946  Solved:653[Submit][Status][Discuss]Description给你一个字符串，它是由某个字符串不断自我连接形成的。但是这个字符串是不确定的，现在只想知道它的最短长度是多少.Input第一行给出字符... 查看详情

bzoj1342:[baltic2007]sound静音问题[单调队列]

1342:[Baltic2007]Sound静音问题TimeLimit: 5Sec  MemoryLimit: 162MBSubmit: 835  Solved: 372[Submit][Status][Discuss]Description静音问题数字录音中，声音是用表示空气压力的数字序列描述的，序列中的每个值称为一 查看详情