Codeforces Round #655 (Div. 2)

A Omkar and Completion

只要找两个相加不等的数交叉构造即可。

AC代码：

int main()
{
  int t;
  sd(t);
  while (t--)
  {
    sd(n);
    rep(i, 1, n)
    {
      if (i & 1)
        printf("500 ");
      else
        printf("501 ");
    }
    printf("\n");
  }
  return 0;
}

B. Omkar and Last Class of Math

设 为两个解，假设 ，那么显然 一定 。这里我们一定要构造 的解，因为 一定 ，而 是 的倍数，就算 也一定 ，所以 也就是说， 可以整除 ，这又等价于 整除 。要让 尽可能小，相当于让 尽可能小也就是 尽可能大。所以总结一下，要让 整除 并且 尽可能大，那就找 的最大的不等于

AC代码：

int main()
{
  int t;
  sd(t);
  while (t--)
  {
    sd(n);
    if (n % 2 == 0)
    {
      pdd(n / 2, n / 2);
      continue;
    }
 
    int ans = -1;
    for (int i = 2; i * i <= n; i++)
    {
      if (n % i == 0)
      {
        ans = max(ans, i);
        ans = max(ans, n / i);
      }
    }
    if (ans == -1)
      ans = 1;
    pdd(ans, n - ans);
  }
  return 0;
}

C. Omkar and Baseball

• 原序列已经是
• 原序列中，有一段区间中所有元素都错位，操作一次。
• 原序列中一部分在原位置，一部分不在原位置，操作两次。

AC代码：

const int N = 5e5 + 50;
int n, k, m;
int a[N];

int main()
{
  int t;
  sd(t);
  while (t--)
  {
    sd(n);
    int cnt = 0;
    rep(i, 1, n)
    {
      sd(a[i]);
      if (a[i] == i)
        cnt++;
    }
    if (cnt == n)
    {
      puts("0");
      continue;
    }
    rep(i, 1, n)
    {
      if (a[i] == i)
        cnt--;
      else
        break;
    }
    per(i, n, 1)
    {
      if (a[i] == i)
        cnt--;
      else
        break;
    }
    if (cnt == 0)
      puts("1");
    else
      puts("2");
  }
  return 0;
}

D. Omkar and Circle

首先把环断开，发现最优情况只可能是把所有奇数位置上的数加起来。因为偶数位置的数根本不可能留到最后。那么这个结论应用到环上就是，很多“偶数”位置其实都会被抛弃，最后的答案一定是，选取恰当的位置把环断开后的奇数位置之和。所以实现的时候只要记录奇偶位置的前缀和，然后

AC代码：

const int N = 5e5 + 50;
int n, k, m;
ll a[N], s[2][N];

int main()
{
  int t;
  sd(n);
  rep(i, 1, n)
  {
    sld(a[i]);
    s[0][i] = s[0][i - 1] + (i % 2 == 0 ? a[i] : 0);
    s[1][i] = s[1][i - 1] + (i % 2 == 1 ? a[i] : 0);
  }
  ll ans = 0;
  rep(i, 1, n)
    ans = max(ans, s[i % 2][i] + s[i % 2 ^ 1][n] - s[i % 2 ^ 1][i]);
  pld(ans);
  return 0;
}