伊埃斯的小站
日记

日记

Tue Jan 14 2025
11 分钟
life 日记
1819 字

上午 Link to 上午

考试

考试链接看不懂的题解

T1 Link to T1

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

T2 Link to T2

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

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

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

T3 Link to T3

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

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

下午 Link to 下午

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

T2 Link to T2

source

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

T1 Link to T1

source

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

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

代码：

CPP
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
signed main()
{
    init();
    scanf("%lld",&n);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld",&a[i].first,&a[i].second);
    sort(a + 1,a + n + 1);
    for (int i = 1; i <= n; i++)
        y[i] = a[i].second;

    //以下4行是离散化
    sort(y + 1,y + n + 1);
    m = unique(y + 1,y + n + 1) - y - 1;
    for (int i = 1; i <= n; i++)
        a[i].second = lower_bound(y + 1,y + m + 1,a[i].second) - y;
    
    //以下六行是统计有多少在点i左边的
    for (int i = 1; i <= n; i++)
    {
        pre[i].first = que(a[i].second);
        pre[i].second = i - 1 - pre[i].first;
        upd(a[i].second,1);
    }

    memset(tree,0,sizeof tree);

    //以下六行是统计有多少在点i右边的
    for (int i = n; i >= 1; i--)
    {
        suf[i].first = que(a[i].second);
        suf[i].second = n - i - suf[i].first;
        upd(a[i].second,1);
    }
    //以下12行是容斥
    int ans = (p2[n] - 1) * n % mod;
    for (int i = 1; i <= n; i++)
    {
        ans = (ans + p2[pre[i].first]) % mod;
        ans = (ans + p2[pre[i].second]) % mod;
        ans = (ans + p2[suf[i].first]) % mod;
        ans = (ans + p2[suf[i].second]) % mod;
        ans = ((ans - p2[pre[i].first + suf[i].first]) % mod + mod) % mod;
        ans = ((ans - p2[pre[i].second + suf[i].second]) % mod + mod) % mod;
        ans = ((ans - p2[pre[i].first + pre[i].second]) % mod + mod) % mod;
        ans = ((ans - p2[suf[i].second + suf[i].first]) % mod + mod) % mod;
    }
    printf("%lld",ans);
    return 0;
}

T4 Link to T4

source

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

dpi,j=min⁡{dpi−1,k}+∣li−j∣dp_{i,j} = \min\{dp_{i - 1,k}\} + |l_{i} - j|

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

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

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

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

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

dpi(x)=∣x−li∣+{dpi−1(x+leni)x∈(−∞,tmpl−li)dpi−1(tmpl)x∈[tmpl−li,tmpr+ri]dpi−1(x−leni−1)x∈(tmpr+ri,+∞)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}

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

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

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

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

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

  • lil_{i} 在中间，ansi=ansi−1ans_{i} = ans_{i - 1}
  • lil_{i} 在左边，那么有 dpi(x)=dpi−1(x)+∣li−x∣dp_{i}(x) = dp_{i - 1}(x) + |l_{i} - x|，那么有 ansi=ansi−1+(tmpl−li)ans_{i} = ans_{i - 1} + (tmpl - l_{i})
  • 右边同理，有 ansi=ansi−1+(li−r)ans_{i} = ans_{i - 1} + (l_{i} - r)

最后放代码：

CPP
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
60
61
62
63
64
#include<bits/extc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 5;
int n;
int l[maxn],r[maxn],len[maxn];
priority_queue<int,vector<int>,less<int>>ql;
priority_queue<int,vector<int>,greater<int>>qr;
signed main()
{
    scanf("%lld",&n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld%lld",l + i,r + i);
        len[i] = r[i] - l[i];
    }

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

    int ans = 0;
    for (int i = 2; i <= n; i++)
    {
        static int pl = 0,pr = 0;

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

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

        if (l[i] < tmpl)//在左边的情况
        {
            ans += tmpl - l[i];
            ql.pop();//原来的拐点不对了
            //因为左边的斜率-1，右边的斜率+1，那么两边的斜率就会相差2
            //在堆里再扔一个长度为0的线段，表现在代码里就是push两次
            //这样就可以保证每条相邻的线斜率相差1
            ql.push(l[i] - pl);
            ql.push(l[i] - pl);
            qr.push(tmpl - pr);
        }
        else if (l[i] > tmpr)
        {
            //同上
            ans += l[i] - tmpr;
            qr.pop();
            qr.push(l[i] - pr);
            qr.push(l[i] - pr);
            ql.push(tmpr - pl);
        }
        else
        {
            //ans不变
            ql.push(l[i] - pl);
            qr.push(l[i] - pr);
        }
    }
    printf("%lld",ans);
    return 0;
}

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

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


Telegram
Douban
Reddit
Pocket