赛前模拟2025/8/28

· · 个人记录

:::epigraph[——__H_JM_\] 这绝对是我写过的最神奇的考试题目。 :::

Part 1 赛事纪录（大事祭）

[8:00]() 考场先开 T1，由于昨天写 T1 异常的顺利，因而我十分相信运气会顺延。

[8:30]() 想了 30 分钟，什么都没想出来（除了暴力，部分分），但在这时，我抬头一看，Asa_fish 竟然已经开始对拍了，内心慌张。

[8:40]() 写了一种特殊解，并借此发现了答案小于等于 3 的性质。

[8:50]() 写了一种神奇的做法，并开始对拍。

[9:00]() 开 T2。

[9:30]() T2 直接切掉了，并且开始写 T3。

[10:10]() 听到了旁边的 GYC 一阵欢呼，原来是他 T2 也做出来了。

[11:10]() 写完暴力后一直在想这道题 k=1 时的 DP 方程，费劲脑洞无法征服。

[12:00]() T4 写了一个贪心，写完后一侧大样利，才发现证伪了，还是写的特殊点。

[12:30]() 又检查了一会 T1。

Part 2 题目

T1

:::epigraph[——iChen] T1 都十分简单，如果写不出来，一定是题目在诈骗你 :::

::::info[我当时的考场想法，不想看的跳过]{open} 首先，答案不大于三，为什么呢？

:::info[证明]{open}

aaa|a|a
aaa|a|a
aaa|a|a

像图中这样分割，就算是最坏情况（图中）我们也最多是 3 :::

所以我当时的想法十分简单，既然这是一个万能方法，我直接特判不就是了吗？

可能是由于 Asa 的刺激，我虽然知道这是错的，仍然写了对拍

后来当然错了，于是我有想到了一个 "好办法"。

我直接大胆猜测不存在相同前缀长度超过 1 的情况，然后就这么 Ale ::::

首先我先假设你已经知道了前文中的那个重要结论。

然后

一个直接的思路是枚举 i, j 统计答案。考虑当前已经枚举了一个 i，如何找到最优的 j。对于 b 的长度 < 3 的所有答案可以暴力枚举 j，只有 O(1) 种。如果 b 的长度 > 3，我们就不需要考虑 j 的选取对 a, b 字符串的影响，于是只考虑 LCP(a, c) 和 LCP(b, c) 的贡献。

可以让 LCP(a, c) + LCP(b, c) = 0 当且仅当存在 c_j \neq a_1 \land c_j \neq b_i。否则：如果 a_1 \neq b_i，我们选 j = n - 1 就有 LCP(a, c) + LCP(b, c) = 1，最优；如果 a_1 = b_i，那后面的 c_j 也都和它们相等，LCP(a, c) + LCP(b, c) \geq 2，还是选 j = n - 1 最优。

没啥好说得了，我的方法相当于在他的基础上多枚举了一些，当然完全没有证明

:::success[AC code]{open}

#include <bits/stdc++.h>
using namespace std;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
const int N=1e5+6;
int n;
int T;
int vis[27];
string a,b,c;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
struct node{
    int c[N];
    void add(int x,int k){
        for(int i=x;i<N;i+=(i&-i))
            c[i]+=k;
    }
    int ask(int x){
        int ans=0;
        for(int i=x;i>0;i-=(i&-i))
            ans+=c[i];
        return ans;
    }
}BIT[27];
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
signed main(){
    cin>>T;
    while(T--){
        cin>>n;
        cin>>a>>b>>c;
        a=' '+a;
        b=' '+b;
        c=' '+c;
        for(int i=0;i<26;i++)
            memset(BIT[i].c,0,sizeof BIT[i].c);
        for(int i=1;i<=n;i++){
            BIT[b[i]-'a'].add(i,1);
        }
        int ANS=1e9;
        for(int p=n;p>=3;p--){
            for(int i=0;i<26;i++){
                if(BIT[i].ask(p-1)-BIT[i].ask(1)>0){
                    ANS=min(ANS,(a[1]==(i+'a'))+(a[1]==c[p])+((i+'a')==c[p]));
                }
            }
        }
        cout<<ANS<<'\n';
    }
    return 0;
}

:::

T2

开局先看图

我们可以看一下样例中的 4 是如何出现的

这个图能够连接 (1-4),(1-5), 但为什么他们能连呢？

有两个条件：（x-y）

所以直接用一个树状数组存储路径上的编号（除了 2）

