\(A. Escalator Conversations\)
用 \(map\) 存楼梯的高度(差)，对每个人看一下需要的楼梯高度是否存在。
int a[N];
void solve(){
int n=read(),m=read(),k=read(),h=read();
map<int,int>mp;
for(int i=1;i<m;i++){
mp[i*k]++;
}
int ans=0;
for(int i=1;i<=n;i++){
int x=read();
if(mp[abs(h-x)]>0)ans++;
}
cout<<ans<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(B. Parity Sort\)
显然对奇偶位置分别排序即可，然后按照原来的奇偶顺序塞进去判断即可。
int a[N];
void solve(){
int n=read();
vector<int>o,e;
for(int i=1;i<=n;i++){
a[i]=read();
if(a[i]%2){
o.push_back(a[i]);//ji
}else{
e.push_back(a[i]);//ou;
}
}
sort(o.begin(),o.end());
sort(e.begin(),e.end());
vector<int>las;
int cnto=0,cnte=0;
for(int i=1;i<=n;i++){
if(a[i]%2){
las.push_back(o[cnto]);
cnto++;
}else{
las.push_back(e[cnte]);
cnte++;
}
}
int ans=1;
for(int i=1;i<n;i++){
if(las[i]<las[i-1])ans=0;
}
puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(C. Tiles Comeback\)
可以推断出如果存在这样的一条路径只有两种情况，一种是头尾相同，一种是头尾不同的。
头尾相同的路径，一定可以化简为一个区块的路径。
头尾不同的路径，一定可以化简为两个区块的路径。
所以两个判断即可。
int a[N];
void solve(){
int n=read(),k=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
if(a[1]==a[n]){ //sp jud
int cnt=0;
for(int i=1;i<=n;i++){
if(a[i]==a[1])cnt++;
}
int ans=0;
if(cnt>=k)ans=1;
puts(ans>0?"YES":"NO");
return ;
}
int cnt=0,f1=n+1;
for(int i=1;i<=n;i++){
if(a[i]==a[1])cnt++;
if(cnt==k){
f1=i;
break;
}
}
cnt=0;
int f2=0;
for(int i=n;i>=1;i--){
if(a[i]==a[n])cnt++;
if(cnt==k){
f2=i;
break;
}
}
int ans=0;
if(f1<f2){
ans=1;
}
puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(D. Prefix Permutation Sums\)
这道题还是有点麻烦的。
前缀和数组如果删的是头部或者中间，那么会有两个数字合成一个数字。而且这个数字要么在后面重复要么会大于 \(n\) ,那我只要记录这个异常值，然后遍历 \(1\) 到 \(n\) ，看看少的数字能不能正好补上。
如果删的是尾部，那么会少一个数字。遍历 \(1\) 到 \(n\) 同样可以计算到答案。
int a[N],pre[N];
map<int,int>mp;
void solve(){
int n=read();
mp.clear();
for(int i=1;i<n;i++){
pre[i]=read();
}
int sp=0;
for(int i=1;i<n;i++){
int x=pre[i]-pre[i-1];
if(mp[x]>0){
sp+=x;
}else if(x>n) {
sp+=x;
}else mp[x]++;
}
int ans=1,cnt=0;
for(int i=1;i<=n;i++){
if(mp[i]==1){
continue;
}else{
cnt++;
sp-=i;
if((sp>=0&&cnt==2)||(cnt==1)){
continue;
}else{
ans=0;
break;
}
}
}
if(sp>0)ans=0;
puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(E. Nastya and Potions\)
因为药水不能合成自身，所以整个合成的方案图是一个拓扑图。使用记忆化搜索的复杂度是 \(O(n)\) 的。
int c[N],ans[N],p[N],vis[N];
vector<int>pf[N];
map<int,int>mp;
int dfs(int u){
if(mp[u]>0)return 0;
if(pf[u].size()==0)return c[u];
if(vis[u]==1)return p[u];
int tmp=0;
for(auto x:pf[u]){
tmp+=dfs(x);
}
vis[u]=1;
return p[u]=min(tmp,c[u]);
}
void solve(){
mp.clear();
int n=read(),k=read();
for(int i=1;i<=n;i++){
c[i]=read();
vis[i]=0;
pf[i].clear();
p[i]=0;
}
for(int i=1;i<=k;i++){
mp[read()]++;
}
for(int i=1;i<=n;i++){
int l=read();
for(int j=1;j<=l;j++){
pf[i].push_back(read());
}
}
for(int i=1;i<=n;i++){
cout<<dfs(i)<<" ";
}
cout<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(F. Lisa and the Martians\)
如果 \(a_i\) 和 \(a_j\) 有某位不相同，那么异或同一个数字再与起来一定为 \(0\) 。所以我们要找异或和尽量小的两个数，这个答案一定存在于排序后的相邻两个数字中。
选择好数字后，考虑最后的 \(x\) ，首先我们可以把两个数字影响不到的更高位设为 \(1\) ，然后对于两个数字异或和为 \(1\) 的地方显然无所谓是什么，但是对于异或和为 \(0\) 的地方必须是与原数字不同的数字。那么选择 \(min(a_i,a_j)\) 异或上长度相同，数位全为 \(1\) 的值即可。
struct node{
int val,id;
friend bool operator<(const node&a,const node&b){
return a.val<b.val;
}
}a[N];
void solve(){
int n=read(),k=read();
vector<int>b(n+1);
for(int i=1;i<=n;i++){
b[i]=a[i].val=read();
a[i].id=i;
}
sort(a+1,a+1+n);
int minn=INF,ansi=-1,ansj=-1;
for(int i=2;i<=n;i++){
if((a[i-1].val^a[i].val)<minn){
minn=a[i-1].val^a[i].val;
ansi=a[i-1].id;
ansj=a[i].id;
}
}
cout<<ansi<<" "<<ansj<<" "<<(1<<k)-1-((1<<((int)log2(min(b[ansi],b[ansj]))+1))-1)+(min(b[ansi],b[ansj])^((1<<((int)log2(min(b[ansi],b[ansj]))+1))-1))<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(G. Vlad and the Mountains\)
首先可以发现 \(i->j->k\) 的时候的花费为 \((h_i-h_j)-(h_j-h_k)=h_i-h_k\) ，显然中转地是不影响结果的，那么我们只是维护出当前的 \(h_i+e\) 能到达的点有哪些，更进一步有哪些点的点权小于 \(h_i+e\) 。
显然可以使用最小生成树的思想离线完成，使用并查集维护无向图的连通情况。
struct node{
int u,v,w,op,id,ans;
friend bool operator<(const node&a,const node&b){
if(a.w==b.w)return a.op<b.op;
return a.w<b.w;
}
}event[N];
int p[N]; //存储每个点的祖宗节点
int find(int x) { // 返回x的祖宗节点
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
bool cmp(node a,node b){
return a.id<b.id;
}
void solve(){
int n=read(),m=read();
vector<int>h(n+1);
for(int i=1;i<=n;i++){
h[i]=read();
p[i]=i;
}
for(int i=1;i<=m;i++){
int x=read(),y=read();
event[i]=(node){x,y,max(h[x],h[y]),0,inf,-1};
}
int q=read();
for(int i=1;i<=q;i++){
int x=read(),y=read(),w=read();
event[i+m]=(node){x,y,w+h[x],1,i,-1};
}
sort(event+1,event+1+m+q);
for(int i=1;i<=m+q;i++){
if(event[i].op==1){
event[i].ans=(find(event[i].u)==find(event[i].v));
}else{
p[find(event[i].u)] = find(event[i].v); // 合并a和b所在的两个集合：
}
}
sort(event+1,event+1+m+q,cmp);
for(int i=1;i<=q;i++){
puts(event[i].ans>0?"YES":"NO");
}
cout<<'\n';
//puts(ans>0?"Yes":"No");
}