日记 - 伊埃斯的博客站

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

Modular Sequence↗

我们看到 $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↗

诶您猜怎么着？赛时我都想到 $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↗

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↗

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

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

还是放一下代码：

1
#include<bits/extc++.h>
2
#define int long long
3
using namespace std;
4
typedef pair<int,int> pii;
5
int n,m;
6
int a[1005][1005];
7
queue<int> tmp[1005];
8
priority_queue<pii> pend;
9
priority_queue<int> dp[1005];
10
template<typename typ>
11
void clear(priority_queue<typ> &q){while (!q.empty())q.pop();}
12
int get(int x){int res = dp[x].top();dp[x].pop();tmp[x].push(res);return res;}
13
void solve()
14
{
15
    scanf("%lld%lld",&n,&m);
16
    for (int i = 0; i <= n; i++)
17
        clear(dp[i]);
18
    for (int i = 1; i <= n; i++)
19
        for (int j = i; j <= n; j++)
20
            scanf("%lld",a[i] + j);
21
    dp[0].push(0);
22
    for (int i = 1; i <= n; i++)
23
    {
24
        clear(pend);
25
        pend.push({a[1][i],-1});// 放进备选
26
        for (int j = 0; j < i; j++)
27
            pend.push({get(j) + a[j + 2][i],j});// 放进备选
28
        for (int j = 1; j <= m && !pend.empty(); j++)
29
        {
30
            auto [val,id] = pend.top();// 取出最大值
31
            pend.pop();
32
            dp[i].push(val);// 转移
33
            if (~id && !dp[id].empty())
34
                pend.push({get(id) + a[id + 2][i],id});// 将它的下一个放进备选
35
        }
36
        for (int j = 0; j < i; j++)
37
        {
38
            while (!tmp[j].empty())
39
            {
40
                dp[j].push(tmp[j].front());
41
                tmp[j].pop();
42
                // 别忘了还原
43
            }
44
        }
45
    }
46
    while (m--)
47
    {
48
        printf("%lld%c",dp[n].top(),m ? ' ' : '\n');
49
        dp[n].pop();
50
    }
51
}
52
signed main()
53
{
54
    int t;
55
    scanf("%lld",&t);
56
    while (t--)
57
        solve();
58
    return 0;
59
}

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

这个喷不了这个是纯糖。

后日谈

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

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

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

Thanks for reading!

日记

周二 3月 25 2025

983 字 · 6 分钟

life 日记