codeforces CF835

wljy1

674人浏览 · 2026-02-12 13:15:05

wljy1 · 2026-02-12 13:15:05 发布

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)，欢迎大家来到他的题解区云遥栈¹

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

初始化

记得在每次循环前将变量归零
- cnt0：代表当前位置右边 0 的个数
- cnt1：代表当前位置左边 1 的个数
- num：初始数组逆序对的数量
- maxs：翻转一个元素后得到的最大贡献
输出并记录初始数组逆序对的数量和数组中 0 的个数(暂由cnt0代表)

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)

本题的关键在于理解传送机制与异或运算的性质。根据异或的自反性（ $\oplus y \oplus y = x$ ），如果我们要从 $a$ 经过一次传送到达 $b$ 且路径异或和为 $0$ ，等价于：从 $a$ 走出的路径异或和 $D_x$ ，必须等于从 $b$ 逆推回去的路径异或和 $C_x$ 。即满足： $D_x \oplus C_x = 0 \implies D_x = C_x$ 。
由此，我们可以将问题转化为一个中途相遇问题：寻找是否存在一个中间点（传送的目的地），使得正向搜索与逆向搜索的异或值相等。

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

这里比较需要思考的点是如何处理递归的返回，这里引入参数 p ，代表走到点 u 的上一个顶点，因为异或的自反性（ $\oplus y \oplus 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;
}

欢迎来到云遥栈 ↩︎

2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

第二十二课：领域建模实战——订单系统最小闭环（实战篇）

本文通过一个最小订单系统案例，演示如何将领域建模从概念落地到代码结构。系统仅实现创建、支付和取消订单三个核心功能，聚焦规则归属而非技术复杂度。采用分层设计：Domain层封装订单实体、金额值对象和状态规则；Repository处理持久化；Biz层负责流程编排；Controller仅处理输入输出。案例展示了领域建模的关键原则：业务规则内聚在Domain层，流程控制由Biz层处理，数据访问归Repos

2048 AI社区

手把手教你设置和使用 Claude Code Agent Teams：高效协作开发实战指南

2048 AI社区

【AI测试全栈：质量】46、构建坚不可摧的AI系统：全链路故障注入测试实战指南

AI系统容错测试实战指南本文深入探讨AI系统的容错测试方法，重点解决传统分布式系统和机器学习特有的双重复杂性挑战。文章提出三大核心验证维度：可用性验证（包括服务降级和优雅退化）、一致性保障（数据完整性和状态一致性）以及恢复能力测试（自动故障检测和快速恢复）。针对AI系统的独特挑战，如模型推理不确定性、数据依赖复杂性和GPU资源突发需求，文章提供了详细的实战方案。包括GPU显存不足的模拟与降级策

2048 AI社区

所有评论(0)

查看更多评论

wljy1

@wljy1

已为社区贡献1条内容