「Solution Set」 4.6 小记

· · 个人记录

P3964 [TJOI2013]松鼠聚会

首先小松鼠们对距离的概念是切比雪夫距离。

切比雪夫距离可以转化为曼哈顿距离。

切比雪夫距离原点为 1 的点在数轴上是边长为 2 的正方形上的 8 个点。

然后这个正方形旋转一下再稍微放缩一下就可以变成这样：

我们发现正好对应曼哈顿距离为 1 的 8 个点（注意要包括正方形边上的 4 的个点）

于是我们可以总结出切比雪夫距离转曼哈顿距离的式子：

x'=\frac {x+y} 2 y'=\frac {x-y} 2

同时我们也可以总结出曼哈顿距离转切比雪夫距离的式子：

x'=x+y y'=x-y

这道题要找一个点使得其他所有点到他的切比雪夫距离之和最小。我们转化成曼哈顿距离之后可以将两维分开计算。

对于 x 这一维，首先将点按照 x 排序：\sum\limits_{i=1}^k (x_k-x_i) +\sum\limits_{i=k+1}^n (x_k-x_i)

=-k\times x_k +\sum\limits_{i=1}^k x_i+(n-k)x_k -\sum\limits _{i=k+1}^n x_i =(n-2k)x_k +2\sum\limits_{i=1}^k x_i-\sum\limits_{i=1}^n x_i

然后这样前缀和求一下就行

Submission

[ARC065E] へんなコンパス

这道题给的是曼哈顿距离。

曼哈顿距离不好求的地方在于两维加起来求和。而切比雪夫距离比较好的是只需要求 \max 相等即可。

对于一个点，和他切比雪夫距离相等的就是两种情况。

\begin{cases} |x-x_1| =d\\|y-y_1|\leq d\end{cases}

或

\begin{cases} |y-y_1| =d\\|x-x_1|\leq d\end{cases}

我们枚举每个点，假如钦定 x 相同，那么先按 x 排序，那么符合条件的点显然被框在了一个区间内。这样我们把这个区间内的点都和自己连边，并且他们之间互相连边，这样在同一个联通块内的一定可以互相到达。（同一个区间内的互相连边是因为他们可以通过枚举的点互相到达）

这样对 x 相同的做一遍，对 y 相同的最一遍，注意两遍不能重复统计。

Submission

[ABC280G] Do Use Hexagon Grid 2

我们通过手玩（我玩了一个半小时没玩出来）可以得到一个点到原点之间的距离的定义：

dis=\max\{ |x|,|y|,|x-y|\}

然后我们发发现就是在一个大小为 D 的正方体内可以有多少种点集。

我们转化之后可以钦定两维 x_0,y_0，求出来所有前两维符合要求的点，按第三维排序。我们双指针求出所有点符合要求的点集。

这样显然会算重。我们用一些容斥原理，只需要减掉前两维在 (x_0+1,y_0)+(x_0,y_0+1)-(x_0+1,y_0+1) 的范围内的就行。

Submission

[ABC280Ex] Substring Sort

给若干个字符串，求所有子串中的第 k 大。

显著是板子题。

但是广义 SAM。

就是当 lst 就有对应字符的儿子的时候是没必要新建节点的，而且新建了有时候会错。因为 cur 自己不包含任何有用的信息。这是不合规范的。所以如果有这样的情况直接特判掉，然后在每个字符串开头的时候 lst=1 即可。

void add(char c)
{
    int p=lst;
    if(st[lst].ch.count(c))
    {
        int q=st[p].ch[c];
        if(st[q].len==st[p].len+1) lst=q;
        else
        {
            int clone=++tot; st[clone].len=st[p].len+1; st[clone].fa=st[q].fa;
            st[clone].ch=st[q].ch;
            while(p!=-1&&st[p].ch[c]==q) st[p].ch[c]=clone,p=st[p].fa;
            st[q].fa=clone; lst=clone;
        }
        return;
    }
    int cur=++tot;  st[cur].len=st[lst].len+1;
    while(p!=-1&&!st[p].ch[c]) st[p].ch[c]=cur,p=st[p].fa;
    if(p==-1) st[cur].fa=1;
    else
    {
        int q=st[p].ch[c];
        if(st[q].len==st[p].len+1) st[cur].fa=q;
        else
        {
            int clone=++tot; st[clone].len=st[p].len+1; st[clone].fa=st[q].fa;
            st[clone].ch=st[q].ch;
            while(p!=-1&&st[p].ch[c]==q) st[p].ch[c]=clone,p=st[p].fa;
            st[cur].fa=st[q].fa=clone;
        }
    }   
    lst=cur;
}

然后是求第 k 大子串的方法。

一种是跳 ch 。这样就是每次直接可最小的跳，不重复跳。每次加上这个状态表示的子串数量，这样就知道每种状态表示的子串的 rk 范围。这样每次可以 lower_bound 的。

另外一种是取反，建后缀树。然后求出每种状态表示的位置，然后对后缀树上的儿子排序，之后按顺序遍历后缀树，就能知道每种状态表示的 rk 范围。

Submission

P9169 [省选联考 2023] 过河卒

身败名裂.jpg

说句闲话，今天 cc0000 在小图灵数据上喜提全国最菜女队。

我们观察到棋盘大小为 10\times 10，表示三个棋子的位置只有 10^6 种状态。这样我们可以建图。

然后我们发现这样可能成环。我不会判环。所以我们可以考虑逆向推，从必胜或必败状态推到初始状态。

我们用拓扑排序搜。

如果我们从状态 a 推到状态 b ，假如状态 a 代表红必胜，a 这一步是黑子先走，b 代表的这一步是红子先走，就说明 b 想赢走 a 一定没毛病，并且因为是 bfs ，所以 a 代表的步数一定最少，所以这时候不用管度数，直接把 b 的度数清空，让 b 直接 =dis(a)+1。然后入队就行。

然后巨大卡常。

一个重要的优化就是状态里不用设此时红子还是黑子先走。因为我们可以通过当前的三个位置推到当前走了奇数步还是偶数步知道当前谁先走，这样省掉了一半状态。

写了 5k /jk

Submission

P5105 不强制在线的动态快速排序

我们可以考虑到重复的数字只有一个是有用的。所以本质还是个不可重集合。

然后我们考虑一段连续区间内的权值怎么计算。

我们先考虑从 1 到 n 的值。

\bigoplus\limits_{i=2}^n i^2-(i-1)^2 =\bigoplus\limits_{i=2}^n 2i-1

相当于奇数的异或和。

相当于把最后一位的 1 单独拎出来，然后前面的是正整数的异或和

就是 (\bigoplus \limits_{i=1}^n i)<<1 |(n\&1)

\bigoplus\limits_{i=1}^n i=\begin{cases} 0 & n\mod 4 =0\\ n & n\mod 4 = 1\\ 1 & n\mod 4 =2\\ n-1 & n \mod 4 =3\end {cases}

所以原式就是 val(n)=\begin{cases} 0 & n\mod 4 =0\\ 2n+1 & n\mod 4= 1\\ 2 & n \mod 4 =2\\ 2n-1 & n\mod 4 =3 \end{cases}

这样一段区间 l\sim r 的值就是 val(r)\oplus val(l)（因为不能算 l 的）

然后一段连续区间的就能求了。

我们可以用珂朵莉树维护线段，然后加加减减边界上的权值。再计算每个连续段的权值就行。

用珂朵莉树写细节有点多。

Submission

CF986C Willem, Chtholly and Seniorious

珂朵莉树就行。都是基本操作。

用我自己那个有病的珂朵莉树好像很麻烦。

Submission