Codeforces Round #845 (Div. 2) 解题报告
\(\text{By DaiRuiChen007}\)
A. Everybody Likes Good Arrays!
简单题，注意到操作一奇一偶一定不优，而操作两个奇数则留下一个奇数，操作两个偶数则留下一个偶数
因此每次操作至多减少一对同奇偶的相邻数对，且存在一种方法使得每次操作都减少一对这样的数对，因此答案就是 \(a_i\equiv a_{i+1}\pmod 2\) 的 \(i\) 的个数
扫描一遍 \(\{a_i\}\) 统计即可
时间复杂度 \(\Theta(n)\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=101;
int a[MAXN];
inline void solve() {
int n,ans=0;
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<n;++i) if(a[i]%2==a[i+1]%2) ++ans;
printf("%d\n",ans);
}
signed main() {
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
B. Emordnilap
考虑一个排列 \(P=\{p_i\}\)，设 \(\operatorname{inv}(P)\) 表示 \(P\) 逆序对数，\(\overline P\) 表示 \(P\) 翻转得到的排列，显然 \(\operatorname{inv}(P)+\operatorname{inv}(\overline P)=\binom n2\)，因此我们只需要考虑跨越 \(P\) 和 \(\overline{P}\) 的逆序对，这样的逆序对数量显然是 \((n-1)+(n-2)+\cdots+0=\binom n 2\)，因此对于任何一个排列 \(P\)，其权值就是 \(2\times \binom n2=n\times (n-1)\)
对于 \(n!\) 种排列，其权值和为 \(n!\times n\times (n-1)\)，直接计算即可
时间复杂度 \(\Theta(n)\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=1e9+7;
inline void solve() {
int n;
scanf("%lld",&n);
int ans=n*(n-1)%MOD;
for(int i=1;i<=n;++i) ans=ans*i%MOD;
printf("%lld\n",ans);
}
signed main() {
int T;
scanf("%lld",&T);
while(T--) solve();
return 0;
}
C. Quiz Master
显然先按 \(a_i\) 排序，枚举选择的学生中权值最小的一个，记为 \(a_l\)，显然此时我们应该选取最小的 \(r\) 使得 \(a_l\sim a_r\) 中的学生可以组队，并用 \(a_r-a_l\) 更新答案
注意到随着 \(l\) 从 \(1\) 向 \(n\) 递增，\(r\) 肯定是单调不降的，因此维护一下双指针的移动，每次移动暴力枚举约数修改即可
时间复杂度 \(\Theta(n\sqrt m)\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+1,INF=1e9;
int n,m,a[MAXN],cnt[MAXN],tot=0;
vector <int> factors[MAXN];
inline void del(int x) {
for(int d:factors[x]) {
if(d>m) break;
--cnt[d];
if(!cnt[d]) ++tot;
}
}
inline void add(int x) {
for(int d:factors[x]) {
if(d>m) break;
if(!cnt[d]) --tot;
++cnt[d];
}
}
inline void solve() {
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i) cnt[i]=0;
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
sort(a+1,a+n+1);
tot=m;
int ans=INF;
for(int l=1,r=0;l<=n;++l) {
while(r<n&&tot!=0) add(a[++r]);
if(tot>0) break;
ans=min(ans,a[r]-a[l]);
del(a[l]);
}
printf("%d\n",(ans==INF)?-1:ans);
}
signed main() {
for(int i=1;i<MAXN;++i) {
for(int j=i;j<MAXN;j+=i) {
factors[j].push_back(i);
}
}
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
D. Score of a Tree
注意到第 \(i\) 个点在第 \(j\) 秒的值 \(a_{i,j}\) 实际上是 \(i\) 的子树中深度为 \(dep_i+j\) 的点的点权异或和，设这样的点有 \(k\) 个
那么我们知道，\(a_{i,j}=1\) 的情况共有 \(C_1=\sum_{d=0}^k [d\bmod 2=1]\times\binom dk\) 种，而 \(a_{i,j}=0\) 的情况共有 \(C_0=\sum_{d=0}^k[d\bmod 2=0]\times \binom dk\) 种
而根据组合数学的基本结论，\(\forall k\in \mathbb{Z^+}:C_0=C_1\)，证明如下：
根据二项式定理，有如下的推导：
\[\begin{aligned}
C_0+C_1
&=\sum_{d=0}^k \binom kd\\
&=\sum_{d=0}^k 1^{d}\times 1^{k-d}\times \binom dk\\
&=(1+1)^{k}=2^k\\[3ex]
C_0-C_1&=\sum_{d=0}^k (-1)^d\times \binom kd\\
&=\sum_{d=0}^k (-1)^d\times 1^{k-d}\times \binom kd\\
&=[(-1)+1]^k=0
\end{aligned}
\]因此 \(C_0=C_1=2^{k-1}\)，证明完毕
因此，每个节点在任何时刻为 \(0\) 或 \(1\) 的概率是均等的，假如 \(i\) 的子树中有深度为 \(dep_i+j\) 的点，那么其在时刻 \(j\) 对答案的贡献是 \(2^{n-1}\)
因此树形 dp 维护一下每个点的最长链大小即可
时间复杂度 \(\Theta(n)\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+1,MOD=1e9+7;
inline int ksm(int a,int b,int m=MOD) {
int ret=1;
while(b) {
if(b&1) ret=ret*a%m;
a=a*a%m;
b=b>>1;
}
return ret;
}
vector <int> G[MAXN];
int dp[MAXN];
inline void dfs(int p,int f) {
for(int v:G[p]) {
if(v==f) continue;
dfs(v,p);
dp[p]=max(dp[p],dp[v]+1);
}
}
inline void solve() {
int n;
scanf("%lld",&n);
for(int i=1;i<=n;++i) G[i].clear(),dp[i]=1;
for(int i=1;i<n;++i) {
int u,v;
scanf("%lld%lld",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,0);
int ans=0;
for(int i=1;i<=n;++i) ans=(ans+dp[i]%MOD)%MOD;
printf("%lld\n",ans*ksm(2,n-1)%MOD);
}
signed main() {
int T;
scanf("%lld",&T);
while(T--) solve();
return 0;
}
E. Edge Reverse
最小化最大值，直接想二分，每次检查权值 \(\le k\) 的边是否翻转
我们注意到，一条可以选择翻不翻转的边可以看成一条双向边，因为没有简单路径会同时经过 \(u\to v\) 和 \(u\gets v\)，否则就产生了环，这一定不优
因此每次把权值 \(\le k\) 的边当成双向的，用 tarjan 缩点后判断 DAG 上入度为 \(0\) 的点是否唯一即可
时间复杂度 \(\Theta((n+m)\log w)\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+1,INF=1e9;
int n,m,ver[MAXN][2],w[MAXN],deg[MAXN];
vector <int> G[MAXN];
int dfn[MAXN],low[MAXN],dfncnt,stk[MAXN],top,bel[MAXN],scccnt;
bool ins[MAXN];
inline void tarjan(int p) {
dfn[p]=low[p]=++dfncnt;
stk[++top]=p,ins[p]=true;
for(int v:G[p]) {
if(!dfn[v]) {
tarjan(v);
low[p]=min(low[p],low[v]);
} else if(ins[v]) low[p]=min(low[p],low[v]);
}
if(dfn[p]==low[p]) {
++scccnt;
int k;
do {
k=stk[top--];
bel[k]=scccnt;
ins[k]=false;
} while(k!=p);
}
}
inline bool check(int k) {
for(int i=1;i<=n;++i) {
deg[i]=0,dfn[i]=0;
ins[i]=false;
G[i].clear();
}
dfncnt=0,top=0,scccnt=0;
for(int i=1;i<=m;++i) {
if(w[i]<=k) {
G[ver[i][0]].push_back(ver[i][1]);
G[ver[i][1]].push_back(ver[i][0]);
} else G[ver[i][0]].push_back(ver[i][1]);
}
for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
for(int u=1;u<=n;++u) {
for(int v:G[u]) {
if(bel[u]!=bel[v]) ++deg[bel[v]];
}
}
int cnt=0;
for(int i=1;i<=scccnt;++i) if(!deg[i]) ++cnt;
return cnt==1;
}
inline void solve() {
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i) scanf("%d%d%d",&ver[i][0],&ver[i][1],&w[i]);
int l=0,r=INF,res=-1;
while(l<=r) {
int mid=(l+r)>>1;
if(check(mid)) res=mid,r=mid-1;
else l=mid+1;
}
printf("%d\n",res);
}
signed main() {
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
F. Comfortably Numb
考虑建立笛卡尔树，得到每个 \(a_i\) 作为区间最大值时，区间左右端点的范围
我们的思路就是枚举其中一个端点，用 01-Trie 维护异或前缀和求解，记 \(sum_i=\oplus_{j=1}^i a_j\)，即异或意义下的前缀和
接下来我们假设区间为 \([l,r]\)，最大值在 \(x\) 上，我们可以分类讨论枚举区间的左端点还是右端点：
- 若 \(x-l+1\le r-x+1\)，枚举左端点 \(i\)，等价于在 \(sum_x\sim sum_r\) 中找到和 \(a_x\oplus sum_{i-1}\) 异或最大的
- 若 \(x-l+1>r-x+1\)，枚举右端点 \(i\)，等价于在 \(sum_{l-1}\sim sum_{x-1}\) 中找到和 \(a_x\oplus sum_i\) 异或最大的
注意到这两个问题就是可持久化 01-Trie 的模板，因此用可持久化 01-Trie 回答这些问题即可
在笛卡尔树上，我们每次枚举其非重儿子的全部子树，因此每个点 \(i\) 被枚举的次数等价于其到根的轻边数量，由于每次经过一条轻边，其所在子树大小至少 \(\times 2\)，因此每个点至多被枚举 \(\log_2 n\) 次（这部分的复杂度分析和 DSU on Tree 是相同的）
时间复杂度 \(\Theta(n\log n\log w)\)，\(w\) 为 \(\{a_i\}\) 的值域
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+1;
struct node {
int son[2],cnt;
node() { son[0]=son[1]=0,cnt=0; }
inline int& operator [](const int &i) { return son[i]; }
} tr[MAXN*35];
int siz;
inline int bit(int x) { return 1<<x; }
inline int dig(int x,int d) { return (x>>d)&1; }
inline void insert(int x,int d,int pre,int now) {
if(d<0) return ;
int c=dig(x,d);
tr[now][c^1]=tr[pre][c^1];
tr[now][c]=++siz;
tr[tr[now][c]].cnt=tr[tr[pre][c]].cnt+1;
insert(x,d-1,tr[pre][c],tr[now][c]);
}
inline int query(int x,int d,int l,int r) {
if(d<0) return 0;
int c=dig(x,d);
if(tr[tr[r][c^1]].cnt-tr[tr[l][c^1]].cnt>0) {
return (1<<d)|query(x,d-1,tr[l][c^1],tr[r][c^1]);
}
return query(x,d-1,tr[l][c],tr[r][c]);
}
int a[MAXN],sum[MAXN],root[MAXN],f[MAXN][20];
inline int pos(int l,int r) {
int k=__lg(r-l+1);
return (a[f[l][k]]>a[f[r-bit(k)+1][k]])?f[l][k]:f[r-bit(k)+1][k];
}
inline int dfs(int l,int r) {
if(l>=r) return 0;
int mid=pos(l,r);
int ans=max(dfs(l,mid-1),dfs(mid+1,r));
if((r-mid+1)<(mid-l+1)) {
for(int i=mid;i<=r;++i) {
ans=max(ans,query(sum[i]^a[mid],31,(l==1)?0:root[l-2],root[mid-1]));
}
} else {
for(int i=l;i<=mid;++i) {
ans=max(ans,query(sum[i-1]^a[mid],31,root[mid-1],root[r]));
}
}
return ans;
}
inline void solve() {
for(int i=0;i<=siz;++i) tr[i]=node();
siz=0;
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]),sum[i]=sum[i-1]^a[i];
for(int i=0;i<=n;++i) {
root[i]=++siz;
insert(sum[i],31,((i==0)?0:root[i-1]),root[i]);
}
for(int i=1;i<=n;++i) f[i][0]=i;
for(int k=1;k<20;++k) {
for(int i=1;i+bit(k-1)<=n;++i) {
f[i][k]=(a[f[i][k-1]]>a[f[i+bit(k-1)][k-1]])?f[i][k-1]:f[i+bit(k-1)][k-1];
}
}
printf("%d\n",dfs(1,n));
}
signed main() {
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
![[数据结构] 二叉搜索树 (二叉排序树)](https://img2023.cnblogs.com/blog/3039354/202302/3039354-20230209215639864-1714301471.jpg)
