日记 - 伊埃斯的博客站

我刚上的青名啊！！！

Serval and Kaitenzushi Buffet↗

这个喷不了这个是纯糖。

我们发现第 $i$ 盘寿司一定是在 $n - i \times (k + 1) + 1$ 分钟前吃掉，所以我们直接维护一个大根堆。如果当前的位置满足有一个整数 $i$ 使得 $n - i \times (k + 1) + 1$ 等于当前位置的下标，我们就把堆顶取出来。

这道题是个人都会去想 dp 吧？

Simple Permutation↗

你说我怎么糖成这样，黄题都做不来。

一句话：从小往大取，取不到就往下找一个质数取。

我赛时还一个劲的猜结论。

Serval and Modulo↗

我们发现，当一个 $k$ 成立，当且仅当 $a_i - b_i \equiv 0 \pmod k$ ，对于 $\sum a_i - \sum b_i$ 也一样。于是我们枚举 $\sum a_i - \sum b_i$ 的每个因子。然后 $O(n)$ check 它是否合法，总复杂度 $O(n \sqrt n)$

考虑 $\forall i \in [1,n],a_i + b_i = x$ 何时可行。当且仅当 $x \ge \max\limits_{i = 1}^{n}(\max(a_i,b_i))$ 且 $\sum\limits_{i = 1}^{n}[a_i + b_i = x] \ge n - cnta - cntb$ 。其中 $cnta$ 和 $cntb$ 分别表示 $a,b$ 中的 $-1$ 个数。我们可以用 map 记录对于每一个 $x$ 的 $\sum\limits_{i = 1}^{n}[a_i + b_i = x]$ ，然后看最大的是否大于等于 $n - cnta - cntb$ 。

1
#include<bits/extc++.h>
2
#define int long long
3
using namespace std;
4
int n,cnta,cntb,_max;
5
int a[2005],b[2005];
6
__gnu_pbds::gp_hash_table<int,int> mpa,mpb,tmp;
7
signed main()
8
{
9
    ios::sync_with_stdio(0);
10
    cin.tie(0);
11
    cout.tie(0);
12
    cin >> n;
13
    for (int i = 1; i <= n; i++)
14
    {
15
        cin >> a[i];
16
        _max = max(_max,a[i]);
17
        if (~a[i])
18
            mpa[a[i]]++;
19
        else
20
            cnta++;
21
    }
22
    for (int i = 1; i <= n; i++)
23
    {
24
        cin >> b[i];
25
        _max = max(_max,b[i]);
26
        if (~b[i])
27
            mpb[b[i]]++;
28
        else
29
            cntb++;
30
    }
31
    //重中之重
32
    for (auto [xa,ya] : mpa)
33
        for (auto [xb,yb] : mpb)
34
            if (xa + xb >= _max)
35
                tmp[xa + xb] += min(ya,yb);
36

37
    int ans = 0;
38
    for (auto [x,y] : tmp)
39
        ans = max(ans,y);
40
    if (ans >= n - cnta - cntb)
41
        cout << "Yes";
42
    else
43
        cout << "No";
44
    return 0;
45
}