ABC 437 心得

A

首先，没啥好说的，答案为 $a \times 12 + b$，也没啥饭堂点。

B

其实这题只需要我们用一个集合存储 $b$ 数组，然后在枚举寻找每一个 $a_i,_j$ 在集合 $b$ 中是否存在，答案为最大存在个数。

int Max = -1e9;
   for (int i = 1;i <= h;i++) {
       int cnt = 0;
       for (int j = 1;j <= w;j++) {
           if (s.find(a[i][j]) != s.end()) {
               cnt++;
           }
       }
       Max = max(Max, cnt);
   }
   cout << Max;

C

这题应该可以看出来是贪心，怎么贪？

初始：

• $\text{坐雪橇重量} = \text{所有} w_i \text{之和}$
• $\text{拉雪橇力量} = 0$

如果 $力量 \geq 重量$，结束

否则：

• 必须把一些驯鹿拉去拉雪橇
  • 每次选择 $p_i + w_i$ 最大 的驯鹿去拉
  • 因为它对 $力量 − 重量$ 的改善最大

重复直到条件满足

$剩下坐着的数量 = N − 拉雪橇数量$

排个序就完了。

const int N = 1e6 + 5;
int T;

struct node {
    int w, p;
    friend bool operator<(node a, node b) {
        return (a.p + a.w) > (b.p + b.w);
    }
}a[N];

signed main() {
    cin >> T;
    for (; T--;) {
        int n, sum = 0, sum1 = 0, now = 0;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i].w >> a[i].p;
            sum1 += a[i].w;
        }
        sort(a + 1, a + n + 1);
        for (int i = 1; i <= n; i++) {
            if (sum >= sum1) break;
            sum += a[i].p, sum1 -= a[i].w, now = i;
        }
        if (sum >= sum1) cout << n - now << "\n";
        else cout << "0\n";
    }
    return 0;
}

饭堂点：没开 long long 被硬控 $10 \ \text{mins}$

D

对于每个 $a_i$，你把 $b$ 分为 $<a_i$ 和 $ >= a_i$的两部分，是不是就把绝对值的问题解决了，然后维护一下 $b$ 的前缀和，在二分就完了。

贡献为：
$$
(b_k < a_i < b_(k+1))
a_i - b_1+ a_i - b_2 … a_i-b_k =
a_i*k - sum(1, k, b[])
$$
大于同理。

signed main() {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    for (int i = 1;i <= m;i++) {
        cin >> b[i];
        sum = (sum + b[i]) % mod;
    }
    sort(b + 1, b + m + 1);
    for (int i = 1;i <= m;i++) {
        s[i] = (s[i - 1] + b[i]) % mod;
    }
    for (int i = 1;i <= n;i++) {
        int now = lower_bound(b + 1, b + m + 1, a[i]) - b;
        ans = ((ans + (((2 * (now - 1) - m) % mod + mod) % mod * (a[i] % mod) % mod) + ((sum - 2 * s[now - 1] % mod + mod) % mod))) % mod;
    }
    cout << ans % mod;
    return 0;
}

饭堂点：

1. 没开 long long
2. 数组开小了