Codeforces Round #835 蒟蒻题解

A. Medium Number

题意

给三个不相等的数，找中位数。

思路

三个数的大小关系总共有六种情况，枚举即可。

但如果追求快速，考虑对数组进行排序。

代码

#include <bits/stdc++.h>
using namespace std;

#define ll long long
// #define TEST
#ifdef TEST
#define sep cout << "---------\n"
#define say(n) cout << n << ' ';
#define sayln(n) cout << n << '\n';
#define val(n) cout << #n << " = " << n << ' ';
#define valln(n) cout << #n << " = " << n << '\n'
#else
#define sep
#define say(n)
#define sayln(n)
#define val(n)
#define valln(n)
#endif

const ll N = 100004;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    int a[3];
    cin >> a[0] >> a[1] >> a[2];
    sort(a, a + 3);
    cout << a[1] << endl;
  }
  return 0;
}

B. Atilla's Favorite Problem

题意

大小为 $xx$ 的字典只含有前 $xx$ 个字母。

现给定一个字符串 $ss$，找到最小的字典，使得字符串中每个字母都在字典中出现过。

思路

考虑贪心，找到字符串中字典序最大的字母即可。

代码

#include <bits/stdc++.h>
using namespace std;

#define ll long long
// #define TEST
#ifdef TEST
#define sep cout << "---------\n"
#define say(n) cout << n << ' ';
#define sayln(n) cout << n << '\n';
#define val(n) cout << #n << " = " << n << ' ';
#define valln(n) cout << #n << " = " << n << '\n'
#else
#define sep
#define say(n)
#define sayln(n)
#define val(n)
#define valln(n)
#endif

const ll N = 100004;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    char str[102];
    cin >> str;
    char max = 'a';
    for (int i = 0; i < n; i++) {
      if (str[i] > max) {
        max = str[i];
      }
    }
    cout << max - 'a' + 1 << endl;
  }
  return 0;
}

C. Advantage

题意

有 $nn$ 个人，每个人有一个力量值 $s_{i}s\_i$，求每个人与剩余所有人中力量最大者的力量差值。

思路

显然题目涉及两种情况：是与不是力量最大者。

那么考虑最大力量 $s_{max}s\_\{max\}$ 和次大力量 $s_{sec}s\_\{sec\}$，

对于最大力量者差值为 $s_{max}-s_{sec}s\_\{max\}\; -\; s\_\{sec\}$，

对于其余的人差值为 $s_i-s_{max}s\_i\; -\; s\_\{max\}$。

代码

#include <bits/stdc++.h>
using namespace std;

#define ll long long
// #define TEST
#ifdef TEST
#define sep cout << "---------\n"
#define say(n) cout << n << ' ';
#define sayln(n) cout << n << '\n';
#define val(n) cout << #n << " = " << n << ' ';
#define valln(n) cout << #n << " = " << n << '\n'
#else
#define sep
#define say(n)
#define sayln(n)
#define val(n)
#define valln(n)
#endif

const ll N = 200004;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    ll n;
    cin >> n;
    ll s[N];
    ll sorted[N];
    for (ll i = 0; i < n; i++) {
      cin >> s[i];
      sorted[i] = s[i];
    }
    sort(sorted, sorted + n);
    for (ll i = 0; i < n; i++) {
      if (s[i] == sorted[n - 1]) {
        cout << sorted[n - 1] - sorted[n - 2] << ' ';
      } else {
        cout << s[i] - sorted[n - 1] << ' ';
      }
    }
    cout << endl;
  }
  return 0;
}

D. Challenging Valleys

题意

对于一个数组，如果有且仅有一个连续的子数组满足

• 每个点相等
• 如果存在左侧与之相邻的一个点，这个点的值大于数组每个点的值
• 如果存在右侧与之相邻的一个点，这个点的值大于数组每个点的值

那么这个数组被称为“峡谷”。

现在给定一个数组，判断其是否是峡谷。

思路

容易发现存在几种情况：

• 子数组在边界
• 子数组不在边界
• 子数组长度为 1
• 子数组长度不为 1

考虑通过给整个数组两端添加值最大的点，来消除子数组在边界的情况。

例如，原本是 [1, 2, 3]，两端加点后变为 [1e10, 1, 2, 3, 1e10]。

为了消除子数组长度不为 1 的情况，只需把连续且相等的点合并即可，不影响最终结果。

实现中的小遗憾

我模板里面 N 是 100004，但是本题要求 200004。

我写了一个要扩大 N 的 TODO，但是忘记真的去扩大了，于是 WA 1。

代码

#include <bits/stdc++.h>
using namespace std;

