日记 - 伊埃斯的博客站

上午

考试

考试链接↗ 看不懂的题解↗

T1

首先，想了一个解法，口胡了一下，假了。
然后又想了一个解法，口胡了一下，又假了。
然后也是思考良久，没想出来。

T2

先看特殊性质 $1$ ：全是 A。然后我们口胡一下，发现，如果设变化前的 A 的数量为 $a$ ，变化之后为 $b$ ，那么有 $a \equiv b \mod{3}$ ，于是我们便拿到了 $20$ 分。

然后又去打了一下特殊性质 $2$ ，挂了。

但是，我打完俩特殊性质，脑袋一热，去写 T3 了。

T3

也是先把暴力打出来了，然后又打了一个比暴力跑的还慢的数位 dp。不出所料，只得了 $20$ 分。

总共也是只得了 $60$ 分，本来应该拿 $140$ 的，因为 T2 是一道黄题，我个糖人，没写出来。具体有多糖呢，请听下回分解。

下午

上午先把 T2 改出来了，现在该讲讲有多糖了。

T2

source↗

因为如果一个 A 要变成 B 的话，只可能变成 $2,8,32,\dots$ ，对 $3$ 取模全都是 $2$ 。于是我们可以把 $S$ 和 $T$ 里的 $A$ 看成 $1$ ， $B$ 看成 $2$ 。然后，每次查询他们的区间和是否在模 $3$ 的意义下同余就行了。

T1

source↗

其实第一个想法是半对的，独立计算每一个点的贡献。记录每一个点左上有多少点，右下有多少点，那么就会有他们乘积数量的贡献。但是正解的话还要加一个容斥。

但是还有一个叫做二维数点的东西，听都没听过。

代码：

1
signed main()
2
{
3
    init();
4
    scanf("%lld",&n);
5
    for (int i = 1; i <= n; i++)
6
        scanf("%lld%lld",&a[i].first,&a[i].second);
7
    sort(a + 1,a + n + 1);
8
    for (int i = 1; i <= n; i++)
9
        y[i] = a[i].second;
10

11
    //以下4行是离散化
12
    sort(y + 1,y + n + 1);
13
    m = unique(y + 1,y + n + 1) - y - 1;
14
    for (int i = 1; i <= n; i++)
15
        a[i].second = lower_bound(y + 1,y + m + 1,a[i].second) - y;
16

17
    //以下六行是统计有多少在点i左边的
18
    for (int i = 1; i <= n; i++)
19
    {
20
        pre[i].first = que(a[i].second);
21
        pre[i].second = i - 1 - pre[i].first;
22
        upd(a[i].second,1);
23
    }
24

25
    memset(tree,0,sizeof tree);
26

27
    //以下六行是统计有多少在点i右边的
28
    for (int i = n; i >= 1; i--)
29
    {
30
        suf[i].first = que(a[i].second);
31
        suf[i].second = n - i - suf[i].first;
32
        upd(a[i].second,1);
33
    }
34
    //以下12行是容斥
35
    int ans = (p2[n] - 1) * n % mod;
36
    for (int i = 1; i <= n; i++)
37
    {
38
        ans = (ans + p2[pre[i].first]) % mod;
39
        ans = (ans + p2[pre[i].second]) % mod;
40
        ans = (ans + p2[suf[i].first]) % mod;
41
        ans = (ans + p2[suf[i].second]) % mod;
42
        ans = ((ans - p2[pre[i].first + suf[i].first]) % mod + mod) % mod;
43
        ans = ((ans - p2[pre[i].second + suf[i].second]) % mod + mod) % mod;
44
        ans = ((ans - p2[pre[i].first + pre[i].second]) % mod + mod) % mod;
45
        ans = ((ans - p2[suf[i].second + suf[i].first]) % mod + mod) % mod;
46
    }
47
    printf("%lld",ans);
48
    return 0;
49
}

T4

source↗

先考虑朴素的 dp 方程：设 $dp_{i,j}$ 表示考虑到第 $i$ 个矩阵，前面都合法的方案数。还有 $len_{i} = r_{i} - l_{i}$ ，那么有转移方程：

dp_{i,j} = \min\{dp_{i - 1,k}\} + |l_{i} - j|

当然，还有一个必不可少的限制条件： $k \in [j - len_{i - 1},j + len_{i}]$ 。

我们把 $dp$ 数组换成函数的形式： $dp_{i}(j)$ ，那么很显然，它是一个下凸的函数。

那有人要问了，为啥呢？具体来说， $dp_{0}$ 是一个值为 $0$ 的常值函数，而 $dp_{1}$ 会在它上面加一个绝对值函数，而绝对值函数是下凸的，那么 $dp_{1}$ 肯定就是下凸的了。 $dp_{2}$ 又会在 $dp_{1}$ 上再加一个绝对值函数，俩下凸加起来也是下凸的。

