Codeforces Round 963 (Div. 2)

Luckyblock / 2024-08-05 / 原文

写在前面
A
B
C
D
E
F1
写在最后

写在前面

比赛地址：https://codeforces.com/contest/1993

妈的睡到 22:35 整点起床，刚下床就开了妈的太刺激！

为了保证队长当前是 1k9 这个事实不变方便劝诱新大神，于是上小号了呃呃，D 调出来了不是太烂感觉暑假肯定能把小号也打上紫嘻嘻

唉反正小号随便打了呃呃

置顶广告：中南大学 ACM 集训队绝赞招新中！

有信息奥赛基础，获得 NOIP 省一等奖并达到 Codeforces rating 1900+ 或同等水平及以上者，可以直接私聊我与校队队长联系，免选拔直接进校集训队参加区域赛！

没有达到该水平但有志于 XPCX 赛事请关注每学年开始的 ACM 校队招新喵！

到这个时候了还缺队友实在不妙！求求求求快来个大神带我呜呜呜呜

A

签到。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    int n; std::cin >> n;
    std::string s; std::cin >> s;
    int ans = 0, cnt1 = 0, cnt[4] = {n, n, n, n};
    for (auto ch: s) {
      if (ch == '?') ++ cnt1;
      else if (cnt[ch - 'A']) -- cnt[ch - 'A'], ++ ans;
    }
    std::cout << ans << "\n";
  }
  return 0;
}

B

模拟。

呃呃反正我是模拟写的，应该有更简单的直接判定的方法。

先特判一开始就合法。然后考虑到奇数+偶数=奇数，则考虑如何将所有偶数变为奇数。观察样例可知，操作次数不会超过偶数个数 +1 次，因为可以选择任意奇数与最大的偶数操作两次，可以造出一个比任何偶数都大的奇数，再使用该奇数操作即可。

则操作次数仅可能为偶数个数，或偶数个数+1。

考虑答案能否取到下界。操作次数为 $O(n)$ 级别则可直接模拟。显然每次操作一定会使用当前最大的奇数进行操作，考虑记录所有偶数并升序排序，然后按顺序使用最大的奇数对所有数操作，并更新最大奇数即可。若在此过程中较小值一直为偶数一方则可取到下界。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define int long long
const int kInf = 1e9 + 2077;
//=============================================================
//=============================================================
//=============================================================
signed main() {
  // freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    int n; std::cin >> n;
    std::vector<int> even;
    int cnt[2] = {0}, maxodd = 0;;
    for (int i = 1; i <= n; ++ i) {
      int x; std::cin >> x;
      if (x % 2 == 1 && x > maxodd) maxodd = x;
      if (x % 2 == 0) even.push_back(x);
      ++ cnt[x % 2];
    }
    if (cnt[0] == 0 || cnt[1] == 0) {
      std::cout << 0 << "\n";
      continue;
    }
    std::sort(even.begin(), even.end());
    
    int flag = 0;
    for (auto x: even) {
      if (x < maxodd) maxodd = x + maxodd;
      else flag = 1;

      if (x > even.back()) break;
    }
    std::cout << cnt[0] + flag << "\n";
  }
  return 0;
}
/*
1
5
999999996 999999997 999999998 999999999 1000000000
*/

C

乱搞。

感觉有一万种方法能过呃呃，我这种属于是最烂的。

发现有 $k\le n$，则第一次全部灯亮一定出现在 $\operatorname{max}_i a_i$ 时刻之后，所有灯变化次数不超过 1 次的时间范围内。于是直接记录每盏灯下一个状态变化的时刻，考虑时刻的变化大力模拟了呃呃，推荐指数不推荐。

复杂度 $O(n)$ 级别。

正确性应该没错吧大概不会被叉吧呃呃呃，反正 system testing 是过了哈哈不过这个 system testing $O(nk)$ 都放过去了真是不好说、、、

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, k, a[kN];
std::vector<int> on, off;
//=============================================================
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    std::cin >> n >> k;
    on.clear(), off.clear();
    for (int i = 1; i <= n; ++ i) std::cin >> a[i];
    std::sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++ i) {
      int d = a[n] - a[i], t = d / k;
      if (t % 2 == 0) on.push_back(a[n] + k - d % k);
      else off.push_back(a[n] + k - d % k);
    }
    if (on.size() == n) {
      std::cout << a[n] << "\n";
      continue;
    }
    
    std::sort(on.begin(), on.end());
    std::sort(off.begin(), off.end());
    int ans = -1, szon = on.size(), szoff = off.size();
    int realszon = szon, realszoff = szoff;
    
    for (int now = 1, i = 0, j = 0, t = a[n]; now <= n; ++ now) {
      if (i == szon) {
        t = off[j];
        on.push_back(off[j] + k);
        ++ szon;
        ++ realszon, -- realszoff;
        ++ j;
      } else if (j == szoff) {
        t = on[i];
        off.push_back(on[i] + k);
        ++ szoff;
        ++ realszoff, -- realszon;
        ++ i;
      } else {
        if (on[i] < off[j]) {
          t = on[i];
          off.push_back(on[i] + k);
          ++ szoff;
          ++ realszoff, -- realszon;
          ++ i;
        } else {
          t = off[j];
          on.push_back(off[j] + k);
          ++ szon;
          ++ realszon, -- realszoff;
          ++ j;
        }
      }

      int ok = 1;
      if (i < szon) if (on[i] == t) ok = 0;
      if (j < szoff) if (off[j] == t) ok = 0;
      if (ok && realszon == n) {
        ans = t; 
        break;
      }
    }
    std::cout << ans << "\n";
  }
  return 0;
}

