Problem - E - Codeforces
（1）题目大意
给你一个字符串，问你让字符串每一对相对应位置都不同的最小操作数是多少？（A[i]和A[n - i],A[i + 1]和A[n - i - 1]）
（2）解题思路
1.首先字符串为奇数一定不可以
2.其次如果字符串中某个字母的个数>n/2，则也不可以
3.答案的构成，不会证明。
考虑主元素法，答案要么就是最大的相同对的字母或者是总共的相同对的总数/2，这两个取个max就行了。
（3）代码实现
#include<bits/stdc++.h>
#define sz(x) (int) x.size()
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 5e5 + 10;void solve(){int n;cin >> n;string s;cin >> s;vector <int> cnt(26);if(n & 1) {cout << -1 << endl;return;}for(auto x : s) cnt[x - 'a'] ++;int mx = 0;for(int i = 0;i < 26;i ++) {if(cnt[i] > n / 2) {cout << -1 << endl;return;}}int l = 0,r = n - 1,ans = 0;for(int i = 0;i < 26;i ++) cnt[i] = 0;while(l < r) {if(s[l] == s[r]) cnt[s[l] - 'a'] ++,ans ++;l ++,r --;}for(int i = 0;i < 26;i ++) mx = max(mx,cnt[i]);cout << max((ans + 1) / 2,mx) << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int T = 1;cin >> T;while(T --) solve();
}Problem - F - Codeforces
（1）题目大意
（2）解题思路
考虑找到最长的那条链，做两次dfs即可，或者考虑换根dp，我的做法是两次dfs，首先从1跑一遍dfs记录一下深度，然后从最远的那个点再跑一次dfs即可。
记第一次dfs处理的数组为dp1，第二次的数组为dp2，则有两种情况
1.需要进行操作：ans = max(ans,dp2[i] * k - dp1[i] * c);
2.不需要进行操作： ans = max(ans,dp1[i]*k);
（3）代码实现
#include<bits/stdc++.h>
#define sz(x) (int) x.size()
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 3e5 + 10;
vector <int> g[N];
int dp1[N],dp2[N];
void dfs1(int u,int f)
{for(auto v : g[u]) {if(v == f) continue;dp1[v] = dp1[u] + 1;dfs1(v,u);}
}void dfs2(int u,int f)
{for(auto v : g[u]) {if(v == f) continue;dp2[v] = dp2[u] + 1;dfs2(v,u);}
}
void solve(){int n,k,c;cin >> n >> k >> c;for(int i = 1;i <= n;i ++) g[i].clear();for(int i = 1;i <= n - 1;i ++) {int u,v;cin >> u >> v;g[u].pb(v),g[v].pb(u);}dp1[1] = 0;dfs1(1,0);int rt = 1;for(int i = 1;i <= n;i ++) {if(dp1[i] > dp1[rt]) rt = i;}dp2[rt] = 0;dfs2(rt,0);ll ans = 0;for(int i = 1;i <= n;i ++) {ans = max(ans,1ll * dp1[i] * k);ans = max(ans,1ll * dp2[i] * k - 1ll * dp1[i] * c);}cout << ans << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int T = 1;cin >> T;while(T --) solve();
}Problem - G2 - Codeforces
（1）题目大意
给你一个长度为n的序列，让你找到i，j，k的对数，满足a[j] = b * a[i],a[k] = b * a[j]。
（2）解题思路
G1我们直接枚举暴力即可，但是G2发现a[i]有1e9，因此我们考虑使用PollardRho暴力分解质因子，然后根据质数平方因子处理出两个数组出来，再根据这些因子计算答案即可。
（3）代码实现
#include "bits/stdc++.h"
#include <cstdint>
#include <functional>
#include <random>
#include <cmath>
#include <cstdint>
#include <functional>
#include <memory>
#include <cassert>
#include <cstdint>
#include <functional>
#include <algorithm>
#include <cstdint>
#include <cassert>
#include <cstdint>
#include <initializer_list>
#define sz(x) (int) x.size()
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
const int N = 1e6 + 10;
int a[N];
namespace OY {template <typename _ModType>struct Barrett {_ModType m_P;__uint128_t m_Pinv;constexpr Barrett() = default;constexpr explicit Barrett(_ModType __P) : m_P(__P), m_Pinv(-uint64_t(__P) / __P + 1) {}constexpr _ModType mod() const { return m_P; }constexpr _ModType mod(uint64_t __a) const {__a -= uint64_t(m_Pinv * __a >> 64) * m_P + m_P;if (__a >= m_P) __a += m_P;return __a;}constexpr _ModType multiply(uint64_t __a, uint64_t __b) const {if constexpr (std::is_same_v<_ModType, uint64_t>)return multiply_ld(__a, __b);elsereturn multiply_64(__a, __b);}constexpr _ModType multiply_64(uint64_t __a, uint64_t __b) const {// assert(__a * __b < 1ull << 64);return mod(__a * __b);}constexpr _ModType multiply_128(uint64_t __a, uint64_t __b) const {if (__builtin_clzll(__a) + __builtin_clzll(__b) >= 64) return multiply_64(__a, __b);return __uint128_t(__a) * __b % m_P;}constexpr _ModType multiply_ld(uint64_t __a, uint64_t __b) const {// assert(m_P < 1ull << 63 && __a < m_P && __b < m_P);if (__builtin_clzll(__a) + __builtin_clzll(__b) >= 64) return multiply_64(__a, __b);int64_t res = __a * __b - uint64_t(1.L / m_P * __a * __b) * m_P;if (res < 0)res += m_P;else if (res >= m_P)res -= m_P;return res;}constexpr _ModType pow(uint64_t __a, uint64_t __n) const {if constexpr (std::is_same_v<_ModType, uint64_t>)return pow_ld(__a, __n);elsereturn pow_64(__a, __n);}constexpr _ModType pow_64(uint64_t __a, uint64_t __n) const {// assert(m_P < 1ull << 32);_ModType res = 1, b = mod(__a);while (__n) {if (__n & 1) res = multiply_64(res, b);b = multiply_64(b, b);__n >>= 1;}return res;}constexpr _ModType pow_128(uint64_t __a, uint64_t __n) const {_ModType res = 1, b = mod(__a);while (__n) {if (__n & 1) res = multiply_128(res, b);b = multiply_128(b, b);__n >>= 1;}return res;}constexpr _ModType pow_ld(uint64_t __a, uint64_t __n) const {_ModType res = 1, b = mod(__a);while (__n) {if (__n & 1) res = multiply_ld(res, b);b = multiply_ld(b, b);__n >>= 1;}return res;}template <typename _Tp>constexpr _Tp divide(_Tp __a) const {if (__a < m_P) return 0;_Tp res = m_Pinv * __a >> 64;if (__a - res * m_P >= m_P) res++;return res;}template <typename _Tp>constexpr std::pair<_Tp, _Tp> divmod(_Tp __a) const {_Tp quo = (__a * m_Pinv) >> 64, rem = __a - quo * m_P;if (rem >= m_P) {quo++;rem -= m_P;}return {quo, rem};}};using Barrett32 = Barrett<uint32_t>;using Barrett64 = Barrett<uint64_t>;
}
namespace OY {template <typename _ModType>struct _MontgomeryTag;template <>struct _MontgomeryTag<uint32_t> {using long_type = uint64_t;static constexpr uint32_t limit = (1u << 30) - 1;static constexpr uint32_t inv_loop = 4;static constexpr uint32_t length = 32;};template <>struct _MontgomeryTag<uint64_t> {using long_type = __uint128_t;static constexpr uint64_t limit = (1ull << 63) - 1;static constexpr uint32_t inv_loop = 5;static constexpr uint32_t length = 64;};template <typename _ModType>struct Montgomery {using _FastType = _ModType;using _LongType = typename _MontgomeryTag<_ModType>::long_type;_ModType m_P;_ModType m_Pinv;_ModType m_Ninv;Barrett<_ModType> m_brt;constexpr Montgomery() = default;constexpr explicit Montgomery(_ModType __P) : m_P(__P), m_Pinv(__P), m_Ninv(-_LongType(__P) % __P), m_brt(__P) {// assert((__P & 1) && __P > 1 && __P <= _MontgomeryTag<_ModType>::limit);for (int i = 0; i < _MontgomeryTag<_ModType>::inv_loop; i++) m_Pinv *= _ModType(2) - __P * m_Pinv;}constexpr _ModType mod() const { return m_brt.mod(); }constexpr _ModType mod(uint64_t __a) const { return m_brt.mod(__a); }constexpr _FastType init(uint64_t __a) const { return reduce(_LongType(mod(__a)) * m_Ninv); }constexpr _FastType raw_init(uint64_t __a) const { return reduce(_LongType(__a) * m_Ninv); }constexpr _FastType reduce(_LongType __a) const {_FastType res = (__a >> _MontgomeryTag<_ModType>::length) - _ModType(_LongType(_ModType(__a) * m_Pinv) * m_P >> _MontgomeryTag<_ModType>::length);if (res >= mod()) res += mod();return res;}constexpr _ModType reduce(_FastType __a) const {_ModType res = -_ModType(_LongType(__a * m_Pinv) * m_P >> _MontgomeryTag<_ModType>::length);if (res >= mod()) res += mod();return res;}constexpr _FastType multiply(_FastType __a, _FastType __b) const { return reduce(_LongType(__a) * __b); }constexpr _FastType pow(_FastType __a, uint64_t __n) const {_FastType res = reduce(_LongType(1) * m_Ninv);while (__n) {if (__n & 1) res = multiply(res, __a);__a = multiply(__a, __a);__n >>= 1;}return res;}template <typename _Tp>constexpr _Tp divide(_Tp __a) const { return m_brt.divide(__a); }template <typename _Tp>constexpr std::pair<_Tp, _Tp> divmod(_Tp __a) const { return m_brt.divmod(__a); }};using Montgomery32 = Montgomery<uint32_t>;using Montgomery64 = Montgomery<uint64_t>;
}
namespace OY {template <typename _Elem>constexpr bool isPrime(_Elem n) {if (std::is_same_v<_Elem, uint32_t> || n <= UINT32_MAX) {if (n <= 1) return false;if (n == 2 || n == 7 || n == 61) return true;if (n % 2 == 0) return false;Barrett32 brt(n);uint32_t d = (n - 1) >> __builtin_ctz(n - 1);for (auto &&a : {2, 7, 61}) {uint32_t s = d, y = brt.pow_64(a, s);while (s != n - 1 && y != 1 && y != n - 1) {y = brt.multiply_64(y, y);s <<= 1;}if (y != n - 1 && s % 2 == 0) return false;}return true;} else {// assert(n < 1ull < 63);if (n % 2 == 0) return false;Montgomery64 mg(n);uint64_t d = (n - 1) >> __builtin_ctzll(n - 1), one = mg.init(1);for (auto &&a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {uint64_t s = d, y = mg.pow(mg.init(a), s), t = mg.init(n - 1);while (s != n - 1 && y != one && y != t) {y = mg.multiply(y, y);s <<= 1;}if (y != t && s % 2 == 0) return false;}return true;}}constexpr auto isPrime32 = isPrime<uint32_t>;constexpr auto isPrime64 = isPrime<uint64_t>;
}
namespace OY {template <typename _Elem>constexpr _Elem gcd(_Elem a, _Elem b) {if (!a || !b) return a | b;int i = std::__countr_zero(a), j = std::__countr_zero(b), k = std::min(i, j);a >>= i;b >>= j;while (true) {if (a < b) std::swap(a, b);if (!(a -= b)) break;a >>= std::__countr_zero(a);}return b << k;}template <typename _Elem>constexpr _Elem lcm(_Elem a, _Elem b) { return a && b ? a / gcd<_Elem>(a, b) * b : 0; }constexpr auto gcd32 = gcd<uint32_t>;constexpr auto gcd64 = gcd<uint64_t>;constexpr auto lcm32 = lcm<uint32_t>;constexpr auto lcm64 = lcm<uint64_t>;
}
namespace OY {struct Pollard_Rho {static constexpr uint64_t batch = 128;static inline std::mt19937_64 s_rander;template <typename _Elem>static _Elem pick(_Elem __n) {// assert(!isPrime<_Elem>(__n));if (__n % 2 == 0) return 2;static Montgomery<_Elem> mg;if (mg.mod() != __n) mg = Montgomery<_Elem>(__n);std::uniform_int_distribution<_Elem> distribute(2, __n - 1);_Elem v0, v1 = mg.init(distribute(s_rander)), prod = mg.init(1), c = mg.init(distribute(s_rander));for (int i = 1; i < batch; i <<= 1) {v0 = v1;for (int j = 0; j < i; j++) v1 = mg.multiply(v1, v1) + c;for (int j = 0; j < i; j++) {v1 = mg.multiply(v1, v1) + c;prod = mg.multiply(prod, v0 > v1 ? v0 - v1 : v1 - v0);if (!prod) return pick(__n);}if (_Elem g = gcd<_Elem>(prod, __n); g > 1) return g;}for (int i = batch;; i <<= 1) {v0 = v1;for (int j = 0; j < i; j++) v1 = mg.multiply(v1, v1) + c;for (int j = 0; j < i; j += batch) {for (int k = 0; k < batch; k++) {v1 = mg.multiply(v1, v1) + c;prod = mg.multiply(prod, v0 > v1 ? v0 - v1 : v1 - v0);if (!prod) return pick(__n);}if (_Elem g = gcd<_Elem>(prod, __n); g > 1) return g;}}return __n;}template <typename _Elem>static auto decomposite(_Elem __n) {struct node {_Elem prime;uint32_t count;};std::vector<node> res;auto dfs = [&](auto self, _Elem cur) -> void {if (!OY::isPrime<_Elem>(cur)) {_Elem a = pick<_Elem>(cur);self(self, a);self(self, cur / a);} else {auto find = std::find_if(res.begin(), res.end(), [cur](auto x) { return x.prime == cur; });if (find == res.end())res.push_back({cur, 1u});elsefind->count++;}};if (__n % 2 == 0) {res.push_back({2, uint32_t(std::__countr_zero(__n))});__n >>= std::__countr_zero(__n);}if (__n > 1) dfs(dfs, __n);std::sort(res.begin(), res.end(), [](auto &x, auto &y) { return x.prime < y.prime; });return res;}template <typename _Elem>static std::vector<_Elem> getFactors(_Elem __n) {auto pf = decomposite(__n);std::vector<_Elem> res;_Elem count = 1;for (auto [p, c] : pf) count *= c + 1;res.reserve(count);auto dfs = [&](auto self, int i, _Elem prod) -> void {if (i == pf.size())res.push_back(prod);else {auto [p, c] = pf[i];self(self, i + 1, prod);while (c--) self(self, i + 1, prod *= p);}};dfs(dfs, 0, 1);std::sort(res.begin(), res.end());return res;}template <typename _Elem>static _Elem EulerPhi(_Elem __n) {for (auto [p, c] : decomposite(__n)) __n = __n / p * (p - 1);return __n;}};
}
void solve(){int n;cin >> n;map <ll,int> cnt1,cnt2;rep(i,1,n) {cin >> a[i];cnt1[a[i]] ++;}ll ans = 0;for(auto [x,c] : cnt1) {auto fac = OY::Pollard_Rho::decomposite<uint32_t>(x);vector <int> v1,v2;v1.pb(1),v2.pb(1);if(c >= 3) ans += 1ll * c * (c - 1) * (c - 2);for(auto [y,cc] : fac) {for(int i = 1;i + 1 <= cc;i += 2) {int ssz = sz(v1);for(int j = 0;j < ssz;j ++) {v1.pb(v1[j] * y);v2.pb(v2[j] * y * y);}}}sort(all(v1));sort(all(v2));v1.erase(unique(all(v1)),v1.end());v2.erase(unique(all(v2)),v2.end());for(int i = 0;i < sz(v1);i ++) {if(v1[i] == 1 || v2[i] == 1) continue;if(cnt2.count(x / v1[i]) && cnt2.count(x / v2[i])) {ans += 1ll * c * cnt2[x / v1[i]] * cnt2[x / v2[i]];}}cnt2[x] = c;}cout << ans << '\n';
}int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int T = 1;cin >> T;while(T --) solve();
}
