Codeforces Round 946 (Div. 3) (A-G)

Posted at 2024-05-22 # Competitive Programming # Codeforces

A. Phone Desktop

在一个 $5 \times 3$ 大小的手机上面上摆放 $x$ 个 $1\times 1$ 大小和 $y$ 个 $2 \times 2$ 大小的手机图标。问最小需要多少个屏幕

先摆大的，剩下的空间摆小的。

void solve() {
  int x, y;
  read(x, y);

  int occupy_full = y / 2;
  bool is_remain = y % 2;

  int remain_cell = occupy_full * 7 + is_remain * 11;

  int big = occupy_full + is_remain;
  int small = std::ceil(std::max(x - remain_cell, int(0)) * 1.0 /15);

  std::cout << occupy_full + (is_remain) + std::ceil(mmax((x - remain_cell), 0) * 1.0 / 15);
}

B. Symmetric Encoding

输入一个字符串 $s$ ，将 $s$ 进行排序去重后得到 $m$ 。根据映射关系将 $s$ 中每个字符 $s_i$ 找到在 $m$ 中对应的 $c_i$ 并替换为替换为 $c_j$ ，其中 $i + j = \mid m \mid$

 void solve() {
    int a;
    std::cin >> a;
    std::string x;
    std::cin >> x;
    std::string y = x;
    std::sort(all(y));
    y.erase(std::unique(all(y)), y.end());
    std::map<char, char> mp;
    for(int i = 0, end = y.size()-1; i < y.size(); i++, end--){
        mp[y[i]] = y[end];
    }
    for(auto ch: x){
        std::cout << mp[ch];
    }
}

C. Beautiful Triple Pairs

给一个序列 $a(\mid a \mid = n)$ ，构造三元组 $t_i = (a_i, a_{i+1}, a_{i+2})\space, 1\le i \le n-2$

求 $t_i$ 中有多少对三元组中只有一个元素不同

假设现在只求最后一个元素不同的元组有多少对。

设对于 $t_i$ ，前两个元素相同的数量减去三个元素相同的数量，即为和 $t_i$ 相比最后一个元素不同的数量。

void solve() {
  i32 n;
  read(n);
  std::vector<int> a(n);
  reads(all(a));

  std::map<std::pair<int, int>, int> fst, snd, thi;
  std::map<std::array<int, 3>, int> cnt;
  i64 ans = 0;

  for (int i = 0; i < n - 2; i++) {
    int q = a[i], w = a[i + 1], e = a[i + 2];

    ans += fst[{w, e}] - cnt[{q, w, e}];
    ans += snd[{q, e}] - cnt[{q, w, e}];
    ans += thi[{q, w}] - cnt[{q, w, e}];

    fst[{w, e}]++;
    snd[{q, e}]++;
    thi[{q, w}]++;
    cnt[{q, w, e}]++;
  }

  std::cout << ans;
}

D. Ingenuity-2

A和B都能向NSEW四个方向移动，现在给出一个操作序列，将序列中每个元素分给A或B，使A和B在同一个点出发时都能到达同一个终点，且A和B都进行了移动。

如果有两个相同的操作，可以将两个操作分别发给A和B
如果有两个相反的操作（比如N和S），可以将其两者发给A或B
将 NS 发给 A，EW 发给B可确保在可行时 A 和B 都能进行移动

思路很乱，写的又臭又长

void solve() {
    int len;
    std::cin >> len;
    std::string instr;
    std::cin >> instr;
    std::map<char, int> cnt;
    for(auto ch: instr){
        cnt[ch]++;
    }
    std::map<char, int> tmp = cnt;
    cnt['N'] %= 2;
    cnt['S'] %= 2;
    cnt['E'] %= 2;
    cnt['W'] %= 2;
    if(cnt['N'] != cnt['S'] || cnt['E'] != cnt['W']){
        std::cout << "NO";
        return;
    }
    std::map<char, int> p = tmp;
    p['N'] -= cnt['N'];
    p['S'] -= cnt['S'];
    p['E'] -= cnt['E'];
    p['W'] -= cnt['W'];

    char flipChar = 'N';
    if(p['N'] > 0 && p['N'] % 2 == 0){
        flipChar = 'N';
    }else if(p['S'] > 0 && p['S'] % 2 == 0){
        flipChar = 'S';
    }else if(p['E'] > 0 && p['E'] % 2 == 0){
        flipChar = 'E';
    }else if(p['W'] > 0 && p['W'] % 2 == 0){
        flipChar = 'W';
    }


    std::string seq;
    int Hcnt = 0, Rcnt =0;


    for(auto ch: instr){
        if(p[ch] != 0) {
            if(p[ch] % 2){
                if(flipChar == ch){
                    seq.push_back('H');
                    Hcnt++;
                }else{
                    seq.push_back('R');
                    Rcnt++;
                }
            }else{
                if(flipChar == ch){
                    seq.push_back('R');
                    Rcnt++;

                }else{
                    seq.push_back('H');
                    Hcnt++;
                }
            }
            p[ch]--;
        }else if(ch == 'N' || ch == 'S') {
            seq.push_back('R');
            Rcnt++;
        }else{
            seq.push_back('H');
            Hcnt++;
        }
    }
    if(Rcnt == 0 || Hcnt==0){
        std::cout << "NO";
    }else{
        std::cout << seq;
    }
}

