codeforces CF835

CF835

A. Medium Number

AC代码

排完序，取第二个即可

#include <bits/stdc++.h>
#define ll long long
#define endl "\\n"
using namespace std;

ll t;
ll a[3];

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);

cin>>t;
while(t—)
{
cin>>a[0]>>a[1]>>a[2];
sort(a,a+3);

cout<<a[1]<<endl;
}
return 0;
}

B. Atilla’s Favorite Problem

AC代码

边输入边记录最大字母，最大字母-‘a’+1 即为需要认识的最少字母数量

#include <bits/stdc++.h>
#define ll long long
#define endl "\\n"
using namespace std;

ll t;
ll n;
ll s[105];

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);

cin>>t;
while(t—)
{
cin>>n;
ll maxs=0;
for(ll i=1;i<=n;i++)
{
char c;
cin>>c;
maxs=max(maxs,(c–(ll)'a'));
}

cout<<maxs+1<<endl;
}
return 0;
}

C.Advantage

AC代码

对比每位选手和除自己外的最强者之间的差距，其实就是需要找出最强者和次强者，然后将最强者和次强者比较，其他人和最强者比较。

#include <bits/stdc++.h>
#define ll long long
#define endl "\\n"
using namespace std;

ll t;
ll n;
ll s[200005];

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);

cin>>t;
while(t—)
{
cin>>n;
ll max1=0,max2=0;
for(ll i=1;i<=n;i++)
{
cin>>s[i];

max2=max(max2,s[i]);
if(max2>max1)swap(max1,max2);
}

for(ll i=1;i<=n;i++)
{
if(s[i]!=max1)cout<<(s[i]–max1)<<" ";
else cout<<(s[i]–max2)<<" ";
}
cout<<endl;
}
return 0;
}

D.Challenging Valleys

AC代码

题目要求在一个数组中，存在一个谷即输出YES，没有或更多都为NO。

这里使用 current 指向当下所在的数组元素，prev 指向current的前一个元素，next 指向与 a[current] 不相等的右边最近元素，如果 a[current] 的右边邻近元素跟它相等，则通过 pos 进行后移，找到不相同的元素后赋值给 a[next] 。由题意，当数组保持递增趋势或递减趋势，依然算一个谷，所以需要将两端设置成极大值。

#include <bits/stdc++.h>
#define ll long long
#define endl "\\n"
using namespace std;

ll t;
ll n;
ll a[200005];

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);

cin>>t;
while(t—)
{
cin>>n;

for(ll i=1;i<=n;i++)
{
cin>>a[i];
}
a[0]=a[n+1]=LONG_LONG_MAX;

ll pos=2;
ll prev=a[0],current=a[1],next;
ll cnt=0;
while(pos<=n+1)
{
next=a[pos];
if(current==next)
{
pos++;
continue;
}
if(prev>current&&current<next)cnt++;

prev=current,current=next,pos++;
}

if(cnt==1)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}

*E.Binary Inversions

AC代码

方法一（贪心）

翻译一下题意，就是需要找出翻转哪个元素后，可以得到逆序对的最大数量。求逆序对数量通常可以使用归并排序或树状数组解决。 假设翻转一个元素 1 ，该元素现在是 0 ，总的逆序对数需要减去原来这个元素 1 和其左边 0 产生的逆序对数，再加上现在这个元素 0 和其右边 1 产生的逆序对数。

贪心一下，想要得到逆序对的最大数量，如果选择将元素 0 翻转成元素 1 ，此时这个元素 0 一定是整个数组中第一个 0 ，只有第一个 0 的位置可以使其右边得到最多的 0 ，使其左边得到最少的 1 ；反之，如果选择将元素 1 翻转成元素 0，此时这个元素 1 一定是整个数组中最后一个 1 。 有了思路这里就用 pos0 记录第一个 0 的位置，pos1 记录最后一个 1 的位置，gain0 表示翻转 0 的贡献，gain1 表示翻转 1 的贡献，求出两者的大小关系即确定了翻转的对象，在正式翻转元素后，这里我套用归并排序求逆序对数量的模版思路复杂了。01逆序的求解比较特殊，直接遍历就好，但是方法是好的，如果这里看懂了该模版，不妨去试试CF790的H2😁

#include <bits/stdc++.h>
#define ll long long
#define endl "\\n"
using namespace std;

ll t;
ll n;
ll a[200005];
ll b[200005];
ll ans;

