yLOI2020 题解

一扶苏一 · 2020-11-14 22:54:05 · 个人记录

A

本题来源于江苏一道模拟题。原题是给定序列 c_i = \frac 1 i，求有多少对 s，t 满足 c_3, c_s, c_t 构成等差数列。

前 16 个点可以随便乱搞，考察选手推式子的能力。

值得注意的是，如果 b \gt c 并且 d = 1，那么式子显然无解。因此，作为一道签到题，输出一排 0 可以得到 25 分的好成绩。

本题大概唯一的难点在于看到正整数直接考虑数论做法然后误入歧途。经过提示排除，我们直接推式子。

之所以会有 dcx = acy + bxy \Rightarrow dcx - bxy=acy 这一步是我们考虑题目限制看起来像是个枚举条件，而我们要进行枚举需要构造出一个减法的形式来，才能确定枚举的范围，因此考虑项，加法变减法。

注意到变量都是正整数，因此 acy 是正整数，x 是正整数，因此 (dc - by) 是正整数。因此 by \lt dc，即 y \lt \frac{dc} b。由此确定了 y 的枚举范围，枚举即可。时间复杂度 O(dc)。

#include <iostream>

typedef long long int ll;

ll a, b, c, d, T;

int main() {
  for (std::cin >> T; T; --T) {
    std::cin >> a >> b >> c >> d;
    int ans = 0;
    for (ll lim = c * d / b, y = 1; y <= lim; ++y) {
      ll u = a * c * y, v = c * d - b * y;
      if (v <= 0) continue;
      if ((u % v) == 0) ++ans;
    }
    std::cout << ans << std::endl;
  }
  return 0;
}

B

这是校内模拟赛的 Day1A

Algorithm 1

考虑枚举初始属性。显然初始属性不会高于需求的最大值，然后用全排列爆搜每种穿装备顺序。时间复杂度 O(n! \times a \times b )。可以通过前三个子任务，期望得分 30 分。

Algorithm 2

注意到因为要先最小化第一个再最小化第二个，所以两个属性实际上是独立的。也即我们可以不考虑第二个属性，先通过枚举确定第一个属性的最小初始值是多少。然后在此基础上通过枚举确定第二个属性的最小初始值。穿装备的顺序同样可以全排列爆搜。这个算法与第一个算法的区别是，将 a 和 b 分开枚举，而不是乘起来。时间复杂度 O(n! \times \max(a, b))。可以通过前四个子任务，期望得分 40 分。

Algorithm 3

从算法 1 的基础上扩展，考虑去掉全排列枚举的部分。我们可以把所有的装备按照 a 值排序。人物的第一个属性增加时，把所有的 a 值不大于当前属性的装备用一个小根堆维护。这个小根堆以 b 为关键字。人物的第二个属性增加时，把堆中所有 b 不大于当前属性的装备取出并穿戴。也即堆里维护的是当前第一个属性符合要求但是第二个属性不符合要求的装备。

枚举初始属性后，每次需要 O(n \log n) 的时间 check 是否合法。总时间复杂度 O(a \times b \times n\log n)。可以通过子任务 1,2,3,5，期望得分 40 分。

Algorithm 4

把算法 2 同样用算法 3 的方式替换掉全排列的部分，时间复杂度 O(\max(a, b) \times n \log n)，可以通过前六个子任务，期望得分 60 分。

Algorithm 5