日记

Tue Jan 14 2025

10 分钟

life 日记

1731 字

上午#

考试

考试链接看不懂的题解

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

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

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

代码：

CPP

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#

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)$

最后放代码：

CPP

#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;
}

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

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

日记

https://nahida.cfd/blog/2025-01-14日记/