- POJ 3007 - Organize Your Train part II
- Time: 1000MS
- Memory: 65536K
- 难度: 中级
- 分类: 基础算法
0x00 POJ 原题
Description
RJ Freight, a Japanese railroad company for freight operations has recently constructed exchange lines at Hazawa, Yokohama. The layout of the lines is shown in Figure 1.
Figure 1: Layout of the exchange lines
A freight train consists of 2 to 72 freight cars. There are 26 types of freight cars, which are denoted by 26 lowercase letters from “a” to “z”. The cars of the same type are indistinguishable from each other, and each car’s direction doesn’t matter either. Thus, a string of lowercase letters of length 2 to 72 is sufficient to completely express the configuration of a train.
Upon arrival at the exchange lines, a train is divided into two sub-trains at an arbitrary position (prior to entering the storage lines). Each of the sub-trains may have its direction reversed (using the reversal line). Finally, the two sub-trains are connected in either order to form the final configuration. Note that the reversal operation is optional for each of the sub-trains.
For example, if the arrival configuration is “abcd”, the train is split into two sub-trains of either 3:1, 2:2 or 1:3 cars. For each of the splitting, possible final configurations are as follows (“+” indicates final concatenation position):
[3:1]
abc+d cba+d d+abc d+cba
[2:2]
ab+cd ab+dc ba+cd ba+dc cd+ab cd+ba dc+ab dc+ba
[1:3]
a+bcd a+dcb bcd+a dcb+aExcluding duplicates, 12 distinct configurations are possible.
Given an arrival configuration, answer the number of distinct configurations which can be constructed using the exchange lines described above.
Input
The entire input looks like the following.
the number of datasets = m
1st dataset
2nd dataset
…
m-th dataset
Each dataset represents an arriving train, and is a string of 2 to 72 lowercase letters in an input line.
Output
For each dataset, output the number of possible train configurations in a line. No other characters should appear in the output.
Sample Input
4
aa
abba
abcd
abcdeSample Output
1
6
12
18Source
0x10 题目概述
给定一个字符串，从任意位置把它切为两半，得到两条子串
定义 子串 1 为 s1，子串 2 为 s2，子串 1 的反串为 s3，子串 2 的反串为 s4
现在从 s1 s2 s3 s4 中任意取出两个串组合，问有多少种不同的组合方法
规定：
- （1）串 Si 不能和其 反串 组合
- （2）
Si+Sj与Sj+Si是两种组合方式（但未必是不同的组合方式）
0x20 解题思路
利用 hash 表查重。
穷举全部组合的情况，每枚举一个就记录一次，假如后面枚举的组合已经存在记录，说明组合重复，计数器不变，否则计数器+1。
本题不能用 STL 的 map 映射，map 太慢会超时，自己写 Hash 表吧！
对于 *ps 指向的字符串 s，我定义的关键字
可以认为 i 为权重，利用字母的 ASCII 得到 key
解决冲突方法为链地址法
0x30 AC 源码
//Memory Time
//2380K 157MS
#include<iostream>
using namespace std;
const int size=80;
const int mod=99991;
int count; //计数器
typedef struct HASH
{
char s[size];
struct HASH* next;
HASH()
{
next=0; //0<=>NULL
}
}Hashtable;
Hashtable* Hash[mod]; //hash[]是指针数组，存放地址
void hash(char* s);
void StrCopy(char* s1,char* s2); //把s2复制到s1，要确保s1.len>s2.len
void StrCut(char* s,char* s1,char* s2,int k,int slen); //把s前k个字符(0~k-1)复制到s1，第k到slen的字符复制到s2
void StrInvert(char* s1,char* s2,int len); //把s1逆序存放到s2
char* StrCat(char* s1,char* s2,char* str); //把s2连接到s1后，存放到s
int main(void)
{
int n;
cin>>n;
while(n--)
{
char train[size];
cin>>train;
int len=strlen(train);
if(len==1)
{
cout<<1<<endl;
continue;
}
memset(Hash,0,sizeof(Hash)); //0 <-> NULL
count=0;
for(int i=1;i<=len-1;i++) //i为火车分开的两部分中，前一部分的节数
{
char s1[size],s2[size];
char s3[size],s4[size]; //s3为s1的逆序，s4为s2的逆序
char str[size];
StrCut(train,s1,s2,i,len);
StrInvert(s1,s3,i);
StrInvert(s2,s4,len-i);
/*标记组合方式*/
hash(train); //s1与s2组合就是原来的train
StrCat(s2,s1,str);
hash(str);
StrCat(s1,s4,str);
hash(str);
StrCat(s4,s1,str);
hash(str);
StrCat(s3,s2,str);
hash(str);
StrCat(s2,s3,str);
hash(str);
StrCat(s3,s4,str);
hash(str);
StrCat(s4,s3,str);
hash(str);
}
cout<<count<<endl;
}
return 0;
}
void hash(char* s)
{
char* ps=s;
int key=0;
for(int i=1;*ps;i++)
key+=*(ps++)*i;
key%=mod;
if(!Hash[key]) //新key
{
Hashtable* pn=new Hashtable; //由于要存放数据，必须申请空间
//Hashtable* pn;只是单纯申请一个地址空间
StrCopy(pn->s,s);
Hash[key]=pn;
count++;
}
else //key值冲突
{
Hashtable* pn=Hash[key]; //pn指向冲突位置的链表开头
if(!strcmp(pn->s,s))
return; //不计数返回
else
{
while(pn->next)
{
if(!strcmp(pn->next->s,s)) //地址冲突且字符串相同
return;
pn=pn->next;
}
//地址冲突但字符串不同
Hashtable* temp=new Hashtable;
StrCopy(temp->s,s);
pn->next=temp; //记录新字符串
count++;
}
}
return;
}
void StrCopy(char* s1,char* s2) //把s2复制到s1
{
char* ps1=s1;
char* ps2=s2;
while(*ps2)
*(ps1++)=*(ps2++);
*ps1='\0';
return;
}
void StrCut(char* s,char* s1,char* s2,int k,int slen) //把s前k个字符(0~k-1)复制到s1，第k到slen的字符复制到s2
{
int i,ps1=0,ps2=0;
for(i=0;i<k;i++)
s1[ps1++]=s[i];
s1[ps1]='\0';
for(;i<slen;i++)
s2[ps2++]=s[i];
s2[ps2]='\0';
return;
}
void StrInvert(char* s1,char* s2,int len) //把s1逆序存放到s2
{
int ps=0;
s2[len]='\0';
for(int i=len-1;i>=0;i--)
s2[i]=s1[ps++];
return;
}
char* StrCat(char* s1,char* s2,char* str) //把s2连接到s1后，存放到s
{
int i,ps=0;
for(i=0;s1[i]!='\0';i++)
str[ps++]=s1[i];
for(i=0;s2[i]!='\0';i++)
str[ps++]=s2[i];
str[ps]='\0';
return str;
}
