Educational Codeforces Round 112 (Rated for Div. 2) [CF-1555]

叔叔我啊

发布于：2021年7月30日

字数：3.4k字

时长：18分钟

A - PizzaForces

PizzaForces is Petya's favorite pizzeria. PizzaForces makes and sells pizzas of three sizes: small pizzas consist of slices, medium ones consist of slices, and large pizzas consist of slices each. Baking them takes , and minutes, respectively.

Petya's birthday is today, and of his friends will come, so he decided to make an order from his favorite pizzeria. Petya wants to order so much pizza that each of his friends gets at least one slice of pizza. The cooking time of the order is the total baking time of all the pizzas in the order.

Your task is to determine the minimum number of minutes that is needed to make pizzas containing at least slices in total. For example:

if friends come to Petya's birthday, he has to order pizzas containing at least slices in total. He can order two small pizzas, containing exactly slices, and the time to bake them is minutes;

if friends come to Petya's birthday, he has to order pizzas containing at least slices in total. He can order a small pizza and a large pizza, containing slices, and the time to bake them is minutes;

if friends come to Petya's birthday, he has to order pizzas containing at least slices in total. He can order small pizzas, medium pizzas and 13 large pizzas, in total they contain slices, and the total time to bake them is minutes;

if only one friend comes to Petya's birthday, he can order a small pizza, and the time to bake it is minutes.

本来应该是用动态规划，但是由于是 A 题。经过仔细阅读不难发现，每一块所需的时间都是，所以问的是组合数大于等于的最小值。

原数为、、，同除以可以得到、、。

证明以下：设有数，若，则必可以得到。

若，则必可以得到。

所以可以得到，若必然可以得到。

回到题目，若，若为偶数，则必然可以由、、相加得到，若为奇数则不行。

所以对进行上取余，不足当作。

#include <iostream>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    long long n;
    cin >> n;
    cout << max(6LL, n + 1) / 2 * 5 << '\n';
  }
}

:hourglass:	:open_file_folder:	:bulb:
62	4.2	朴素

这里再放一个动态规划的算法。、、的最大公倍数为。所以如果则必定可以化简为。在的部分使用贪心，在的部分使用动态规划。因为数据范围小，动态规划使用提前打表的形式。

#include <iostream>
#include <vector>

using namespace std;

int main() {

  int step;
  cin >> step;
  int lcm = 2 * 2 * 2 * 3 * 5;
  vector<int> dp(2 * lcm);
  for (int i = 1; i < 2 * lcm; i++) {
    int v1 = (i - 6) >= 0 ? dp[i - 6] : 0;
    int v2 = (i - 8) >= 0 ? dp[i - 8] : 0;
    int v3 = (i - 10) >= 0 ? dp[i - 10] : 0;
    dp[i] = min({v1 + 15, v2 + 20, v3 + 25});
  }
  while (step--) {
    long long n;
    cin >> n;
    if (n / lcm == 0) {
      cout << dp[n % lcm] << endl;
    } else {
      cout << (1ll * dp[lcm - 1] * (n / lcm - 1) + dp[n % lcm + lcm]) << endl;
    }
  }
}

:hourglass:	:open_file_folder:	:bulb:
62	4.2	动态规划

B - Two Tables

You have an axis-aligned rectangle room with width and height , so the lower left corner is in point and the upper right corner is in .

There is a rectangular table standing in this room. The sides of the table are parallel to the walls, the lower left corner is in , and the upper right corner in .

You want to place another rectangular table in this room with width and height with the width of the table parallel to the width of the room.

The problem is that sometimes there is not enough space to place the second table without intersecting with the first one (there are no problems with tables touching, though).

You can't rotate any of the tables, but you can move the first table inside the room.

Example of how you may move the first table.

What is the minimum distance you should move the first table to free enough space for the second one?

题目给定一个矩形，可以移动改矩形，使得能够放得下另一个。

易见，最简单的方法就是上下或者左右移动，使得能够放下。

思路就很简单：上下能否放下计算上下移动所需的最小距离左右能否放下计算左右移动所需的最小距离

#include <iomanip>
#include <iostream>

using namespace std;

const int INF = int(1e9);

