2024牛客暑期多校训练营8

A. Haitang and Game

通过审题可以知道，最后的胜者和若干次操作后最多能增加的数的奇偶有关。

由于 $a_i$ 较小，所以我们枚举每一个没出现过的 $x,x\in [1,1e5]$， 考虑如何让 $x$ 出现，很简单，有两个数的 $gcd$ 等于 $x$ 呗，好像说了废话。

那我们怎么快速寻找这么两个数呢，在遍历 $x$ 的时候查找它的所有倍数，如果出现过并且这些所有的倍数 $gcd$ 值为 $x$ 的话则 $x$ 可以出现。如果 $x\%2=1$ 先手获胜，否则后手获胜，时间复杂度 $O(Tnlogn)$ 。

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define YES "YES"
#define NO "NO"
#define all(a) a.begin(), a.end()
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
const double eps = 1e-9;
const int N = 1e6 + 10;
const int M = 1e6 + 10;
const int INF = 1e18 + 10;
const int mod = 1e9 + 7;
const int base = 23333;
const double pi = acos(-1.0);
//mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
int a[N];
void solve()
{vector<int> jl(1e5 + 10, 0);int n;cin >> n;for(int i = 1;i <= n;i++){cin >> a[i];jl[a[i]] = 1;}int cnt = 0;for(int i = 1;i <= 1e5;i++){if(jl[i]) continue;int flag = 0, now = 0;for(int j = i;j <= 1e5;j += i){if(jl[j]){if(flag == 0){now = j;flag = 1;}else now = __gcd(now, j);}}if(now == i) cnt++;}if(cnt % 2 == 1) cout << "dXqwq" << '\n';else cout << "Haitang" << '\n';
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while (t--) solve();return 0;
}

E.Haitang and Math

赛时一直在调 $O(T\sqrt{n})$ 的做法，但是没调出来，都这么轻量级了还不让过，真是可恶。

比赛结束之后才发现居然有 $PollardRho$ 这样的黑科技，可以在 $\sqrt[4]{n}$ 的时间复杂度求得一个数的最大质因子，真是学到了。

