Codeforces Round #851 (Div. 2) 题解
A. One and Two
取 \(\log_2\)，变成加号，前缀和枚举 \(s[i]=\dfrac{s[n]}{2}\)。
B. Sum of Two Numbers
对于每一位，如果是偶数则平均分，如果是奇数则分给当前数字和小的数多 \(1\)。
C. Matching Numbers
随便推个构造即可，给个参考。
void solve(){
int n;
cin>>n;
if(n%2==0){
cout<<"NO"<<endl;
return;
}
cout<<"YES"<<endl;
n*=2;
cout<<"1 "<<n<<endl;
for(int i=2,tmp=n-2;i<=(n+2)/4;i++,tmp-=2)
cout<<i<<" "<<tmp<<endl;
for(int i=(n+2)/4+1,tmp=n-1;i<=n/2;i++,tmp-=2)
cout<<i<<" "<<tmp<<endl;
return;
}
D. Moving Dots
考虑所求对于一个状态，必然是两个点“双向奔赴”的时候才有贡献。枚举这相邻的两个点 \(x,y\)，然后发现 \([x-len,y+len-1]\) 这一范围内其他数取不了。使用 lower_bound 随便求就好了。
时间复杂度 \(O(n^2\log n)\)。
E. Sum Over Zero
转移为前缀和，写出 \(dp\) 状态为：
\[f_i=\max(f_{i-1},\max_{j<i,s_j\leq s_i} f_{j-1}+(i-j)) \]考虑把 \(f_{j-1}-j\) 试做一个整体，那么相当于维护这玩意最小值。
树状数组即可。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define ll long long
#define MP make_pair
inline ll read(){
ll re=0;char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9') re=10*re+ch-'0',ch=getchar();
return re;
}
int n;
namespace sugt{
int mx[200005];
void build(){
for(int i=1;i<=n;i++) mx[i]=-1e9;
}
int lowbit(int x){
return x&(-x);
}
void ins(int x,int y){
while(x<=n){
mx[x]=max(mx[x],y);
x+=lowbit(x);
}
return;
}
int query(int x){
int res=-1e9;
while(x){
res=max(res,mx[x]);
x-=lowbit(x);
}
return res;
}
}
ll s[200005],t[200005];
int f[200005];
map<ll,int> M;int tot=0;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>s[i];
s[i]+=s[i-1];
t[i]=s[i];
}
sort(t,t+n+1);
for(int i=0;i<=n;i++)
if(!M[t[i]]) M[t[i]]=++tot;
for(int i=0;i<=n;i++)
s[i]=M[s[i]];
sugt::build();
sugt::ins(s[0],0);
for(int i=1;i<=n;i++){
f[i]=max(f[i-1],sugt::query(s[i])+i);
sugt::ins(s[i],f[i-1]-i);
}
cout<<f[n];
return 0;
}
F. XOR, Tree, and Queries
引理： 假设 \(w(u,v)\) 为 \(u,v\) 路径上所有边权异或，则 \(w(u,v)=w(1,u)\ \text{xor}\ w(1,v)\)。
本题相当于给 \(w(1,u)\) 赋权。\(w(1,u)\) 有贡献当且仅当 \(d(u)\) 为奇数。
对于每个 \((u,v,w)\) 连边，每个连通块选代表点，代表点确定整个块确定。
拆位枚举即可。
标签：ch,int,题解,ll,Codeforces,Div,include From： https://www.cnblogs.com/KawaiiOU/p/17107630.html