雅礼 \(2023.12.20\) 习题课记录（讲解版）

前言

Always CF，Never AT。

又双是 CF 题，只能说“水”，AK 了。

水题（只放代码）

B - Two Vessels（CF1872A)

有分别装有 \(a, b\) 单位水的两个杯子，容量无限大。现在有一个勺子，容量为 \(c\)，每次可以从一个杯子里舀一勺不超过 \(c\) 单位的水（\(c\) 可以不是整数），放入另一个杯子中。请问最少需要多少次操作才能使两个杯子里的水量相同。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;

using ll = long long;

#define mtest for (cin >> t; t; -- t)

const int kMaxN = 5e4 + 50, kMaxM = 1.8e5 + 18, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;

ll a, b, c;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  mtest {
    cin >> a >> b >> c;
    ll ans = 0;
    if (a < b) {
      swap(a, b);
    }
    for (; a > b; ++ ans) {
      a -= c, b += c;
    }
    cout << ans << '\n';
  }
  return 0;
}

高级水题 & 低级正常题

C - The Corridor or There and Back Again（CF1872B)

有若干个房间排成一行，其中有 \(n\) 个房间有陷阱，对于这 \(n\) 个房间，它们有两个属性：\(d_i\) 和 \(s_i\)，分别代表标号和陷阱形成的时间，即若你第 \(t\) 秒第一次到达 \(i\) 号房间，\(t+s_i\) 秒时陷阱就会在此房间形成，此后你无法通过此房间。每秒你可以走到与当前房间标号相邻的房间。你需要从 \(1\) 号房间走到 \(k\) 号房间，并且再从 \(k\) 号房间走回 \(1\) 号房间。求 \(k\) 最大是多少。

我们可以发现，当碰到机关时，你最多可以往后走 \((s_i - 1) \div 2\) 个房间了。所以我们的答案就是 \(\min_{i = 1}^{n} d_i + (s_i - 1) \div 2\)。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;

using ll = long long;

#define mtest for (cin >> t; t; -- t)

const int kMaxN = 110, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;

ll n, d, s;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  mtest {
    cin >> n;
    ll ans = kLInf;
    for (int i = 1; i <= n; ++ i) {
      cin >> d >> s;
      ans = min(ans, d + (s - 1) / 2);
    }
    cout << ans << '\n';
  }
  return 0;
}

D - Non-coprime Split（CF1872C）

给出 \(l,r\)，构造一组 \(a,b\) 使满足以下条件：

• \(l \le a+b \le r\)
• \(\gcd(a,b) \neq 1\)

若有多组解，则输出任意一组。

我们可以发现 \(l \sim r\) 区间内，如果一个数 \(n\) 不是质数。设它的最小因数为 \(x\)，那么 \(\gcd(x,\ n - x) = 1\)。所以我们枚举 \(l \sim r\)，如果 \(i\) 不是质数，那么就输出 \(i\) 的最小因数和 \(i - (i\) 的最小因数\()\)。如果 \(l \sim r\) 区间内没有满足条件的 \(i\)，输出 \(-1\)（无解）。时间复杂度 \(O(t·(r - l + 1)·\sqrt{i})\)。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;

using ll = long long;

#define mtest for (cin >> t; t; -- t)

const int kMaxN = 110, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;

ll l, r; 

ll M(ll x) { // 求最小因数
  for (int i = 2; i * i <= x; ++ i) { // 枚举因数
    if (!(x % i)) {
      return i;
    }
  }
  return 0;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  mtest {
    cin >> l >> r;
    bool f = 0;
    for (int i = l; i <= r; ++ i) { // 枚举 l~r 区间
      int r = M(i); // 求最小因数
      if (!r) {
        continue;
      }
      f = 1;
      cout << r << ' ' << i - r << '\n';
      break;
    }
    if (!f) {
      cout << "-1\n"; // 无解
    }
  }
  return 0;
}

G - United We Stand（CF1859A）

一共 \(t\) 组数据，每组数据给定一个长度为 \(n\) 的数组 \(a\)，将其分为两个数组，使得任意第二个数组中的数不可以整除任意第一个数组中的数。

构造题，这种题最简单。

