AtCoder Beginner Contest 408 D-F 题解

D. Flip to Gather

题意

给你一个长度为 $N$ 的 $01$ 字符串 $S$，每次操作可以选择 $1\le i\le N$，把 $S_i$ 变成 $1-S_i$。

你要使得这个字符串的所有 $1$ 必须连续存在，求最小操作数。

思路

假设最终的序列从 $l$ 到 $r$ 都是 $1$，其余是 $0$；设 $S$ 表示这个答案需要的操作数。

不难想到前缀和维护区间和，设 $a_i,b_i$ 分别表示前 $i$ 位中为 $0,1$ 的数量。

则
$$\begin{array}{rl}S& =[l左边1的数量]+[l\sim r之间0的数量]+[r右边1的数量]\\ & =b_{l-1}+(a_r-a_{l-1})+(b_n-b_r)\\ & =(b_{l-1}-a_{l-1})-(b_r-a_r)+b_n\end{array}$$
由于 $b_n$ 的值与 $l,r$ 无关，所以可以把它提出来，最后再加上，所以，令 $S^{\prime }=S-b_n$。

则 $S^{\prime }=(b_{l-1}-a_{l-1})-(b_r-a_r)$，可以发现，对于每个 $r$，我们只要找到最小的 $(b_{l-1}-a_{l-1})$ 即可，在前面计算过程中用一个变量 $mn$ 记录就可以了。

最终答案为 $S^{\prime }+b_n$。

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
void solve(){int n;string s;cin>>n>>s;int ans=0,mn=0;int one=0,zero=0;//即上文说的b_i和a_ifor(int i=0;i<n;i++){if(s[i]=='1') one++;else zero++;ans=min(ans,mn-(one-zero));mn=min(mn,one-zero);}cout<<ans+one<<endl;
}
signed main(){int T;cin>>T;while(T--){solve();}return 0;
}

E. Minimum OR Path

题意

给你一个 $N$ 个点 $M$ 条边的无自环的无向图，第 $i$ 条边连接 $u_i$ 和 $v_i$，权值为 $w_i$。

在所有从 $1$ 到 $n$ 的简单路径（不经过同一点两次的路径）中，找到边权或和的最小值。

思路

贪心。把最终答案转换成二进制数看，接下来所说的高位、低位都指二进制位：

可以发现，越高位的贡献越大，而且二进制数 $100000>011111$，即，只要高位是 $0$，不管低位怎么增加都还是比原来小；

所以，要使答案最小，首先要使高位尽可能小。

那就可以从高位往低位贪心，假设一开始的答案的 $31$ 位每一位都是 $1$。从第 $31$ 位开始，假设这一位是 $0$，并把这个图的边全部删除（认为这个图上只有点，无边，后续逐渐加边），然后将所有的满足 $[其边权的(当前位)和(之前已经确定不是1的位)不是1]$ 的边全部加入这个图，检测这个图是否连通。

若连通，说明这一位可以为 $0$，且这一位为 $0$ 时的对答案的贡献一定比为 $1$ 时的小，所以将答案的这一位设为 $0$；

否则，说明这一位只能为 $1$，那么答案的这一位还是 $1$，保留原值。

接下来说一下如何判断图是否联通：使用并查集（$\text{DSU}$）。对于每一位，处理之前先把 $f{a}_i$ 初始化为 $i$，然后，对于每条满足要求（上面已经说过了）的边 $(u,v)$，将 $f{a}_{find(v)}=f{a}_{find(u)}$。

时间复杂度为 $O((N+M)\times \log N)$。

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=200005;
int n,m;
int fa[maxn];
struct Node{int u,v,w;
}e[maxn];
int find(int x){if(fa[x]==x) return fa[x];return fa[x]=find(fa[x]);
}
signed main(){cin>>n>>m;int one=0,zero=0;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;e[i]={u,v,w};}for(int a=30;a>=0;a--){for(int i=1;i<=n;i++){fa[i]=i;}for(int i=1;i<=m;i++){if(e[i].w&(zero|(1<<a))) continue;int u=e[i].u,v=e[i].v;if(u>v) swap(u,v);if(find(u)==find(v)) continue;fa[find(v)]=fa[find(u)];}if(find(n)==find(1)){zero|=(1<<a);}else{one|=(1<<a);}}cout<<one<<endl;return 0;
}

F. Athletic

题意

有 $N$ 个架子，第 $i$ 个高度为 $H_i$，$H$ 为长度为 $N$ 的排列。一开始，你可以选择站在任意一个架子上，当你在架子 $i$ 上时，你可以移动到满足以下条件的任意一个架子 $j$ 上：

• $H_i-H_j\ge D$ 且 $1\le |i-j|\le R$ （$D$ 和 $R$ 已经给定）。

求出你的最大移动次数。

思路

考虑动态规划。设 $f_i$ 表示到高度为 $i$ 的那个架子移动的最大次数，$po{s}_i$ 表示 $i$ 在 $H$ 中出现的位置。

则朴素的转移为 $f_i={\max }_{[1\le j\le N]且[po{s}_i-R\le po{s}_j\le po{s}_i+R]且[j-i\ge D]}{f}_j+1$。

显然这个复杂度是 $O(N^2)$ 的，所以我们要想出一个 $O(\log n)$ 或 $O(1)$ 查询区间最大值的方法。

考虑线段树维护区间最大值，对于每个高度 $i$，将 $f_{i+D}$ 的值加入线段树（若 $i+D>N$ 就不加），然后区间查询 $[po{s}_i-R,po{s}_i+R]$ 的最大值为 $p$，则 $f_i=p+1$。最终最大的 $f_i$ 值即为答案。

时间复杂度 $O(N\log N)$。

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=2e9;
const int maxn=500005;
struct SEGMENT_TREE{int mx[maxn<<2];void init(){memset(mx,-1,sizeof(mx));}void update(int x,int pos,int val,int l,int r){if(l==r) return void(mx[x]=val);int mid=l+r>>1;if(pos<=mid) update(x<<1,pos,val,l,mid);else update(x<<1|1,pos,val,mid+1,r);mx[x]=max(mx[x<<1],mx[x<<1|1]);}int query(int x,int L,int R,int l,int r){if(L<=l&&r<=R) return mx[x];int mid=l+r>>1,ans=-inf;if(L<=mid) ans=max(ans,query(x<<1,L,R,l,mid));if(R>mid) ans=max(ans,query(x<<1|1,L,R,mid+1,r));return ans;}
}TR;
int h[maxn],f[maxn];
int pos[maxn];
signed main(){int n,D,R;cin>>n>>D>>R;TR.init();for(int i=1;i<=n;i++){cin>>h[i];pos[h[i]]=i;}for(int i=n;i>=1;i--){if(i+D<=n) TR.update(1,pos[i+D],f[i+D],1,n);f[i]=TR.query(1,max(1ll,pos[i]-R),min(n,pos[i]+R),1,n)+1;}int ans=0;for(int i=1;i<=n;i++){ans=max(ans,f[i]);}cout<<ans<<endl;return 0;
}