小小的总结

本人的第一场XCPC系列比赛，可惜遗憾打铁了，或许是对组队赛不熟悉，亦或许是队友直接磨合不好

但主要原因应该是自己太菜了（

赛时过了EDJ三题，A和队友琢磨了好久，最后思路是对的，但是不知道卡在了哪里，B题另一位队友的思路也是对的，但是代码写史了，WA了以后也调不出来

汉堡放凉了也没吃滚榜的时候才吃的ww

总结下来，打印的板子几乎没用到，够到铜牌（甚至银牌）只需要思维敏捷就够了

所以加训思维，少学无用算法，或许对我这种弱队菜鸡才是最优解。

另外还要加强和队友的配合，赛时和他们通思路好几次都是思路没法对到一块，要花好长时间理解他们（或许是我脑子转不动的问题）

下面是题解，按照难度（自认）排序

E. Registration

签到，

用一个map记录第\(t\)秒有多少队伍报名，然后遍历map，若第\(t_i\)秒的报名人数\(v\leq x\)则记入答案，否则跳过

void solve()
{ 
  ll n, x;
  cin >> n >> x;
  map<ll, ll> mp;
  ll tot = 0;
  for (int i = 1; i<=n; i++)
  {
    ll v;
    cin >> v;
    mp[v]++;
  }
  for (auto [v, c]:mp)
  {
    if (c<=x) tot+=c;
  }
  cout << tot << endl;
}

J. Would You Make a Convex?

由于要去任意三根都要组成一个非退化凸多边形，只要三根能组成，那再加一根到这三根里面就一定可以组成一个非退化凸多边形，所以我们可以只考虑能不能组成三角形

因此对木棍长度排序，组成非退化三角形的条件是两边之和大于第三边，所以两个两个的遍历排序后的长度数组，用二分找出满足条件且尽可能大的边，则由于数组有序，这一段区间内的所有木棍都可以组成非退化三角形，遍历取最长区间内的元素即可，若最长区间小于3则不存在满足要求的子集

这个还是比较好想的，赛时队友直接给出了思路写了，一发A

void solve()
{ 
  int n;
  cin >> n;
  vector<ll> arr(n+1);
  for (int i = 1; i<=n; i++)
  {
    cin >> arr[i];
  }
  sort(arr.begin()+1, arr.end());
  int maxl = -1;
  PII maxi = {0,0};
  for (int i = 1; i<n; i++)
  {
    int t = arr[i]+arr[i+1];
    int it = lower_bound(arr.begin()+1, arr.end(), t)-arr.begin()-1;
    // cout << it << endl;
    if (it-i+1>maxl)
    {
      maxl = it-i+1;
      maxi = {i, it};
    }
  }
  // cout << maxl << endl;
  if (maxl>=3)
  {
    cout << maxl << " ";
    for (int i = maxi.first; i <= maxi.second; i++)
    {
      cout << arr[i] << " ";
    }
  }
  else
  {
    cout << 0;
  }
  cout << endl;
}

D. Qenerals

由于占领不同堡垒带来的收益是一样的，显然我们应该贪心的占领代价小的堡垒

所以需要对堡垒进行排序，枚举当前堡垒能不能在\(sec\)秒时买入，若由于士兵数\(x'\)不够而无法买入，则我们需要等待\(\lceil \frac{a_i-x'}{i-1} \rceil\)秒才能继续购买，直到需要等待的时间超过了总时间，提前结束，更新ans

同时要考虑到中间过程主动停止购买，以当前士兵产量过完剩余时间得到的总数是否最优，因此除了超过总时间，每次购入堡垒也需要更新\(ans \larr \max\{ans, sod+(m-sec)\times cu\}\)，其中\(m\)为总秒数，\(sec\)为已经过去的秒数，\(cur\)为当前士兵产量，\(sod\)为当前士兵数

至于为什么这道题我会认为比J难，是因为赛时思路歪了，一直以为是枚举当前秒数一直尽可能在一秒内占领尽可能多堡垒，于是没和队友对上电波，还好队友给力码完A掉了这题

