日记

我刚上的青名啊！！！

Serval and Kaitenzushi Buffet# Link to

这个喷不了这个是纯糖。

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

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

Simple Permutation# Link to

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

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

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

Serval and Modulo# Link to

我们发现，当一个 $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)$

Uniform Sum# Link to

泥硕德兑，但是 atcoder 的 rmj 为啥也挂了？

考虑 $\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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include<bits/extc++.h>
#define int long long
using namespace std;
int n,cnta,cntb,_max;
int a[2005],b[2005];
__gnu_pbds::gp_hash_table<int,int> mpa,mpb,tmp;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        _max = max(_max,a[i]);
        if (~a[i])
            mpa[a[i]]++;
        else
            cnta++;
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> b[i];
        _max = max(_max,b[i]);
        if (~b[i])
            mpb[b[i]]++;
        else
            cntb++;
    }
    //重中之重
    for (auto [xa,ya] : mpa)
        for (auto [xb,yb] : mpb)
            if (xa + xb >= _max)
                tmp[xa + xb] += min(ya,yb);

    int ans = 0;
    for (auto [x,y] : tmp)
        ans = max(ans,y);
    if (ans >= n - cnta - cntb)
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

[国家集训队] middle# Link to

设中位数为 $x$，大于等于 $x$ 的置为 $1$，反之置为 $-1$。那么区间和大于等于 $0$ 的一定大于等于实际的中位数。我们就可以二分了。对于每个值维护一个线段树，线段树里存区间和，区间最大前缀和，区间最大后缀和。但是 $n$ 个线段树开不下，于是我们考虑可持久化。

后日谈 # Link to 后日谈

NOIp 是 11 月下旬，现在是 3 月中旬，我还有 8 个月的时间。

然而 6 月就要决定能不能继续冲省选了，所以只有 3 个月了。