int main() {
  cout << fixed << setprecision(9);
  int t;
  cin >> t;
  while (t--) {
    int W, H;
    int x1, y1, x2, y2;
    int w, h;
    cin >> W >> H;
    cin >> x1 >> y1 >> x2 >> y2;
    cin >> w >> h;
    int ans = INF;
    if (x2 - x1 + w <= W) {
      ans = min(ans, max(0, w - x1));
      ans = min(ans, max(0, x2 - (W - w)));
    }
    if (y2 - y1 + h <= H) {
      ans = min(ans, max(0, h - y1));
      ans = min(ans, max(0, y2 - (H - h)));
    }
    if (ans == INF)
      cout << -1 << endl;
    else
      cout << double(ans) << endl;
  }
  return 0;
}

:hourglass:	:open_file_folder:	:bulb:
78	4.2	朴素

C - Coin Rows

Alice and Bob are playing a game on a matrix, consisting of rows and columns. The cell in the -th row in the -th column contains coins in it.

Initially, both Alice and Bob are standing in a cell . They are going to perform a sequence of moves to reach a cell .

The possible moves are:

Move right — from some cell to ;

Move down — from some cell to .

First, Alice makes all her moves until she reaches . She collects the coins in all cells she visit (including the starting cell).

When Alice finishes, Bob starts his journey. He also performs the moves to reach and collects the coins in all cells that he visited, but Alice didn't.

The score of the game is the total number of coins Bob collects.

Alice wants to minimize the score. Bob wants to maximize the score. What will the score of the game be if both players play optimally?

题目要求 Alice 先选，使得 Bob 能获得的金额尽量小。然后 Bob 再选，使得获得的金额最大。其中 Alice 选中的金额 Bob 中不计入。

仔细研究路线可以发现，Bob 要不就收集下方的金额，要不就收集上方的金额。

所以目标是研究 Alice 发生转角的地方。Alice 转向后，有上层转向下层。所以可以通过一个指针来确定和的最小值。

发生转角后，Bob 的值就成为了上排减去 Alice 经过值和下排减去 Alice 经过值的最大值。

思路就很简单：寻找 Alice 的转折处转折处上方剩余和下方剩余的最大值（即 Bob 获得的值）收集每次的值取最小

#include <iostream>
#include <vector>

using namespace std;

const int INF = 2e9 + 10;

int main() {
  int t;
  cin >> t;
  for (int _ = 0; _ < t; ++_) {
    int n;
    cin >> n;
    vector<vector<int>> a(2, vector<int>(n));
    for (int i = 0; i < 2; ++i) {
      for (int j = 0; j < n; ++j) {
        cin >> a[i][j];
      }
    }
    int ans = INF;
    int sum1 = 0, sum2 = 0;
    for (int i = 0; i < n; ++i) {
      sum1 += a[0][i];
    }
    for (int i = 0; i < n; ++i) {
      sum1 -= a[0][i];
      ans = min(ans, max(sum1, sum2));
      sum2 += a[1][i];
    }
    cout << ans << endl;
  }
}

:hourglass:	:open_file_folder:	:bulb:
249	5.3	贪心

D - Say No to Palindromes

Let's call the string beautiful if it does not contain a substring of length at least , which is a palindrome. Recall that a palindrome is a string that reads the same way from the first character to the last and from the last character to the first. For example, the strings a, , , are palindromes, but the strings , , are not.

Let's define cost of a string as the minimum number of operations so that the string becomes beautiful, if in one operation it is allowed to change any character of the string to one of the first letters of the Latin alphabet (in lowercase).

You are given a string of length , each character of the string is one of the first letters of the Latin alphabet (in lowercase).

You have to answer queries — calculate the cost of the substring of the string from -th to -th position, inclusive.

题目要求修改字符串使得原字符串不包含回文字符串。

经过简单的尝试，使用 abc, acb, bac, bca, cab, cba 作为循环节的字符串才符合要求。如果具有其它字符，则必定会包含回文。

因为不同要求均对同一段字符串进行处理，所以可以先对字符串进行预处理。

预处理的时候会进行字符统计。将字符划分成三个一段，统计如果以 abc, acb, bac, bca, cab, cba 作为循环节不符合的段数。在计算时就可以使用尾减去首来判断当前缺少或重复的字符个数。修改这些字符即可完成要求。