求出最大质因子之后就可以通过质因子分解分解出所有的质因子，再通过 $dfs$ 求出所有的因子，对于 $[1,108]$ 的所有 $S(m)$ 求一下题目中的式子是否成立即可，注意去重。时间复杂度有点玄学，大概是 $O(\frac{T\sqrt{n}}{logn})$，交上去之后跑的飞起，这个故事告诉我们，学好算法还是很重要滴。

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define YES "YES"
#define NO "NO"
#define all(a) a.begin(), a.end()
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
const double eps = 1e-9;
const int N = 1e6 + 100;
const int M = 1e6 + 10;
const int INF = 1e18 + 100;
const int mod = 1e9 + 7;
const int base = 23333;
// mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
int max_factor, n, nn;
int quick_pow(int x, int p, int mod) // 快速幂
{int ans = 1;while (p){if (p & 1) ans = (__int128)ans * x % mod;x = (__int128)x * x % mod;p >>= 1;}return ans;
}
bool Miller_Rabin(int p) // 判断素数
{if (p < 2) return 0;if (p == 2) return 1;if (p == 3) return 1;int d = p - 1, r = 0;while (!(d & 1)) ++r, d >>= 1; // 将d处理为奇数for (int k = 0; k < 10; ++k){int a = rand() % (p - 2) + 2;int x = quick_pow(a, d, p);if (x == 1 || x == p - 1) continue;for (int i = 0; i < r - 1; ++i){x = (__int128)x * x % p;if (x == p - 1) break;}if (x != p - 1) return 0;}return 1;
}
int Pollard_Rho(int x)
{int s = 0, t = 0;int c = (int)rand() % (x - 1) + 1;int step = 0, goal = 1;int val = 1;for (goal = 1;; goal *= 2, s = t, val = 1) // 倍增优化{for (step = 1; step <= goal; ++step){t = ((__int128)t * t + c) % x;val = (__int128)val * abs(t - s) % x;if ((step % 127) == 0){int d = __gcd(val, x);if (d > 1) return d;}}int d = __gcd(val, x);if (d > 1) return d;}
}
void fac(int x)
{if (x <= max_factor || x < 2) return;if (Miller_Rabin(x)) // 如果x为质数{max_factor = max(max_factor, x); // 更新答案return;}int p = x;while (p >= x) p = Pollard_Rho(x); // 使用该算法while ((x % p) == 0) x /= p;fac(x), fac(p); // 继续向下分解x和p
}
vector<int> pri;
map<int, int> mp, cnt;
int ans;
int coun(int x)
{int res = 0;while(x > 0){res += x % 10;x /= 10;}return res;
}
void dfs(int now, int res, int tt)
{//cout << now << " " << res << " " << tt << '\n';if(res > tt) return;if(now == pri.size()){if(tt % res == 0 && n % res != 0 && !cnt[res] && coun(res) == n - tt){//cout << res << '\n';cnt[res] = 1;ans++;}return;}dfs(now + 1, res, tt);if(mp[pri[now]]){mp[pri[now]]--;dfs(now, res * pri[now], tt);mp[pri[now]]++;}
}
void solve()
{srand((unsigned)time(NULL));cin >> n;ans = 0;cnt.clear();for(int ii = 1;ii <= min(n - 2, 108LL);ii++){pri.clear();mp.clear();max_factor = 0;nn = n - ii;fac(nn);pri.push_back(max_factor);nn /= max_factor;mp[max_factor]++;for(int i = 2; i <= nn / i; ++i) {if(nn % i == 0){pri.push_back(i);while (nn % i == 0) {mp[i]++;nn /= i;}}}if (nn > 1){mp[nn]++;pri.push_back(nn);}//cout << n - ii << " " << pri.size() << '\n';//for(auto u : pri) cout << u << " " << mp[u] << '\n';dfs(0, 1, n - ii);}cout << ans << '\n';
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while (t--) solve();return 0;
}

J. Haitang and Triangle

$n$ 个数相邻三三组合最多有 $n-2$ 种组合方式，但是包含 $1$ 的那一组一定组成不了三角形，所以 $k=n-2$ 时无解。

$k=0$ 时，形如 $d,2d,3d,d-1,2d-1,3d-1,\dots ,1,1+d,1+2d$ 这样的排列是满足条件的，$d=\lfloor \frac{(n-k)}{3}\rfloor$。

那 $k>0$ 怎么放呢，不难发现，把除了 $1$ 的其他 $m$ 个数按顺序发如 $2,3,4,\dots ,m$，每个长度为三的字串都能构成一个三角形，所以我们左边放 $k=0$ 时的情况，右边放其他数。再根据 $d\%3$ 的不同值往端点插入数，增加构不成三角形的区间长度，时间复杂度 $O(\sum n)$。

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define YES "YES"
#define NO "NO"
#define all(a) a.begin(), a.end()
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
const double eps = 1e-9;
const int N = 1e6 + 100;
const int M = 1e6 + 10;
const int INF = 1e18 + 100;
const int mod = 1e9 + 7;
const int base = 23333;
// mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count())
void solve()
{int n, m;cin >> n >> m;vector<int> flag(n + 5);if(m == n - 2){cout << -1 << '\n';return;}int x = n - m;int d = x / 3;vector<int> ans;if (x % 3 == 0) {for (int i = 0;i < d;i++) {ans.push_back(d - i);ans.push_back(2 * d - i);ans.push_back(3 * d - i);}for (int i = 1;i <= m;i++) ans.push_back(3 * d + i);}if (x % 3 == 1) { ans.push_back(n);for (int i = 0;i < d;i++) {ans.push_back(d - i);ans.push_back(2 * d - i);ans.push_back(3 * d - i);}for (int i = 1;i <= m;i++) ans.push_back(3 * d + i);}if (x % 3 == 2) {ans.push_back(3 * d + 1);for (int i = 0;i < d;i++) {ans.push_back(d - i);ans.push_back(2 * d - i);ans.push_back(3 * d - i);}ans.push_back(3 * d + 2);for (int i = 3;i <= m + 2;i++) ans.push_back(3 * d + i);}for (auto x : ans) cout << x << " ";cout << "\n";
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while (t--) solve();return 0;
}

K. Haitang and Ava

从前往后匹配 $ava$ 或者 $avava$ 串，如果能匹配完输出 $Yes$ ，否则输出 $No$ ，时间复杂度 $O(\sum S)$。

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define YES "YES"
#define NO "NO"
#define all(a) a.begin(), a.end()
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
const double eps = 1e-9;
const int N = 1e6 + 10;
const int M = 1e6 + 10;
const int INF = 1e18 + 10;
const int mod = 1e9 + 7;
const int base = 23333;
const double pi = acos(-1.0);
//mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
void solve()
{string s;cin >> s;int pos = 0;for(int i = 0;i < s.size();){if(i + 5 <= s.size()){if(s[i] == 'a' && s[i + 1] == 'v' && s[i + 2] == 'a' && s[i + 3] == 'v' && s[i + 4] == 'a'){i += 5;pos = i;}else if(s[i] == 'a' && s[i + 1] == 'v' && s[i + 2] == 'a'){i += 3;pos = i;}else break;}else if(i + 3 <= s.size()){if(s[i] == 'a' && s[i + 1] == 'v' && s[i + 2] == 'a'){i += 3;pos = i;}else break;}else break;}if(pos == s.size()) cout << "Yes" << '\n';else cout << "No" << '\n';
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while (t--) solve();return 0;
}