526互联

Codeforces Round 916 (Div. 3)

发布时间 2023-12-20 23:50:24作者: Luckyblock

目录

写在前面

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

第二天没早八打个 div3 休闲娱乐保持下手感，然而 div3 都 AK 不了了，纯纯废物一个，天天上大学导致的。

唉，一学期碰上好几个 byd 恼弹老师，大学一秒也不想上了，折磨。

马娘台服马上 1.5 周年了好耶，小林历奇我来辣ᕕ(◠ڼ◠)ᕗ

A

水。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    int n = read();
    std::string s; std::cin >> s;
    int ans = 0, cnt[27];
    for (int i = 0; i < 26; ++ i) cnt[i] = i + 1;
    for (int i = 0; i < n; ++ i) -- cnt[s[i] - 'A'];
    for (int i = 0; i < 26; ++ i) ans += (cnt[i] <= 0);
    std::cout << ans << "\n";
  }
  return 0;
}

B

构造：\(1, 2, \cdots, k, n, n-1, \cdots, k+1\)。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    int n = read(), k = read();
    for (int i = 1; i <= k; ++ i) std::cout << i << " ";
    for (int i = n; i > k; -- i) std::cout << i << " ";
    std::cout << "\n";
  }
  return 0;
}

C

发现最优的操作序列一定等价于：

  • 首先连续地取 \(a_1, a_2, \cdots, a_m(m\le k)\)。
  • 然后不断地取 \(\max_{1\le i\le m} b_i\)。

于是枚举上述操作序列中的 \(m\) 检查所有情况取总价值的最大值即可。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, k, a[kN], b[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    n = read(), k = read();
    for (int i = 1; i <= n; ++ i) a[i] = read();
    for (int i = 1; i <= n; ++ i) b[i] = read();
    LL ans = 0, sum = 0, maxval = 0;
    for (int i = 1; i <= std::min(n, k); ++ i) {
      sum += a[i];
      maxval = std::max(maxval, 1ll * b[i]);
      ans = std::max(ans, sum + 1ll * (k - i) * maxval);
    }
    std::cout << ans << "\n";
  }
  return 0;
}

D

如果钦定了 \(x<y<z\) 要求最大化 \(a_x + b_y + c_z\) 就成了傻逼题，考虑枚举 \(y\)，则 \(a_x\) 和 \(c_z\) 分别为 \(a, c\) 的前缀最大值 \(\max_{1\le x<y} a_x\) 和后缀最大值 \(\max_{y<z\le n} c_z\)。

