Codeforces Round 888 (Div. 3)补题

Escalator Conversations（Problem - A - Codeforces）

题目大意：有一个自动扶梯，共有m级台阶，每级台阶高为k，上面有n个人，我们规定如果两人站在不同的台阶上，高度恰好相同时可以进行交谈，小f身高为h，它想知道它可以和多少人进行交谈。

思路：这题没什么难度，就是小f与其他人的高度差要恰好是k的倍数，同时有两个限定条件，两人不能站在同一级台阶上，则不能与高度相同的人进行交谈，另外台阶总共m级，到第m级时就到终点了，所以倍数需要小于m。

#include<bits/stdc++.h>
using namespace std;
int main()
{int t;scanf("%d",&t);while(t--){int n,m,k,h,c=0;scanf("%d%d%d%d",&n,&m,&k,&h);for(int i=1;i<=n;i++){int x;scanf("%d",&x);int d=abs(h-x);if(d&&d%k==0&&d/k<m) c++;}printf("%d\n",c);}
}

Parity Sort（Problem - B - Codeforces）

题目大意：给定一个数组a[],我们每次可以选择两个元素进行交换，需要满足两个元素的奇偶性相同，问最后能否得到一个非降序数组。

思路：这道题显然就是奇数和偶数内部进行排序，我们可以先将奇数元素分别进行排序，然后按照原数组中每个数的奇偶性往里面填，最后看看我们填好的数组是否有序即可。

#include<bits/stdc++.h>
using namespace std;
int a[200010],b[200010];
vector<int>j,o;
int main()
{int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);if(a[i]&1) j.push_back(a[i]);else o.push_back(a[i]);}sort(j.begin(),j.end());reverse(j.begin(),j.end());sort(o.begin(),o.end());reverse(o.begin(),o.end());for(int i=1;i<=n;i++){if(a[i]&1) b[i]=j.back(),j.pop_back();else b[i]=o.back(),o.pop_back();}int c=0,flag=0;for(int i=1;i<=n;i++){if(c>b[i]) {flag=1;break;}c=b[i];}if(flag) printf("NO\n");else printf("YES\n");}
}

Tiles Comeback（Problem - C - Codeforces）

题目大意：有一排瓷砖，总共n块，第i块有一个颜色ci，当前处在第1块，最后要到第n块，每次可以随意跳，产生一个路径，长度为p，p可以整除k，并且满足将p按照k块一个区域进行划分的话，可以划分出若干个区域，区域内部颜色相同，相邻区域之间颜色不一定不同，问是否存在这样的路径p。

思路：这道题看似麻烦，但是很简单，一定要把题目看清楚，相邻区域同与不同皆可。总共只有两种大的情况，开头和结尾相同，开头和结尾不同。如果开头和结尾相同，那么只要在数组中找到k个与开头相同的元素即可，结尾字符可以与找到的最后一个进行替换；如果开头和结尾不同，那么就从开头找k个，从结尾找k个，两者找到的区间不相交即可。一定要把题目看清楚。

#include<bits/stdc++.h>
using namespace std;
int c[200010];
int main()
{int t;scanf("%d",&t);while(t--){int n,k;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++) scanf("%d",&c[i]);if(c[1]==c[n]){int i,cnt=0;for(i=1;i<=n;i++){if(c[i]==c[1]) cnt++;if(cnt==k) break;}if(cnt==k) printf("YES\n");else printf("NO\n");	}else{int i=1,j=n,cnt=0;for(i=1;i<=n;i++){if(c[i]==c[1]) cnt++;if(cnt==k) break;}cnt=0;for(j=n;j>=1;j--){if(c[j]==c[n]) cnt++;if(cnt==k) break;}if(i<j) printf("YES\n");else printf("NO\n");}}
}

Prefix Permutation Sums（Problem - D - Codeforces）

题目大意：对于一个排列，我们求出其前缀和，但现在前缀和少了一位数，现在给出一个少了一位的前缀和数组，问它是否对应一个排列。

