OneKuma

OneKuma's Blog

One Lonely Kuma.
github
bilibili
twitter
首頁封存作品集關於

Codeforces Round 935 (Div. 3) 題解

#XCPC167
AI 翻譯
這篇文章透過AI由簡體中文翻譯成繁體中文。查看原文
AI 生成的摘要
比賽包含四個部分：A. 設置營地，B. 煙火，C. 左右房屋，D. 雪費琳姆貓頭鷹。每個部分都有不同的問題和解決方法。

比賽

A. 設置營地#

有 3 種人需要住帳篷，分別有 aa，bb，cc 個，第一種人是小波奇只願意自己住，第二種人是喜多一定要和另外 2 個人一起住，第三種人無所謂。每個帳篷最多住 3 個人，最少需要幾個帳篷？

小波奇自己住，喜多盡可能內部配隊，第三種人填補喜多的空缺，然後除 3 上取整。

B. 煙火#

有兩種煙火，分別在 0,a,2a,3a,…0,a,2a,3a,\dots 和 0,b,2b,3b,…0,b,2b,3b,\dots 時刻綻放，每次綻放持續 m+1m+1 個單位時間，即分別在 [0,m],[a,a+m],[2a,2a+m],[3a,3a+m],…[0,m],[a,a+m],[2a,2a+m],[3a,3a+m],\dots 和 [0,m],[b,b+m],[2b,2b+m],[3b,3b+m],…[0,m],[b,b+m],[2b,2b+m],[3b,3b+m],\dots 時刻是綻放的。對所有時間點，求最大同時有多少個煙火綻放？

顯然，看一下第 mm 時刻有多少個綻放即可，答案是 (1+⌊ma⌋)+(1+⌊mb⌋)(1 + \lfloor \frac{m}{a} \rfloor) + (1 + \lfloor \frac{m}{b}\rfloor) ​。

C. 左右房子#

有一條街有 nn 個住戶，被一條路劃分成左右兩邊，每個住戶有一個住在左邊或右邊的意願 a1,a2,…,ana_1, a_2, \dots, a_n。現在，你要安排這條路的位置，使得左右兩邊都必須至少有住戶數除 2 上取整個人滿意，並且最小化其距離中點的距離，並且最小化道路坐標。

雖然條件很多，但是只需要從左到右枚舉道路放在哪即可，前後記一下前綴和，即可快速判斷合法性。

D. 天使貓頭鷹#

有一排長度為 nn 的隊列，你現在站在隊列最右邊（坐標 n+1n+1）。假設你當前在位置 ii，你每次可以往左邊跳到位置 j<ij < i，花費代價 aj+∑k=j+1ibka_j + \sum_{k=j+1}^{i} b_k。你現在目標跳到小於等於 mm 的某個位置，問最小代價。

原問題相當於每個位置選一個代價 aia_i 或 bib_i 花費，因為每個位置都只會從中選擇其一計算一次，並且最後一次花費的是 aia_i，就能構造出一個合法的跳躍方案。注意，你需要枚舉最後一次的落點是在 [1,m][1,m] 中的某處，因為可能存在 bb 很小 aa 很大的情況。

E. 二分搜尋#

給你一個亂序的長度為 nn 的排列，你可以最多 2 次，任意交換 2 個位置，使得對這個排列運行二分查找能找到答案。

乍一看你似乎要構造一個長度為 ⌊log⁡2n⌋\lfloor \log_2n \rfloor 的序列來讓二分查找正確運行，但其實這就想歪了。可以發現，雖然二分的過程是亂的，但是確實實打實的在縮減目標區間到唯一一個。我們其實只需要讓它隨便運行，然後把答案放到隨便運行的目標位置上即可。

我們在二分的過程中標記一下訪問過哪些位置，那麼剩下的位置都可以隨意交換，最後找一個沒動過的位置換一下即可。注意，在隨便二分的過程中，因為可能半路就找到了答案，這時候需要額外花費一次操作，把答案換到一個別的地方。

反正大概是這麼個意思，隨便亂寫了一通，加了點 assert，但是能過。

F. 基里爾和蘑菇#

給了你 nn 個蘑菇，每個蘑菇有一個權值 a1,a2,a3,…,ana_1,a_2,a_3,\dots,a_n。你可以從中選出 kk 個蘑菇，權值是選出的蘑菇的權值最小值乘 kk。還有一個限制是，有一個排列 p1,p2,p3,…,pnp_1, p_2, p_3, \dots, p_n，若你選擇的 kk 個蘑菇，則這些 ap1,ap2,…,apk−1a_{p_1}, a_{p_2}, \dots, a_{p_{k-1}} 蘑菇的權值清空，無法選擇。求最大權值的前提下，最小選擇個數。

