【题解】2023年第六届传智杯复赛第一场题解
补题链接：https://ac.nowcoder.com/acm/contest/72647#question
作为复赛，本场比赛难度略高于初赛，且都是原创题，总体比赛强度还是比初赛高一个档次的。复赛第一场一共8题，其中A组使用6题：BDEFGH；B组使用6题：ACDEFG
A 小红劈字符串
比赛通过率：87.79%
知识点：字符串，模拟
思路：签到题。只需要判断字符串长度是否是3的倍数即可。如果是3的倍数，则在的地方添加一个空格；否则无解。
参考代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[101026],sum[101010];
signed main(){
int n,m,i,j,k,x,y,c=0;
string s;
cin>>s;
if(s.length()%3!=0)return cout<<-1,0;
for(i=0;i<s.length();i++){
if(i*3==s.length()*2)cout<<" ";
cout<<s[i];
}
}
B 赝品
比赛通过率：82.33%
知识点：数组、哈希、模拟
思路：建议使用map等哈希容器（java为HashMap，python为dict），这样可以比较方便统计每个元素的次数。另外也可以通过排序等方式来达成目的。
参考代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[101026],sum[101010];
signed main(){
int n,i,j,k,x,y,c=0;
cin>>n;
map<int,int>m;
for(i=0;i<n;i++)cin>>x,m[x]++;
vector<int>v;
for(auto i:m){
if(i.second==1)v.push_back(i.first);
}
cout<<v.size()<<'\n';
for(auto i:v)cout<<i<<" ";
}
C 小红的数字分裂
比赛通过率：36.61%
知识点：数论、贪心
思路：一个比较显然的结论是，最终需要将数组的元素变成所有元素的gcd（最大公约数）。因此每个元素需要分裂的次数可以直接求出来。这个结论的证明可以结合辗转相除法的性质，请大家自行思考。
参考代码：
#include <bits/stdc++.h>
using namespace std;
int a[101010];
int main() {
int n,i,g=0;
cin>>n;
for(i=0;i<n;i++){
cin>>a[i];
g=__gcd(a[i],g);
}
long long s=0;
for(i=0;i<n;i++){
s+=a[i]/g-1;
}
cout<<s;
}
D 小红的字符串同构
比赛通过率：26.21%
知识点：组合数学
思路：我们可以先计算出满足第一个条件的字符串数量：用乘法原理计算，答案为。
然后我们需要减去和原字符串同构的情况，答案为最大的字符减去最小的字符这么多。
参考代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[101026],sum[101010];
int suma[101010],sumb[101010];
int pow2[101010];
int mod=1e9+7;
signed main(){
int n,i,j=0,k,x,y,c=0;
string s;
cin>>s;
int ma=0,mi=1e9;
int res=1;
for(auto i:s){
ma=max(ma,(int)(i-'a'));
mi=min(mi,(int)(i-'a'));
res=res*25%mod;
}
cout<<res-(26-(ma-mi+1));
}
E 小红的树上赋值方案
比赛通过率：4.53%
知识点：树形dp
思路：我们记录dp[u][i][j]代表以u节点的子树，当u节点赋值为的时候，该子树权值和模3等于
的方案数。在dfs的时候转移即可。
参考代码：
#include <bits/stdc++.h>
using ll = long long;
template <typename T, auto f = std::multiplies<T>()>
constexpr static T power(T a, int64_t b) {
assert(b >= 0);
T res;
if constexpr (std::is_arithmetic_v<T>) {
res = 1;
} else {
res = a.identity();
}
while (b) {
if (b & 1) {
res = f(res, a);
}
b >>= 1;
a = f(a, a);
}
return res;
}
template <typename T, T MOD>
struct ModInt {
using prod_type = std::conditional_t<std::is_same_v<T, int>, int64_t, __int128>;
T val;
constexpr ModInt(const int64_t v = 0) : val(v % MOD) { if (val < 0) val += MOD; }
constexpr ModInt operator+() const { return ModInt(val); }
constexpr ModInt operator-() const { return ModInt(MOD - val); }
constexpr ModInt inv() const { return power(*this, MOD - 2); }
constexpr friend ModInt operator+(ModInt lhs, const ModInt rhs) { return lhs += rhs; }
constexpr friend ModInt operator-(ModInt lhs, const ModInt rhs) { return lhs -= rhs; }
constexpr friend ModInt operator*(ModInt lhs, const ModInt rhs) { return lhs *= rhs; }
constexpr friend ModInt operator/(ModInt lhs, const ModInt rhs) { return lhs /= rhs; }
constexpr ModInt &operator+=(const ModInt x) {
if ((val += x.val) >= MOD) val -= MOD;
return *this;
}
constexpr ModInt &operator-=(const ModInt x) {
if ((val -= x.val) < 0) val += MOD;
return *this;
}
constexpr ModInt &operator*=(const ModInt x) {
val = prod_type(val) * x.val % MOD;
return *this;
}
constexpr ModInt &operator/=(const ModInt x) { return *this *= x.inv(); }
bool operator==(const ModInt b) const { return val == b.val; }
bool operator!=(const ModInt b) const { return val != b.val; }
friend std::istream &operator>>(std::istream &is, ModInt &x) noexcept { return is >> x.val; }
friend std::ostream &operator<<(std::ostream &os, const ModInt x) noexcept { return os << x.val; }
constexpr static ModInt identity() { return 1; }
constexpr ModInt pow(int64_t p) { return power(*this, p); }
};
using Z = ModInt<int, 1'000'000'007>;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::string s;
std::cin >> s;
std::vector<std::vector<int>> g(n);
for (int i = 1; i < n; i++) {
int f;
std::cin >> f;
f--;
g[f].push_back(i);
}
std::vector dp(n, std::vector(3, std::vector<Z>(3)));
auto dfs = [&](auto &&self, int u) -> void {
dp[u][1][1] = 1;
dp[u][2][2] = 1;
for (auto v : g[u]) {
self(self, v);
for (int i = 1; i <= 2; i++) {
std::vector<Z> tmp(3);
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
tmp[(j + k) % 3] += dp[u][i][j] * (dp[v][1][k] + dp[v][2][k]);
}
}
dp[u][i] = tmp;
}
}
if (s[u] == 'R') {
for (int i = 1; i <= 2; i++) {
dp[u][i][1] = 0;
dp[u][i][2] = 0;
}
}
};
dfs(dfs, 0);
auto get = [&](int u) -> Z {
Z res = 0;
for (int i = 1; i <= 2; i++) {
for (int j = 0; j < 3; j++) {
res += dp[u][i][j];
}
}
return res;
};
std::cout << get(0) << "\n";
return 0;
}
F 小红的区间查询
比赛通过率：5.03%
知识点：线段树、离散化
思路：直接维护区间的相交情况比较困难。我们可以首先进行离散化，然后在值域上开线段树进行维护区间和。当添加一个区间时，我们进行区间加1；删除一个区间时，我们进行区间减1。这样，问题可以转化为，如果存在一个大于1的值，则意味着存在两个区间相交。这样我们可以通过询问全局最大值解决。
参考代码：
#include<bits/stdc++.h>
using namespace std;
struct node{
int l,r;
int ma,lz;
};
node t[802020];
void pushup(int p){
t[p].ma=max(t[p*2].ma,t[p*2+1].ma);
}
void build(int p,int l,int r){
t[p].l=l;
t[p].r=r;
t[p].lz=t[p].ma=0;
if(l==r)return;
int mid=l+r>>1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
pushup(p);
}
void pushdown(int p){
int x=t[p].lz;
t[p*2].ma+=x;
t[p*2].lz+=x;
t[p*2+1].ma+=x;
t[p*2+1].lz+=x;
t[p].lz=0;
}
void add(int p,int l,int r,int x){
if(t[p].l>=l&&t[p].r<=r){
t[p].lz+=x;
t[p].ma+=x;
return;
}
if(t[p].lz)pushdown(p);
int mid=t[p].l+t[p].r>>1;
if(mid>=l)add(p*2,l,r,x);
if(mid+1<=r)add(p*2+1,l,r,x);
pushup(p);
}
int ask(int p,int l,int r){
if(t[p].l>=l&&t[p].r<=r){
return t[p].ma;
}
if(t[p].lz)pushdown(p);
int mid=t[p].l+t[p].r>>1,res=-1e9;
if(mid>=l)res=max(res,ask(p*2,l,r));
if(mid+1<=r)res=max(res,ask(p*2+1,l,r));
pushup(p);
return res;
}
vector<vector<int>>v;
int main(){
int n,i,j;
cin>>n;
map<int,int>mp;
for(i=0;i<n;i++){
char c;
int x,y;
cin>>c>>x>>y;
v.push_back({c=='+',x,y});
mp[x]=mp[y]=0;
}
j=1;
for(auto &[x,y]:mp){
y=j++;
}
build(1,1,j);
for(auto i:v){
if(!i[0])add(1,mp[i[1]],mp[i[2]],-1);
else add(1,mp[i[1]],mp[i[2]],1);
if(ask(1,1,j)>1)cout<<"Yes\n";
else cout<<"No\n";
}
}
G 小红和小紫的取数游戏
比赛通过率：1.26%
知识点：博弈，数论，哈希
思路：首先我们将该博弈问题进行抽象，可以比较轻松得出以下结论：如果初始所有元素乘积为完全平方数，那么小紫获胜；否则小红获胜。
因此我们可以先用的根号分解，对于次数和为奇数的素因子，我们需要使得该素因子的次数变成偶数即可。那么这道题等价为：给定一个数组，询问有多少个连续子数组满足子数组所有元素中，出现次数为奇数素因子的乘积恰好等于
。（
为初始给定的数的奇数次数因子乘积）。
要解决这个问题，我们可以首先使用筛法，预处理出每个元素的素因子次数。然后使用哈希批量维护区间信息。在处理过程中，我们可以对初始的因子进行特殊标记，减少哈希中需要处理的不同因子数论，避免出现tle或者mle。
参考代码：
#include <bits/stdc++.h>
using ll = long long;
struct EulerSieveSimple {
const int N;
std::vector<int> minp, primes;
std::map<int, int> prime_id;
EulerSieveSimple(int n) : N(n), minp(n + 1) {
for (int i = 2; i <= N; ++i) {
if (!minp[i]) {
minp[i] = i;
prime_id[i] = primes.size();
primes.push_back(i);
}
for (auto p : primes) {
if (i * p > n) break;
minp[i * p] = p;
if (i % p == 0) break;
}
}
}
std::vector<std::pair<int, int>> prime_factors(int n) {
std::vector<std::pair<int, int>> factors;
while (n > 1) {
int p = minp[n], cnt = 0;
while (n % p == 0) {
cnt++;
n /= p;
}
factors.emplace_back(p, cnt);
}
return factors;
}
} sieve(1'000'000);
template <typename T, auto f = std::multiplies<T>()>
constexpr static T power(T a, int64_t b) {
assert(b >= 0);
T res;
if constexpr (std::is_arithmetic_v<T>) {
res = 1;
} else {
res = a.identity();
}
while (b) {
if (b & 1) {
res = f(res, a);
}
b >>= 1;
a = f(a, a);
}
return res;
}
template <typename T, T MOD>
struct ModInt {
using prod_type = std::conditional_t<std::is_same_v<T, int>, int64_t, __int128>;
T val;
constexpr ModInt(const int64_t v = 0) : val(v % MOD) { if (val < 0) val += MOD; }
constexpr ModInt operator+() const { return ModInt(val); }
constexpr ModInt operator-() const { return ModInt(MOD - val); }
constexpr ModInt inv() const { return power(*this, MOD - 2); }
constexpr friend ModInt operator+(ModInt lhs, const ModInt rhs) { return lhs += rhs; }
constexpr friend ModInt operator-(ModInt lhs, const ModInt rhs) { return lhs -= rhs; }
constexpr friend ModInt operator*(ModInt lhs, const ModInt rhs) { return lhs *= rhs; }
constexpr friend ModInt operator/(ModInt lhs, const ModInt rhs) { return lhs /= rhs; }
constexpr ModInt &operator+=(const ModInt x) {
if ((val += x.val) >= MOD) val -= MOD;
return *this;
}
constexpr ModInt &operator-=(const ModInt x) {
if ((val -= x.val) < 0) val += MOD;
return *this;
}
constexpr ModInt &operator*=(const ModInt x) {
val = prod_type(val) * x.val % MOD;
return *this;
}
constexpr ModInt &operator/=(const ModInt x) { return *this *= x.inv(); }
bool operator==(const ModInt b) const { return val == b.val; }
bool operator!=(const ModInt b) const { return val != b.val; }
friend std::istream &operator>>(std::istream &is, ModInt &x) noexcept { return is >> x.val; }
friend std::ostream &operator<<(std::ostream &os, const ModInt x) noexcept { return os << x.val; }
constexpr static ModInt identity() { return 1; }
constexpr ModInt pow(int64_t p) { return power(*this, p); }
};
namespace Hashing {
constexpr uint64_t mod = 1'000'000'000'000'000'003ULL;
using hash_t = ModInt<int64_t, mod>;
const hash_t base = std::mt19937_64(std::chrono::steady_clock::now().time_since_epoch().count())() % mod;
static std::vector<hash_t> pow{1};
static void expand_pow(size_t sz) {
if (pow.size() - 1 >= sz) {
return;
}
auto old_size = pow.size();
pow.resize(sz * 2 + 1);
for (auto i = old_size; i <= sz * 2; i++) {
pow[i] = pow[i - 1] * base;
}
}
static void flip(uint64_t &h, int p) {
if (p >= pow.size()) {
expand_pow(p);
}
h ^= pow[p].val;
}
} // namespace Hashing
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
ll n, x;
std::cin >> n >> x;
std::vector<ll> a(n);
for (auto &i : a) {
std::cin >> i;
}
uint64_t hash_x = 0;
for (auto p : sieve.primes) {
int c = 0;
while (x % p == 0) {
x /= p;
c++;
}
if (c % 2 == 1) {
Hashing::flip(hash_x, sieve.prime_id[p]);
}
}
if (x != 1) {
std::cout << "0\n";
return 0;
}
std::vector<uint64_t> hash_a;
for (auto &i : a) {
uint64_t hash = 0;
for (auto [p, c] : sieve.prime_factors(i)) {
if (c % 2 == 1) {
Hashing::flip(hash, sieve.prime_id[p]);
}
}
hash_a.push_back(hash);
}
std::map<uint64_t, int> cnt{std::pair(0ULL, 1)};
ll ans = 0;
uint64_t cur = 0;
for (int i = 0; i < n; i++) {
cur ^= hash_a[i];
if (cnt.count(cur ^ hash_x)) {
ans += cnt[cur ^ hash_x];
}
cnt[cur]++;
}
std::cout << ans << "\n";
return 0;
}
H 小红的红色段数量
比赛通过率：5.48%
知识点：启发式合并
思路：本题其实只需要求出每个节点染红后，最终排列中“红色段”数量是多少即可。该方案可以用树上启发式合并来解决：首先使用set维护子树节点信息，当添加/删除节点时，需要同时在set中查询红色段的数量影响。随后将小的子树的set合并到大的上面即可。
参考代码：
#include <bits/stdc++.h>
using ll = long long;
struct HLD {
int n;
std::vector<int> a, pos;
std::vector<int> sz, fa;
std::vector<std::vector<int>> g;
std::vector<bool> exist;
std::vector<int> ans;
int res;
HLD() {}
HLD(int n) {
init(n);
}
void init(int n) {
this->n = n;
a.resize(n);
pos.resize(n);
sz.resize(n);
fa.resize(n);
g.assign(n, {});
exist.assign(n, false);
ans.resize(n);
res = 0;
}
void addEdge(int u, int v) {
g[u].push_back(v);
g[v].push_back(u);
}
void work(int root = 0) {
fa[root] = -1;
dfs1(root);
for (int i = 0; i < n; i++) {
pos[a[i]] = i;
}
solve(root, true);
}
void dfs1(int u) {
if (fa[u] != -1) {
g[u].erase(std::find(g[u].begin(), g[u].end(), fa[u]));
}
sz[u] = 1;
for (auto &v : g[u]) {
fa[v] = u;
dfs1(v);
sz[u] += sz[v];
if (sz[v] > sz[g[u][0]]) {
std::swap(v, g[u][0]);
}
}
}
void add_subtree(int u, int ignore = -1) {
exist[pos[u]] = true;
res++;
if (pos[u] - 1 >= 0 && exist[pos[u] - 1]) {
res--;
}
if (pos[u] + 1 < n && exist[pos[u] + 1]) {
res--;
}
for (auto v : g[u]) {
if (v == ignore) continue;
add_subtree(v);
}
}
void delete_subtree(int u) {
exist[pos[u]] = false;
res--;
if (pos[u] - 1 >= 0 && exist[pos[u] - 1]) {
res++;
}
if (pos[u] + 1 < n && exist[pos[u] + 1]) {
res++;
}
for (auto v : g[u]) {
delete_subtree(v);
}
}
void solve(int u, bool keep) {
for (auto v : g[u]) {
if (v == g[u].front()) continue;
solve(v, false);
}
if (g[u].size()) {
solve(g[u].front(), true);
}
add_subtree(u, g[u].size() ? g[u].front() : -1);
ans[u] = res;
if (!keep) {
delete_subtree(u);
}
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
HLD hld(n);
for (auto &i : hld.a) {
std::cin >> i;
i--;
}
for (int i = 0; i < n - 1; i++) {
int u, v;
std::cin >> u >> v;
u--, v--;
hld.addEdge(u, v);
}
hld.work();
std::cout << std::fixed << std::setprecision(10);
std::cout << std::accumulate(hld.ans.begin(), hld.ans.end(), 0.) / n << '\n';
return 0;
}