void merge(ll l,ll r)
{
if(l>=r)return;

ll mid=l+(r–l>>1);
ll p1=l,p2=mid+1;
merge(l,mid),merge(mid+1,r);

ll pos=l;
while(p1<=mid && p2<=r)
{
if(a[p1]<=a[p2])b[pos++]=a[p1++]; //这里的关系判断要比CF790的H2多个等号
else
{
b[pos++]=a[p2++];
ans+=mid–p1+1;
}
}
while(p1<=mid)b[pos++]=a[p1++];
while(p2<=r)b[pos++]=a[p2++];
for(ll i=l;i<=r;i++)
{
a[i]=b[i];
}
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);

cin>>t;
while(t—)
{
cin>>n;

ll pos0=–1; //第一个0的索引 //这个地方的查找注意一下
ll pos1=–1; //最后一个1的索引
for(ll i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]==0)
{
if(pos0==–1)pos0=i;
}
else pos1=i;
}

ll gain0=–1,gain1=–1; //翻转0或1的收益
if(pos0 != –1)
{
ll left1 = 0, right0 = 0;
for(int i = 1; i < pos0; i++) if(a[i] == 1) left1++;
for(int i = pos0 + 1; i <= n; i++) if(a[i] == 0) right0++;
gain0 = right0 – left1; // 收益 = 增加的对数 – 减少的对数
}

if(pos1 != –1)
{
ll left1 = 0, right0 = 0;
for(int i = 1; i < pos1; i++) if(a[i] == 1) left1++;
for(int i = pos1 + 1; i <= n; i++) if(a[i] == 0) right0++;
gain1 = left1 – right0; // 收益 = 增加的对数 – 减少的对数
}

if(gain0>0 || gain1>0) //收益需要大于0，否则不翻转
{
if(gain0>gain1)a[pos0]=1;
else a[pos1]=0;
}

ans=0;
merge(1,n);

cout<<ans<<endl;
}
return 0;
}

方法二(动态贡献法)

这里介绍一位大佬的方法，时间复杂度也从法一的O(nlogn)优化成O(n)，欢迎大家来到他的题解区云遥栈¹

根本思路是将数组最初的逆序对的数量算出，再把每个点都挨个尝试翻转一下，求出贡献最大的那个点，然后相加即可

for(ll i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]==0)
{
num+=cnt1;
cnt0++;
}
else cnt1++;
}

在此循环中，cnt0 和 cnt1 暂时用来计数，这里一个循环代替了方法一的归并排序求逆序对的数量

cnt1=0;
for(ll i=1;i<=n;i++)
{
if(a[i]==0) //将0翻转成1
{
cnt0—;
maxs=max(maxs,cnt0–cnt1);
}
else //将1翻转成0
{
maxs=max(maxs,cnt1–cnt0);
cnt1++;
}
}

cnt1 代表当前位置左边 1 的个数，这里先赋值为 0 ，因为第一个元素左边没有数字。第一次循环 cnt0 依然储存着全数组 0 的个数，所以如果当前元素为 0 ，那么该元素右边 0 的个数为 cnt0-1 ，此时 cnt0 代表当前元素从 0 翻转成 1 得到的逆序对的数量，cnt1 代表着未翻转前的数量，因此 cnt0-cnt1 代表该元素翻转的贡献。如果当前元素为 1 ，记得在取完最值后，加上该元素 1 ，为下一个元素需要左边 1 的个数时做准备。

最终代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll t;
ll n;
ll a[200005];
ll cnt0; //当前位置右边0的个数
ll cnt1; //当前位置左边1的个数
ll num=0; //初始数组逆序对数
ll maxs=0; //翻转一个元素后得到的最大贡献

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);

cin>>t;
while(t—)
{
cin>>n;
cnt0=0,cnt1=0,num=0,maxs=0;
for(ll i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]==0)
{
num+=cnt1;
cnt0++;
}
else cnt1++;
}
cnt1=0;
for(ll i=1;i<=n;i++)
{
if(a[i]==0) //将0翻转成1
{
cnt0—;
maxs=max(maxs,cnt0–cnt1);
}
else //将1翻转成0
{
maxs=max(maxs,cnt1–cnt0);
cnt1++;
}
}

cout<<num+maxs<<endl;
}
return 0;
}

*F.Quests

AC代码(二分+贪心)

此题的输出有 “Impossible”、“Infinity” 和具体 k 值三种结果，因此我就先分类讨论，处理相对好想的不可能有 k 值和 k 值无穷大这两个结果。事先已将数组 a 从大到小排过序，数组 m 为数组 a 的前缀和。