void solve()
{ 
  ll n, m;
  cin >> n >> m;
  vector<ll> arr(n+1);
  for (int i = 1; i<=n; i++)
  {
    cin >> arr[i];
  }
  sort(arr.begin()+1, arr.end());
  ll cur = 1; // 每秒士兵生产速度
  ll sod = 0; // 总士兵数
  ll ans = m*cur; // 最佳答案
  ll sec = 0; // 目前时间
  for (int i = 1; i<=n; i++) 
  {
    if (sec>=m) break;
    if (sod>=arr[i])
    {
      sod-=arr[i];
      cur++;
      ans = max(ans, sod+(m-sec)*cur);
      continue;
    }
    ll need = arr[i]-sod;
    ll nt = ((need+cur-1)/cur);
    if (sec+nt>m)
    {
      ans = max(ans, sod+(m-sec)*cur);
      break;
    }
    sec+=nt;
    sod+=nt*cur;
    sod-=arr[i];
    cur++;
    ans = max(ans, sod+(m-sec)*cur);
  }
  cout << ans << endl;

}

A. North and South

由题意可知，每次操作会使长度为偶数的区间内，奇数下标元素值加一，偶数下标元素值减一

所以每次操作进行的仅仅是区间内相邻值（从右往左）的交换，整个序列的和不变

因此使得序列a中所有数相等的这个值一开始就可以确定：\(n|{\Sigma a_i}\)，因此若序列和不能被长度整除，就无解

设最终达到的值是\(fin\)，可以贪心的选择最小的区间\(l=2\)，若\(a_i\leq fin\)，我们可以尽可能的把右边的值往左边移动，否则救不回来，无解

因此我们可以记录序列a的前缀和\(pre\)与当前位置应该到达的总和\(i\times fin\)，若\(pre>i\times fin\)，证明此时前缀已经超过所需，但交换只能从右向左，所以多出的值没法处理，无解

接下来是有解的情况，我们要尽可能最小化步数：

设\(t = i\times fin-pre_i\)，\(t\)就是要想该区间到达\(fin\)值缺少的值

由于一次操作是在偶数区间上进行的，所以每次操作只会影响相同奇偶性下标的元素的前缀

所以奇数下标的需求和偶数下标的需求需要分开解决

举个例子：

设操作区间为[2,5]，则一次操作对数组的影响是[+1,-1,+1,-1]，对应的前缀和变化是[+1,0,+1,0]，你会发现，受到影响的位置只有偶数下标2和4

设操作区间为[1,4]，同理，对应前缀和变化是[+1,0,+1,0]，但此时下标是从1开始，所以受到影响的位置只有奇数下标1和3

这就是为什么要分别统计奇数下标前缀和偶数下标前缀

则我们可以分别统计操作次数了，他们均满足\(\Sigma\max\{0,pre_i-pre_{i-1}\}\)，即有多少个奇数/偶数区间不能被先前的区间覆盖，统一进行操作而需要新开区间

A题我和另一个队友想了两个多小时，思路正确但是代码写的太长导致不知道哪里错误

到最后也没调出来，可能放弃这个题去帮忙开B题或者L题会更好一点吧

void solve()
{ 
  ll n;
  cin >> n;
  vector<ll> arr(n+1);
  for (int i = 1; i<=n; i++)  
  {
    cin >> arr[i];
  }
  // ll op = 0;
  ll tot = accumulate(arr.begin()+1, arr.end(), 0ll);
  if (tot%n)
  {
    cout << -1 << endl;
    return ;
  }
  ll fin = tot/n;
  ll ans = 0, pre = 0, preo = 0, pree = 0;
  for (ll i = 1; i<=n; i++)
  {
    pre+=arr[i];
    ll t = i*fin-pre;
    if (t<0) 
    {
      cout << -1 << endl;
      return ;
    }
    if (i&1)
    {
      ans += max(0ll, t-preo);
      preo = t;
    }
    else
    {
      ans += max(0ll, t-pree);
      pree = t;
    }

  }
  cout << ans << endl;
}

B. Operating Robot

题意是给定一个操作串，0代表向右，1代表向上，2可以自己改，机器人会一直按照操作串循环前进，直到到达\((x,y)\)，或指明无法到达

机器人为了到达\((x,y)\)，要走\(x+y\)步，这些步中，可以分为按照操作串走\(\frac{(x+y)}{n}\)轮，再加上走操作串前缀\((x+y)\bmod n\)步，我们设为\(rnd\)和\(left\)

我们首先扣去固定的操作，只看数位2

