- 浏览: 389167 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
wsyzyrxp:
非常感谢 兄弟 帮了我大忙
[opengl]弹簧质点法模拟柔性布料以及椭球碰撞的opengl实现 -
mingdry0304:
[opengl]彩色立方体旋转 -
tyfengyu:
我刚刚更改的代码加上了标准差stdVal,故recoMat应该 ...
[python]用python实现的pca算法 -
tyfengyu:
python的pca代码有2处错误:1.finalData = ...
[python]用python实现的pca算法 -
暴风雪:
McFlurry 写道前排(凑字数)!擦你怎么摸来这里的
诈尸总结
大致题意:
给出一个字符串,要求在这个字符串后面添加最少的字母使其成为回文串。
大致思路:
要注意添加的字母数不能为0,要分奇偶讨论。
#include<iostream> #include<cstdio> #include<vector> #include<cstring> using namespace std; const int nMax =1000012; int num[nMax]; int sa[nMax], rank1[nMax], height[nMax]; int wa[nMax], wb[nMax], wv[nMax], wd[nMax]; int cmp(int *r, int a, int b, int l){ return r[a] == r[b] && r[a+l] == r[b+l]; } void da(int *r, int n, int m){ // 倍增算法 r为待匹配数组 n为总长度 m为字符范围 int i, j, p, *x = wa, *y = wb, *t; for(i = 0; i < m; i ++) wd[i] = 0; for(i = 0; i < n; i ++) wd[x[i]=r[i]] ++; for(i = 1; i < m; i ++) wd[i] += wd[i-1]; for(i = n-1; i >= 0; i --) sa[-- wd[x[i]]] = i; for(j = 1, p = 1; p < n; j *= 2, m = p){ for(p = 0, i = n-j; i < n; i ++) y[p ++] = i; for(i = 0; i < n; i ++) if(sa[i] >= j) y[p ++] = sa[i] - j; for(i = 0; i < n; i ++) wv[i] = x[y[i]]; for(i = 0; i < m; i ++) wd[i] = 0; for(i = 0; i < n; i ++) wd[wv[i]] ++; for(i = 1; i < m; i ++) wd[i] += wd[i-1]; for(i = n-1; i >= 0; i --) sa[-- wd[wv[i]]] = y[i]; for(t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i ++){ x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p - 1: p ++; } } } void calHeight(int *r, int n){ // 求height数组。 int i, j, k = 0; for(i = 1; i <= n; i ++) rank1[sa[i]] = i; for(i = 0; i < n; height[rank1[i ++]] = k){ for(k ? k -- : 0, j = sa[rank1[i]-1]; r[i+k] == r[j+k]; k ++); } } int Log[nMax]; int best[20][nMax]; void initRMQ(int n) {//初始化RMQ for(int i = 1; i <= n ; i ++) best[0][i] = height[i]; for(int i = 1; i <= Log[n] ; i ++) { int limit = n - (1<<i) + 1; for(int j = 1; j <= limit ; j ++) { best[i][j] = min(best[i-1][j] , best[i-1][j+(1<<i>>1)]); } } } int lcp(int a,int b) {//询问a,b后缀的最长公共前缀 a = rank1[a]; b = rank1[b]; if(a > b) swap(a,b); a ++; int t = Log[b - a + 1]; return min(best[t][a] , best[t][b - (1<<t) + 1]); } char str[nMax]; int main(){ int i,j,n,cas=0,len; Log[0] = -1; for(int i=1;i<=nMax;i++){ Log[i]=(i&(i-1))?Log[i-1]:Log[i-1] + 1 ; } while(scanf("%s",str)!=EOF){ len=strlen(str); n=0; for(i=0;i<len;i++){ num[n++]=str[i]; } num[n++]=126; for(i=len-1;i>=0;i--){ num[n++]=str[i]; } num[n]=0; memset(height,0,sizeof(height)); da(num, n + 1,130); calHeight(num,n); initRMQ(n); int start,ans=1,tmp; int ans1=len-1,ans2=len-1; int len1,len2,fuck=0; for(i=len-1;i>0;i--){ tmp=lcp(i,n-i-1); ///首先考虑回文长度是奇数的情况 // printf("1lcp(%d,%d)=%d\n",i,n-i-1,tmp); if(tmp>=len-i){ if(len%2==1&&i==len/2)continue; ans1=i; } tmp=lcp(i,n-i); ///考虑回文长度是偶数的情况 // printf("lcp(%d,%d)=%d len-i=%d\n",i,n-i,tmp,len-i); if(tmp>=len-i){//&&((!len&1)&&i==len/2)){ if(len%2==0){ if(i==len/2){ continue; } } fuck=1; ans2=i; // cout<<"fffuuuccckkk\n"; } } if(len==1){ cout<<str<<str<<endl; continue; } // cout<<ans1<<" "<<ans2<<" "<<fuck<<endl; len1=(ans1)*2+1; len2=ans2*2; if(len1<len2||!fuck){ for(i=0;i<ans1;i++)cout<<str[i]; for(i=ans1;i>=0;i--)cout<<str[i]; cout<<endl; } else{ for(i=0;i<ans2;i++)cout<<str[i]; for(i=ans2-1;i>=0;i--)cout<<str[i]; cout<<endl; } } return 0; }
发表评论
-
[树状数组]poj 2299
2014-12-13 20:58 1912题意 求一列数字的逆序数。 思路 ... -
[树状数组]hdoj 1166
2014-12-12 01:21 2题意 http://acm.hdu.edu.cn/ ... -
[树状数组]hdoj 1166
2014-12-12 01:21 890题意 http://acm.hdu.edu.cn/ ... -
[离散化+线段树]poj2528
2014-12-01 23:16 617题意 给出每个海报的位置,问最后没有被完全覆盖 ... -
[线段树区间合并]poj 3667
2014-12-01 11:45 796i题意 和poj1823差不多,加了一个查 ... -
[线段树区间更新]poj 1823
2014-12-01 02:56 896题意 一个旅馆有n个房间,有m次操作,每次操作可 ... -
[线段树]poj 3368
2014-11-29 07:58 747题意 给出一串数字,有m次询问,每次询问[ab ... -
[线段树成段更新]poj 2777
2014-11-28 01:33 1130题意: 一段区间从1-n的初始颜色为1,每 ... -
[线段树]poj 2182
2014-11-27 23:13 613题意: n头牛站队,每头牛都有一个属于[ ... -
[线段树]poj 3264
2014-11-27 21:57 504题意 给出一串数字,m个询问,对于每次询问求出 ... -
[线段树成段更新]hdoj 1698
2014-11-27 21:00 724题意: 对一个线段上的值进行修改,一次可以把[i, ... -
[线段树成段更新]poj 3468
2014-11-27 12:43 704题意: 给出一串n个数,每次操作分为两种,分 ... -
[线段树]poj 2828
2014-11-26 22:02 726题意 n个人插队,每次某个人都会选择插入第i个 ... -
[线段树]hdoj 2795
2014-11-25 20:33 871题意:一个高h宽w的二维空间,每次放进去一个高为1,宽为a的 ... -
[线段树]hdoj 1394
2014-11-24 22:40 934题意 给出一列n个数字,每一个数字都和其他 ... -
[后缀数组]acdream 1430
2014-10-16 14:08 530大致题意: 求出一个字符串(len<=1 ... -
[KMP+乱搞]hdoj 4749
2014-10-11 15:22 780大致题意: 求文本串中最多能选出多少子串,使得这 ... -
[KMP]hdoj 4763
2014-10-10 11:39 696题意: 给出一个字符串,问是否存在这样的子串E使得 ... -
[后缀数组][二分]hdu 5008
2014-09-27 10:10 1023大致题意: 给出一个长度小于100000的字符串 ... -
[线段树,单点更新]hdoj 1754:I Hate It
2012-10-21 21:33 1299大致题意: 给出一个数组,在线更新点的值,查询区 ...
相关推荐
3. **Ural State University**(<http://acm.timus.ru/>) - **特点**:题库质量高,适合高级选手。 - **适用人群**:适合高级编程学习者。 4. **USACO Gate**(<http://ace.delos.com/usacogate>) - **特点**...
资源分类:Python库 所属语言:Python 资源全名:ural-0.28.0.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
* 俄罗斯:乌拉尔大学(URAL)、萨拉托夫大学(SGU)、EL Judge(MIPT) * 西班牙:瓦拉杜利德大学(UVA) * 美国:USACO * 波兰:SPOJ * 吉尔吉斯斯坦:KRSU 学习论坛BBS链接 学习论坛BBS链接是信息学爱好者和...
通过分析后缀数组的性质可知,最长的公共前缀一定会出现在后缀数组中相邻位置的两个后缀之间,即height[i]表示了这两个后缀之间的最长公共前缀。因此,只需要遍历后缀数组,检查每一对相邻的后缀是否来自不同的原始...
- **后缀数组**和**高度数组**:在字符串处理问题中,如PKU 2774和PKU 1743,后缀数组和高度数组用于找到最长公共前缀或最长不可重叠重复子串。 - **二分查找**:在多个题目中,如寻找第K大的数或判断子串是否存在...
1. **数据结构**:书中详细介绍了数组、链表、栈、队列等基本数据结构,并对这些数据结构的应用进行了深入探讨。 2. **排序算法**:对常见的排序算法(如冒泡排序、插入排序、选择排序、快速排序、归并排序等)进行...
- 俄罗斯托木斯克国立大学(URAL):http://acm.timus.ru/ - 白俄罗斯国立大学(SGU):http://acm.sgu.ru/ - 哈尔滨工业大学(HIT):http://acm.hit.edu.cn/ - 湖南大学(HNU):...
【标题】"acm_ural_1099" 是一个与编程竞赛相关的主题,通常在ACM(国际大学生程序设计竞赛)或类似的算法比赛中出现。这类问题旨在测试参赛者解决算法问题的能力,通常需要使用一种或多种编程语言来编写解决方案。 ...
标题 "acm_ural_1148" 指向的是一个 ACM(国际大学生程序设计竞赛)问题,这个问题在 Ural University Online Judge(乌拉尔大学在线评测系统)上编号为 1148。描述中的 "Pascal acm_timus_ural_1148.pas" 表明提供...
2. Empire strikes back (ural 1520):这是一个与圆相关的问题,虽然具体细节未给出,但可以推测同样需要运用离散化策略来解决。 总结起来,离散化方法在解决与圆有关的计算问题时,通过将连续的几何对象转换为离散...
例如URAL1470 UFOs问题,可以通过三维树状数组来高效解决。 3. **线段树**: - 线段树是一种数据结构,可以用于在线性时间内处理区间查询和区间更新。在POJ2482 Stars in Your Window问题中,由于数值范围很大,...
《Ural URAL 解题思路》 在编程竞赛和算法挑战的世界中,Ural University的在线判题系统,简称Ural或URAL,是许多程序员磨炼技能的重要平台。它提供了丰富的算法题目,涵盖数据结构、图论、动态规划、数学等多个...
URAL部分测试数据是针对Timus Online Judge平台的一个竞赛或练习问题的数据集。Timus Online Judge是一个流行的在线编程竞赛和练习平台,它为参赛者提供了一系列的编程题目,以提升编程技能和算法理解能力。这个数据...
"ural部分题解"是一个关于编程竞赛平台Ural(也称为URAL Online Judge或University of Maribor Algorithmic contests)的解题集,由大牛出品。这个资源包含Vol1到Vol3的部分题目解答,虽然不完整,但大约涵盖了200道...
3. 文本ural特征:在文本识别中,词频、n-gram、TF-IDF等方法用于提取文本的关键信息。 4. 频域特征:如傅立叶变换、小波分析等,将信号从时域转换到频域,揭示其内在的周期性和频率信息。 特征选择也非常重要,好...
HDU、PKU和URAL是三个著名的在线编程竞赛平台,它们为程序员提供了丰富的算法题目,帮助参赛者提升编程技能和算法理解能力。这些平台的题目通常涵盖了基础算法、数据结构、数学逻辑等多个方面,对于准备各类编程竞赛...
2. Ural: 俄罗斯乌拉尔大学的在线判题系统,提供多种语言支持,适合练习基础到高级的算法题目。 3. Uva (University of Valladolid): 来自西班牙的一站式编程竞赛平台,拥有大量经典题目。 4. Poi: 波兰华沙大学的...
- **URAL**: <http://acm.timus.ru/> - **SPOJ**: <https://www.spoj.com/> - **Codeforces**: <https://codeforces.com/> 这些网站为算法学习者提供了丰富的练习资源。 ### 二、算法书籍推荐 #### 《算法导论...
- **俄罗斯 (URAL)**:`http://acm.timus.ru/` - 俄罗斯的一个著名在线评测系统。 - **圣彼得堡国立大学 (SGU)**:`http://acm.sgu.ru/` - 圣彼得堡国立大学的在线评测系统。 - **莫斯科物理技术学院 (MIPT)**:`...