于是仅需枚举 \(x,y,z\) 大小关系的全排列并进行上述过程即可。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
int n, ans, a[3][kN], maxv1[kN], maxv2[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
void solve(int p1_, int p2_, int p3_) {
  maxv1[0] = maxv2[n + 1] = 0;
  for (int i = 1; i <= n; ++ i) maxv1[i] = std::max(maxv1[i - 1], a[p1_][i]);
  for (int i = n; i >= 1; -- i) maxv2[i] = std::max(maxv2[i + 1], a[p2_][i]);
  for (int i = 2; i < n; ++ i) ans = std::max(ans, a[p3_][i] + maxv1[i - 1] + maxv2[i + 1]);
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    n = read();
    for (int i = 1; i <= n; ++ i) a[0][i] = read();
    for (int i = 1; i <= n; ++ i) a[1][i] = read();
    for (int i = 1; i <= n; ++ i) a[2][i] = read();
    ans = 0;
    for (int i = 0; i < 3; ++ i) {
      for (int j = 0; j < 3; ++ j) {
        for (int k = 0; k < 3; ++ k) {
          if (i != j && j != k && i != k) {
            solve(i, j, k);
          }
        }
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

E1/E2

发现题意等价于共有 \(n\) 个物品，Alice 取物品 \(i\) 可以获得价值 \(a_i-1\)，Bob 取物品 \(i\) 可以获得价值 \(b_i -1\)，两方交替取物品直至取完获得价值和差值的最大值。

然后就是 HDU 多校的原了，见：https://www.cnblogs.com/luckyblock/p/17586948.html 中的 7323。

考虑贪心，发现 Alice 取走一个物品可以让自己获得 \(a-1\) 的贡献并让对方获得 \(−(b-1)\) 的贡献，Bob 取走一个物品可以让自己获得 \(b-1\) 的贡献并让对方获得 \(−(a-1)\) 的贡献，于是将物品按照 \((a-1)+(b-1)\) 排序，两个人轮流按顺序取物品即可。

证明见官方题解。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n;
struct AgnesDigital {
  int x, y, z;
} a[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
bool cmp(AgnesDigital fir_, AgnesDigital sec_) {
  return fir_.z > sec_.z;
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    n = read();
    for (int i = 1; i <= n; ++ i) a[i].x = read() - 1;
    for (int i = 1; i <= n; ++ i) a[i].y = read() - 1;
    for (int i = 1; i <= n; ++ i) a[i].z = a[i].x + a[i].y;
    std::sort(a + 1, a + n + 1, cmp);
    LL ans = 0;
    for (int i = 1, j = 1; i <= n; ++ i, j = -j) {
      if (j == 1) ans += a[i].x;
      else ans -= a[i].y;
    }
    printf("%lld\n", ans);
  }
  return 0;
}

F

妈的场上卡这么道傻逼题了 YY 了俩假算法过不了准备下班了突然脑子一抽想了个超级傻逼贪心过了我草呃呃

贪心方法挺多的，这里说下我的感觉还挺简单的做法。

手玩下样例，发现题目中的过程等价于不断地选择一对叶节点配对并将它们删除，则经过若干轮配对后树剩下的部分一定是一条以 1 为根的链，目标实际上就是最小化剩下的这条链的长度。贪心地考虑，应当优先选择深度较深的节点进行配对，使得在减小最长链长度的同时让更多原来的非叶节点成为叶节点来参与配对。则有一个非常显然的贪心，不断地选择两个最深的叶节点并删除即可。

dfs 预处理后优先队列简单实现即可，总时间复杂度 \(O(n\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;
//=============================================================
int n, ans;
int fa[kN], son[kN], dep[kN];
int edgenum, head[kN], v[kN], ne[kN];
bool vis[kN];
std::priority_queue <pr <int, int> > q1;
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
void Add(int u_, int v_) {
  v[++ edgenum] = v_;
  ne[edgenum] = head[u_];
  head[u_] = edgenum;
}
void Init() {
  n = read();

  edgenum = 0, ans = 0;
  for (int i = 1; i <= n; ++ i) {
    head[i] = son[i] = dep[i] = 0;
    vis[i] = 0;
  }
  for (int i = 2; i <= n; ++ i) {
    fa[i] = read();
    Add(fa[i], i);
  }
}
void Dfs(int u_, int fa_) {
  dep[u_] = dep[fa_] + 1;
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    Dfs(v_, u_);
    ++ son[u_];
  }
  if (son[u_] == 0) vis[u_] = 1, q1.push(mp(dep[u_], u_));
}
void solve() {
  while (!q1.empty()) q1.pop();
  Dfs(1, 0);
  while (q1.size() >= 2) {
    int x = q1.top().second; q1.pop();
    int y = q1.top().second; q1.pop();
    ++ ans;
    -- son[fa[x]], -- son[fa[y]];
    if (!son[fa[x]] && !vis[fa[x]]) vis[fa[x]] = 1, q1.push(mp(dep[fa[x]], fa[x]));
    if (!son[fa[y]] && !vis[fa[y]]) vis[fa[y]] = 1, q1.push(mp(dep[fa[y]], fa[y]));
  }
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    Init();
    solve();
    printf("%d\n", ans);
  }
  return 0;
}
/*
1
7
1 2 1 1 3 3

1
7
1 1 3 2 2 4
*/

G1

一种图论做法。

对于某种颜色的两个出现位置 \(p_1, p_2(p_1<p_2)\)，显然当点亮了其中之一后，区间 \([p_1 + 1, p_2 - 1]\) 中的所有位置都可以点亮。于是考虑将所有位置均看做节点，对于每种颜色的两个出现位置 \(p_1, p_2(p_1<p_2)\)，均连边 \(p_1\leftrightarrow p_2\) 与 \(p_1, p_2\rightarrow i (p_1 <i<p_2)\)，然后进行 SCC 缩点。

显然对于某个 SCC 中的节点，只要点亮了其中之一就可以点亮该 SCC 中所有节点与可到达的其他节点。于是第一问的最少需要初始点亮的位置的个数即为缩点后入度为 0 的 SCC 的个数，在这些 SCC 中分别任取一个位置点亮即可。

对于第二问的方案计数，显然这样缩点后所有 SCC 的大小均为偶数 \(2\times k\) 且 \(k\) 为 SCC 中的颜色种类数，则对于一个入度为 0 的 SCC 选择其中初始点亮位置时有 \(2\times k\) 种方案，则总方案数即为所有 入度为 0 的 SCC 大小的乘积。

要连至多 \(O(n^2)\) 级别的边，总时空复杂度为 \(O(n^2)\) 级别。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const LL p = 998244353;
const int kN = 2e3 + 10;
const int kM = kN * kN;
//=============================================================
int n, pos[2][kN], col[kN];
int edgenum, head[kN], v[kM], ne[kM];
int dfnnum, belnum, dfn[kN], low[kN], bel[kN], sz[kN];
int into[kN];
std::stack<int> st;
LL ans1, ans2;
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
void Add(int u_, int v_) {
  v[++ edgenum] = v_;
  ne[edgenum] = head[u_];
  head[u_] = edgenum;
}
void Init() {
  n = read();
  dfnnum = belnum = edgenum = 0;
  ans1 = 0, ans2 = 1;

  for (int i = 1; i <= 2 * n; ++ i) {
    pos[0][i] = pos[1][i] = 0;
    head[i] = 0;
    dfn[i] = low[i] = bel[i] = sz[i] = 0;
    into[i] = 0;
  }

  for (int i = 1; i <= 2 * n; ++ i) {
    int x = col[i] = read();
    if (!pos[0][x]) pos[0][x] = i;
    else pos[1][x] = i;
  } 
  for (int i = 1; i <= n; ++ i) {
    int l = pos[0][i], r = pos[1][i];
    Add(l, r), Add(r, l);
    for (int j = l + 1; j < r; ++ j) {
      Add(l, j), Add(r, j);
    }
  }
}
void Tarjan(int u_) {
  low[u_] = dfn[u_] = ++ dfnnum;
  st.push(u_);
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (!dfn[v_]) {
      Tarjan(v_);
      low[u_] = std::min(low[u_], low[v_]);
    } else {
      low[u_] = std::min(low[u_], dfn[v_]);
    }
  }
  if (dfn[u_] == low[u_]) {
    ++ belnum;
    for (int now = 0; now != u_; st.pop()) {
      now = st.top();
      bel[now] = belnum;
      ++ sz[belnum];
    }
  }
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    Init();
    for (int i = 1; i <= 2 * n; ++ i) {
      if (!dfn[i]) Tarjan(i);
    }
    for (int u_ = 1; u_ <= 2 * n; ++ u_) {
      for (int i = head[u_]; i; i = ne[i]) {
        int v_ = v[i];
        if (bel[u_] != bel[v_]) {
          ++ into[bel[v_]];
        }
      }
    }
    for (int i = 1; i <= belnum; ++ i) {
      if (into[i]) continue;
      ++ ans1;
      ans2 = ans2 * sz[i] % p;
    }
    printf("%lld %lld\n", ans1, ans2);
  }
  return 0;
}
/*
1
2
2 2 1 1
*/

G2

有了 G1 之后发现瓶颈在区间连边上，再看看这个数据范围显然是给线段树优化建图跑的。

然而线段树优化建图后跑完缩点之后再套用上面的统计答案的算法有点小问题，SCC 中仅有原图中的点才对大小有贡献，优化建图中的虚拟节点虽然也会被算进去但是是是无贡献的，且有的入度为 0 的 SCC 仅由虚拟节点构成。

不过也很好解决，先跑一个拓扑排序不断地删除入度为 0 的仅由虚拟节点构成的 SCC，再检查所有入度为 0 的 SCC，将这些 SCC 的大小视为其中的原图中的点的个数即可。

总时空复杂度 \(O(n\log n)\) 级别。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const LL p = 998244353;
const int kN = 2e6 + 10;
const int kM = 1e7 + 10;
//=============================================================
int n, pos[2][kN], col[kN];
int edgenum, head[kN], v[kM], ne[kM];
int dfnnum, belnum, dfn[kN], low[kN], bel[kN], sz[kN];
int into[kN];
std::stack<int> st;
std::vector<int> newv[kN];

int nodenum, rt;
LL ans1, ans2;
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
void Add(int u_, int v_) {
  v[++ edgenum] = v_;
  ne[edgenum] = head[u_];
  head[u_] = edgenum;
}
namespace Seg {
  #define ls lson[now_]
  #define rs rson[now_]
  #define mid ((L_+R_)>>1)
  const int kNode = kN << 2;
  int lson[kNode], rson[kNode];
  void Build(int &now_, int L_, int R_) {
    if (L_ == R_) {
      now_ = L_;
      return ;
    }
    now_ = ++ nodenum;
    Build(ls, L_, mid), Build(rs, mid + 1, R_);
    Add(now_, ls), Add(now_, rs);
  }
  void Modify(int now_, int L_, int R_, int l_, int r_, int u_) {
    if (l_ > r_) return ;
    if (l_ <= L_ && R_ <= r_) {
      Add(u_, now_);
      return ;
    }
    if (l_ <= mid) Modify(ls, L_, mid, l_, r_, u_);
    if (r_ > mid) Modify(rs, mid + 1, R_, l_, r_, u_);
    return ;
  }
  #undef ls
  #undef rs
  #undef mid
}
void Init() {
  n = read();
  for (int i = 1; i <= nodenum; ++ i) {
    newv[i].clear();
    head[i] = 0;
    dfn[i] = low[i] = bel[i] = sz[i] = 0;
    into[i] = 0;
  }
  for (int i = 1; i <= 2 * n; ++ i) {
    pos[0][i] = pos[1][i] = 0;
  }
  dfnnum = belnum = edgenum = 0;
  nodenum = 2 * n, rt = 0;
  ans1 = 0, ans2 = 1;

  for (int i = 1; i <= 2 * n; ++ i) {
    int x = col[i] = read();
    if (!pos[0][x]) pos[0][x] = i;
    else pos[1][x] = i;
  } 
  Seg::Build(rt, 1, 2 * n);
  for (int i = 1; i <= n; ++ i) {
    int l = pos[0][i], r = pos[1][i];
    Add(l, r), Add(r, l);
    Seg::Modify(rt, 1, 2 * n, l + 1, r - 1, l);
    Seg::Modify(rt, 1, 2 * n, l + 1, r - 1, r);
  }
}
void Tarjan(int u_) {
  low[u_] = dfn[u_] = ++ dfnnum;
  st.push(u_);
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (!dfn[v_]) {
      Tarjan(v_);
      low[u_] = std::min(low[u_], low[v_]);
    } else if (!bel[v_]) {
      low[u_] = std::min(low[u_], dfn[v_]);
    }
  }
  if (dfn[u_] == low[u_]) {
    ++ belnum;
    for (int now = 0; now != u_; st.pop()) {
      now = st.top();
      bel[now] = belnum;
      sz[belnum] += (now <= 2 * n);
    }
  }
}
void Topsort() {
  std::queue <int> q;
  for (int i = 1; i <= belnum; ++ i) {
    if (!into[i] && !sz[i]) q.push(i);
  }
  while (!q.empty()) {
    int u_ = q.front(); q.pop();
    for (auto v_: newv[u_]) {
      if (!(-- into[v_]) && !sz[v_]) {
        q.push(v_);
      }
    }
  }
  for (int i = 1; i <= belnum; ++ i) {
    if (into[i] || !sz[i]) continue;
    ++ ans1;
    ans2 = ans2 * sz[i] % p;
  }
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    Init();
    for (int i = 1; i <= nodenum; ++ i) {
      if (!dfn[i]) Tarjan(i);
    }
    for (int u_ = 1; u_ <= nodenum; ++ u_) {
      for (int i = head[u_]; i; i = ne[i]) {
        int v_ = v[i];
        if (bel[u_] != bel[v_]) {
          newv[bel[u_]].push_back(bel[v_]);
          ++ into[bel[v_]];
        }
      }
    }
    Topsort();
    printf("%lld %lld\n", ans1, ans2);
  }
  return 0;
}
/*
1
2
2 2 1 1
*/

写在最后

学到了什么：

  • D：不是所有的 \(a_{n+1}\) 都等于 0，多测不清空，亲人两行泪。
  • G：点亮某个位置后可使其他某些位置也被点亮——可转化为有向图上的缩点问题。

我不要期末考试呜呜

不知道第二轮能不能捡个 ec 名额呃呃、、、唉，菜！