前言
第一次做出 6 道题。
比赛过程
A 题白给，耗时 \(\text{1min}\)。
B 题白给，然而突然忘了 odd number 是奇数还是偶数，于是翻译了一下。耗时 \(\text{2mins}\)。
C 题直接并查集，看到数据范围按秩合并都没写，耗时 \(\text{2mins}\)。
D 题也比较白给，然而我写了个欧拉筛，耗时 \(\text{7mins}\)。
E 题白给，然而我太菜了，往 \(dp\) 想了半天也不会，于是直接浪费几十分钟也不会，然后看 F。
F 题直接上字符串哈希，由于听说 AT 的数据很严，于是用 \(10^9+7\) 和 \(998244353\) 做模数写了双哈希，调试了亿下就过了。耗时约 \(\text{35mins}\)。
E 题回来再看，又想了半天，啥也不会，于是打算先写个暴力，写完发现如果当前答案超过 \(10^6\) 直接返回就好了，顿时茅塞顿开，感觉自己就是个大**，然后就过了。算上想的时间，耗时 \(\text{39mins}\)(……)。
虽然做出 4 道，但由于我在 E 浪费太多时间，导致最终也就 600 多名，不过还是有进步的。
最终排名：\(\text{rk616}\)
最终Rating：\(\text{1045+97=1142}\)
题目总结
由于 A,B,C 比较白给，于是写一下 D,E,F 的。
D - Happy New Year 2023
题意：给你一个 \(N(1\le N \le9 \times 10^{18})\)，而 \(N=p^2q(p,q \text{为质数})\)，求出 \(p, q\)。
思路：
我们如果把 \(p^2q\) 看成 \(p\times p \times q\)，就会发现一个有趣的事实：
\[\min\{p,p,q\}=\min\{p,q\} <\sqrt[3]{N} < 3 \times 10^6 \]所以我们可以用欧拉筛筛出所有 \(3 \times 10^6\) 以内的质数，然后枚剧检验即可。这样时间复杂度是 \(O(3000000T)\)。
代码：
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 10000000
bool p[N + 5] = {false};
vector<int> pr;
void init() {
memset(p, true, sizeof p);
p[0] = p[1] = false;
for (int i = 2; i <= N; i++) {
if (p[i])
pr.push_back(i);
for (int j = 0; j < (int)pr.size() && i * pr[j] <= N; j++) {
p[i * pr[j]] = false;
if (i % pr[j] == 0)
break;
}
}
}
long long n;
void solve() {
cin >> n;
for (int i = 0; i < (int)pr.size(); i++) {
if (n % pr[i] == 0) {
if (n % (1ll * pr[i] * pr[i]) == 0)
printf("%lld %lld\n", pr[i] * 1ll, n / (1ll * pr[i] * pr[i]));
else {
long long ans = (sqrt(n / pr[i]) + 0.5);
printf("%lld %lld\n", ans, pr[i] * 1ll);
}
break;
}
}
}
int main() {
init();
int T;
cin >> T;
while (T--)
solve();
return 0;
}
E - Count Simple Paths
题意：设一张 \(N\) 个点 \(M\) 条边的无向图中有 \(K\) 条起点为 1 的简单路径，保证每个点的度数小于等于 \(10\), 求出 \(\min\{K,10^6\}\)。
思路：
直接暴力搜索，然后如果当前路径总数大于 1000000 直接返回即可，最多 \(10^6\) 次。
代码：
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 2e5 + 5;
int n, m;
vector<int> e[MAXN];
int cnt[MAXN] = {0};
bool vis[MAXN] = {false};
int dfs(int x) {
vis[x] = true;
int ans = 1;
for (auto i: e[x])
if (!vis[i]) {
ans += dfs(i);
if (ans >= 1000000)
return 1000000;
}
vis[x] = false;
return ans;
}
int main() {
cin >> n >> m;
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
cout << dfs(1);
return 0;
}
F - ABCBAC
题意：有一个长度为 \(N\) 的字符串 \(S\) 和一个整数 \(i(0\le i\le N)\)，我们构造出一个长度为 \(2N\) 字符串 \(T\) 满足：\(T\) 的前 \(i\) 个字符是 \(S\) 的前 \(i\) 个字符；\(T\) 的第 \(i+1\) 到第 \(i+n\) 个字符组成的子串是 \(S\) 反转；T 的后 \(n-i\) 个字符是 \(S\) 的后 \(n-i\) 个字符。
思路：
官方题解说了个什么 Z 函数？不会，我只会哈希。
这题哈希思路非常简单，只要记录前缀和后缀即可。为了防止哈希冲突，我用 \(10^9+7\) 和 \(998244353\) 这两个大质数做模数写双哈希，这样不容易被卡。时间复杂度 \(O(n)\)。
代码：
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
string s;
const long long mod1 = 1e9 + 7;
const long long mod2 = 998244353;
const int Base = 26;
long long pw1[2000005] = {0}, pw2[2000005] = {0};
long long pre1[2000005] = {0}, pre2[2000005] = {0};
long long suf1[2000005] = {0}, suf2[2000005] = {0};
void init() {
pw1[0] = pw2[0] = 1;
for (int i = 1; i <= 2 * n; i++)
pw1[i] = (pw1[i - 1] * 26) % mod1, pw2[i] = (pw2[i - 1] * 26) % mod2;
pre1[0] = pre2[0] = 0;
for (int i = 1; i <= 2 * n; i++) {
pre1[i] = (Base * pre1[i - 1] + (s[i - 1] - 'a')) % mod1;
pre2[i] = (Base * pre2[i - 1] + (s[i - 1] - 'a')) % mod2;
}
suf1[2 * n + 1] = suf2[2 * n + 1] = 0;
for (int i = 2 * n; i >= 1; i--) {
suf1[i] = (Base * suf1[i + 1] + (s[i - 1] - 'a')) % mod1;
suf2[i] = (Base * suf2[i + 1] + (s[i - 1] - 'a')) % mod2;
}
}
long long sqry1(int l, int r) {
return (suf1[l] - suf1[r + 1] * pw1[r - l + 1] % mod1 + mod1) % mod1;
}
long long sqry2(int l, int r) {
return (suf2[l] - suf2[r + 1] * pw2[r - l + 1] % mod2 + mod2) % mod2;
}
int main() {
cin >> n;
cin >> s;
init();
bool f = false;
for (int i = 0; i <= n; i++) {
long long tmp1 = sqry1(i + 1, i + n), tmp2 = sqry2(i + 1, i + n);
if (i == 0) {
long long p1 = (pre1[2 * n] - pw1[n] * pre1[n] % mod1 + mod1) % mod1;
long long p2 = (pre2[2 * n] - pw2[n] * pre2[n] % mod2 + mod2) % mod2;
if (p1 == tmp1 && p2 == tmp2) {
for (int j = i + n; j >= i + 1; j--)
cout << s[j - 1];
cout << endl << i << endl;
f = true;
break;
}
}
else if (i == n) {
if (pre1[i] == tmp1 && pre2[i] == tmp2) {
for (int j = i + n; j >= i + 1; j--)
cout << s[j - 1];
cout << endl << i << endl;
f = true;
break;
}
}
else {
long long p1 = (pre1[i] * pw1[n - i] % mod1 + pre1[2 * n] - pre1[n + i] * pw1[n - i] % mod1 + mod1) % mod1;
long long p2 = (pre2[i] * pw2[n - i] % mod2 + pre2[2 * n] - pre2[n + i] * pw2[n - i] % mod2 + mod2) % mod2;
if (p1 == tmp1 && p2 == tmp2) {
for (int j = i + n; j >= i + 1; j--)
cout << s[j - 1];
cout << endl << i << endl;
f = true;
break;
}
}
}
if (!f)
cout << -1;
return 0;
}