首页 > ACM题库 > HDU-杭电 > hdu 1932 Ambiguous Codes-字符串[解题报告]C++
2013
12-26

hdu 1932 Ambiguous Codes-字符串[解题报告]C++

Ambiguous Codes

问题描述 :

An extensive area of research in computer science is the field of communications. With computer networks being part of everyday life of many people, the development of ways for making networks faster, more reliable and secure is constantly needed. This practical need motivates an extensive research activity in the theory behind communications.

The very first thing needed to establish any kind of communication is a common code. A code is a way of changing the form of a piece of information into some other form, in general to make it possible to convey that piece of information from one place to another. Flag codes used by boats and the Morse code used in telegraphy are examples of codes for translating letters into different forms to enable communication over different media.

More formally, a code is a set of strings composed of symbols from one alphabet. Each string defined in the code is called a code word. A message is then composed concatenating a set of code words to convey the information needed. For example, in Morse code the alphabet is composed of the symbols hyphen and dot; letter “S” is represented by the code word “…”, letter “O” is represented by the code word “—”, and therefore the distress message “SOS” in Morse code is “…—…”.

Codes for communication can have many desirable and undesirable properties such as ambiguity, entropy, redundancy, and many more. In this problem we will focus on ambiguity as a key property.

A code is ambiguous when there exists a message using that code that can be partitioned into different sequences of code words. In other words, in an ambiguous code a message may have more than one meaning. For example, consider the binary alphabet, composed of symbols {0,1}. For the code composed of the words {10, 01, 101} the message 10101 can be understood as 10-101 or 101-01 and therefore the code is ambiguous. On the other hand, for the code composed of the words {01, 10, 011} no ambiguous message exists and therefore the code is unambiguous.

As a part of the computer science community, you are required to develop a tester that checks if codes are ambiguous. In case a code is indeed ambiguous, you are also required to report the length (i.e. the number of symbols) of the shortest ambiguous message for that code.

输入:

Each test case will consist on several lines. In all test cases the alphabet will be the set of hexadecimal digits (decimal digits plus the uppercase letters “A” to “F”). The first line of a test case will contain an integer N (1 <= N <= 100), the number of code words in the code. Each of the next N lines describes a code word and contains a different and non-empty string of at most 50 hexadecimal digits.
Input is terminated by N = 0.

输出:

Each test case will consist on several lines. In all test cases the alphabet will be the set of hexadecimal digits (decimal digits plus the uppercase letters “A” to “F”). The first line of a test case will contain an integer N (1 <= N <= 100), the number of code words in the code. Each of the next N lines describes a code word and contains a different and non-empty string of at most 50 hexadecimal digits.
Input is terminated by N = 0.

样例输入:

3
10
01
101
3
AB
BA
ABB
0

样例输出:

5
-1


题意大概是这样的
就是让我们去早这么一个字符串,是由前面给的字符串拼成的,然后如果这个拼成的字符能够拆成另外的由前面给出的字符串的话就是Ambiguous ,让我们输出长度最短的Ambiguous 的长度,如果没有就输出-1
如输入
01
10
101
可以找到最短的10101
它可以看成是101 01组成
也可以看成10 101组成
所以就输出10101的长度5

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#define maxn 100+5
#define maxlen 50+5
int n;
char str[maxn][maxlen];
int toX[maxn][maxlen][maxn];
int toY[maxn][maxlen][maxn];
int need[maxn][maxlen][maxn];
int len[maxn];
using namespace std;
void check(){
    for(int i = 0; i < n; i++){
        len[i] = strlen(str[i]);
    }
    for (int i = 0; i < n; i++){
        for (int j = 1; j <= len[i]; j++){
            for (int k = 0; k < n; k++){
                if(j == len[i] && i == k){//如果str[k]就是str[i]本身
                    toX[i][j][k] = -1;
                }
                else if(memcmp(str[i] + len[i] - j, str[k], min(j, len[k])) == 0){
                    toX[i][j][k]  = j > len[k] ? i : k;
                    toY[i][j][k] = fabs(j - len[k]);
                    need[i][j][k] = j > len[k] ? 0 : len[k] - j;
                }
                else  toX[i][j][k]  = -1;
            }
        }
    }
}
const int maxq = (maxn) * (maxlen) * 10;
int q[maxq],begin,end;
int dis[maxn][maxlen];
bool inq[maxn][maxlen];
void spa(){
    begin = 0;
    end = 0;
    memset(dis, 0x3f, (sizeof(dis)));
    memset(inq, 0, sizeof(inq));
    for(int i = 0; i < n; i++){
        q[end++] = i;
        q[end++] = len[i];
        dis[i][len[i]] = len[i];
        inq[i][len[i]] = true;
    }
    while(begin != end){
        int x = q[begin++];
        int y = q[begin++];
        if (begin == maxq)  begin = 0;
        inq[x][y] = false;
        for(int i = 0; i < n; i++){
            if(toX[x][y][i] != -1){
                int xx = toX[x][y][i];
                int yy = toY[x][y][i];
                int ll = need[x][y][i];
                if(dis[xx][yy] > dis[x][y] + ll){//如果dis[xx][yy]还没有求出来
                    dis[xx][yy] = dis[x][y] + ll;
                    if(!inq[xx][yy]){
                        q[end++] = xx;
                        q[end++] = yy;
                        if(end == maxq){
                            end = 0;
                        }
                        inq[xx][yy] = true;//标记inq[xx][yy]在队列中
                    }
                }
            }
        }
    }
}
void output(){
    int ans = 0x3f000000;
    for(int i = 0; i < n; i++){
        if(ans > dis[i][0]){
            ans = dis[i][0];
        }
    }
    printf("%d\n", ans >= 0x30000000 ? -1 : ans);
}
int main(){
        while(scanf("%d", &n), n){
            for (int i = 0; i < n; i++){
                scanf("%s", str[i]);
            }
        /*判断每一个字符串的最后的每一位可以用哪一个字符串的前几位接上,记下最后的几位是属于哪个
        字符串(toX来储存),相对多出了几位(用toY来储存), 需要在当前的字符串后面加上几位才能、
        得到新串(need来储存)*/
        check();
        /*枚举出所有在末尾加字符串后的结果*/
        spa();
        output();
        }
}

 


  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n