#define ll long long
// #define TEST
#ifdef TEST
#define sep cout << "---------\n"
#define say(n) cout << n << ' ';
#define sayln(n) cout << n << '\n';
#define val(n) cout << #n << " = " << n << ' ';
#define valln(n) cout << #n << " = " << n << '\n'
#else
#define sep
#define say(n)
#define sayln(n)
#define val(n)
#define valln(n)
#endif

const ll N = 200004;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    ll n;
    cin >> n;
    ll id = 1;
    ll a[N];
    ll last = -1;
    for (int i = 0; i < n; i++) {
      ll num;
      cin >> num;
      if (num == last) {
        continue;
      }
      last = num;
      a[id] = num;
      id++;
    }
    a[id] = 1e10;
    id++;
    a[0] = 1e10;
    ll cnt = 0;
    for (int i = 1; i < id - 1; i++) {
      if (a[i - 1] > a[i] && a[i + 1] > a[i]) {
        cnt++;
      }
    }
    if (cnt == 1) {
      cout << "YES" << endl;
    } else {
      cout << "NO" << endl;
    }
  }
  return 0;
}

E. Binary Inversions

题意

对于一个二进制数组，你可以选择翻转其中一个数，也可以选择不翻转。

你的目标是使逆序对数量最多，输出最大可能的逆序对数量。

数组任选两个数，如果较大的数出现在较小的数的前面，那么这是一个逆序对。

思路

考虑贪心，分三种情况：

• 如果能通过把 0 翻转成 1 获得最大逆序对，那么翻转的 0 应该在数组最左侧
• 如果能通过把 1 翻转成 0 获得最大逆序对，那么翻转的 1 应该在数组最右侧
• 不修改数组获得最大逆序对（其实去掉这种情况也能过）

统计逆序对可以采用 CDQ 分治，但是由于数组中只存在 0 和 1，

可以直接统计以每个数结尾的逆序对数量，只需要记录每个数前面的 1 的数量即可。

实现中的小遗憾

最初在找到数组中第一个 0 的时候没有 break，导致对更多的情况进行了穷举，喜提 TLE 1。

代码

#include <bits/stdc++.h>
using namespace std;

#define ll long long
// #define TEST
#ifdef TEST
#define sep cout << "---------\n"
#define say(n) cout << n << ' ';
#define sayln(n) cout << n << '\n';
#define val(n) cout << #n << " = " << n << ' ';
#define valln(n) cout << #n << " = " << n << '\n'
#else
#define sep
#define say(n)
#define sayln(n)
#define val(n)
#define valln(n)
#endif

const ll N = 200004;

bitset<N> a;
ll inv;
// return num of 1
ll countInv(ll l, ll r) {
  if (r - l == 1) {
    ll result = 0;
    if (a[l] == 1)
      result++;
    return result;
  }
  ll m = l + ((r - l) >> 1);
  ll left = countInv(l, m);
  ll right = countInv(m, r);
  inv += left * (r - m - right);
  return left + right;
}
void getInv(ll n) {
  inv = 0;
  countInv(0, n);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    ll n;
    cin >> n;
    for (ll i = 0; i < n; i++) {
      int ax;
      cin >> ax;
      a[i] = ax;
    }
    ll maxInv = 0;
    getInv(n);
    if (inv > maxInv) {
      maxInv = inv;
    }
    for (ll i = 0; i < n; i++) {
      if (a[i] == 0) {
        a[i] = 1;
        getInv(n);
        if (inv > maxInv) {
          maxInv = inv;
        }
        a[i] = 0;
        break;
      }
    }
    for (ll i = n - 1; i >= 0; i--) {
      if (a[i] == 1) {
        a[i] = 0;
        getInv(n);
        if (inv > maxInv) {
          maxInv = inv;
        }
        a[i] = 1;
        break;
      }
    }
    cout << maxInv << endl;
  }
  return 0;
}

F. Quests

题意

总共有 $2\le n\le 2\cdot 10^{5}2\; \backslash le\; n\; \backslash le\; 2\; \backslash cdot\; 10^5$ 个任务，完成第 $ii$ 个任务可以获得 $a_{i}a\_i$ 个硬币，

一天只能完成一个任务，每个任务完成后将有 $kk$ 天不能选择该任务，

例如，$k=2k\; =\; 2$ 时，在第一天完成一个任务，那么在第二、三天都不能选择该任务，到第四天才可以。

你的目标是在 $1\le d\le 2\cdot 10^{5}1\; \backslash le\; d\; \backslash le\; 2\; \backslash cdot\; 10^5$ 天内获得至少 $cc$ 个硬币，

求最大的 $kk$。如果 $kk$ 无穷大，输出 Infinity；找不到 $kk$，则输出 $ImpossibleImpossible$。

思路

容易发现如果更大的 $kk$ 符合要求，那么更小的 $kk$ 也符合。