如果 \(a\) 中所有元素相同，无解。否则，我们把 \(a\) 分割成两个数组，\(a_n\) 为第二个数组，然后把 \(a\) 数组从 \(n - 1\) 个元素从后往前遍历，如果当前数与后一个数相同，把它分给第二个数组，否则停止分割。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;

using ll = long long;

#define mtest for (cin >> t; t; -- t)

const int kMaxN = 110, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;

int n, a[kMaxN], ans1[kMaxN], ans2[kMaxN];

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  mtest {
    memset(ans2, 0, sizeof ans2);
    cin >> n;
    int l1 = 0, l2 = 0;
    for (int i = 1; i <= n; ++ i) {
      cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    if (a[1] == a[n]) {
      cout << "-1\n";
    } else {
      ans2[++ l2] = a[n];
      for (int i = n - 1; i >= 1; -- i) {
        if (a[i] == a[i + 1]) {
          ans2[++ l2] = a[i];
        } else {
          break;
        }
      }
      cout << n - l2 << ' ' << l2 << '\n';
      for (int i = 1; i <= n - l2; ++ i) {
        cout << a[i] << ' ';
      }
      cout << '\n';
      for (int i = 1; i <= l2; ++ i) {
        cout << ans2[i] << ' ';
      }
      cout << '\n';
    }
  }
  return 0;
}

E - Plus Minus Permutation（CF1872D）

数学题。

我们尽量在 \(p_{k_1·x}(1 \le k_1 \le \lfloor \frac{n}{x} \rfloor)\) 放大的数，\(p_{k_2·y}(1 \le k_2 \le \lfloor \frac{n}{y} \rfloor)\) 放小的数。套一些公式即可。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;

using ll = long long;

#define mtest for (cin >> t; t; -- t)

const int kMaxN = 110, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;

ll n, x, y;

ll lcm(ll a, ll b) {
  return a / __gcd(a, b) * b;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  mtest {
    cin >> n >> x >> y;
    ll nx = n / x, ny = n / y;
    nx -= n / lcm(x, y), ny -= n / lcm(x, y);
    ll ans = (2 * n - nx + 1) * nx / 2;
    ans -= (ny + 1) * ny / 2;
    cout << ans << '\n';
  } 
  return 0;
}

正常题

接下来的题才算正常题。

F - Serval and Toxel's Arrays（CF1789C）

给你一个零时刻的长度为 \(n\) 的数组 \(a_i\)。

时刻 \(i\ (1 \le i \le m)\) 的数组是在时刻 \(i-1\) 的基础上把位置 \(p_i\) 的数改成 \(v_i\) 得到的。

现在让你求出 \(\sum_{i=0}^m \sum_{j=i+1}^m f(i,j)\)，其中 \(f(i,j)\) 的值为时刻 \(i\) 和时刻 \(j\) 的数组拼起来后一共有几种数字。

我们知道对答案 \(x\) 造成贡献有两种情况：

1. \(a_i\) 含有 \(x\)，但 \(a_j\) 不含有 \(x\)。

2. \(a_i\) 和 \(a_j\) 都含有 \(x\)。

设 \(f_i\) 为 \(i\) 在第 \(f_i\) 中出现过了，可以算出它们贡献分别为 \(s_x(m - s_x + 1)\)， \(\dfrac{(s_x)^2 - s_x}{2}\)。

\(e^{i\pi}\) 年 OI 一场空，不清空数组见祖宗。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;

using ll = long long;

#define mtest for (cin >> t; t; -- t)

const int kMaxN = 4e5 + 40, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;

ll n, m, a[kMaxN], b[kMaxN], c[kMaxN], ans = 0;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  mtest {
    ans = 0;
    cin >> n >> m;
    // 清空数组 清空数组 清空数组
    for (int i = 1; i <= n + m; ++ i) {
      c[i] = 0;
      b[i] = -1;
    }
    // 清空数组 清空数组 清空数组
    for (int i = 1; i <= n; ++ i) {
      cin >> a[i];
      b[a[i]] = 0;
    }
    for (ll i = 1, x, y; i <= m; ++ i) {
      cin >> x >> y;
      if (a[x] != y) {
        c[a[x]] += i - b[a[x]];
        b[a[x]] = -1;
        b[y] = i;
      }
      a[x] = y;
    }
    for (ll i = 1; i <= n + m; ++ i) {
      c[i] += (m - b[i] + 1) * (b[i] != -1);
    }
    for (ll i = 1; i <= n + m; ++ i) {
      ans += c[i] * (m - c[i] + 1) + c[i] * (c[i] - 1) / 2;
    }
    cout << ans << '\n';
  }
  return 0;
}