用前缀和记录操作串中0，1，2的个数，则\(pre_i[n]\times rnd+pre_i[left]\)就是总固定要走的步数，把这些分别从\(x,y\)里减去，剩下的\(x,y\)就是我们要通过操作2来实现的移动，若减完了\(x,y\)已经是负数，就直接返回无解

接下来操作2，我们可以简单的将所有的2分为四段，分别为\(a\):前缀2变0，\(b\):前缀2变1，\(c\):后缀2变0，\(d\):后缀2变1，后缀的意思是最后走不完一整轮操作时，剩下没有操作的后缀串，此时的\(x\)和\(y\)可以由以下公式拼凑： \[ x = (rnd+1)\times a+left\times c \\ y = (rnd+1)\times b+left\times d \] 枚举前缀2变0，从大到小，因为要让字典序尽可能小，其余段数可以计算而得。首先要满足够减，即若\(x\)或\(y\)小于\(rnd\)数，说明不符合，其次，若算出来的后缀数与前缀数拼不成最终的\(x\)和\(y\)，也不符合

另外，当\(rnd=0\)，也就是不需要一轮就可以结束的情况需要特判，此时需要满足前缀要完全符合\(x\)与\(y\)，且后缀尽可能的放0

发现一种情况满足直接跳出即可，此时一定是最优解，按照此时的01数量构造字符串

队友一眼出的题，但是没写出来有点可惜

这个代码好想不好写，补题的时候想了两种思路写了快200行的史山最后推倒重构，借鉴了队里其他人的码

void solve()
{ 
  ll n, x, y;
  cin >> n >> x >> y;  
  string s;
  cin >> s;
  vector<ll> pre0(n+1), pre1(n+1), pre2(n+1);
  for (int i = 0; i<n; i++)
  {
    pre0[i+1] = pre0[i]+(s[i]=='0'?1:0);
    pre1[i+1] = pre1[i]+(s[i]=='1'?1:0);
    pre2[i+1] = pre2[i]+(s[i]=='2'?1:0);
  }
  ll rnd = (x+y)/n;
  ll left = (x+y)%n;
  x-=(pre0[n]*rnd+pre0[left]);
  y-=(pre1[n]*rnd+pre1[left]);
  if (x<0||y<0)
  {
    cout << -1 << endl;
    return ;
  }

  // 前缀/后缀+从2变为几
  bool flag = 0;
  ll pre20, pre21, suf20, suf21;
  for (pre20 = pre2[left]; pre20>=0; pre20--)
  {
    pre21 = pre2[left] - pre20;
    if (rnd==0)
    {
      if (pre20!=x||pre21!=y)continue;
      suf20 = pre2[n]-pre2[left];
      suf21 = 0;
      flag = 1;
      break;
    }
    else
    {
      if (x<pre20*(rnd+1)||y<pre21*(rnd+1)) continue;
      suf20 = (x-pre20*(rnd+1))/rnd;
      suf21 = (y-pre21*(rnd+1))/rnd;
      if (suf20<0||suf21<0) continue;
      if (x!=(rnd+1)*pre20+rnd*suf20||y!=(rnd+1)*pre21+rnd*suf21) continue;
      flag = 1;
      break;
    }
  }
  if (!flag)
  {
    cout << -1 << endl;
    return ;
  }
  int idx = 0;
  for (int i = 0; i<n; i++)
  {
    if (s[i]=='2')
    {
      idx++;
      if (idx>=1&&idx<=pre20) cout << '0';
      else if (idx>pre20&&idx<=pre20+pre21) cout << '1';
      else if (idx>pre21&&idx<=pre20+pre21+suf20) cout << '0';
      else if (idx>suf20&&idx<=pre20+pre21+suf20+suf21) cout << '1';

    }
    else
    {
      cout << s[i];
    }
  }
  cout << endl;
}

L/M. Yesterday Once More

Ad-hoc/构造

很奇妙的构造，具体意思是在\(n+1\)行与\(n\)列的网格中，除了第一行与第n＋1行无障碍，其余的满足

第i行恰有一个障碍
第j列至多有一个障碍

从\((1,1)\)开始，构造一种移动串能到达n＋1行，若某次移动碰到障碍，则这次移动无效，直接到下一个移动

Easy版要求移动次数不超过\(30n\)，Hard版不超过\(10n\)

这道题其实上只要把所有可能的情况都移动一遍就行，首先考虑如下形状：

由于第一行和最后一行无障碍，则行障碍肯定比列少一个，一定有一列是空的