1. 不可能有 k 值

如果连续完成 d 天最高报酬的任务都无法达到目标 c ，即 k 不存在。

2. k为无穷大

• 如果任务数量小于目标天数，k 想取无穷大，那么所有任务结束必须至少达到目标金币数。
• 如果任务数量大于目标天数，k 想取无穷大，那么在目标天数下，需要保证完成目标天数的任务，并获得大于等于目标金币数量。

3. 具体 k 值

这里想到二分来处理本题，由于在此情况下，k 一定有具体值，然而在面对大于目标天数的 k 时处理方式相同，题目要求取 k 的最大值，而在此情况下，k 又不可能为无穷大，因此这里将二分的右端点设置成 d 。需要注意的是，**冷却 k 天意味着循环天数为 k+1 。**由于数组下标最大可取 n ，这里用 min进行处理。接下来只需要贪心处理即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll t;
ll n; //任务数
ll c; //所需硬币数
ll d; //天数
ll a[200005];
ll m[200005]; //前缀和

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);

cin>>t;
while(t—)
{
cin>>n>>c>>d;
for(ll i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+n+1,greater<>());
for(ll i=1;i<=n;i++)
{
m[i]=m[i–1]+a[i];
}

if(a[1]*d<c) //不可能
{
cout<<"Impossible"<<endl;
continue;
}

if(m[min(n,d)]>=c) //无穷大
{
cout<<"Infinity"<<endl;
continue;
}

ll l=0,r=d+1,mid;
ll current;
while(l+1!=r)
{
mid=l+(r–l>>1);
ll cycle=mid+1; //k天冷却意味着循环为k+1

current=d/cycle*m[min(cycle,n)]+m[min(d%cycle,n)];
if(current>=c)l=mid;
else r=mid;
}

cout<<l<<endl;
}
return 0;
}

G.SlavicG’s Favorite Problem

AC代码(DFS)

本题的关键在于理解传送机制与异或运算的性质。根据异或的自反性（

x

⊕

y

⊕

y

=

x

x \\oplus y \\oplus y = x

x⊕y⊕y=x），如果我们要从

a

a

a 经过一次传送到达

b

b

b 且路径异或和为

0

0

0，等价于： 从

a

a

a 走出的路径异或和

D

x

D_x

Dx​，必须等于从

b

b

b 逆推回去的路径异或和

C

x

C_x

Cx​。即满足：

D

x

⊕

C

x

=

0
  

⟹
  

D

x

=

C

x

D_x \\oplus C_x = 0 \\implies D_x = C_x

Dx​⊕Cx​=0⟹Dx​=Cx​。 由此，我们可以将问题转化为一个中途相遇问题：寻找是否存在一个中间点（传送的目的地），使得正向搜索与逆向搜索的异或值相等。

思路就是先从b点出发，找到所有可能到达的点的 x 值存入 set ，再从点 a 出发，找到所有可能的 x 值与 set 存储的值比对。

这里比较需要思考的点是如何处理递归的返回，这里引入参数 p ，代表走到点 u 的上一个顶点，因为异或的自反性（

x

⊕

y

⊕

y

=

x

x \\oplus y \\oplus y = x

x⊕y⊕y=x）， 所以在深度搜索时搜到父节点返回毫无意义，这里在深搜前做了个判断。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll t;
ll n; //顶点数
ll a; //起点
ll b; //终点
vector<vector<pair<ll,ll>>> m; //first：邻近点，second：权值
set<ll> s; //记录b的邻近权值
ll ans=0;

void dfsa(ll u,ll x,ll p) //顶点u，x值，点u的父节点
{
if(u==b)return;
if(s.count(x))
{
ans=1;
return;
}

for(auto& y:m[u])
{
if(ans)return;
if(y.first!=p)dfsa(y.first,x^y.second,u); //防止重复
}
}
void dfsb(ll u,ll x,ll p)
{
if(u!=b)s.insert(x);

for(auto& y:m[u])
{
if(y.first!=p)
{
dfsb(y.first,x^y.second,u);
}
}
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);

cin>>t;
while(t—)
{
cin>>n>>a>>b;
ans=0;
m.clear();
m.resize(n+1);
s.clear();
for(ll i=1;i<=n–1;i++)
{
ll u,v,w;
cin>>u>>v>>w;
m[u].push_back({v,w});
m[v].push_back({u,w});
}

dfsb(b,0,–1);
dfsa(a,0,–1);

cout<<(ans==1?"YES":"NO")<<endl;
}
return 0;
}