同时，如果 $k=2\cdot 10^{5}k\; =\; 2\; \backslash cdot\; 10^5$ 符合要求，考虑到 $d\le 2\cdot 10^{5}d\; \backslash le\; 2\; \backslash cdot\; 10^5$，

这说明不需要重复完成任务，因此 $kk$ 可以无穷大。

因此考虑二分 $kk$，只需判断一个 $kk$ 是否符合要求即可。

对于固定的 $kk$，有两种情况：

• $k\le n-1k\; \backslash le\; n\; -\; 1$，那么每天都有任务做
• $k>n-1k\; \backslash gt\; n\; -\; 1$，那么需要间隔，或者每个任务只完成一次就能获得足够的硬币

考虑通过加入大量虚拟的 $00$ 硬币任务来统一上述两种情况，

实际实现时只需要判断数组访问是否越界即可。

考虑贪心，每一天如果能做任务就做任务，而且选择当前能做的硬币最多的任务。

由于 $d\log nd\; \backslash log\; n$ 的复杂度已经能过，可以直接对每一天进行模拟。

不必要的优化

考虑到有大量的重复单元，因此考虑预处理 $a_{i}a\_i$ 前缀和 pre[n]，

这样 pre[i] 代表从 $00$ 选到 $ii$ 获得的硬币数量。

考虑 round = c / pre[k] 和 rem = c % pre[k] 的实际意义，

round 代表选多少轮才能使得剩余需要的硬币数量小于 pre[k]，

rem 表示这时剩余需要的硬币数量。存在两种情况：

• rem == 0
• rem > 0

第一种情况中，考虑到最后的一些零硬币任务可以不选，

需要的时间应当是 (round - 1) * (k + 1) + min(k + 1, n)。

第二种情况中，没有零硬币任务可以不选，因为后面还要选一些任务。

选择的任务数量是最小的 $ii$，使得 pre[i] >= rem。

因此需要的时间应当是 round * (k + 1) + i + 1。

实现中的小遗憾

没有想到统一 $k\le n-1k\; \backslash le\; n\; -\; 1$ 和 $k>n-1k\; \backslash gt\; n\; -\; 1$ 的情况，

同时没有想到可以直接模拟，进行了不必要的优化，

因此消耗了接近一个小时才完成本题。

同时，由于最初并没有考虑到 $k\le n-1k\; \backslash le\; n\; -\; 1$ 的情况，花了 20 分钟写了样例都过不了的代码。

再次出现 for 找到值忘记 break 的情况，导致出现神秘 bug，找了很久。

后来由于没有考虑到 rem == 0 的情况，喜提 WA 1。

总得来说，我在这题的分类讨论能力表现极差，可能是因为前面已经消耗了较多能量。

代码

#include <bits/stdc++.h>
using namespace std;

#define ll long long
// #define TEST
#ifdef TEST
#define sep cout << "---------\n"
#define say(n) cout << n << ' ';
#define sayln(n) cout << n << '\n';
#define val(n) cout << #n << " = " << n << ' ';
#define valln(n) cout << #n << " = " << n << '\n'
#else
#define sep
#define say(n)
#define sayln(n)
#define val(n)
#define valln(n)
#endif

const ll N = 200004;
ll a[N];
ll pref[N];
ll n;
ll c;
ll d;

bool validK(ll k) {
  ll days, round, rem, remDay;
  if (k <= n - 1) {
    round = c / pref[k];
    rem = c % pref[k];
    if (rem == 0) {
      remDay = 0;
    } else {
      for (ll i = 0; i < k + 1; i++) {
        if (pref[i] >= rem) {
          remDay = i + 1;
          break;
        }
      }
    }
    days = (k + 1) * round + remDay;
  } else {
    round = c / pref[n - 1];
    rem = c % pref[n - 1];
    if (rem == 0) {
      remDay = 0;
    } else {
      for (ll i = 0; i < n; i++) {
        if (pref[i] >= rem) {
          remDay = i + 1;
          break;
        }
      }
    }
    if (remDay == 0) {
      days = (k + 1) * (round - 1) + n;
    } else {
      days = (k + 1) * round + remDay;
    }
  }
  val(k);
  val(days);
  valln(d);
  return days <= d;
}

ll searchK(ll l, ll r) {
  if (r - l == 1) {
    if (validK(l)) {
      return l;
    } else {
      return -1;
    }
  }
  ll mid = l + ((r - l) >> 1);
  if (validK(mid)) {
    return searchK(mid, r);
  } else {
    return searchK(l, mid);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    cin >> n >> c >> d;
    for (ll i = 0; i < n; i++) {
      cin >> a[i];
    }
    sort(a, a + n);
    for (ll i = 0; i < n; i++) {
      if (i == 0) {
        pref[i] = a[n - 1];
      } else {
        pref[i] = pref[i - 1] + a[n - 1 - i];
      }
    }
    ll k = searchK(0, N);
    if (k == N - 1) {
      cout << "Infinity" << endl;
    } else if (k == -1) {
      cout << "Impossible" << endl;
    } else {
      cout << k << endl;
    }
  }
  return 0;
}

