AtCoder Regular Contest 136

把之前abc丢的分都加回来了,敲开心QwQ,坚持补ARC就完事了!
今天还跟dian神学习了一点离线和莫队,祝dian神微软面试成功！！！

A.给定只含ABC的字符串,可用$A$替换$BB$,也可用$BB$替换$A$,对给定字符串进行处理使得字典序最小

solution:我感觉我的做法很优了hh,总之大家怎么做都离不开贪心,我们尽量把BB换成A,并尽量把A靠前移

#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int inf = 1e18;
constexpr int maxn = 2e5 + 5;

inline void solve()
{
  int n; cin >> n;
  string s; cin >> s;
  for (int i = 0; i < n - 1; i ++)
  {
    if (s[i] == 'B')
    {
      if (s[i + 1] == 'A')
      {
        swap(s[i], s[i + 1]);
      }
      else if (s[i + 1] == 'B')
      {
        s[i] = 'A';
        s[i + 1] = 'D';
      }
    }
  }
  for (char ch : s)
  {
    if (ch == 'D') continue;
    cout << ch;
  }
}

signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
  return 0;
}

B.给定序列和操作:可将$A_i, A_{i+1}, A_{i+2}$转换为$A_{i+2}, A_{i}, A_{i+1}$,也就是将三项中最后一个数前移,问是否能够使得若干次操作后$A=B$

solution:我发现$1 2 3 4 5$并不能变成$1 2 3 5 4$,大家不信可以手动模拟一下,所以最后我们只需要对给定$A_i$不断转换到$B_i$,从前往后逐位模拟,最后再判断一下最后两位即可

#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int inf = 1e18;
constexpr int maxn = 5000 + 5;

inline void solve()
{
  int n; cin >> n;
  vector<int> a(maxn), b(maxn);
  vector<int> cnta(maxn), cntb(maxn);
  for (int i = 1; i <= n; i ++) 
  {
    cin >> a[i];
    cnta[a[i]] ++;
  }
  for (int i = 1; i <= n; i ++) 
  {
    cin >> b[i];
    cntb[b[i]] ++;
  }
  for (int i = 1; i <= 5000; i ++)
  {
    if (cnta[i] != cntb[i]) 
    {
      cout << "No\n";
      return ;
    }
    if (cnta[i] > 1)
    {
      cout << "Yes\n";
      return ;
    }
  }

  for (int i = 1; i <= n - 2; i ++)
  {
    if (a[i] != b[i])
    {
      int cur = -1;
      for (int j = i + 1; j <= n; j ++)
      {
        if (b[i] == a[j]) 
        {
          cur = j; 
          break;
        }
      }

      while (cur - i > 1)
      {
        rotate(a.begin() + cur - 2, a.begin() + cur, a.begin() + cur + 1);
        cur -= 2;
      }
      if (cur - i == 1) rotate(a.begin() + cur - 1, a.begin() + cur, a.begin() + cur + 2);
    }
  }
  if (a[n - 1] == b[n - 1] && a[n] == b[n]) cout << "Yes\n";
  else cout << "No\n";

}

signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
  return 0;
}

C.在封闭序列中选定下标$i$与数值$k$,使得$i$之后(包含$i$)共$k$项都+1,问
使得空序列变成$A$序列的最小操作次数

solution:这个序列中的最大数$mx$,是我们操作的下界,这是必须理解的,而且这个操作次数与封闭序列之间的绝对值差有关系,大家可以这样想,如果各个元素之间的绝对值差为$0$,那我们的操作次数只与$mx$有关,除此之外,我们对所有的绝对值差求和再除以$2$,这两个数值的较大值为$ans$

#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int inf = 1e18;
constexpr int maxn = 2e5 + 5;

inline void solve()
{
  int n; cin >> n;
  vector<int> a(n); 
  for (int &x : a) cin >> x;
  int ans = 0;
  for (int i = 0; i < n; i ++) ans += abs(a[i] - a[(i + 1) % n]);
  ans /= 2;
  ans = max(ans, *max_element(a.begin(), a.end()));
  cout << ans << "\n";
}

signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
  return 0;
}
/*
在封闭序列中选定下标i与数值k,使得i之后(包含i)共k项都+1,问
使得空序列变成A序列的最小操作次数
*/

D.题目意思是，让你在一个序列中查找无法进位的两个数的个数(计无进位二元组数)

注释见题解

#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int inf = 1e18;
constexpr int maxn = 2e5 + 5;

constexpr int pw10(int n)
{
    return n == 0 ? 1 : pw10(n - 1) * 10;
}

inline bool check(int a, int b)
{
  while (a && b)
  {
    int c = a % 10, d = b % 10;
    if (c + d >= 10) return false;
    a /= 10;
    b /= 10;
  }
  return true;
}

inline void solve()
{
  int n; cin >> n;
  vector<int> a(n);
  for (int &x : a) cin >> x;
  constexpr int L = 6;
  constexpr int S = pw10(L);
  vector<int> dp(S);
  for (int x : a) dp[x] ++;
  for (int i = 0; i < L; i ++)
  {
    int w = pw10(i);
    for (int j = 0; j < S; j ++)
    {
      if ((j / w) % 10 < 9)
      {
        dp[j + w] += dp[j];
      }
    }
  }
  int ans = 0;
  for (int x : a)
  {
    ans += dp[S - 1 - x];
    if (check(x, x)) ans --;
  }
  cout << ans / 2 << "\n";
}

signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
  return 0;
}

/*
在0到1e6-1的数据中，我们让X支配Y
对于每个i(0<=i<=5)x的对应位>y的对应位
计算x+y无进位，此时(10^L - 1 - X)支配Y，Ai的数字是可知的
如果我们用2进制取代十进制，就是快速zeta变换
此外，同样的算法在十进制下一样可行，特别的地方是我们应该dp讲a转化为x到x+10^i，如果对应i的位置<9(0<=i<=5)
算法复杂度O(N+L*10^L)
*/

E.待补 -> 不懂

F.待补 -> 数学