A. Escalator Conversations
题意：有一个扶梯，有n个人要站扶梯，这个扶梯有m个位置，第i个位置的高度为i*k，Vlad高H，第i个人高h[i]，当且仅当两个人所处的位置高度加上自身身高刚好相同时才能谈话，问能和Vlad谈话的有多少人。
Solution
直接计算即可
void solve()
{
int n,m,k,H;cin>>n>>m>>k>>H;
int ans=0;
for(int i=1;i<=n;i++)
{
int x;cin>>x;
int dif=abs(x-H);
if(dif%k!=0||(dif/k>m-1)||(dif/k==0))
{
continue;
}
ans++;
}
cout<<ans<<"\n";
}
B. Parity Sort
题意：给出一个序列，可以进行任意次交换两个奇偶性相同的数，问最后能否排成有序序列
Solution
直接把奇数偶数取出来从小大的排一遍即可
void solve()
{
int n;cin>>n;
multiset<int>st1,st2;
for(int i=1;i<=n;i++)
{
int x;cin>>x;
if(x&1)
{
st1.insert(x);
a[i]=1;
}
else
{
st2.insert(x);
a[i]=0;
}
}
for(int i=1;i<=n;i++)
{
if(a[i]==1)
{
b[i]=*(st1.begin());
st1.erase(st1.begin());
}else
{
b[i]=*(st2.begin());
st2.erase(st2.begin());
}
}
for(int i=1;i<n;i++)
{
if(b[i+1]<b[i])
{
cout<<"NO\n";
return;
}
}
cout<<"YES\n";
}
C. Tiles Comeback
题意：给一条有n块的路，从第一块出发，每次可以跳过任意块，问能否有一条路径，使得它的长度能被k整除，且分成length/k块后，每块内部的颜色相同。
Solution
看1和n的颜色是否相同，如果相同，则再找k-2块，如果不同，则分别从1和n开始往中间找，直到找到并且l<r
void solve()
{
int n,k;cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
if(n==1)
{
cout<<(k==1?"YES\n":"NO\n");
return;
}
if(a[1]==a[n])
{
int res=2;
for(int i=2;i<=n-1;i++)
{
if(res%k==0)break;
if(a[i]==a[1])res++;
}
cout<<(res%k==0?"YES\n":"NO\n");
}else
{
int res1=1,res2=1;
if(res1%k==0&&res2%k==0)
{
cout<<"YES\n";
return;
}
int l=2,r=n-1;
while(l<n)
{
if(res1%k==0)break;
if(a[l]==a[1])res1++;
if(res1%k==0)break;
l++;
}
while(r>1)
{
if(res2%k==0)break;
if(a[r]==a[n])res2++;
if(res2%k==0)break;
r--;
}
//cout<<l<<" "<<r<<"\n";
if(l<r&&res1%k==0&&res2%k==0)
{
cout<<"YES\n";
}else cout<<"NO\n";
}
}
D. Prefix Permutation Sums
题意：给出一个前缀和数组，它是由[1,2...,n]的某个排列组成的，但是这个前缀和数组缺少了某一个数，问它是否能还原成某个排列
Solution
考虑到只缺少了一个数，所以我们可以对前缀和数组做个差分，相邻的数之间的差可能会出现以下三种情况
1.出现若干1到n之间的数，每个数只出现一遍
2.出现若干1到n之间的数，并且出现一个数大于n
3.出现若干1到n之间的数，有一个数会出现两次
我们可以通过记录差分的和与还有哪些数未出现，最后将它们作比较来判断
void solve()
{
int n;cin>>n;
int sum=0;
set<int>st;
for(int i=1;i<n;i++)
{
cin>>a[i];
b[i]=a[i]-a[i-1];
sum+=i;
st.insert(i);
}
st.insert(n);
sum+=n;
sort(b+1,b+n);
vector<int>v;
for(int i=1;i<n;i++)
{
if(b[i]<=n)
{
if(st.count(b[i]))
{
st.erase(b[i]);
sum-=b[i];
}else
{
v.push_back(b[i]);
}
}else
{
v.push_back(b[i]);
}
}
if(v.size()==1)
{
cout<<(sum==v[0]?"YES\n":"NO\n");
}else if(v.size()==0)
{
cout<<(sum==(*(st.begin()))?"YES\n":"NO\n");
}
else
{
cout<<"NO\n";
return;
}
}
E. Nastya and Potions
题意：有n种药水，每个的购价是a[i]，并且每种药水可以由若干其他药水合成，现在有k个药水是无限供应的（不要钱），问获得每个药水的最低价格是多少
Solution
考虑到不会出现两个相互循环的情况，我们可以通过记忆化搜索来处理答案，如果已经处理出答案或者它已经为0了则可以直接返回
int dfs(int x)
{
if(dp[x]!=-1)return dp[x];
int res=a[x];
int sum=0;
if(e[x].size()!=0)
{
for(auto it:e[x])
{
sum+=dfs(it);
}
return dp[x]=min(res,sum);
}else
{
return dp[x]=res;
}
}
void solve()
{
int n,k;cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
e[i].clear();
dp[i]=-1;
}
for(int i=1;i<=k;i++)
{
int x;
cin>>x;
a[x]=0;
}
for(int i=1;i<=n;i++)
{
int x;cin>>x;
for(int j=1;j<=x;j++)
{
int y;cin>>y;
e[i].push_back(y);
}
}
//cout<<dfs(1)<<"\n";
for(int i=1;i<=n;i++)
{
cout<<dfs(i)<<" \n"[i==n];
}
}
F. Lisa and the Martians
题意：给出一个数组，数组的数都小于等于2k，现在选择两个数和一个x(x<2k)，定义他们的结果为
问最大结果是多少
Solution
模拟一遍可以发现，如果a[i]和a[j]在某一位上是0和1，那么结果的这一位必定是0，反之一定是1，所以我们可以发现只要a[i]与a[j]的异或值最小即可，有一个结论
一个数组内的两个数的最小的异或值为排序后的最小的相邻数的异或值。
struct node
{
int x,y;
}e[N];
bool cmp(node a,node b)
{
return a.x<b.x;
}
void solve()
{
int n,k;cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
e[i].x=a[i];
e[i].y=i;
}
sort(e+1,e+1+n,cmp);
int res=1e18;
int pos=-1;
for(int i=1;i<n;i++)
{
int u=e[i+1].x^e[i].x;
if(u<res)
{
pos=i;
res=u;
//cout<<e[i].y<<" "<<e[i+1].y<<" "<<u<<"\n";
}
}
int ans=0;
for(int i=0;i<k;i++)
{
if((!((e[pos].x>>i)&1))&&(!((res>>i)&1)))ans+=(1LL<<i);
}
cout<<e[pos].y<<" "<<e[pos+1].y<<" "<<ans<<"\n";
}