A - Torn Lucky Ticket（CF1895C）

A 题放压轴，emmmmm……

给出 \(n\) 个长度最多为 \(5\) 的由 \(1\) 到 \(9\) 构成的字符串 \(s\)。求出有多少个 \((i,j)\) 满足 \(s_i + s_j\) 所形成的字符串长度为偶数，并且前半部分的数字之和等于后半部分的数字之和。

我这种做法似乎很稀奇。

我们开一个 map，下标为 pair<long long, long long>，一个存各位数字之和，一个存长度。

每次根据字符串的长度分类讨论：

• \(i = 1\)，只能挑选长度为 \(1\) 的。

• \(i = 2\)，只能挑选长度为 \(2\) 的。

• \(i = 3\)，既可以挑选长度为 \(3\) 的，又可以挑选长度为 \(1\) 的。

• \(i = 4\)，既可以挑选长度为 \(4\) 的，又可以挑选长度为 \(2\) 的。

• \(i = 5\)，可以挑选长度为 \(1, 3, 5\) 的。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <map>

using namespace std;

using ll = long long;

#define mtest for (cin >> t; t; -- t)

const int kMaxN = 2e5 + 20, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;

ll n, ans = 0;
string s[kMaxN];
map<pair<ll, ll>, ll> mp;
vector<ll> v;

void W(ll i, ll len) {
  if (len == 1) {
    ans += mp[{v[i - 1], 1}];
  } else if (len == 2) {
    ans += mp[{v[i - 1], 2}];
  } else if (len == 3) {
    ans += mp[{v[i - 1], 3}];
    ans += mp[{v[i - 1] - 2 * (s[i].back() - '0'), 1}];
    ans += mp[{v[i - 1] - 2 * (s[i].front() - '0'), 1}];
  } else if (len == 4) {
    ans += mp[{v[i - 1], 4}];
    ans += mp[{v[i - 1] - 2 * (s[i].back() - '0'), 2}];
    ans += mp[{v[i - 1] - 2 * (s[i].front() - '0'), 2}];
  } else {
    ans += mp[{v[i - 1], 5}];
    ans += mp[{v[i - 1] - 2 * (s[i].back() - '0'), 3}];
    ans += mp[{v[i - 1] - 2 * (s[i].front() - '0'), 3}];
    ans += mp[{v[i - 1] - 2 * ((s[i].front() - '0') + (s[i][1] - '0')), 1}];
    ans += mp[{v[i - 1] - 2 * ((s[i].back() - '0') + (s[i][3] - '0')), 1}];
  }
} 

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; ++ i) {
    ll cnt = 0;
    cin >> s[i];
    for (int j = 0; j < s[i].size(); ++ j) {
      cnt += s[i][j] - '0';
    }
    v.push_back(cnt);
    ++ mp[{cnt, s[i].size()}];
  }
  for (int i = 1; i <= n; ++ i) {
    W(i, s[i].size());
  }
  cout << ans << '\n';
  return 0;
}

本栏目推荐文章
• 2023年度总结
• 算法练习题
• CSP-J/S 2023 游记
• Libevent [补档-2023-08-29]
• 本地套接字 [补档-2023-07-24]
• UDP通信 [补档-2023-07-22]
• 多路io复用epoll [补档-2023-07-20]
• 多路io复用Select [补档-2023-07-16]
• 多路io复用pool [补档-2023-07-19]
• socket编程 [补档-2023-07-10]

习题 2023 12 20习题2023 12 20 2023 12 20 会议2023 12 20 习题2023 12 27 日记2023 12 20 12.20 12 20 12月20日 12月20日总结 12.20 12 20