D

二分答案，最长上升子序列。

令下标从 0 开始编号。每次删保证删除的是长度为 $k$ 的子区间，即每次删除的数的下标 $\bmod k$ 恰好构成了 $\bmod k$ 的一个剩余系，手玩下很容易发现，若最终剩下 $n'$ 个数，其下标 $\bmod k$ 按顺序一定为 $0, 1, \cdots, n'-1$。

中位数为 $x$ 的必要条件是数列中不小于 $x$ 的数不少于 $\left\lceil\frac{n'}{2}\right\rceil$ 个，发现答案有单调性，考虑二分答案并每次检查枚举量 $\operatorname{lim}$ 是否合法，即检查是否存在某个子序列 $L = \{a_{l_0}, a_{l_1}, \cdots, a_{l_{n'-1}}\}$，有 $\forall 0\le i\le n'-1, l_i\bmod k = i, l_{i - 1}< l_i$，且 $L$ 中有不少于 $\left\lceil\frac{n'}{2}\right\rceil$ 个不小于 $\operatorname{lim}$ 的数。

发现 $l_{i - 1}< l_i$ 等价于选择的数的下标 $i\bmod k$ 一个 $0\sim n'-1$ 的最长上升子序列。则选择不小于 $\operatorname{lim}$ 的数时，仅需保证它们的下标 $i\bmod k$ 的值是严格单调递增的，即可保证存在一种操作方案使它们出现在同一个 $L$ 中。

于是每次 check 时，考虑对 $a$ 中所有不小于 $\operatorname{lim}$ 且 $i\bmod k\le n'-1$ 的位置 $i$，记录 $i\bmod k$ 的值并求最长上升子序列，其长度 $\operatorname{len}$ 即为子序列 $L$ 中不小于 $\operatorname{lim}$ 的数的最大数量，检查是否有 $\operatorname{len}\ge \left\lceil\frac{n'}{2}\right\rceil$ 即可。

总时间复杂度 $O(n\log v\log n)$ 级别，常数非常小大概不会被叉哈哈。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 5e5 + 10;
//=============================================================
int n, k, nn;
LL a[kN], ans;
//=============================================================
namespace Bit {
  #define lowbit(x) ((x)&(-x))
  const int kLim = kN << 1;
  int lim, nowtime, t[kLim], tim[kLim];
  void Init(int lim_) {
    lim = lim_, ++ nowtime;
  }
  void Insert(int pos_, int val_) {
    for (int i = pos_; i <= lim; i += lowbit(i)) {
      if (tim[i] != nowtime) t[i] = 0, tim[i] = nowtime;
      t[i] = std::max(t[i], val_);
    }
  }
  int Max(int pos_) {
    int ret = 0;
    for (int i = pos_; i; i -= lowbit(i)) {
      if (tim[i] != nowtime) t[i] = 0, tim[i] = nowtime;
      ret = std::max(ret, t[i]);
    }
    return ret;
  }
}
bool check(LL lim_) {
  std::vector<int> pos {-1};
  for (int i = 0; i < n; ++ i) {
    if (a[i] >= lim_ && i % k < nn) 
      pos.push_back(i % k + 1);
  }
  int len = 0;
  Bit::Init(k + 1);
  for (int i = 1, sz = pos.size(); i < sz; ++ i) {
    int ret = Bit::Max(pos[i] - 1) + 1;
    Bit::Insert(pos[i], ret);
    len = std::max(len, ret);
  }
  return len >= (nn / 2 + 1);
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    std::cin >> n >> k;
    for (int i = 0; i < n; ++ i) std::cin >> a[i];
    if (n % k == 0) nn = k;
    else nn = (n % k);

    ans = 0;
    for (LL l = 1, r = 1e9; l <= r; ) {
      LL mid = (l + r) >> 1ll;
      if (check(mid)) {
        l = mid + 1;
        ans = mid;
      } else {
        r = mid - 1;
      }
    }
    std::cout << ans << "\n";
  }
  return 0;
}
/*
1
4 3
3 9 9 2
5 3
3 2 5 6 4
7 1
5 9 2 6 5 4 6
8 2
7 1 2 6 8 3 4 5
4 5
3 4 5 6
*/

E

待补。

观测群友大神 isaunoya 的交流好像有很类似的套路题：https://www.luogu.com.cn/problem/AT_agc016_d。

F1

待补。

考虑镜像操作，将移动范围扩大到 $2w \times 2h$ 的区域，并将区域平移到第一象限，则仅需考虑统计经过 $(k_1\times 2w,k_2\times 2h)$ 多少次，$k_1, k_2$ 任取。

写在最后

学到了什么：

D：考虑剩余系。

你说的对按照常理来说现在又是夹带私货环节：

结尾广告：中南大学 ACM 集训队绝赞招新中！

有信息奥赛基础，获得 NOIP 省一等奖并达到 Codeforces rating 1900+ 或同等水平及以上者，可以直接私聊我与校队队长联系，免选拔直接进校集训队参加区域赛！

没有达到该水平但有志于 XPCX 赛事请关注每学年开始的 ACM 校队招新喵！

到这个时候了还缺队友实在不妙！求求求求快来个大神带我呜呜呜呜