思路：少了一位前缀和，这个前缀和的位置有两种可能，一种是最后一个丢了，那么我们还原出来的只差一个数，可以直接判是，如果是前面的丢了，那么我们还原的时候，还原出来的某一位数应该是排列中的两个数相加，和可能大于n，也可能小于n，如果小于n，那么一定有一个数出现两次。所以可以用map将所有的出现的数及它的出现次数统计出来，然后遍历map，将小于等于n的数标记一下，同时在map中减掉一次，然后遍历n，找一找有几个数没被标记，同时计算出没被标记的数的和，如果是一个，那么直接输出yes，如果是两个，那么就看两个数的和是否在map中，如果大于两个，直接判否。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int st[200010];
signed main()
{int t;scanf("%lld",&t);while(t--){int n;scanf("%lld",&n);int c;map<int,int>mp;for(int i=0;i<n-1;i++){int x;scanf("%lld",&x);if(!i) mp[x]++;else mp[x-c]++;c=x;st[i]=0;}st[n-1]=st[n]=0;for(auto it:mp){if(it.first<=n) st[it.first]=1,mp[it.first]--;//可能会有两个数的和小于n的，那么某个数就会被标记两次}int tmp=0;c=0;for(int i=1;i<=n;i++){if(!st[i]) {tmp += i;c++;}}if(c>2) printf("NO\n");else if(c==2) {if(mp[tmp]) printf("YES\n");else printf("NO\n");}else printf("YES\n");}
}

Nastya and Potions（Problem - E - Codeforces）

题目大意：现在已知n种药水单瓶的价格，同时其中的k中药水我们已经有无限多，其中一种药水可以由多种药水混合得到，问获得每瓶药水需要多少金币。

思路：因为一瓶药水可以由一些药水获得，而这些药水又可以由另一些药水混合，所以我们可以直接对每种药水进行深搜，为了优化我们可以加个记忆化搜索，另外我们已知的是单价，所以一次只能买一瓶，不用考虑药水可以重复利用的问题。至于图如何建，我们只要在每瓶药水和可以获得它的药水之间建一条有向边即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[200010];
int st[200010];
int h[200010],e[200010],ne[200010],idx;
void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfs(int u)
{if(st[u]) return dp[u];st[u]=1;int sum=0,c=0;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];sum += dfs(j);c++;}if(c) dp[u]=min(dp[u],sum);return dp[u];
}
signed main()
{int t;scanf("%lld",&t);while(t--){int n,k;scanf("%lld%lld",&n,&k);for(int i=1;i<=n;i++) scanf("%lld",&dp[i]),st[i]=0,h[i]=-1;for(int i=1;i<=k;i++){int x;scanf("%d",&x);dp[x]=0;}idx=0;for(int i=1;i<=n;i++){int m;scanf("%lld",&m);for(int j=1;j<=m;j++){int x;scanf("%lld",&x);add(i,x);}}for(int i=1;i<=n;i++){int res=dfs(i);printf("%lld ",res);}printf("\n");}
}

Lisa and the Martians（Problem - F - Codeforces）

题目大意：定义严格小于2^k的数为火星数字，现有n个火星数字组成的数组a[]，要求从中选两个数字，并且随便找一个火星数组x,使得(a[i]^x)&(a[j]^x)最大，输出i,j,x。

思路：这里既然涉及到位运算，那么就从二进制的角度考虑，最后一步运算求得是&,所以就要使两者异或x后对应的位数中有尽可能多的相同的1，再往前推一步，那么就是要求a[i]和a[j]中要有尽可能多的位数相同。那么问题就转化成从数组中找到两个数，不对，我们要找的这个数尽可能的大，那么就是高位尽可能能的放1，那么就是两个数高位尽可能的相同。有一个贪心的思路，就是说按照非降序排列后，选出来的数应该相邻，相邻两个数比不相邻的数高位相同的概率大一点，但是这个很难证明，不过可以写。那么就可以在线性的时间复杂度内解决。

#include<bits/stdc++.h>
using namespace std;
int main()
{int t;scanf("%d",&t);while(t--){int n,k;scanf("%d%d",&n,&k);vector<pair<int,int>>c;for(int i=1;i<=n;i++) {int x;scanf("%d",&x);c.push_back({x,i});}sort(c.begin(),c.end());int mx=-1,d=0,l,r;//mx需要为一个小于0的数，因为结果可能为0for(int i=0;i<n-1;i++){int a=c[i].first,b=c[i+1].first;int sum=0,x=0;for(int j=k-1;j>=0;j--){if( (a>>j&1)==(b>>j&1) ){sum += 1<<j;if(!(a>>j&1)) x += 1<<j; }}if(sum>mx){mx=sum,d=x,l=c[i].second,r=c[i+1].second;}}printf("%d %d %d\n",l,r,d);}
}

 但是，这个题主要想考察的是用trie树求最大同或值。因为只有两数二进制的同一位上的数值相同，才能在结果中变成1，同1同0都是相同，所以，就是求最大同或值。这里会有相同的数出现，所以我们先查询再插入，为了保证查询结果，trie树最初需要全部初始化成0.

#include<bits/stdc++.h>
using namespace std;
const int M=200010*32;
struct node
{int pos;int son[2];
}tree[M];
int ans,ansx,pos1,pos2;
void query(int u,int num,int bit,int cnt,int cntx,int pos)
{if(bit==-1){if(cnt>ans){ans=cnt;ansx=cntx;pos1=pos;pos2=tree[u].pos;}return;}int s=(num>>bit)&1;if(tree[u].son[s]){cnt += (1<<bit);if(!s) cntx += (1<<bit);query(tree[u].son[s],num,bit-1,cnt,cntx,pos);}else query(tree[u].son[!s],num,bit-1,cnt,cntx,pos);
}
int now=0;
void insert(int u,int num,int bit,int pos)
{if(bit==-1){tree[u].pos=pos;return;}int s=(num>>bit)&1;if(!tree[u].son[s]) tree[u].son[s]=++now;insert(tree[u].son[s],num,bit-1,pos);
}
int main()
{int t;scanf("%d",&t);while(t--){int n,k;scanf("%d%d",&n,&k);for(int i=0;i<=n*k;i++) {tree[i].pos=tree[i].son[0]=tree[i].son[1]=0;}now=0;ans=0;ansx=0;pos1=1,pos2=2;for(int i=1;i<=n;i++){int x;scanf("%d",&x);query(0,x,k-1,0,0,i);insert(0,x,k-1,i);}printf("%d %d %d\n",pos1,pos2,ansx);}
}

这里初始情况要记得考虑，也就是将pos1赋成1，pos2赋成0，最小为0，可能结果就是0，那么就无法更新，所以要人为指定。tree[i].son[0]和tree[i].son[1]当中存的相当于指针，这个可以类比邻接表来看。