如果左右处于某一段的中间，由于循环节循环，所以已经遍历，不存在漏算。

注：如果使用快速读取技巧时间可以缩短到十分之一。

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  string s;
  cin >> s;
  vector<vector<int>> pr(6, vector<int>(n + 1));
  string t = "abc";
  int cur = 0;
  do {
    for (int i = 0; i < n; ++i)
      pr[cur][i + 1] = pr[cur][i] + (s[i] != t[i % 3]);
    ++cur;
  } while (next_permutation(t.begin(), t.end()));
  while (m--) {
    int l, r;
    cin >> l >> r;
    int ans = n;
    for (int i = 0; i < 6; ++i)
      ans = min(ans, pr[i][r] - pr[i][l - 1]);
    cout << ans << endl;
  }
}

:hourglass:	:open_file_folder:	:bulb:
1107	10.2	前缀和

E - Boring Segments

You are given segments on a number line, numbered from to . The -th segments covers all integer points from to and has a value .

You are asked to select a subset of these segments (possibly, all of them). Once the subset is selected, it's possible to travel between two integer points if there exists a selected segment that covers both of them. A subset is good if it's possible to reach point starting from point in arbitrary number of moves.

The cost of the subset is the difference between the maximum and the minimum values of segments in it. Find the minimum cost of a good subset.

In every test there exists at least one good subset.

题目要求寻找一个长度至少为的区间，使得区间内的最大值与最小值之差最小。

典型的线段树，这里使用延迟更新的线段树来降低时间复杂度。

#include <algorithm>
#include <iostream>
#define lc(x) (x) << 1
#define rc(x) (x) << 1 | 1

using namespace std;

const int maxn = 300005, maxt = 4000005;
int n, m, ans;
int minn[maxt], lazy[maxt];
struct Segment {
  int l, r, v;
} s[maxn];
inline int cmp(Segment a, Segment b) { return a.v < b.v; }
inline void get_lazy(int now, int v) { lazy[now] += v, minn[now] += v; }
inline void push_down(int now) {
  if (lazy[now])
    get_lazy(lc(now), lazy[now]), get_lazy(rc(now), lazy[now]), lazy[now] = 0;
}
void update(int l, int r, int now, int L, int R, int v) {
  if (L <= l && r <= R) {
    get_lazy(now, v);
    return;
  }
  int mid = (l + r) >> 1;
  push_down(now);
  if (L <= mid)
    update(l, mid, lc(now), L, R, v);
  if (mid < R)
    update(mid + 1, r, rc(now), L, R, v);
  minn[now] = min(minn[lc(now)], minn[rc(now)]);
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    cin >> s[i].l >> s[i].r >> s[i].v;
  sort(s + 1, s + 1 + n, cmp);
  ans = s[n].v;
  int l = 1, r = 0;
  while (r < n) {
    r++, update(1, m - 1, 1, s[r].l, s[r].r - 1, 1);
    while (l <= r && minn[1] > 0) {
      ans = min(ans, s[r].v - s[l].v);
      update(1, m - 1, 1, s[l].l, s[l].r - 1, -1), l++;
    }
  }
  cout << ans << endl;
  return 0;
}

:hourglass:	:open_file_folder:	:bulb:
1497	39.0	尺取 + 线段树

F - Good Graph

You have an undirected graph consisting of vertices with weighted edges.

A simple cycle is a cycle of the graph without repeated vertices. Let the weight of the cycle be the XOR of weights of edges it consists of.

Let's say the graph is good if all its simple cycles have weight . A graph is bad if it's not good.

Initially, the graph is empty. Then queries follow. Each query has the next type:

— add edge between vertices and of weight if it doesn't make the graph bad.

For each query print, was the edge added or not.

题解采用了 LCT 圆方树。看提交中有些靠着深搜优化外加读取加速也能过，但是一旦关闭读取加速就会导致超时。

#include <algorithm>
#include <array>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

#define fore(i, l, r) for (int(i) = int(l); (i) < int(r); (i)++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef pair<int, int> pt;

