Codeforces Round 965 (Div. 2)

Luckyblock / 2024-08-11 / 原文

写在前面
A
B
C
D
E1
写在最后

写在前面

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

为了保证队长当前是 1k9 这个事实不变方便劝诱新大神，于是上小号。

比较手速场呃呃，小号大概也能上紫了爽，要是手快点还能更爽。

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

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

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

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

A

签到。

草怎么那么多 fst 的不懂。

//
/*
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 xc, yc, k; std::cin >> xc >> yc >> k;
    for (int i = 1; i <= k - k % 2; i += 2) {
      std::cout << xc + (i / 2 + 1) << " " << yc << "\n";
      std::cout << xc - (i / 2 + 1) << " " << yc << "\n";
    }
    if (k % 2) std::cout << xc << " " << yc << "\n";
  }
  return 0;
}

B

思维，结论。

本地 check 了一下发现样例中给定排列与答案里，有且仅有 $[1, n]$ 的和是相等的，于是猜想一定存在一种构造方案，使得两个排列仅有 $[1, n]$ 的和相等。

赛时猜了个结论，直接把所有位置循环向后位移一位即可，本地跑了几组数据 check 了一下发现可行于是交上去过了。

其正确性是显然的，考虑给定的排列 $a$ 与循环向后位移一位得到的排列 $b$，对于任意一个长度小于 $n$ 的区间 $[l, r]$，一定有：

\[\sum_{l\le i\le r} b_i = \sum_{l - 1\le i\le r - 1} a_i \not= \sum_{l\le i\le r} a_i \]

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================4
int n, a[kN], ans[kN];
//=============================================================
//=============================================================
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;
    for (int i = 1; i <= n; ++ i) std::cin >> a[i];
    for (int i = 2; i <= n; ++ i) ans[i] = a[i - 1];
    ans[1] = a[n];
    for (int i = 1; i <= n; ++ i) std::cout << ans[i] << " ";

    // LL cnt = 0;
    // for (int i = 1; i <= n; ++ i) {
    //   for (int j = i; j <= n; ++ j) {
    //     LL s1 = 0, s2 = 0;
    //     for (int k = i; k <= j; ++ k) {
    //       s1 += a[k], s2 += ans[k];
    //     }
    //     if (s1 == s2) ++ cnt;
    //   }
    // }
    // std::cout << cnt << "\n";
    std::cout << "\n";
  } 
  return 0;
}
/*
3
2
1 2
2 1
5
1 2 3 4 5
3 5 4 2 1
7
4 7 5 1 2 6 3
6 2 1 4 7 3 5
*/

C

枚举，数据结构。

考虑枚举最终答案里的 $a_i$，再考虑通过修改增大 $a_i$ 和增大中位数的代价：

若有 $b_i = 1$，显然一次修改至少使 $a_i:=a_i + 1$ 而不一定使中位数 $+1$，显然此时应仅修改 $a_i$，对答案的贡献即 $a_i + k + \operatorname{median}(c_i)$，直接对顶堆动态维护删去 $a_i$ 的中位数即可。单次检查的时间复杂度为 $O(\log n)$ 级别。

若有 $b_i = 0$，则此时仅能修改其他位置使中位数增大，一个显然的想法是二分答案枚举增大后的中位数的值 $\operatorname{mid}$，则仅需检查能否通过修改使 $c = \left\lfloor\frac{n - 1}{2}\right\rfloor + 1$ 个数不小于 $\operatorname{mid}$。

