日记

昨天祝老问我 dp 要不要加难度，我说加。

Modular Sequence# Link to

我们看到 $a_i$ 可以是 $a_{i - 1} \bmod y$ 也可以是 $a_{i - 1} + y$。那么肯定有 $a_1 \equiv a_2 \equiv a_3 \dots \pmod y$，于是我们判断无解首先就判断 $s \equiv (x \bmod y) \times n \pmod y$。然后我们设 $ans_i = a_i \times y + (x \bmod y)$。那么 $a$ 数组肯定形如 $\{st,st + 1,st + 2,\dots,st + k_0,0,1,2,3,\dots,k_1,0,1,2,3,\dots,k_2,\dots,0,1,2,3,\dots,k_?\}$。且 $\sum\limits_{i = 1}^{n}a_i = \frac{s - (x \bmod y) \times n}{y}$。

然后我尝试贪心构造 $a$，成功的 wrong answer Solution exists, but participant said No (test case 3970)。这个 3970 就很绝望。

正解是 dp，设 $dp_s$ 表示使得 $\sum\limits_{i = 1}^{n}a_i = s$ 的最小 $n$。我们可以通过枚举最后一段的长度来转移。枚举状态 $O(n)$，转移 $O(\sqrt{n})$。合起来 $O(n\sqrt{n})$。然后根据它来判断是否可行。构造合法序列就看它从哪里转移的就行了。

Distance to Different# Link to

诶您猜怎么着？赛时我都想到 $80\%$ 了，然后放弃去看上面的那道了。

我们发现 $b$ 数组一定可以分成几段，最左边的一段单调递减，最右边的一段单调递增。中间的先递增再递减。于是我们设 $dp_{i,j}$ 表示分 $j$ 段，最后一段结尾为 $i$ 的方案数。我们发现，如果一段长度为 $2$ 的区间其实和两段长度为 $1$ 的区间形态一样，于是我们规定中间的段长度不能为 $2$。于是我们有转移：$dp_{i,j} = \sum\limits_{k = 0}^{i - 1}dp_{k,j - 1} - dp_{i - 2,j - 1}$，注意特判第一段和最后一段不需要减 $dp_{i - 2,j - 1}$。

GCD on a grid# Link to

hrl：祝老特有的不识数，1600 ~ 2000 的题里面放 2100，2100 ~ 2400 的题里面放 1900。

我：你就偷着乐吧！

我们发现路径一定经过 $a_{1,1}$。于是我们考虑循环 $a_{1,1}$ 的每一个因数 $i$。看看是否有一条路径只经过模 $i$ 为 $0$ 的数。时间复杂度 $O(n^2)$。带一个 $240$ 左右的常数。因为 $1 \times 10^6$ 的数量级因数最多就 $240$ 多个。

Learning to Paint# Link to

其实老早以前就看过这道题。但是没做。

我们发现，一个位置 $j$ 如果要转移 $i$，那么贡献一定是 $a_{j + 2,i}$，这是不变的。我们就可以设 $dp_i$ 为将前 $i$ 个数分段的最大的 $k$ 个数。转移就是这样：先从 $\forall j \in [-1,i),dp_{j}$ 里取出最大的放进备选里，然后执行 $k$ 次，每次从备选里去最大的一个，并把它接着的下一个放进备选。

还是放一下代码：

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59

#include<bits/extc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
int n,m;
int a[1005][1005];
queue<int> tmp[1005];
priority_queue<pii> pend;
priority_queue<int> dp[1005];
template<typename typ>
void clear(priority_queue<typ> &q){while (!q.empty())q.pop();}
int get(int x){int res = dp[x].top();dp[x].pop();tmp[x].push(res);return res;}
void solve()
{
    scanf("%lld%lld",&n,&m);
    for (int i = 0; i <= n; i++)
        clear(dp[i]);
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            scanf("%lld",a[i] + j);
    dp[0].push(0);
    for (int i = 1; i <= n; i++)
    {
        clear(pend);
        pend.push({a[1][i],-1});// 放进备选
        for (int j = 0; j < i; j++)
            pend.push({get(j) + a[j + 2][i],j});// 放进备选
        for (int j = 1; j <= m && !pend.empty(); j++)
        {
            auto [val,id] = pend.top();// 取出最大值
            pend.pop();
            dp[i].push(val);// 转移
            if (~id && !dp[id].empty())
                pend.push({get(id) + a[id + 2][i],id});// 将它的下一个放进备选
        }
        for (int j = 0; j < i; j++)
        {
            while (!tmp[j].empty())
            {
                dp[j].push(tmp[j].front());
                tmp[j].pop();
                // 别忘了还原
            }
        }
    }
    while (m--)
    {
        printf("%lld%c",dp[n].top(),m ? ' ' : '\n');
        dp[n].pop();
    }
}
signed main()
{
    int t;
    scanf("%lld",&t);
    while (t--)
        solve();
    return 0;
}

这玩意的 clear 调了我 $30$ min。究其原因是没传引用。

这个喷不了这个是纯糖。

后日谈 # Link to 后日谈

yzp 在做图论简单题。然而这些题我老早就做过了。

但是黄色的题啊，我一眼就看出来了，而且 $O(n^2)$ 都能过的题，他看不出来？？？

然后尝试理解线性基，只能感叹数学的神奇。