:::success[AC code]{open} code：

#include <bits/stdc++.h>
#define int long long
using namespace std;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
const int N=2e5+5,Mod=1e9+7;
int n;
int ans;
int tot,head[N],ver[N<<1],nxt[N<<1];
struct node{
    int c[N];
    void add(int x,int k){
        for(int i=x;i<N;i+=(i&-i))
            c[i]+=k;
    }
    int ask(int x){
        int ans=0;
        for(int i=x;i>0;i-=(i&-i))
            ans+=c[i];
        return ans;
    }
}BIT;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
void add(int a,int b){
    ver[++tot]=b;
    nxt[tot]=head[a],head[a]=tot;
}
void dfs(int x,int fa){
    ans+=BIT.ask(x-1);
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(y==fa) continue;
        BIT.add(y,1);
        dfs(y,x);
        BIT.add(y,-1);
    }
}
int Pow(int x,int y){
    int ans=1;
    while(y){
        if(y&1) ans=ans*x%Mod;
        x=x*x%Mod,y>>=1;
    }
    return ans;
}
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
signed main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        add(a,b),add(b,a);
    }
    dfs(1,0);
    cout<<Pow(2,ans)<<'\n';
    return 0;
}

:::

T3

:::epigraph[——__H_J_M__] 这不是人做的，Maybe :::

暴力 \color{#52c41a} \mathcal {25tps}

:::info[TJ(仅供参考，防止PDF)]

巡逻网络

k = 1

先考虑 k = 1，也即一维的情况。

整个题的贡献可以拆为三个部分：固定点内部互相的贡献、固定点与可选点之间的贡献、可选点内部互相的贡献。

第一种贡献是个定值，可以预处理出来；第二种贡献相当于在选择可选点的时候每个点会有一个额外权值，所以我们主要考虑第三部分，也即可选点内部之间的贡献如何处理。

考虑可选点，由于我们要求的是最大的曼哈顿距离和，且注意到绝对值本身就可以理解成最大值：

|a| + |b| = \max(a + b, a - b, -a + b, -a - b)

也就是说，绝对值比时无关紧要，我们只需要考虑安排好每个数每一维正负号的贡献就好了。

举个例子，假设已经选择了 m 个点，那么你可以先排序成 x_1 \leq x_2 \leq \cdots \leq x_m，然后你按贡献计算 \sum_{i=1}^m (2i - m - 1)x_i = \sum_{j\neq i} |x_i - x_j|。我们实际上只需要枚举 m! 种排列，然后将 \sum_{i=1}^m (2i - m - 1)x_i 的最大值算出来。

所以在一维的情况下，自然可以设一个 DP 出来：设 f(i, S) 表示前 i 个点中，已经设定了一些点位于 S 这些位置的情况下，所能产生的贡献最大值。此处的 S 应当是 m 位二进制数。也就是相当于用块压 DP 枚举了点坐标大小的 m! 种排列。

转移时，把第 i 个点放到第 p 个位置，贡献将会是 (2p - m - 1)x_i + c_i，其中 c_i 表示第 i 个点与其他固定点之间的贡献。如此块压 DP，复杂度是 O(nm^2m)，其中 n 代表可选点数，也即 m + t。

k = 2

其实本质上也没有什么区别，只是现在选择第 i 个点之后要同时考虑 x_i 和 y_i 的位置。

设 f(i, S_1, S_2) 表示前 i 个点中，已经设定了一些点的 x 坐标占据了 S_1 的位置，y 坐标占据了 S_2 的位置，所能产生的贡献最大值。

转移时，把第 i 个点的 x 坐标放到 p_1 的位置，y 坐标放到 p_2 的位置，贡献将会是 (2p_1 - m - 1)x_i + (2p_2 - m - 1)y_i + c_i，复杂度粗略估计一下大概是 O(nm^2m)，已经可以过了。

但是注意到，S_1 和 S_2 互相之间是有限制的，因为他们总需要保证出现的点数相同，不可能会是 O(4^m) 级别的状态量。实际上考虑枚举两个状态中出现的点数 k，状态量应当为

\sum_{k=0}^m \binom{m}{k}^2

这是 O(\frac{4^m}{\sqrt{m}}) 的。

拓展

考虑一下有多次询问的情况，以及 k = 3.4 的情况怎么做？ :::

T4

···

\color{white} \Huge \textsf {TA不应该出现在这里}

Part 3 展望未来

保T1T2，争T3T4。