目录
A. Medium Number
中位数,排序之后处于中间位置的数
void solve()
{
n=3;
vector<int> a(n);
for(auto&v:a) cin>>v;
sort(a.begin(),a.end());
cout<<a[1]<<endl;
return ;
}B. Atilla’s Favorite Problem
依照题目意思只需要求一下最大的字母排序即可
int res=0;
string a; cin>>n>>a;
for(int i=0;i<a.size();i++)
res=max(res,a[i]-'a'+1);
cout<<res<<endl;C. Advantage
依照题目的意思我们只需要存两个值即可
对于最厉害的除了他之外就是次厉害的而其他的都是最厉害的
while(t--){
cin>>n;
for(int i=1;i<=n;i++) {
cin>>a[i];
b[i]=a[i];
}
sort(b+1,b+1+n);
for(int i=1;i<=n;i++){
if(a[i]!=b[n]) cout<<a[i]-b[n]<<" ";
else cout<<a[i]-b[n-1]<<" ";
}
cout<<endl;
}D. Challenging Valleys
理清题目意思就是题目中不能出现先升之后下降的
那就是先下降再上升我们可以使用双指针来移动
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int ans=0,f=0;
int j=1;
while(j<=n-1&&a[j]>=a[j+1]) j++;
while(j<=n-1&&a[j]<=a[j+1]) j++;
cout<<(j<n ? "NO" : "YES")<<endl;
return ;
}E. Binary Inversions
我们改变一个带来的贡献是改变之后增加的-改变之后减少的
首先我们要算出来逆序对原来为01穿我们只需要维护一个前缀1
的数量就好,然后算出后缀的1来计算贡献即可
int a[N],b[N],c[N];
void solve()
{
cin>>n;
LL ans=0,cnt=0;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
if(a[i]) cnt++;
if(!a[i]) ans+=cnt;
}
//b 记录1
int ans1=0;
for(int i=1;i<=n;i++){
b[i]=ans1;
if(a[i]) ans1++;
}
int ans0=0;
for(int i=n;i>=1;i--){
c[i]=ans0;
if(!a[i]) ans0++;
}
LL res=ans;
for(int i=1;i<=n;i++)
{
if(a[i]) res=max(res,ans+b[i]-c[i]);
else res=max(res,ans-b[i]+c[i]);
}
cout<<res<<endl;
return ;F. Quests
依照题目意思我们发现是具有二分性质的,如果我当前天数可以那少一点也肯定可以注意特盘掉不可以的就是即使k=0全部用最大的依旧不可以,接着就是一个二分了,我们注意两个情况
如果k<n那么我们就只会用前k个然后来判断多的和n的关系考虑这种多次循环我们需要使用前缀和是来快速维护求和
int a[N],b[N],c[N];
void solve()
{
cin>>n;
LL ans=0,cnt=0;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
if(a[i]) cnt++;
if(!a[i]) ans+=cnt;
}
//b 记录1
int ans1=0;
for(int i=1;i<=n;i++){
b[i]=ans1;
if(a[i]) ans1++;
}
int ans0=0;
for(int i=n;i>=1;i--){
c[i]=ans0;
if(!a[i]) ans0++;
}
LL res=ans;
for(int i=1;i<=n;i++)
{
if(a[i]) res=max(res,ans+b[i]-c[i]);
else res=max(res,ans-b[i]+c[i]);
}
cout<<res<<endl;
return ;G. SlavicG’s Favorite Problem
注意理清题目意思我们只能跳一回那么也就是说我只要从我这个位置出发之后看能到达的所有位置有多少可能,然后直接跳到某一个位置朝着b走就可以了，为了实现这个过程我们可以
先从起点跑一次不抵达终点即可看看所有的可能,然后从终点反向跑一次看有没有出现一样只要是有一样就是有答案
int h[N],ne[N],w[N],e[N],idx;
bool flag;
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int fa,int x)
{
mp[x]=1;
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==fa) continue;
if(j==ed) continue;
dfs(j,u,w[i]^x);
}
}
void dfs1(int u,int fa,int x)
{
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==fa) continue;
dfs1(j,u,w[i]^x);
if(flag) return ;
if(mp[w[i]^x]){
flag=true;
cout<<"YES"<<endl;
}
}
}
void solve()
{
memset(h,-1,sizeof h);
mp.clear();
idx=0;
cin>>n>>st>>ed;
for(int i=1;i<n;i++){
int a,b,c; cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
flag=false;
dfs(st,0,0);
dfs1(ed,0,0);
if(!flag) cout<<"NO"<<endl;