從 11 到 nn（雖然只能大概到一半）枚舉選了幾個蘑菇，維護剩餘蘑菇的前 kk 大，然後清除一下對應的蘑菇。

大概感覺能直接搞個堆就行，但是不想動腦直接貼了個樹狀數組維護第 kk​ 大。

G. 煮粥和粥#

有 nn 個人排成一隊吃飯，有一堆它們在隊列裡排序的規則，問前 DD 時刻內能否每人吃過一次，或者報告不行。

沒寫，大概搞個什麼數據結構維護弄一弄，感覺一堆細節不想寫。

H. GCD 更大#

給你一個大小為 nn 的數組，你現在要將他們分成兩塊，且每塊至少有 2 個元素，第一塊求他們的 gcd⁡\gcd，第二塊求他們的 bitwiseAND⁡\operatorname{bitwise AND} 加上參數 xx。求是否存在一種分割方案，使得第一塊的權值嚴格大於第二塊。

顯然，第一塊的 gcd⁡\gcd 的數只需要 2 個就行了，因為數越多 gcd⁡\gcd 越小；同樣，bitwiseAND⁡\operatorname{bitwise AND}​ 也是數越多越小，但是是符合目標的。

那麼我可以直接枚舉 gcd⁡\gcd，然後怎麼判一判就行了，然後就沒寫也沒細想了，應該差不多能做。

代碼#

A. 設置營地#

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <vector>

using namespace std;

const int inf = 1e9 + 7;
const int maxn = 300000 + 5;

int n, a[maxn];

int main() {
#ifdef DEBUG
  freopen("../assets/in.txt", "r", stdin);
#endif

  int T;
  scanf("%d", &T);
  while (T--) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    int cnt = a;
    cnt += b / 3;
    b %= 3;
    if (b > 0 && b + c < 3) {
      puts("-1");
      continue;
    } else {
      if (b > 0) {
        c -= 3 - b;
        cnt++;
      }
      cnt += (c + 2) / 3;
      printf("%d\n", cnt);
    }
  }

  return 0;
}

B. 煙火#

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <vector>

using namespace std;

const int inf = 1e9 + 7;
const int maxn = 300000 + 5;

int main() {
#ifdef DEBUG
  freopen("../assets/in.txt", "r", stdin);
#endif

  int T;
  scanf("%d", &T);
  while (T--) {
    long long a, b, m;
    scanf("%lld%lld%lld", &a, &b, &m);
    long long ans = 2 + m / a + m / b;
    printf("%lld\n", ans);
  }

  return 0;
}

C. 左右房子#

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <vector>

using namespace std;

const int inf = 1e9 + 7;
const int maxn = 300000 + 5;

int n, pre[maxn], suf[maxn];
char buf[maxn];

int main() {
#ifdef DEBUG
  freopen("../assets/in.txt", "r", stdin);
#endif

  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d%s", &n, buf + 1);
    pre[0] = 0; suf[n + 1] = 0;
    for (int i = 1; i <= n; i++) {
      pre[i] = pre[i - 1] + (buf[i] == '0');
    }
    for (int i = n; i >= 1; i--) {
      suf[i] = suf[i + 1] + (buf[i] == '1');
    }
    pre[n + 1] = pre[n]; suf[0] = suf[1];

    auto check = [&](int p) {
      int l = pre[p];
      int r = suf[p + 1];
      return l >= (p + 1) / 2 && r >= (n - p + 1) / 2;
    };
    int ans = -1;
    for (int i = 0; i <= n; i++) {
      if (check(i)) {
        if (ans == -1 || abs(n - ans - ans) > abs(n - i - i)) {
          ans = i;
        }
      }
    }
    assert(ans != -1);
    printf("%d\n", ans);
  }

  return 0;
}

D. 天使貓頭鷹#

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <vector>

using namespace std;

const int inf = 1e9 + 7;
const int maxn = 300000 + 5;

int n, m, a[maxn], b[maxn];

int main() {
#ifdef DEBUG
  freopen("../assets/in.txt", "r", stdin);
#endif

  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
      scanf("%d", a + i);
    }
    for (int i = 1; i <= n; i++) {
      scanf("%d", b + i);
    }

    long long ans = 0, mn = a[m], sum = 0;
    for (int i = n; i > m; i--) {
      ans += min(a[i], b[i]);
    }
    for (int i = m; i >= 1; i--) {
      mn = min(mn, a[i] + sum);
      sum += b[i];
    }
    printf("%lld\n", ans + mn);
  }

  return 0;
}