template <class A, class B>
ostream &operator<<(ostream &out, const pair<A, B> &p) {
  return out << "(" << p.x << ", " << p.y << ")";
}
template <class A> ostream &operator<<(ostream &out, const vector<A> &v) {
  fore(i, 0, sz(v)) {
    if (i)
      out << " ";
    out << v[i];
  }
  return out;
}

const int INF = int(1e9);
const li INF64 = li(1e18);

int n, q;
vector<array<int, 3>> es;

inline bool read() {
  if (!(cin >> n >> q))
    return false;
  es.resize(q);
  fore(i, 0, q) {
    cin >> es[i][0] >> es[i][1] >> es[i][2];
    es[i][0]--;
    es[i][1]--;
  }
  return true;
}

vector<vector<pt>> g;

const int LOG = 19;
vector<int> up[LOG];
vector<int> tin, tout;
vector<int> xr;
int T = 0;

void dfs(int v, int p, int curXor) {
  tin[v] = T++;
  xr[v] = curXor;
  up[0][v] = p;
  fore(pw, 1, LOG) up[pw][v] = up[pw - 1][up[pw - 1][v]];

  for (auto [to, w] : g[v]) {
    if (to == p)
      continue;
    dfs(to, v, curXor ^ w);
  }
  tout[v] = T;
}

void buildLCA() {
  fore(pw, 0, LOG) up[pw].resize(n);
  tin.assign(n, -1);
  tout.assign(n, -1);
  xr.assign(n, 0);

  T = 0;
  fore(v, 0, n) {
    if (tin[v] != -1)
      continue;
    dfs(v, v, 0);
  }
}

int isPar(int p, int v) { return tin[p] <= tin[v] && tout[v] <= tout[p]; }

int lca(int u, int v) {
  if (isPar(u, v))
    return u;
  if (isPar(v, u))
    return v;

  for (int pw = LOG - 1; pw >= 0; pw--) {
    if (!isPar(up[pw][v], u))
      v = up[pw][v];
  }
  return up[0][v];
}

vector<int> par, rk;

void init(int n) {
  par.assign(n, 0);
  iota(par.begin(), par.end(), 0);
  rk.assign(n, 1);
}

int top(int v) {
  if (par[v] != v)
    return par[v] = top(par[v]);
  return v;
}

bool unite(int u, int v) {
  u = top(u);
  v = top(v);
  if (u == v)
    return false;
  if (rk[u] < rk[v])
    swap(u, v);
  par[v] = u;
  rk[u] += rk[v];
  return true;
}

vector<int> F;
void inc(int pos, int val) {
  for (; pos < sz(F); pos |= pos + 1)
    F[pos] += val;
}
int sum(int pos) {
  int ans = 0;
  for (; pos >= 0; pos = (pos & (pos + 1)) - 1)
    ans += F[pos];
  return ans;
}

void addOnPath(int v, int l) {
  while (v != l) {
    inc(tin[v], 1);
    inc(tout[v], -1);
    v = up[0][v];
  }
}

inline void solve() {
  init(n);
  g.resize(n);

  vector<int> ans(q, -1);
  fore(i, 0, q) {
    int u = es[i][0];
    int v = es[i][1];
    int x = es[i][2];

    if (unite(u, v)) {
      ans[i] = 1;
      g[u].emplace_back(v, x);
      g[v].emplace_back(u, x);
    }
  }

  buildLCA();
  F.assign(2 * n + 5, 0);

  fore(i, 0, q) {
    if (ans[i] != -1)
      continue;

    ans[i] = 0;
    int u = es[i][0];
    int v = es[i][1];
    int x = es[i][2];

    int xorPath = xr[u] ^ xr[v];
    if ((xorPath ^ x) != 1)
      continue;

    int l = lca(u, v);
    int usedOnPath = sum(tin[u]) + sum(tin[v]) - 2 * sum(tin[l]);
    if (usedOnPath > 0)
      continue;

    ans[i] = 1;
    addOnPath(u, l);
    addOnPath(v, l);
  }

  for (int res : ans)
    cout << (res ? "YES" : "NO") << '\n';
}

int main() {
  cout << fixed << setprecision(15);
  if (read()) {
    solve();
  }
  return 0;
}