我们可以尽可能的贴着障碍向右移动，直到碰到一个洞可以钻下去，可以构造RDLD，这里往左移动是为了避免正下方有障碍，如：

接下来考虑第二种形状：

这种情况下，从\((1,1)\)直接捅下去会被两面障碍夹击，RDLD会完全卡住，需要向上走，

依旧贴着障碍向右移动，直到碰到一个洞可以钻下去，可以构造URRD，这种构造可以保证找到一个洞钻下去，钻下去以后需要继续移动，我们考虑继续贴着障碍移动，首先下去以后尽可能向左走L直到碰到障碍，接下来构造DL贴着障碍下侧向左移动，一次即可，因为障碍在上面，下面不会再有障碍了，可以一直D移动到\(n+1\)行

综上，移动方案为RDLD*n+URRD*n+n*L+DL+nD，这是\(10n+2\)次移动，多了两次

另外发现，对于n列，我们发现只需要进行URRD\(n-1\)次就可以到达结尾，这样可以减少四次，一共移动\(10n-2\)次

后面上课补题一节课想出了easy并压到了\(10n+2\)

void solve()
{ 
  int n;
  cin >> n;
  cout << 10*n-2<<endl;
  
  string ans;
  for (int i = 1; i<=n; i++)
  {
    ans+="RDLD";
  }
  for (int i = 1; i<n; i++)
  {
    ans+="URRD";
  }
  for (int i = 1; i<=n; i++)
  {
    ans+="L";
  }
  ans+="DL";
  for (int i = 1; i<=n; i++)
  {
    ans+="D";
  }
  cout << ans << endl;
}

C. Palindromic and Balanced

首先理解平衡括号串和回文括号串：

平衡括号串：由一对括号括起来的括号串
回文括号串：满足回文的括号串，即类似于(S( 和)S)的串

显然一个括号串不能同时满足这两个性质，所以题目的平衡回文括号串定义为平衡括号串内部是回文括号串

即满足\(s_1=(, s_k=)\)且\(s_{2～k}\)满足回文，如(())()，被两个括号括起来的是一个回文括号串

我们考虑同时向头尾插入相同长度的括号串，为了满足回文与平衡，只有下面两种情况：头插()尾插)(或头插)(尾插()

因为如果插入((那尾部也得插入((，不满足平衡性质，右括号同理

考虑区间DP，dp[l][r]表示区间\(l\)到\(r\)之间最长合法子串的长度，则有如下转移： \[ dp_{i,j}= \left\{\begin{array}{ll} \max\{dp_{i,j},dp_{i＋1,j},dp_{i,j-1}\} & 删除左右端点\\ dp_{i+2,r-2}+4 & 头尾子串 \end{array}\right. \] 因此基本思路是：

寻找最大的平衡串：找最靠外的一对()
若该串长度小于4，则只能是())或(()，特判输出2
否则区间DP转移

void solve()
{ 
  int n;
  cin >> n;
  string s;
  cin >> s;
  s = " "+s;
  vector<vector<ll>> dp(n+1, vector<ll>(n+1));
  // 寻找满足平衡串的起点与终点
  ll l = -1, r = -1;
  for (int i = 1; i<=n; i++)
  {
    if (s[i]=='('&&l==-1) l = i;
  }
  for (int i = n; i>=1; i--)
  {
    if (s[i]==')'&&r==-1) r = i;
  }

  if (l>r||l==-1||r==-1)
  {
    cout << 0 << endl;
    return ;
  }
  // (()和())
  if (r-l+1<4)
  {
    cout << 2<<endl;
    return ;
  }
  // l ? ? ? ? r
  for (int len = 4; len<=n; len++)
  {
    for (int i = l+1; i<=r-len+1; i++)
    {
      int j = i+len-1; 
      dp[i][j] = max({dp[i][j], dp[i+1][j], dp[i][j-1]});

      if (s[i]=='('&&s[i+1]==')'&&s[j-1]==')'&&s[j]=='(')
      {
        dp[i][j] = dp[i+2][j-2]+4;
      }
      if (s[i]==')'&&s[i+1]=='('&&s[j-1]=='('&&s[j]==')')
      {
        dp[i][j] = dp[i+2][j-2]+4;
      }

    }
  }
  cout << dp[l+1][r-1]+2 << endl;
}

红魔咖啡馆

【题解】2026西安ICPC邀请赛