G. SlavicG's Favorite Problem

题意

判断带边权树中能否从 $aa$ 到 $bb$，使得路径中每条边权的异或结果为 $00$。

除了终点，路径不能经过 $bb$。

允许瞬移一次，瞬移的终点不能是 $bb$，起点任意。

思路

由于异或结果只和起点与终点有关，而且起点终点调换不会改变异或结果，

题目中存在两条路径，一条起点已知，一条终点已知，

考虑统一两条路径，将终点已知的路径的起点和终点调换，这样其为起点已知的路径。

题目等效于找到两点 $c,dc,\; d$，使得 $aa$ 到 $cc$ 路径边权异或结果与 $bb$ 到 $dd$ 边权异或结果相同。

这样，任何路径除了起点，不能经过 $bb$；

$dd$ 为瞬移的终点，因此 $dd$ 不能等于 $bb$。

在树中分别以 $a,ba,\; b$ 为起点进行一次深度优先搜索，

即可算出 $aa$ 到 $cc$ 的路径以及 $bb$ 到 $dd$ 的路径的所有可能的边权异或结果。

只需判断两个集合是否有相同元素，如果有则存在符合题目要求的路径，如果没有则不存在。

如果用数组存储，考虑排序后双指针查找；

如果用 set 存储，直接判断，复杂度即为 $O(n\log n)O(n\; \backslash log\; n)$。

实现中的小遗憾

不清晰等效关系，对题目有所遗忘，导致调了很久才考虑到 $dd$ 不能等于 $bb$ 等细节。

所幸成功 1A，没有造成恶劣影响。

不应合并 dfs 使得代码结构比较反直觉，增加思维量。

用 set 判重代码会更优美，这样可以只创建一个 set，在第二次 dfs 时直接判重。

代码

#include <bits/stdc++.h>
using namespace std;

#define ll long long
// #define TEST
#ifdef TEST
#define sep cout << "---------\n"
#define say(n) cout << n << ' ';
#define sayln(n) cout << n << '\n';
#define val(n) cout << #n << " = " << n << ' ';
#define valln(n) cout << #n << " = " << n << '\n'
#else
#define sep
#define say(n)
#define sayln(n)
#define val(n)
#define valln(n)
#endif

const ll N = 100004;
// to, weight
vector<pair<ll, ll>> edges[N];
ll n, a, b;

inline void init() {
  for (ll i = 1; i <= n; i++) {
    edges[i].clear();
  }
}

inline void add_edge(ll x, ll y, ll w) {
  edges[x].emplace_back(y, w);
  edges[y].emplace_back(x, w);
}

bitset<N> vis;

inline void initDfs() { vis.reset(); }

bool ftlock;

inline void dfs(ll v, ll num, void (*cb)(ll)) {
  if (ftlock) {
    ftlock = false;
  } else {
    cb(num);
  }
  vis[v] = 1;
  for (auto i = edges[v].begin(); i != edges[v].end(); i++) {
    if (!vis[i->first] && i->first != b) {
      dfs(i->first, num ^ i->second, cb);
    }
  }
  vis[v] = 0;
}

vector<ll> choice[2];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  initDfs();
  int t;
  cin >> t;
  while (t--) {
    choice[0].clear();
    choice[1].clear();
    cin >> n >> a >> b;
    init();
    for (ll i = 0; i < n - 1; i++) {
      ll u, v, w;
      cin >> u >> v >> w;
      add_edge(u, v, w);
    }
    ftlock = false;
    dfs(a, 0, [](ll i) {
      choice[0].emplace_back(i);
      say("add a");
      valln(i);
    });
    ftlock = true;
    dfs(b, 0, [](ll i) {
      choice[1].emplace_back(i);
      say("add b");
      valln(i);
    });
    sort(choice[0].begin(), choice[0].end());
    sort(choice[1].begin(), choice[1].end());
    auto ptr0 = choice[0].begin();
    auto ptr1 = choice[1].begin();
    bool result = false;
    while (true) {
      if (*ptr0 == *ptr1) {
        say("Find same");
        valln(*ptr0);
        result = true;
        break;
      } else if (*ptr0 < *ptr1) {
        ptr0++;
        if (ptr0 == choice[0].end()) {
          break;
        }
      } else if (*ptr1 < *ptr0) {
        ptr1++;
        if (ptr1 == choice[1].end()) {
          break;
        }
      }
    }
    cout << (result ? "YES" : "NO") << endl;
  }
  return 0;
}