- 浏览: 197326 次
- 性别:
- 来自: 武汉
文章分类
- 全部博客 (137)
- c++ (74)
- c++,算法,回溯 (2)
- DP问题。 (9)
- DP问题,0/1背包问题 (3)
- 数学问题 (6)
- 贪心算法 (10)
- 排序 (16)
- 数据结构 (7)
- 容器 (2)
- 模拟问题 (2)
- 水题 (8)
- 并查集 (3)
- 非技术 (2)
- 素数问题 (1)
- DFS (3)
- 二叉树 (1)
- 递归 (1)
- 图论 (5)
- 最小生成树 (5)
- 最短路径 (6)
- bell_flaod算法 (2)
- hash (3)
- 二分查找 (1)
- 搜索 (5)
- BFS (5)
- STL (3)
- 字符串hash (1)
- 拓扑排序 (1)
- 字典树 (4)
- 哈弗曼树 (1)
- KMP (7)
- 线段树 (9)
- 树状数组 (6)
- 全排列 (2)
- DP问题 (2)
- LCS (1)
- 最长不下降子序列 (2)
- 面试经验 (3)
大致题意: 给定一个字符串,从任意位置把它切为两半,得到两条子串 定义 子串1为s1,子串2为s2,子串1的反串为s3,子串2的反串为s4 现在从s1 s2 s3 s4中任意取出两个串组合,问有多少种不同的组合方法 规定: (1) 串Si不能和其 反串 组合 (2) Si+Sj 与 Sj+Si 是两种组合方式(但未必是不同的组合方式) 代码如下:
思路:字符串ELFHash 哈希,针对本题来说就是把组合后的字符串转化为数字存起来,进行比较。
//题意:给定一个字符串,从任意位置把它切为两半,得到两个子串
//定义子串1为s1,子串2为s2,子串1的反串为s3,子串2的反串为s4
//现在从s1 s2 s3 s4中任意取出两个串组合,问有多少种不同的组合方法
//限制: (1) 串Si不能和其反串组合 (2) Si+Sj与Sj+Si是两种组合方式(但未必是不同的组合方式)
#include <iostream> //字符串ELFHash 哈希
#include <algorithm>
#include<string>
using namespace std;
const int M=10000; //M=100000 MLE M=100000 7972K 844MS M=10000 928K 79MS
int len,res;
char table[10000][80],str[80],tmp[80];
int ELFHash(char a[80])
{
int h = 0;
int x = 0;
for(int i=0;i<len;++i)
{
h = (h << 4) + (a[i]);
if ((x = h & 0xF0000000L) != 0)
{
h ^= (x >> 24);
h &= ~x;
}
}
return h % M;
}
void insert(char a[]) //ELFHash函数对字符串判重
{
int i=ELFHash(a);
while(strlen(table[i])>0&&strcmp(a,table[i])!=0)
i=(i+1)%M;
if(strlen(table[i])==0)
{
strcpy(table[i],a);
res++;
}
}
int main()
{
int t,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%s",str);
len=strlen(str);
tmp[len]='\0';
res=0;
for(i=0;i<M;++i)
strcpy(table[i],"");
insert(str);
reverse(&str[0],&str[len]);
insert(str);
for(i=0;i<len-1;++i) //( 0 i ),( i+1 len-1 ) 设原字符串拆分为两个子串 A,B,经重新组合变成 C,D
{
//前三个insert都是C对应A,D对应B,不应出现"正向 正向"的组合,因为这正是原字符串
//后三个insert都是C对应B,D对应A,不应出现"反向 反向"的组合,因为这正是原字符串的翻转
for(j=0;j<=i;++j)
tmp[j]=str[j];
for(j=i+1;j<len;++j)
tmp[i+len-j]=str[j];
insert(tmp); //正向 反向 ,表示 A(!B) , (!B)意思是反向
for(j=0;j<=i;++j)
tmp[i-j]=str[j];
for(j=i+1;j<len;++j)
tmp[j]=str[j];
insert(tmp); //反向 正向 ,表示 (!A)B
for(j=0;j<=i;++j)
tmp[i-j]=str[j];
for(j=i+1;j<len;++j)
tmp[i+len-j]=str[j];
insert(tmp); //反向 反向 ,表示 (!A)(!B)
for(j=i+1;j<len;++j)
tmp[j-i-1]=str[j];
for(j=0;j<=i;++j)
tmp[j+len-i-1]=str[j];
insert(tmp); //正向 正向 ,表示 BA
for(j=i+1;j<len;++j)
tmp[j-i-1]=str[j];
for(j=0;j<=i;++j)
tmp[len-1-j]=str[j];
insert(tmp); //正向 反向 ,表示 B(!A)
for(j=i+1;j<len;++j)
tmp[len-1-j]=str[j];
for(j=0;j<=i;++j)
tmp[j+len-i-1]=str[j];
insert(tmp); //反向 正向 ,表示 (!B)A
}
printf("%d\n",res);
}
return 0 ;
}
发表评论
-
虚函数、纯虚函数、虚基类、抽象类、虚函数继承、虚继承
2013-08-29 14:34 791虚函数:虚函数是C++中用于实现多态(polymorphis ... -
排序算法总结
2013-05-17 11:00 793选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法, ... -
poj 3122
2012-12-11 19:51 817题意:作者要开一个生日party,他现在拥有n块高度都为1 ... -
poj 3273
2012-12-11 16:49 951题意:给你天数n,和每天需要花的钱,让你把这些天分成m份(每份 ... -
字典树学习材料
2012-05-30 14:29 938字典树,又称单词查找树,Trie树,是一种树形结构,典型应 ... -
poj 1159
2012-05-28 19:08 1406题目大意:给你一段字符串,让你求出在中间最少加入几个字符 ... -
poj 3176
2012-05-28 14:47 983大致题意: 输入一个n层的三角形,第i层有i个数,求从第 ... -
poj 1260
2012-05-28 09:54 1578题意解释: 有n个等级的珠宝,等级依次升高,等级越高价钱越高 ... -
poj 1836
2012-05-28 09:22 2676是POJ2533的扩展题。题意不难,令到原队列 ... -
poj 2533
2012-05-26 15:36 1213在做这道题目之前,首先让我们了解一下什么是LIS算法,LIS俗 ... -
poj 3267
2012-05-26 09:43 779从程序可以看出,第i个位置到L所删除的字符数,总是先取最坏情况 ... -
poj 1276
2012-05-25 16:20 2358题意: 这道题的意思是给你一堆钱,各种面值的都有,比 ... -
poj 1094
2012-05-25 13:54 1068题意:给出字母个数,和有限个有序对(a<b)求出能确定字 ... -
poj 3393
2012-05-23 17:00 1232大致题意: 科普文一篇,文章80%都是无用信息,因为 ... -
poj 3096
2012-05-10 21:09 970题意: 定义D-pairs表示取字符串s中相距为D的两个字母 ... -
poj 1426
2012-04-26 20:11 2127大致题意: 给出一个整数n,(1 <= n <= ... -
poj 1797
2012-04-24 15:05 1593题目大意是就是何处一个图,n个顶点和m条边,每个边都有最大承载 ... -
poj 1338
2012-04-23 10:20 1228题意:题目意思是求由2,3,5的乘积组成的数从大到小排列,从1 ... -
poj 2021
2012-04-19 15:00 904题意:Ted今年100岁,给出n对他家族的关系:“父 ... -
poj 1656
2012-04-19 10:07 1097题目要求:一道纯的模拟题目。 直接上代码: ...
相关推荐
北大POJ3007-Organize Your Train part II 解题报告+AC代码
包含15类的POJ推荐50题,可全面复习或学习算法。 除此外还包含三种级别的水平(初级、中级、高级)应掌握的算法及数据结构及... (poj3096,poj3007)(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj分类poj分类poj分类poj分类
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
北大POJ2002-Squares 解题报告+AC代码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码