Codeforces 888 div3 A-G

A. Escalator Conversations

分析

二者身高差为k的倍数且不超过m-1倍，身高差不能为0（即不能在同一个阶梯）

C++代码

#include<iostream>
using namespace std;
void solve(){int n,m,k,H,ans=0;cin>>n>>m>>k>>H;for(int i=0;i<n;i++){int x;cin>>x;if(H!=x&&abs(H-x)%k==0&&abs(H-x)/k<=m-1)ans++;}cout<<ans<<endl;
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
} 

B. Parity Sort

分析

把奇数和偶数分开排序，然后依次填充原数组奇数和偶数的地方，判断是否有前面的数大于后面的情况，如果有，则输出NO

C++代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void solve(){int n;cin>>n;vector<int> s(n+5,0),a,b;for(int i=1;i<=n;i++){cin>>s[i];if(s[i]%2)b.push_back(s[i]);else a.push_back(s[i]);}sort(a.begin(),a.end());sort(b.begin(),b.end());int ia=0,ib=0,flag=0;for(int i=1;i<=n;i++){if(s[i]%2==0)s[i]=a[ia++];else s[i]=b[ib++];if(s[i]<s[i-1]){flag=1;break;}}if(flag)puts("NO");else puts("YES");
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}

C. Tiles Comeback

分析

k=1，直接从a[1]跳到a[n]

k!=1

1、a[1]==a[n]，找有没有k个a[1]即可

2、a[1]!=a[n]，找k个a[1]和k个a[n]且要按顺序

C++代码

#include<iostream>
using namespace std;
void solve(){int n,k;cin>>n>>k;int a[n+5];for(int i=1;i<=n;i++)cin>>a[i];if(k==1)puts("YES");else if(a[1]==a[n]){int sum=0;for(int i=1;i<=n;i++)if(a[i]==a[1])sum++;if(sum>=k)puts("YES");else puts("NO");}else{int cnt1=1,cnt2=1,l=n;for(int i=2;i<=n;i++){if(a[i]==a[1])cnt1++;if(cnt1==k){l=i;break;}}for(int j=n-1;j>l;j--)if(a[j]==a[n])cnt2++;if(cnt2<k)puts("NO");else puts("YES");}
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}

D. Prefix Permutation Sums

分析

对于给定的数组a，找出它的原数组s

因为a只丢了一个元素，所以原数组的1~n的排列中一定有两个数没出现，如果大于两个元素，则原数组不存在

对原数组的每个小于等于n的元素标记出现过，如果元素出现次数大于1或者元素>n，就用cnt记录下来；接下来找出未出现过的两个数的和sum，如果等于cnt，则表示原数组存在，否则不存在

C++代码

