网址压缩

Posted on Edited on In

题目大意：我们现在的任务是给定𝑁个只包含小写字母的字符串，你需要输出对这𝑁个字符串进行压缩的结果。你可以使用任意的压缩算法，但你需要保证满足如下的性质：1、压缩的结果字符串仍然只有小写字母。2、压缩的结果不能是空串，且长度必须要比原来的字符串短。3、相同的字符串压缩结果必须相同，不同的字符串压缩结果必须不同。任意满足上述条件的压缩方法都是正确的，所以你的目标就是对给定的𝑁个字符串进行压缩。数据保证有解。

按长度排个序，然后a,b,c,…z,aa,ab,ac….就可以了

关键是就是模拟

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>

using namespace std;

map<string, bool> mp;
map<string, string> Hash;

struct yhm
{
    string s, res, id;
}q[1666];

inline bool cmp1(yhm a, yhm b)
{
    return a.s.length() < b.s.length();
}

inline bool cmp2(yhm a, yhm b)
{
    return a.id < b.id;
}

signed main()
{
    int i, n = read();
    for (i = 1; i <= n; ++ i) getline(cin, q[i].s), q[i].id = i;
    sort(q + 1, q + n + 1, cmp1);

    char p1 = 'a', p2 = 'a', p3 = 'a'; int num = 1;

    for (i = 1; i <= n; ++ i)
    {
        string now = q[i].s;
        if (mp[now])
        {
            q[i].res = Hash[now];
            continue;
        }

        string x;

        if (num == 1) x = p1, Hash[now] = q[i].res = x;
        else if (num == 2) x = p2, x += p1, Hash[now] = q[i].res = x;
        else if (num == 3) x = p3, x += p2, x += p1, Hash[now] = q[i].res = x;

        int num_now = num;
        if (num_now == 1)
        {
            if (p1 == 'z') ++ num, p1 = 'a';
            else ++ p1;
        }
        if (num_now == 2)
        {
            if (p1 == 'z')
            {
                if (p2 == 'z') ++ num, p1 = p2 = 'a';
                else ++ p2, p1 = 'a';
            }
            else ++ p1;
        }
        if (num_now == 3)
        {
            if (p1 == 'z')
            {
                if (p2 == 'z')
                {
                    if (p3 == 'z') ++ num, p1 = p2 = p3 = 'a';
                    else ++ p3, p1 = p2 = 'a';
                }
                else ++ p2, p1 = 'a';
            }
            else ++ p1;
        }
        mp[now] = true;
    }

    sort(q + 1, q + n + 1, cmp2);
    
    for (i = 1; i <= n; ++ i) cout << q[i].res << '\n';

    return 0;
}

后记：

这次考试在评测的时候，第二题编译错误挂了40分，第一题没有SPJ挂了90分

我依旧是倒数

今天下午考试头疼别疼，一直低烧，很难受，但是硬撑着，期望得分是100+40+10pts，这个水平属于中游

我觉得我可以，我也有实力去搞第三题，但是在那种环境下，我实在没办法投入精力去想，我觉得我能做到150pts已经很棒了

而180就已经是前三名了

这个分数的变化非常大，也非常好得到，并不是不会，通常都是差一点点的小细节

我从来不知道别人怎么看我，我也从来不觉得自己比他们差，我不知道我比他们强在哪里，但是我自信比他们强

或许可以称为自负，wlj学长说，最终的CSP/NOIp都会见分晓的

虎瘦雄心在，人穷志不短

无论落魄到什么地步，都不要触碰做人的底线，心怀勇气的走下去，只有这样才能逐渐摆脱困境