UVa 10132 File Fragmentation (想法题)

10132 - File Fragmentation

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1073

Your friend, a biochemistry major, tripped while carrying a tray of computer files through the lab. All of the files fell to the ground and broke. Your friend picked up all the file fragments and called you to ask for help putting them back together again.

Fortunately, all of the files on the tray were identical, all of them broke into exactly two fragments, and all of the file fragments were found. Unfortunately, the files didn't all break in the same place, and the fragments were completely mixed up by their fall to the floor.

You've translated the original binary fragments into strings of ASCII 1's and 0's, and you're planning to write a program to determine the bit pattern the files contained.
Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

Input will consist of a sequence of ``file fragments'', one per line, terminated by the end-of-file marker. Each fragment consists of a string of ASCII 1's and 0's.

Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

Output is a single line of ASCII 1's and 0's giving the bit pattern of the original files. If there are 2N fragments in the input, it should be possible to concatenate these fragments together in pairs to make N copies of the output string. If there is no unique solution, any of the possible solutions may be output.

Your friend is certain that there were no more than 144 files on the tray, and that the files were all less than 256 bytes in size.
Sample Input

1

011
0111
01110
111
0111
10111

Sample Output

01110111

学英语=v=~

1. all of the files on the tray were identical, all of them broke into exactly two fragments.

文件盒里的所有文件都是完全一样的,所有文件都恰好碎成了两部分。

2. If there is no unique solution, any of the possible solutions may be output.

如果没有唯一解,任何可能的答案都可以是输出。(但是题目不是Special Judge,所以只有一种文件的拼法)

思路:最短的碎片长度+最长的碎片长度=原文件的长度,所以枚举排序后的s[0]和最长的碎片拼成的文件,去比较s[1]和其他碎片拼成的文件,看是否相同。

查看本栏目更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

完整代码:

/*0.015s*/

#include<cstdio>
#include<cstring>
#include<cstdlib>  

char s[160][260], a[260], b[260];
int n, len;  

int cmp(const void* a, const void* b)
{
    return strlen((char*)a) < strlen((char*)b);
}  

bool judge()
{
    for (int i = n - 1; i >= 0; --i)
    {
        if (strlen(s[1]) + strlen(s[i]) != len) continue;
        strcpy(b, s[1]);
        strcat(b, s[i]);
        if (strcmp(a, b) == 0) return true;
        ///如果本来当前所拼的文件a就是错(不是原文件)的,那我们是不可能拼到另一个一样错的文件
        strcpy(b, s[i]);
        strcat(b, s[1]);
        if (strcmp(a, b) == 0) return true;
    }
    return false;
}  

int main()
{
    int T, i, min, max;
    scanf("%d\n", &T);
    while (T--)
    {
        n = 0;
        while (gets(s[n]) && s[n][0]) ++n;
        qsort(s, n, sizeof(s[0]), cmp);
        min = strlen(s[0]);
        max = strlen(s[n - 1]);
        len = min + max;
        for (i = n - 1; i >= 0 && (int)strlen(s[i]) == max; --i)///找那些最长的碎片去匹配s[0]
        {
            strcpy(a, s[0]);
            strcat(a, s[i]);
            if (judge()) break;
            strcpy(a, s[i]);
            strcat(a, s[0]);
            if (judge()) break;
        }
        puts(a);
        if (T) putchar(10);
    }
    return 0;
}

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索文件
, strlen
, fragment
, fragment 筛选
, b/s
, qsort
, files
, of
, The
Fragments
en 10132 4中文版、din en 10132 4中文、en10132 中文、10132、讯飞 10132,以便于您获取更多的相关知识。

时间: 2024-10-25 23:32:49

UVa 10132 File Fragmentation (想法题)的相关文章

uva 10132 - File Fragmentation

点击打开链接uva 10132 题目意思:   有一个人有n个文件,每个文件都是相同的,现在这n个文件的每一个文件都被分成了两部分用字符序列表示,要我们找到原来文件的字符序列. 解题思路:    1:每一个文件都是分裂成两部分,每一种文件都是相同的,那么只要找到最小的长度和最大的长度,那么加起来就是文件的长度记为L.                      2:知道了文件的长度,那么如果我们从第一个子串假设为S1开始,让它分别和后面的字串相匹配,匹配处理有两种可能AB和BA,如果长度为L,那么

UVa 12004 Bubble Sort:想法题

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3155 枚举交换次数算期望太麻烦,不妨换个思路:对于任意一对数字,它们之间发生交换的概率和不交换的概率是相等的,那这对数字提供的期望值就为1/2.总共有C(n,2)对数字,所以最终的期望值就为n*(n-1)/4 完整代码: 01./*0.015s*/ 02. 03.#include<cs

UVa 10132:File Fragmentation

链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1073 类型: 贪心+回溯 原题: The Problem Your friend, a biochemistry major, tripped while carrying a tray of computer files through the l

UVa 105 The Skyline Problem (想法题)

105 - The Skyline Problem Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=41 这题有个很巧的思路:离散化. 什么意思呢?既然每栋大楼的高和左右边界都是整数,那么不妨把线段用一个个整点表示.既然最后只求一个轮廓,那么对每个横坐标,就记

UVa 10795 A Different Task:汉诺塔&amp;amp;想法题

10795 - A Different Task Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=456&page=show_problem&problem=1736 The (Three peg) Tower of Hanoi problem is a popular one in computer science

UVa 10152 ShellSort (想法题)

10152 - ShellSort Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=1093 He made each turtle stand on another one's back And he piled them all up in a nine

UVa 12502 Three Families:想法题

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3946 哈哈.考想法的一道题. 首先注意到这句话:You may assume both families were cleaning at the same speed. 所以按理来说,(样例1中)本应该周末每个家庭都花3小时来清理花园,但A在忙完自己的一部分

CERC 2004 / UVa 1335 Beijing Guards:二分&amp;amp;贪心&amp;amp;想法题

1335 - Beijing Guards Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=456&page=show_problem&problem=4081 Beijing was once surrounded by four rings of city walls: the Forbidden City Wa

UVa 571 Jugs (想法题)

571 - Jugs Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=512 思路: 由于是special judge,所以构造出一个可行解就可以. 论断:如果A是空的就加水,不空就向B倒,B满了之后就empty掉,这样在B中一定可以形成0~B的任意一个解.