[NWRRC2015] Hash Code Hacker 题解

· · 题解

P7055 题解

题目传送门

看到这题的时候，千万不要被样例搞晕了，这题其实只需要适当的找规律。

这时我们可以考虑不要变化字符串的长度，把字符串中间的一些字串变化，得到哈希代码相同的字符串。

思考一会后，发现两个子串：cc 和 dD，cc 在当前位置变成 dD 时，字符串的哈希代码相同。

证明：

假设第一个 c 在字符串的第 x 位。

则 cc 的哈希代码为：

\begin{aligned} &99\times31^{n-i-1}+99\times31^{n-(i-1)-1}\\ &=99\times31^{n-i-2}\times31+99\times31^{n-i-2}\\ &=99\times32\times31^{n-i-2}\\ &=3168\times31^{n-i-2}\\ \end{aligned}

而 dD 的哈希代码为：

\begin{aligned} &100\times31^{n-i-1}+68\times31^{n-(i-1)-1}\\ &=100\times31^{n-i-2}\times31+68\times31^{n-i-2}\\ &=(100\times31+68)\times31^{n-i-2}\\ &=3168\times31^{n-i-2}\\ \end{aligned}

至此，证明结束，结论成立。

于是我们想到可以将一个仅由 c 构成的字符串，将里面的 cc 变成 dD，为了方便，只变连续的一段。

Code

#include <bits/stdc++.h>
using namespace std;
int n;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= 100; i++){
        for (int j = 1; j <= 100 - i + 1; j++){
            if (n){
                n--;
            } else {
                return 0;
            }
            for (int k = 1; k < j; k++){
                cout << "cc";
            }
            for (int k = 1; k <= i; k++){
                cout << "dD";
            }
            for (int k = j + i; k <= 100; k++){
                cout << "cc";
            }
            cout << endl;
        }
    }
    return 0;
}

此代码时间复杂度 O(n)，空间复杂度 O(1)，完美过关！