考虑先查询原数列中不小于 $\operatorname{mid}$ 的数的个数 $c'$，再查询原数列中小于 $\operatorname{mid}$ 且 $b_i=1$ 的数，则最优的操作是选择其中最大的 $c - c'$ 个数使它们变为 $\operatorname{mid}$，查询他们的和与 $(c - c')\times \operatorname{mid}$ 的差值是否不大于 $k$ 即可。

上述原数列中不小于 $\operatorname{mid}$ 的数的个数、以及原数列中小于 $\operatorname{mid}$ 且 $b_i=1$ 的数，均可以通过维护排序后的原数列，再在上面二分得到，在此基础上最大的 $c - c'$ 个数可通过维护前缀和得到，则单次检查的时间复杂度为 $O(\log v\log n)$ 级别。

总时间复杂度 $O(n\log v\log n)$ 级别。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define pr std::pair
#define mp std::make_pair
const int kN = 2e5 + 10;
const LL kMaxa = 2e9;
//=============================================================
int n, k, a[kN], b[kN];
int a1num, sorta1[kN], sorta[kN];
LL sum[kN];
//=============================================================
namespace Set {
  const int kInf = 1e9 + 2077;
  std::multiset<int> less, greater;
  void init() {
    less.clear(), greater.clear();
    less.insert(-kInf), greater.insert(kInf);
  }
  void adjust() {
    while (less.size() > greater.size() + 1) {
      std::multiset<int>::iterator it = (--less.end());
      greater.insert(*it);
      less.erase(it);
    }
    while (greater.size() > less.size()) {
      std::multiset<int>::iterator it = greater.begin();
      less.insert(*it);
      greater.erase(it);
    }
  }
  void add(int val_) {
    if (val_ <= *greater.begin()) less.insert(val_);
    else greater.insert(val_);
    adjust();
  }
  void del(int val_) {
    std::multiset<int>::iterator it = less.lower_bound(val_);
    if (it != less.end()) {
      less.erase(it);
    } else {
      it = greater.lower_bound(val_);
      greater.erase(it);
    }
    adjust();
  }
  int get_middle() {
    return *less.rbegin();
  }
}
void init() {
  std::cin >> n >> k;
  Set::init();
  for (int i = 1; i <= n; ++ i) {
    std::cin >> a[i];
    Set::add(a[i]);
  }

  a1num = 0;
  for (int i = 1; i <= n; ++ i) {
    std::cin >> b[i];
    sorta[i] = a[i];
    if (b[i] == 1) sorta1[++ a1num] = a[i];
  }
  std::sort(sorta + 1, sorta + n + 1);
  std::sort(sorta1 + 1, sorta1 + a1num + 1);
  for (int i = 1; i <= a1num; ++ i) sum[i] = sorta1[i] + sum[i - 1];
}
LL solveb1(int pos_) {
  Set::del(a[pos_]);
  LL ret = Set::get_middle();
  Set::add(a[pos_]);
  return ret;
}
LL solveb0(int pos_) {
  LL ret = 0;
  int middle = (n - 1) / 2 + 1;

  for (LL l = 1, r = kMaxa; l <= r; ) {
    LL mid = (l + r) >> 1ll;
    int p1 = std::lower_bound(sorta1 + 1, sorta1 + a1num + 1, mid) - sorta1;
    int p2 = std::lower_bound(sorta + 1, sorta + n + 1, mid) - sorta;
    int c1 = p1 - 1, c2 = n - (p2 - 1) - (a[pos_] >= mid);

    if (c2 >= middle) {
      ret = mid;
      l = mid + 1;
      continue;
    }

    int need = middle - c2;
    if (need > c1) {
      r = mid - 1;
      continue;
    }

    if (1ll * sum[c1] - sum[c1 - need] + k < 1ll * need * mid) {
      r = mid - 1;
    } else {
      ret = mid;
      l = mid + 1;
    }
  }
  return ret;
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    init();
    LL ans = 0;
    for (int i = 1; i <= n; ++ i) {
      if (b[i] == 1) {
        ans = std::max(ans, 1ll * a[i] + k + solveb1(i));
      } else {
        ans = std::max(ans, 1ll * a[i] + solveb0(i));
      }
    }
    std::cout << ans << "\n";
  }
  return 0;
}

D

DP。

游戏题照例先先手玩下。以下称先手移动的仅能走边 $(i, i + 1)$ 的牛牛为先手，另一牛牛为后手。边 $(i, i + 1)$ 称为杂鱼边，其他边称为牛逼边。

发现考虑先手必胜需要大力枚举起点比较麻烦，于是取个反考虑起点固定为 1 的后手必胜。

发现对于某个先手的起点 $s$，后手必胜的充要条件是存在一条牛逼边 $(u, v)$，满足：

$s > u$，使得先手不会把岛屿 $u$ 干掉。
记 $f_u$ 为后手从 1 到 $u$ 的最短路的长度，有 $s < v - (f_{u} + 1)$，使得后手可以比先手更早地到达 $v$，将先手到达终点的必经之路干掉。

于是考虑拓扑排序 DP 求得从 1 到每个节点的最短路径，在此过程中对于每个节点 $u$ 枚举所有出边 $(u, v)$，则对于先手的起点 $s\in [u + 1, v - (f_{u} + 1) - 1]$ 均为后手必胜的，可通过差分维护。

最后还原答案序列输出即可，总时间复杂度 $O(n + m)$ 级别。

虽然赛时懒得想了真的写了拓扑排序但实际上并无必要，拓扑序实际上即 $1\sim n$，直接大力枚举即可。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, m;
int edgenum, into[kN], head[kN], v[kN << 1], ne[kN << 1];
int ans[kN], f[kN];
//=============================================================
void addedge(int u_, int v_) {
  v[++ edgenum] = v_;
  ne[edgenum] = head[u_];
  head[u_] = edgenum;

  ++ into[v_];
}
void topsort() {
  std::queue<int> q;
  for (int i = 1; i <= n; ++ i) f[i] = kN;
  f[1] = 0;
  q.push(1);

  while (!q.empty()) {
    int u_ = q.front(); q.pop();
    for (int i = head[u_]; i; i = ne[i]) {
      int v_ = v[i];
      f[v_] = std::min(f[v_], f[u_] + 1);
      int l = u_ + 1, r = v_ - (f[u_] + 1) - 1;
      if (l <= r) ++ ans[l], -- ans[r + 1];

      if (!(-- into[v_])) q.push(v_);
    }
  }
}
//=============================================================
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 >> m;
    edgenum = 0;
    for (int i = 1; i <= n; ++ i) head[i] = into[i] = ans[i] = 0;
    for (int i = 1; i < n; ++ i) addedge(i, i + 1);
    for (int i = 1; i <= m; ++ i) {
      int u_, v_; std::cin >> u_ >> v_;
      addedge(u_, v_);
    }
    topsort();
    for (int i = 1; i < n; ++ i) {
      ans[i] += ans[i - 1];
      std::cout << (ans[i] <= 0);
    }
    std::cout << "\n";
  }
  return 0;
}
/*
1
15 3
2 8
4 9
8 15

11000111000111
12345678901234
*/

E1

妈的什么东西怎么开局十分钟就有光速过的

写在最后

学到了什么：

C：想好在写！别看到什么求什么数量啊 k 大值啊就高潮了光速拉个板子过了改了改发现还歹删了唐氏得一批

你说的对按照常理来说现在又是夹带私货环节，为师已经迫不及待地要看 C104 的【中国翻訳】了口牙

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

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

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

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