NFLSPC #1 I题 Not another easy problem 题解

2018-12-04 19:52:51 By fizzydavid

参考答案: https://acm.nflsoj.com/submission/11795

test 1

签到。

test 2

输出一组在规定范围内的勾股数。

test 3

给定一个数组,让你用最少的操作,每次交换两个数,将这个数组排好序。手玩出$6$次操作的解就可以获得满分。

test 4

给定哈希值,让你求出一个符合要求的字符串。哈希方法是用$26$进制的ull。

直接将给定哈希值转成$26$进制即可。注意我们在转换前需要先将每个字符的'a'的ascii码减掉,这样所有字符就变成$0$~$25$的整数了。

test 5

给定哈希值,让你求出一个符合要求的字符串。哈希方法是用$31$进制的ull。

和test $4$做法类似。将给定哈希值转成$31$进制。不过此时可能有字符超出了小写字母的范围(即大于等于$26$)。若假定哈希后的每个字符是随机的,那么我们发现所有字符都是小写字母的概率大概是$10$%。我们可以随机几个不同的长度,或将哈希值加若干个$2^{64}$(可以将$2^{64}$转化为$31$进制数后对应位数相加,避免超出longlong范围的数值计算),期望$10$次即可得到所有字符都是小写字母的解。

test 6

给定哈希值,让你求出一个符合要求的字符串。哈希是模$10^9+7$。

随机字符串满足哈希值的概率大概是$\frac{1}{mod}$。期望随机$mod$次即可得到正确答案。

test 7

首先将所有字符串中的字符的ASCII码同时减去一个值,并同时改变哈希值。那么我们可以把字符视为任意整数。

考虑我们现在有一个字符串。我们有两种操作可以改变它的哈希值。

1) 将字符串复制一遍。 此时哈希值被乘上了$base^{len}+1$,注意这是一个偶数,那么哈希值的因子2的个数一定会至少加1。

2) 将字符串每个字符取反后复制一遍。 此时哈希值被乘上了$base^{len}-1$,注意如果$len=2^a$,那么哈希值的因子2的个数会增加$a$。

接下来考虑用这两种操作构造出所有哈希值的2的因子个数恰好为0至63的字符串。之后可以类似高斯消元得出一个满足任意给定哈希值的合法的字符串。

如果想要得到高分,那么需要尝试减小字符串的长度。注意以上两种操作都让长度变长了,那么我们可以考虑将每个字符的值乘2来代替操作2。不过这样有可能会导致字符的值域过大,不能用char表示,所以这种操作不应该在值域过大时使用。

注意到构造给定哈希值并不需要所有64种字符串,我们只需要其中的一部分。再发现2的因子在0至63的字符串中,只有个别字符串长度比较大。由于最终构造字符串长度是我们用到的字符串长度的最大值,所以我们可以考虑多次随机来减小字符串长度。

如果大家有更优秀的构造方法,欢迎与我交流。

这个测试点的构造方法的灵感来源于https://codeforces.com/blog/entry/4898

test 8

卡快排。直接复制下发程序,按顺序将每次选取的mid位置上的值从小到大赋值即可将其卡到$O(n^2)$。注意需要还原出初始数组。

test 9

卡贪心。

手动构造可以将前三个贪心卡掉。第四个随机需要加入大量选上就不是最优的物品。可以参考标算答案。

太阳说直接随机也可以得到$10$分的好成绩。不过需要保证答案选的物品数量不能太多也不能太少)

test 10

给定a数组经过若干次运算和赋值操作后的b数组,求a数组。

用程序将下发程序的代码处理后,考虑倒着还原出a数组。考虑一个$c\ = a\ \texttt{op}\ b\ $的式子(op是运算符)。我们知道这个式子之后的$a,b,c$的值,但是不知道这个式子之前$c$的值。于是每次还原时$c$将会变成未知数。若三个变量中至多有一个未知数,那么我们可以推算出这个未知数应该是多少。程序验证发现数据保证了不会出现两个或以上的未知数 (其实我也不知道我有没有保证这个性质,如果数据出错可以联系我)。将所有操作倒着处理一遍后,最后剩下的那些未知数可以随便赋值。

qwq

出题人test #4,#5,#6,#10是直接生成的答案,并没有自己做一遍。所以如果题目有问题请联系我(雾)。

其实出题人有点想直接出一道卡哈希专题的(划掉)。

评论

回复

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。