E. 二分搜尋#

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <vector>

using namespace std;

const int inf = 1e9 + 7;
const int maxn = 300000 + 5;

int n, x, a[maxn];

void check() {
//  for (int i = 1; i <= n; i++) {
//    printf("%d%c", a[i], " \n"[i == n]);
//  }

  int l = 1, r = n + 1;
  while (r - l > 1) {
    int m = (l + r) / 2;

    if (a[m] <= x) {
      l = m;
    } else {
      r = m;
    }
  }
//  printf(": %d %d\n", l, a[l]);

  assert(r - l == 1 && a[l] == x);
}

int main() {
#ifdef DEBUG
  freopen("../assets/in.txt", "r", stdin);
#endif

  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &n, &x);
    for (int i = 1; i <= n; i++) {
      scanf("%d", a + i);
    }

    vector<pair<int,int>> ans;

    int l = 1, r = n + 1;
    vector<int> visited(n + 1, 0);
    while (r - l > 1) {
      int m = (l + r) / 2;

      if (a[m] == x && r - l > 1) {
        int found = -1;
        for (int i = 1; found == -1 && i <= n; i++) {
          if (!visited[i]) found = i;
        }
        assert(found != -1);
        ans.push_back({ m, found });
        swap(a[m], a[found]);
      }

      visited[m] = 1;

      if (a[m] <= x) {
        l = m;
      } else {
        r = m;
      }
    }

    if (a[l] != x) {
      int found = -1;
      for (int i = 1; found == -1 && i <= n; i++) {
        if (a[i] == x) found = i;
      }
      assert(found != -1 && !visited[found]);
      visited[found] = 1;

      ans.push_back({ found, l });
      swap(a[found], a[l]);
    }

    printf("%d\n", (int) ans.size());
    for (auto& p: ans) {
      printf("%d %d\n", p.first, p.second);
    }

    check();
  }

  return 0;
}

F. 基里爾和蘑菇#

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <vector>

using namespace std;

const int inf = 1e9 + 7;
const int maxn = 300000 + 5;

struct BIT {
  static const int R = 1 << 21;

  int a[R];

  inline int lowbit(int x) { return x & -x; }

  void insert(int i, int v) {
    for (; i < R; i += lowbit(i)) a[i] += v;
  }
  void clear(int i) {
    for (; i < R; i += lowbit(i)) a[i] = 0;
  }

  int findx(int p, int rk) {
    // if (p > R) return -1;
    if (p & 1) {
      // if (p + (a[p] < rk) > R) return -1;
      return p + (a[p] < rk);
    } else {
      if (rk > a[p]) return findx(p + lowbit(p) / 2, rk - a[p]);
      else return findx(p - lowbit(p) / 2, rk);
    }
  }
  int findx(int rk) {
    return findx(R >> 1, rk);
  }
} f;

int n, a[maxn], p[maxn];

int main() {
#ifdef DEBUG
  freopen("../assets/in.txt", "r", stdin);
#endif

  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &n);

    vector<int> lsh;
    auto gid = [&](int x) -> int {
      return int(lsh.end() - lower_bound(lsh.begin(), lsh.end(), x));
    };

    for (int i = 1; i <= n; i++) {
      scanf("%d", a + i);
      lsh.push_back(a[i]);
    }
    for (int i = 1; i <= n; i++) {
      scanf("%d", p + i);
    }

    sort(lsh.begin(), lsh.end());
    lsh.resize(unique(lsh.begin(), lsh.end()) - lsh.begin());
    for (int i = 1; i <= n; i++) {
      f.insert(gid(a[i]), 1);
    }

    long long ans = 0;
    int cnt = 0;
    for (int i = 1; i + i - 1 <= n; i++) {
      int id = f.findx(i);
      int val = lsh[lsh.size() - id];
//      printf("Find: %d %d\n", id, val);
      if (1ll * val * i > ans) {
        ans = 1ll * val * i;
        cnt = i;
      }

      // 刪除
      f.insert(gid(a[p[i]]), -1);
    }

    printf("%lld %d\n", ans, cnt);

    for (int i = 1; i <= n; i++) f.clear(gid(a[i]));
  }

  return 0;
}
載入中......
此文章數據所有權由區塊鏈加密技術和智能合約保障僅歸創作者所有。