#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
void solve(){int n;cin>>n;LL a[n+5]={0},b[n+5]={0},cnt=0,flag=0;for(int i=1;i<n;i++)cin>>a[i];vector<LL> s;for(int i=1;i<n;i++){//找出原数组sLL t=a[i]-a[i-1];s.push_back(t);}for(int i=0;i<n-1;i++){if(s[i]<=n){b[s[i]]++;if(b[s[i]]>1)cnt=s[i];}else cnt=s[i];}LL sum=0,k=0;for(int i=1;i<=n;i++)if(!b[i])k++,sum+=i;if(k>2||k==2&&sum!=cnt)flag=1;if(!flag)puts("YES");else puts("NO"); 
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}

E. Nastya and Potions

分析

一个药水x可以被几种药物混合制成就建几条指向x的边，建完边后就用拓扑排序做，所有入度为0的药水的价格只能是它本身的价格，入度不为0的价格可以由其他的药水混合制成，最终的最低价格为min(直接买的价格，由其他药水混合的价格)

C++代码

#include<iostream>
#include<queue>
using namespace std;
typedef long long LL;
const int N=200010;
int h[N],e[N],ne[N],idx;
LL a[N],d[N],w[N];
int n,k;
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void solve(){cin>>n>>k;for(int i=1;i<=n;i++)h[i]=-1,w[i]=0,d[i]=0;idx=0;for(int i=1;i<=n;i++)cin>>a[i];while(k--){//输入所有无限免费供应的药水int x;cin>>x;a[x]=0;}for(int i=1;i<=n;i++){int m,x;cin>>m;while(m--){cin>>x;add(x,i);d[i]++;//i的入度加一}}queue<int> q;for(int i=1;i<=n;i++)//入度为0的药水的价格只能是它本身的价格，不能由别的药水混合制成if(!d[i])w[i]=a[i],q.push(i);while(q.size()){int t=q.front();q.pop();w[t]=min(w[t],a[t]);//更新药水t的价格for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];w[j]+=w[t];//计算药水j由别的药水混合所需的价格if(--d[j]==0)q.push(j);}}for(int i=1;i<=n;i++)cout<<w[i]<<" ";cout<<endl;
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}

F. Lisa and the Martians

分析

求(a[i]^x)&(a[j]^x)的最大值，即a[i]^x和a[j]^x的二进制数相同的位置尽可能多且尽可能在高位，即a[i]和a[j]二进制相同的位置尽可能多，即不同的位置尽可能少且尽可能为低位，

则可以装换成求a[i]^a[j]的最小值

有个常用结论：n个数的最小异或对答案就是排序后最小的相邻异或和

所以直接排序后求最小相邻异或和即可

然后计算t

对于选择的a[i]和a[j]，从前往后枚举第0~k-1位，

如果a[i]和a[j]的第i位都是0，则t的第i位一定是1

如果a[i]和a[j]的第i位都是1，则t的第i位一定是0

如果一个0一个1，则t的第i位随意

C++代码

#include<iostream>
#include<algorithm>
#include<map>
#include<array>
#include<vector>
using namespace std;
const int N=200010,INF=2e9;
void solve(){int n,k;cin>>n>>k;vector<array<int,2>> a(n);for(int i=0;i<n;i++){int x;cin>>x;a[i]={x,i+1};}sort(a.begin(),a.end());int minn=INF,id1,id2,ai,aj;for(int i=0;i<n-1;i++){auto [c,d]=a[i];auto [e,f]=a[i+1];if((c^e)<minn){minn=(c^e);id1=d,id2=f;ai=c,aj=e;}}int t=1,x=0;for(int i=0;i<=k-1;i++){int a1=ai>>i&1,a2=aj>>i&1;//a1=a2=0则x的该位一定是1;  a1!=a2则x的该位可以是0也可以是1,这里当成0; a1=a2=1则x的该位一定是0if((a1==0&&a2==0))x+=t;t*=2;}cout<<id1<<" "<<id2<<" "<<x<<endl;
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
} 

G. Vlad and the Mountains

分析

这题在线做法肯定会超时，那么可以用离线做法，先存储所有询问，再统一处理

首先，对于一对询问a,b,e，依题意，不能到达高度大于h[a]+e的山上

所以把每条边的权值设置成连接该边的两点的高度较大值

vector<array<int,3>> edge;//按照edge[i]={w,a,b}，先是权值，然后是两个点

然后把每条边按照权值从小到大排序

vector<array<int,4>> query;//按照edge[i]={h[a]+e,a,b,i}，先是h[a]+e，然后两个点，然后是询问的编号

对所有询问按照h[a]+e从小到大排序

然后依次枚举每个询问，每次将权值<=h[a]+e的边加入到并查集，然后判断a和b是否在同一连通块中，如果是，就可以从a走到b，否则不能

C++代码

#include<iostream>
#include<vector>
#include<array>
#include<algorithm>
using namespace std;
const int N=200010;
int p[N],h[N];
int find(int x){if(p[x]!=x)p[x]=find(p[x]);return p[x];
}
void merge(int a,int b){a=find(a),b=find(b);if(a!=b)p[a]=b;
}
void solve(){int n,m,q;cin>>n>>m;for(int i=1;i<=n;i++)p[i]=i;//并查集 for(int i=1;i<=n;i++)cin>>h[i];vector<array<int,3>> edge(m);//存储所有的边 for(int i=0;i<m;i++){int a,b;cin>>a>>b;edge[i]={max(h[a],h[b]),a,b};}sort(edge.begin(),edge.end());cin>>q;vector<array<int,4>> query(q);for(int i=0;i<q;i++){int a,b,e;cin>>a>>b>>e;query[i]={h[a]+e,a,b,i};}sort(query.begin(),query.end());vector<int> ans(q,0);int t=0;for(auto [h,u,v,i]:query){//把所有高度小于等于h的点都加入到并查集中while(t<m&&edge[t][0]<=h){//只能走到高度小于等于h的山merge(edge[t][1],edge[t][2]);t++;}if(find(u)==find(v))ans[i]=1;} for(int i=0;i<q;i++)if(ans[i])puts("YES");else puts("NO");
}
int main(){int t;cin>>t;while(t--){solve();} return 0;
}