那又有人要问了，为啥俩下凸加起来也是下凸的呢？因为下凸的定义是二阶导恒为正，如果你把俩函数加起来，他们的一阶导相加了，二阶导也就相加了。两个正数又加不出来负数。

根据 zxy 教我们的二次函数求最值方法（这里要推广到凸函数），设这个函数在 $[tmpl,tmpr]$ 的范围内斜率为 $0$ 。那么我们直接开始分类讨论：

dp_{i}(x) = |x - l_{i}| + \begin{cases} dp_{i - 1}(x + len_{i}) & x \in (- \infty,tmpl - l_{i}) \\ dp_{i - 1}(tmpl) & x \in [tmpl - l_{i},tmpr + r_{i}] \\ dp_{i - 1}(x - len_{i - 1}) & x \in (tmpr + r_{i},+ \infty) \end{cases}

先看大括号，那么发现，每次就相当于把 $dp_{i - 1}$ 从某一个 $k = 0$ 的地方分开，左边往左移 $len_{i}$ ，右边往右移 $len_{i - 1}$ ， $tmpl$ 变成 $tmpl - len_{i}$ ， $tmpr$ 变成 $tmpr + len_{i + 1}$ ，对于这个偏移，我们用两个变量记录就行了。

现在我们来看加入绝对值的情况。加入绝对值肯定会让 $l_{i}$ 左右两侧的斜率发生变化，也就是：左边的斜率 $-1$ ，右边的 $+1$ 。然后，我们又来分类讨论啦。

$l_{i}$ 在中间，那么加入之后， $tmpl$ 和 $tmpr$ 肯定就是 $l_{i}$ 了。
$l_{i}$ 在左边，那么现在的 $tmpl$ 和 $tmpr$ 在哪里呢？
我们看，因为右边要 $+1$ ，那么右边原本斜率为 $-1$ 的就变成了中间 $k = 0$ ，而 $l_{i}$ 左边就是斜率变成 $-2$ 。
右边同理。

然后，我们就可以记录每一个在左或者右的拐点，用堆维护，每次就可以取到中间的 $[tmpl,tmpr]$ ，然后再进行操作。

最后一个问题：如何统计答案？
设 $ans_{i}$ 表示 $dp_{i}$ 中间那段 $k = 0$ 的纵坐标。

$l_{i}$ 在中间， $ans_{i} = ans_{i - 1}$
$l_{i}$ 在左边，那么有 $dp_{i}(x) = dp_{i - 1}(x) + |l_{i} - x|$ ，那么有 $ans_{i} = ans_{i - 1} + (tmpl - l_{i})$
右边同理，有 $ans_{i} = ans_{i - 1} + (l_{i} - r)$

最后放代码：

1
#include<bits/extc++.h>
2
#define int long long
3
using namespace std;
4
const int maxn = 1e5 + 5;
5
int n;
6
int l[maxn],r[maxn],len[maxn];
7
priority_queue<int,vector<int>,less<int>>ql;
8
priority_queue<int,vector<int>,greater<int>>qr;
9
signed main()
10
{
11
    scanf("%lld",&n);
12
    for (int i = 1; i <= n; i++)
13
    {
14
        scanf("%lld%lld",l + i,r + i);
15
        len[i] = r[i] - l[i];
16
    }
17

18
    //最开始的拐点只有l[1]
19
    ql.push(l[1]);
20
    qr.push(l[1]);
21

22
    int ans = 0;
23
    for (int i = 2; i <= n; i++)
24
    {
25
        static int pl = 0,pr = 0;
26

27
        //记录偏移量
28
        pl -= len[i];
29
        pr += len[i - 1];
30

31
        //计算tmpl,tmpr
32
        int tmpl = ql.top() + pl;
33
        int tmpr = qr.top() + pr;
34

35
        if (l[i] < tmpl)//在左边的情况
36
        {
37
            ans += tmpl - l[i];
38
            ql.pop();//原来的拐点不对了
39
            //因为左边的斜率-1，右边的斜率+1，那么两边的斜率就会相差2
40
            //在堆里再扔一个长度为0的线段，表现在代码里就是push两次
41
            //这样就可以保证每条相邻的线斜率相差1
42
            ql.push(l[i] - pl);
43
            ql.push(l[i] - pl);
44
            qr.push(tmpl - pr);
45
        }
46
        else if (l[i] > tmpr)
47
        {
48
            //同上
49
            ans += l[i] - tmpr;
50
            qr.pop();
51
            qr.push(l[i] - pr);
52
            qr.push(l[i] - pr);
53
            ql.push(tmpr - pl);
54
        }
55
        else
56
        {
57
            //ans不变
58
            ql.push(l[i] - pl);
59
            qr.push(l[i] - pr);
60
        }
61
    }
62
    printf("%lld",ans);
63
    return 0;
64
}

于是，颓废的一天就这么的过完了。

希望下次模拟赛能够不要切不出糖题。

Thanks for reading!

日记

周二 1月 14 2025

1699 字 · 9 分钟

life 日记