POJ 3007 - Organize Your Train part II


问题描述

给定一个字符串,从任意位置把它切为两半,得到两条子串

定义 子串1为s1,子串2为s2,子串1的反串为s3,子串2的反串为s4

现在从s1 s2 s3 s4中任意取出两个串组合,问有多少种不同的组合方法

规定

  • (1)串Si不能和其 反串 组合
  • (2)Si+SjSj+Si 是两种组合方式(但未必是不同的组合方式)

解题思路

利用hash表查重。

穷举全部组合的情况,每枚举一个就记录一次,假如后面枚举的组合已经存在记录,说明组合重复,计数器不变,否则计数器+1 。

本题不能用STL的map映射,map太慢会超时,自己写Hash表吧!

对于 *ps 指向的字符串s,我定义的关键字

可以认为i为权重,利用字母的ASCII得到key

解决冲突方法为链地址法

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;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
 上一篇
POJ 3299 - Humidex POJ 3299 - Humidex
POJ 3299 - Humidex Time: 1000MS Memory: 65536K 难度: 水题 分类: 无 问题描述无。 解题思路纯粹的数学公式,直接求解即可。 AC 源码 Download Link /* Aut
2011-05-26
下一篇 
POJ 1691 - Painting A Board POJ 1691 - Painting A Board
POJ 1691 - Painting A Board Time: 1000MS Memory: 10000K 难度: 中级 分类: 记忆化搜索 问题描述墙上有一面黑板,现划分为多个矩形,每个矩形都要涂上一种预设颜色C。 由于涂色时,颜
2011-05-17
  目录