题解 P6660 【[POI 2019] Pisarze】

· · 题解

update：远古题解，修复了部分意识流表述，并且尽可能地修复了不符合题解格式规范的问题。如果还有格式问题，辛苦管理员指出。

在和 @shenmadongdong 的合作下拿到了 100 分。
不要问我为什么代码和他那么像（其实是一模一样），本来就是合作的
声明：打表程序主要为我写，主程序主要由 shenmadongdong 写。（所以大部分提交都是 shenmadongdong 提交的）
还有，打表程序已经丢失了（悲）。

之前看到这个帖子说用什么 b2z 压缩，但是我完全不会，所以只能自己瞎摸索。

首先有一个朴素的想法，把所有单词统计在每个文本中出现的次数，存在一个 map 中，再通过某种方法得出单词在文本中出现的频率。

最后在处理的时候，读入一个串，得到每个单词它在每个文本中出现频率，相乘后，输出最大的值对应的文本。
这样的准确性比较高，实际上，对于一个文本，只要有一个单词没有在串中出现，它的权值就会直接变为 0，因此不会选择这段文本。

显然这样会超出代码长度限制，因此我们需要压缩。
首先是最简单的压缩：压入 map 的函数很长，我们可以用一个函数来实现。
void G(string s,int a,int b,int c){mp[s].p=a;mp[s].s=b;mp[s].m=c;} 但是单词实在太多了，这样是远远不够的。

我的方法可能比较奇怪，就是对于一个单词，每 3 位划分当作一个新的“单词”。
比如对于单词 \mathrm{abcdef}，分解成 \mathrm{abc\ bcd \ cde\ def} 4 个单词，然后放入 map 中
这样虽然单词变多了，但是由于只剩下 3 位，有很多重复的了。
（注：不到 3 位的单词直接存，反正也不多）

但是这样还是存不下。
我们考虑将一些用处不是很大的 3 位串去掉。

假如一个单词在 3 个文本中出现的频率差不多，我们可以不要他。
if (Max>Min*X\*X为自己定义的实数*\)
我觉得这样操作比较好，因为这样一定可以把只在部分文本中出现过的单词存进去。
经过一定的调参，我们可以把打表程序压到 50kb 以下。

然后获得 84 分的好成绩。

这样的单词数目还是太少，准确率不够高。
我们可以再定义 3 个函数，对于函数内部有两个数都是 0 的单词（即只在一个文本中出现的单词）定义一个新的函数，可以略微压缩一些代码长度，因此可以调 X 输出更多的单词。 

void P(J s){mp[s].p=1,mp[s].s=0,mp[s].m=0;}
void M(J s){mp[s].m=1,mp[s].s=0,mp[s].p=0;}
void S(J s){mp[s].s=1,mp[s].p=0,mp[s].m=0;}

获得 92 分。link

P.S.：然后我们走了一些弯路，决定不区分大小写来压缩，但是这样失真过大，最终决定还是区分大小写。

然后我们觉得用一个函数来搞还是太占字符数，每次都要双引号啊，括号啊什么的挺麻烦的。我们就把单词压入不同的字符串里，进行字符串的处理，这样又能多打一些单词。
比如说，其中的一段字符串长这样：spi115,220,50spl47,39,16spo1340,612,196spr446,213,69。
可以获得 96 分。link

如果你能看到上面的这一份代码，你会发现字符串 G3 中有很多逗号，那是为了区分不同的数字。（注：Prus.txt 里面是存在数字的，但是这些数字一定存在 P1 P2 P3 字符串中，不会对 G3 的判断造成干扰，因为其他两个文本中都没有数字）

这些逗号占得位置很多，我们考虑怎么把它去掉。
这里我们把数字用 91 进制表示，用了 美元符号 到 ~ 的所有字符，然后如果单词有超过 8100 的数字，就直接用函数，不然的话这个数字一定可以压在 2 位字符中。

实测压缩效果并不好，因为很多数字都是只有 1 位的。
因此我们再加了一个特判，如果单词里面的数字没有超过 91 的，那就把它放入另外一个字符串内，这个字符串中每个单词一定都可用 3 个字符来表示参数。
这样就可以多输出一些单词啦！
最终我的代码参数 X 压到了 1.6（最开始是 15）。
然后经过主程序中的一些调参，达到了 98 分。
link

经过我们的一些试验，我们发现在上述过程中，X 并非是越小越好，大概在 1.7 时表现最优。
那么我们就多出了一些空间，考虑打一些其他的东西。
我们选择对于每个单词，将它首尾相接拼成一个 2 位字符串，用函数放入另外一个 map 中。
很遗憾，加上这个以后代码又超过 50kb 了

然后再用类似于上面的处理，把它压入两个字符串中。
然而还是会超。

我们再增加一些筛选条件，顺便也把上面的 3 位字符串也筛选一下。
这里增加了限定如果总出现次数比较少，就不输出。
最后再经过漫长地调参过程（这个过程主要在LOJ上进行），我们达到了 99 分！
link

我们又加入了一些限制条件，在分数下降不严重的情况下省下了另外一些空间。
然后我们再考虑打一些其他的东西。

注意到我们还是在对每个单词独立地进行处理，没有考虑到它是一段连续的文本。
这里我们选择将前一个单词的最后一位和后一个单词的第一位拼起来，再开一个 map 存储。
它又超了。
如果它的出现总数比较小，那么它在输入中的概率也比较小，那么我们可以不输出它。
int SSUM=mp[tmp].p+mp[tmp].s+mp[tmp].m;
if (SSUM>=?)
然后我们再进行一些诡异地调参，得到了更好的成绩（只是通过了更多测试点，分数没有提高）

我们对我们得分最低的点 #64 进行了分析

然后，我们发现，如果去掉之前的P S M这类函数的操作，对其他点影响不大，但是 #64 得分掉得挺多。
于是我们决定打出一部分 4 位字符串。
这 4 位字符串，我们选择只截取一个单词的前 4 位，并且这个字符串只在一个文本中出现的时候输出。
然后限定了一下出现次数，在 LOJ 上获得 PC 100 分。（大概是四舍五入成 100 分了） 

if (L==4)
{
    if (PP==0 && (SS==0 && mp[tmp].m>=6)) MA[++cntM[L]][L]=tmp2,cerr<<mp[tmp].m<<endl;
    else if (PP==0 && (MM==0 && mp[tmp].s>=6)) SA[++cntS[L]][L]=tmp2,cerr<<mp[tmp].s<<endl;
    else if (MM==0 && (SS==0 && mp[tmp].p>=6)) PA[++cntP[L]][L]=tmp2,cerr<<mp[tmp].p<<endl;
    continue;
}

（但是在洛谷上还是99分）

接下来开始乱调参。
我们把 3 个 6 分别换成 3,3,9 左右（具体记不清了）就能在 LOJ 上 AC 了。
然而这样还是超出代码限制了（51.5k）。
然后是一个诡异的操作：我们发现字符串 S3 的长度比较长，就把 S3 给删了。
然后依然能 AC，并且代码在长度限制内。
至于为什么，我也不清楚，反正这本来就是个乱搞题。
那么我们就愉快地过了这道题啦。
link
AC代码，经过地狱般的压行，谨慎食用