P1965 夜夜的数据加强 题解

这是VIJIOS上的一道题，原题的链接https://vijos.org/p/1965

先上代码，用C++写的

# include<iostream> using namespace std;int fa[100001]; int savemod[400][400][400]; int ii[100000]; // a^(i-1) 从1开始使用 int jj[100000]; // 1+a+a^2+a^(i-2) 从1开始使用 bool ans[400][400][400];int len; int amod[400][400]; // amod[i][j] = i % j;int main() {int x, a, b;int i, j, k;int n, c;cin >> n >> c;for (i = 1; i <= n-1; i++){cin >> fa[i];if (fa[i] >= i || fa[i] < 0 || fa[i] >= c){cout << "Unsuccessful Hack Attempt" << endl;return 0;}}if (n == 1){for (x = 0; x < c; x++)for (a = 0; a < c; a++)for (b = 0; b < c; b++)cout << x << " " << a << " " << b << endl;return 0;}int tmp;for (i = 0; i < c; i++)for (j = i; j < c; j++){tmp = (i*j) % c;for (k = 0; k < c - tmp; k++) {savemod[i][j][k] = tmp + k;savemod[j][i][k] = tmp + k;}for (k = 0; k < tmp; k++){savemod[i][j][c-tmp+k] = k;savemod[j][i][c-tmp+k] = k;}}for (i = 1; i < 400; i++)for (j = 2; j < 400; j++) amod[i][j] = i % j;int s;bool flag = false;if (n - 1 > c){for (a = 0; a < c; a++){for (b = 0; b < c; b++){for (i = n-2; i >= c; i--){if (savemod[fa[i]][a][b] != fa[i+1]) break;}if (i < c) for (x = 0; x < c; x++){for (s = savemod[x][a][b],j = 2; j <= c && amod[s][j] == fa[j]; s=savemod[s][a][b], j++);if (j > c){ans[x][a][b] = true;flag = true;}}}}} else{for (a = 0; a < c; a++){ii[1] = 1;for (i = 2; i < n; i++){ii[i] = savemod[ii[i-1]][a][0];}jj[1] = 0;for (i = 2; i < n; i++){jj[i] = savemod[jj[i-1]][a][1];}for (b = 0; b < c; b++)for (x = 0; x < c; x++)if (amod[savemod[x][ii[n-1]][savemod[b][jj[n-1]][0]]][n-1] == fa[n-1] && amod[savemod[x][ii[2]][savemod[b][jj[2]][0]]][2] == fa[2]){for (j = n-2; j>2 && amod[savemod[x][ii[j]][savemod[b][jj[j]][0]]][j] == fa[j]; --j);if (j == 2){flag = true;ans[x][a][b] = true;}}}}if (flag == false){cout << "Unsuccessful Hack Attempt" << endl;} else{for (i = 0; i < c; i++)for (j = 0; j < c; j++)for (k = 0; k < c; k++) if (ans[i][j][k]) cout << i << " " << j << " " << k << endl;}return 0; }

这里参考了该题doc写的题解，题解的地址为https://vijos.org/p/1965/solution。如果单纯用doc的暴力方法是不能通过的（能通过第5个测试点，但是后面的测试点不能通过），我另外加了一个优化。

考虑到N比C大很多的情况，这个时候计算fa[i]时取余运算（%i），就不起作用了，可以简化为
fa[i+1] = (fa[i] * a + b) % c（这里i >= c）
在这里只和a和b有关，与x无关，因此可以先枚举a和b，然后检验a和b是否可行，如果可行就进行，接下来枚举x再校验数列i<=c的情况（此时后面不需要校验了）。

另外这个程序要仔细编写，做尽可能的预处理，下面的测试结果可以看到在第5个测试点是很惊险地通过了。

测试数据 #0: Accepted, time = 15 ms, mem = 315184 KiB, score = 5测试数据 #1: Accepted, time = 0 ms, mem = 315180 KiB, score = 5测试数据 #2: Accepted, time = 0 ms, mem = 315180 KiB, score = 5测试数据 #3: Accepted, time = 0 ms, mem = 315184 KiB, score = 5测试数据 #4: Accepted, time = 937 ms, mem = 315184 KiB, score = 5测试数据 #5: Accepted, time = 0 ms, mem = 315184 KiB, score = 5测试数据 #6: Accepted, time = 0 ms, mem = 315180 KiB, score = 5测试数据 #7: Accepted, time = 0 ms, mem = 315180 KiB, score = 5测试数据 #8: Accepted, time = 15 ms, mem = 315188 KiB, score = 5测试数据 #9: Accepted, time = 0 ms, mem = 315180 KiB, score = 5测试数据 #10: Accepted, time = 78 ms, mem = 315184 KiB, score = 5测试数据 #11: Accepted, time = 93 ms, mem = 315184 KiB, score = 5测试数据 #12: Accepted, time = 93 ms, mem = 315184 KiB, score = 5测试数据 #13: Accepted, time = 78 ms, mem = 315184 KiB, score = 5测试数据 #14: Accepted, time = 93 ms, mem = 315180 KiB, score = 5测试数据 #15: Accepted, time = 390 ms, mem = 315180 KiB, score = 5测试数据 #16: Accepted, time = 296 ms, mem = 315180 KiB, score = 5测试数据 #17: Accepted, time = 375 ms, mem = 315180 KiB, score = 5测试数据 #18: Accepted, time = 437 ms, mem = 315184 KiB, score = 5测试数据 #19: Accepted, time = 359 ms, mem = 315184 KiB, score = 5Accepted, time = 3259 ms, mem = 315188 KiB, score = 100

总结

以上是生活随笔为你收集整理的P1965 夜夜的数据加强 题解的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。