洛谷P2724 联系 Contact

- 17通过
- 86提交
题目提供者该用户不存在
标签
难度普及/提高-

讨论题解

题目背景

奶牛们开始对用射电望远镜扫描牧场外的宇宙感兴趣。最近，他们注意到了一种非常奇怪的脉冲调制微波从星系的中央发射出来。他们希望知道电波是否是被某些地外生命发射出来的，还是仅仅是普通的的星星发出的

题目描述

帮助奶牛们用一个能够分析他们在文件中记下的记录的工具来找到真相。他们在寻找长度在A到B之间（包含A和B本身）在每天的数据文件中重复得最多的比特序列 (1 <= A <= B <= 12)。他们在找那些重复得最多的比特序列。一个输入限制告诉你应输出多少频率最多的序列。

符合的序列可能会重叠，并且至少出现一次的序列会被计数

输入输出格式

输入格式：

第一行：三个用空格分隔的整数: A, B, N; (1 <= N < 50)

第二行及以后: 一个最多200，000字符的序列，全是0或1; 每行字符数不大于80。

输出格式：

输出N个频率最高的序列（按照频率由高到低的次序）。由短到长排列频率相同的这些序列，如果长短相同，按二进制大小排列。如果出现的序列个数小于N，输出存在的序列。

对于每个存在的频率，先输出单独包含该频率的一行，再输出以空格分隔的这些序列。每行六个（除非剩下的少于六个）。

输入输出样例

输入样例#1：

2 4 10
01010010010001000111101100001010011001111000010010011110010000000

输出样例#1：

23
00
15
01 10
12
100
11
11 000 001
10
010
8
0100
7
0010 1001
6
111 0000
5
011 110 1000
4
0001 0011 1100

说明

在样例里，序列100出现了12次，而序列1000出现了5次。次数最多的序列是00，出现了23次。

题目翻译来自NOCOW。

USACO Training Section 3.1

分析：一开始想到的是dp,但是发现不太现实，那么就要枚举所有可能的序列，并且记录次数？那么用结构体吗？这样的话每搜到一个序列，就要在已经记录的结构体中查找，花费了太长时间，可以将序列和次数关联起来的还有map,那么用一个map,将所有符合条件的序列的次数都统计下来,先枚举长度为a的，再枚举长度为a+1的，枚举到长度为b的为止.，由于序列的个数不明确，所以用一个不定长数组vector,那么根据题目的条件排序后，再按照要求输出，这个输出要求真**多.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <vector>

using namespace std;

struct node
{
    string s;
    int sizee;
};

int a, b, n;
string temp, s;
map<string, int> m;
vector <node> v;

bool cmp(node a, node b)
{
    if (a.sizee != b.sizee)
        return a.sizee > b.sizee;
    if (a.s.size() != b.s.size())
        return a.s.size() < b.s.size();
    return a.s < b.s;
}

int main()
{
    scanf("%d%d%d
", &a, &b, &n);
    while (cin >> temp)
        s += temp;

    while (a <= b)
    {
        for (int i = s.size() - a; i >= 0; i--)
        {
            string t = s.substr(i, a);
            if (m[t] == 0)
            {
                node tt;
                tt.s = t;
                tt.sizee = 0;
                v.push_back(tt);
            }
            m[t]++;
        }
        a++;
    }
    for (int i = 0; i < v.size(); i++)
        v[i].sizee = m[v[i].s];
    sort(v.begin(), v.end(), cmp);
    int cur = 0;
    while (n--)
    {
        if (cur == v.size())
            break;
        cout << v[cur].sizee << endl << v[cur].s;
        int num = 1;
        while (++cur < v.size() && v[cur].sizee == v[cur - 1].sizee)
        {
            if (num == 6)
            {
                printf("
");
                num = 0;
            }
            else
                printf(" ");
            cout << v[cur].s;
            ++num;
        }
        printf("
");
    }

    return 0;
}