Codeforces Round 974 (Div.3) 题解
A. Robin Helps 模拟
按照题意模拟即可。
void Showball(){
int n,k;
cin>>n>>k;
int cur=0,ans=0;
for(int i=0;i<n;i++){
int x;
cin>>x;
if(x>=k) cur+=x;
else if(!x){
if(cur>=1) cur--,ans++;
}
}
cout<<ans<<endl;
}
B. Robin Hood and the Major Oak 数学
奇数相乘结果永远为奇数，所以 \(i^i\) 的奇偶性与 \(i\) 的奇偶性一样。所以判断区间奇数个数是否是偶数即可。
void Showball(){
int n,k;
cin>>n>>k;
if(((n+1)/2-(n-k+1)/2)&1) cout<<"NO\n";
else cout<<"YES\n";
}
C. Robin Hood in Town 二分
单调性显然成立，考虑二分答案。\(check\) 函数按照题目模拟即可。注意二分范围要取到 \(1e18\)。
void Showball(){
int n;
cin>>n;
vector<int> a(n);
LL sum=0;
for(int i=0;i<n;i++){
cin>>a[i];
sum+=a[i];
}
if(n<=2) return cout<<"-1\n",void();
auto check=[&](LL x){
double avg=((sum+x)*1.0)/(2.0*n);
int cnt=0;
for(int i=0;i<n;i++){
if(a[i]<avg) cnt++;
}
return cnt>n/2;
};
LL l=0,r=1e18;
while(l<r){
LL mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l<<endl;
}
D. Robert Hood and Mrs Hood 思维
问题的关键是求解与区间 \([l,r]\) 相交的区间有多少个？直接求不好求解，需要线段树，不妨思考问题的反面。与区间 \([l,r]\) 不相交的区间有多少个？显然为右端点小于 \(l\) 的区间和左端点大于 \(r\) 的区间数之和。这两部分我们都可以维护一个前缀和后缀即可。
void Showball(){
int n,d,k;
cin>>n>>d>>k;
vector<int> L(n+2),R(n+2);
for(int i=1;i<=k;i++){
int l,r;
cin>>l>>r;
L[l]++;
R[r]++;
}
for(int i=1;i<=n;i++) R[i]+=R[i-1];
for(int i=n;i>=0;i--) L[i]+=L[i+1];
int maxn=-inf,minn=inf,imaxn=0,iminn=0;
for(int i=1;i+d-1<=n;i++){
int t=R[i-1]+L[i+d];
if(t>maxn) maxn=t,imaxn=i;
if(t<minn) minn=t,iminn=i;
}
cout<<iminn<<" "<<imaxn<<endl;
}
E. Rendez-vous de Marian et Robin 最短路
最短路问题，先不考虑骑马，那么答案自然就是以 \(1\) 和 \(n\) 为起点跑两遍最短路，然后枚举一遍相遇的点，维护一下答案即可。考虑骑马，一旦骑过马，那么之后的权值为都原本的一半，因此我们可以开一个额外的数组维护骑马情况下的最短路。并且把是否骑马也存到优先队列中即可。
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
const i64 inf=1e18;
void Showball(){
int n,m,h;
cin>>n>>m>>h;
vector<int> has_house(n);
for(int i=0;i<h;i++){
int x;
cin>>x;
x--;
has_house[x]=1;
}
vector<vector<array<int,2>>> e(n);
while(m--){
int u,v,w;
cin>>u>>v>>w;
u--;
v--;
e[u].push_back({v,w});
e[v].push_back({u,w});
}
auto dijkstra=[&](int s){
priority_queue<array<i64,3>,vector<array<i64,3>>,greater<array<i64,3>>> pq;
pq.push({0LL,s,0});
vector<array<i64,2>> dis(n,{inf,inf});
dis[s][0]=0;
vector<array<int,2>> st(n);
while(!pq.empty()){
auto [d,u,house]=pq.top();
pq.pop();
if(st[u][house]) continue;
st[u][house]=1;
if(!house&&has_house[u]){
pq.push({d,u,1});
}
for(auto [v,w]:e[u]){
int nw=house?w/2:w;
if(dis[v][house]>d+nw){
dis[v][house]=d+nw;
pq.push({dis[v][house],v,house});
}
}
}
vector<i64> d(n);
for(int i=0;i<n;i++){
d[i]=min(dis[i][0],dis[i][1]);
}
return d;
};
auto d1=dijkstra(0);
auto dn=dijkstra(n-1);
i64 ans=inf;
for(int i=0;i<n;i++){
ans=min(ans,max(d1[i],dn[i]));
}
if(ans==inf) ans=-1;
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
cin>>t;
while(t--){
Showball();
}
return 0;
}
F. Sheriff's Defense 树形DP
简单的树形DP，考虑每个营地是否强化即可。
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
void Showball(){
int n,c;
cin>>n>>c;
vector<vector<int>> e(n);
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
u--;
v--;
e[u].push_back(v);
e[v].push_back(u);
}
vector<array<i64,2>> dp(n);
function<void(int,int)> dfs=[&](int u,int fa)->void{
dp[u][0]=0;
dp[u][1]=a[u];
for(auto v:e[u]){
if(v==fa) continue;
dfs(v,u);
dp[u][0]+=max(dp[v][0],dp[v][1]);
dp[u][1]+=max(dp[v][0],dp[v][1]-2*c);
}
};
dfs(0,-1);
cout<<max(dp[0][0],dp[0][1])<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
cin>>t;
while(t--){
Showball();
}
return 0;
}
H. Robin Hood Archery 思维+异或哈希/莫队
容易发现，警长最多平局，不会取得胜利。并且只有区间内所有数出现次数为偶数次时才会达成平局，否则必败。
容易想到前缀异或和，区间异或为 \(0\)。但其实这是一个必要不充分条件，比如：\(1, 2 , 3\) 这三个数的异或和为 \(0\) 。但是并不是满足要求的。因此，为了防止发生冲突，我们可以借助哈希。并且原本的区间异或操作可以用差值去求解。
#include<bits/stdc++.h>
using namespace std;
using u64=unsigned long long;
const int N = 1e6+10;
u64 h[N];
void init(){
mt19937_64 rnd(time(0));
for(int i=1;i<N;i++){
h[i]=rnd();
}
}
void Showball(){
int n,q;
cin>>n>>q;
vector<u64> pre(n+1);
for(int i=1;i<=n;i++){
int x;
cin>>x;
pre[i]=pre[i-1]^h[x];
}
while(q--){
int l,r;
cin>>l>>r;
if(pre[r]==pre[l-1]) cout<<"YES\n";
else cout<<"NO\n";
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
cin>>t;
init();
while(t--){
Showball();
}
return 0;
}
当然，这道题目也可以用莫队解决。维护同样的问题，那么我们只需要去维护出现次数为奇数的数量是否为 \(0\) 即可。有一些卡常，把 \(vector\) 换成普通数组就过了。
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
const int N=1e6+10;
struct Q{
int l,r,id;
}q[N];
int cnt[N],pos[N],a[N],ans[N];
void Showball(){
int n,m;
cin>>n>>m;
//分块
int siz=sqrt(n);
for(int i=1;i<=n;i++){
cin>>a[i];
cnt[a[i]]=0;
pos[i]=i/siz;
}
for(int i=0;i<m;i++){
cin>>q[i].l>>q[i].r;
q[i].id=i;
}
sort(q,q+m,[&](Q x,Q y){
return pos[x.l]!=pos[y.l]?pos[x.l]<pos[y.l]:(pos[x.l]&1?x.r<y.r:x.r>y.r);
});
int l=1,r=0;
int count=0;
auto Add=[&](int x){
cnt[a[x]]^=1;
if(cnt[a[x]]==1) count++;
else count--;
};
for(int i=0;i<m;i++){
while(q[i].l<l) Add(--l);
while(q[i].r>r) Add(++r);
while(q[i].l>l) Add(l++);
while(q[i].r<r) Add(r--);
ans[q[i].id]=count;
}
for(int i=0;i<m;i++) cout<<(ans[i]?"NO\n":"YES\n");
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
cin>>t;
while(t--){
Showball();
}
return 0;
}