E. Money Buys Happiness

小 C 每个月赚 $x$ 元，在 $m$ 个月中每个月都可以花费 $c_i$ 元获取 $h_i$ 的快乐值，这种操作最多进行1次。

$m$ 个月后小 C 的快乐值最大是多少

似乎是 PTA 上的原题

注意数据范围发现 $m$ 和 $h$ 出奇的小，故可以将背包的维度掉转一下。使 $dp[i][j]$ 表示第 $i$ 个月有 $h$ 快乐的时候花了多少钱

那么就有 $dp[i][j] = \begin{cases}\max\left(dp[i-1][j-h[i]] - c[i] + x,dp[i-1][j] + x\right) &, j - h[i] \ge 0 \\ dp[i][j] = dp[i - 1][j] + x &, \text{Otherwise}\end{cases}$

int dp[67][50017];

void solve(){
    int m, x;
    read(m, x);
    std::vector<int> c(m + 1), h(m + 1);
    int max_h = 50010;
    for (int i = 1; i <= m; i++){
        read(c[i], h[i]);
    }

    std::memset(dp, -0x3f, sizeof(dp));
    dp[0][0] = 0;

    for (int i = 1; i <= m; i++){
        for (int j = 0; j <= max_h; j++){
            if (j - h[i] >= 0 && dp[i - 1][j - h[i]] >= c[i]){
                dp[i][j] = std::max(dp[i - 1][j - h[i]] - c[i] + x, dp[i-1][j] + x);
            }else{
                dp[i][j] = dp[i - 1][j] + x;
            }
        }
    }
    int ans = 0;
    for (int j = 0; j <= max_h; j++){
        if (dp[m][j] >= 0){
            ans = mmax(ans, j);
        }
    }
    std::cout << ans;
}

F. Cutting Game

有 $a\times b$ 大小的格子，上面摆有 $n$ 个物品。A 和 B 轮流从上、下、左或右侧删一定的行或列，每当他们删去的格子上有1个物品时得一分。给出格子、物品和操作，求得分

拿个 set 存位置打暴力即可，注意行列

复杂度 $n\log{n}$

void solve() {
  int a, b, n, m;
  read(a, b, n, m);

  std::set<std::pair<int, int>> rchip, cchip, removed;
  for (int i = 0; i < n; i++) {
    int x, y;
    read(x, y);
    rchip.insert({x, y});
    cchip.insert({y, x});
  }

  int lbound = 1, rbound = b, tbound = 1, bbound = a;

  int point[2] = {0, 0};

  for (int i = 0; i < m; i++) {
    char op;
    int opnum;
    std::cin >> op >> opnum;
    if (op == 'U') {
      while (!rchip.empty() && rchip.begin()->first - tbound < opnum) {
        cchip.erase({rchip.begin()->second, rchip.begin()->first});
        rchip.erase(rchip.begin());
        point[i % 2]++;
      }
      tbound += opnum;
    } else if (op == 'D') {
      while (!rchip.empty() && bbound - rchip.rbegin()->first < opnum) {
        cchip.erase({rchip.rbegin()->second, rchip.rbegin()->first});
        rchip.erase(--rchip.end());
        point[i % 2]++;
      }
      bbound -= opnum;
    } else if (op == 'L') {
      while (!cchip.empty() && cchip.begin()->first - lbound < opnum) {
        rchip.erase({cchip.begin()->second, cchip.begin()->first});
        cchip.erase(cchip.begin());
        point[i % 2]++;
      }
      lbound += opnum;
    } else {
      while (!cchip.empty() && rbound - cchip.rbegin()->first < opnum) {
        rchip.erase({cchip.rbegin()->second, cchip.rbegin()->first});
        cchip.erase(--cchip.end());
        point[i % 2]++;
      }
      rbound -= opnum;
    }
  }
  std::cout << point[0] << " " << point[1];
}

G. Money Buys Less Happiness Now

在 $m$ 个月中每月收入 $x$ 元，每个月都可以花费 $c_i$ 元购买 1 点幸福

输出最大幸福

反悔贪心。由于每次购买的幸福都是1，所以在钱不够是反悔1次总能得到最优解

void solve() {
    int m, x;
    read(m, x);
    std::vector<int> c(m);
    reads(all(c));

    std::priority_queue<int> rec;

    int bag = 0;
    int happ = 0;
    for(auto v: c){
        if(bag < v && !rec.empty() && rec.top() > v){
            // regret
            bag += rec.top();
            rec.pop();
            bag -= v;
            rec.push(v);
        }else if(bag >= v){
            happ++;
            rec.push(v);
            bag-=v;
        }

        bag += x;
    }
    std::cout << happ;
}

Mslxl

Integrate Life