CSP-S2025游记

XRRRRcode · 2025-11-01 23:25:31 · 生活·游记

Update on 2025.11.7：改正了游记中的错误，更新各题考场代码和分数，少量修改了细节内容。

Update on 2025.11.9：更新了题面。

前言

本文中为满足整体观感，部分区域未采用标准格式。

初赛不说了，88 分，第一次提高组初赛做这么爽。

赛前

6:10 左右起床，吃完金拱门大概 6:40 赶到学校。虚晃一枪，然后逃掉早读溜去机房，路上还遇到了隔壁班班主任兼我们的英语老师，差点被 gank。

到机房晨读树状数组、线段树、Tarjan、最短路还有 KMP（可惜考场上没想到怎么用）。大概 1 个小时这样后开始刷 b 站后来还开了把王者。

9:00 这样就出发了，路上又打了几把王者睡了会儿觉，还给 bjx 大佬拍了合影，想看的私我。

11:30 到杭州，下车以后呈游离态寻找食物。和几个同学一起去了一家黄焖鸡的饭店，那个茄子还怪好吃的（雾

和 bjx 点了菜 AA 下来每人 18.5，总的来说还是肥肠有性价比的。bjx 大佬甚至吃饭的时候都还要给他姐调题，太卷了喵。哦对了，还有 bjx 超绝视角的帅照，想看私我。

过了一会儿吧，和组织失联了，本来准备去喝 luckin coffee，后来还是决定去找波（老师）。找到后她居然让我们做 J 组 T3 和 T4，看到题目两眼一黑，大概就只会暴力和特殊性质，就感觉 S 组已经没希望了。当然像波这种超标的口胡选手肯定是 2 分钟一道直接胡完了。

1:30 集合，然后就 balabala 到考场了（实名举报波带领大约 30 人闯红灯）。进校门时波直接被保安拦下来质问身份，波拼尽全力无法战胜，最后还是我和 bjx 出面解围喵。笑嘻了哈哈哈哈哈哈哈哈。

还有，你知道把考试袋从书包里拿出来时发现上面沾满了像粑粑一样的巧克力酱时的绝望吗……

手机开机放口袋（bushi

赛时

刚坐下没多久坐我右边的社恐（社交恐怖分子）问我借笔（骗你的，其实压根没还），问我多大了，后来还问我是不是前年 NOI 金牌（重名的）。抽象。

T1

看到题目第一时间想到的并不是 DP（这和大部分人貌似不太一样），而是一种接近正解但错误的贪心：当人数等于限制时，每次放入的元素与原序列中价值最小的元素交换。

想了差不多 5 分钟，然后写了大约 20 分钟，确定了这个想法时错误的，遂决定重构。当时也不是很崩溃，毕竟我原本的目标是在 2 个小时以内写完 T1。

其实 OI 比赛灵光乍现还是挺重要的，重构的时候一开始想到了用 priority_queue 维护 3 个序列（复习的时候优先队列做多了导致的）。由此又想到了在原贪心一个个放入的基础上先每次挑选最大值维护 ans，考虑反悔以满足条件，用单次的排序优化掉优先队列插入元素的时间复杂度。注意到大小超过 \frac{n}{2} 的序列至多只有一个，于是可以将多余的元素放置到其他任意序列中而不用考虑超过限制的问题。为保证总价值最大，每次挑选移动后损失最小的元素（可以预处理，并按此排序），在 ans 中减去损失值，直至序列大小达到 \frac{n}{2} 后即可输出答案。

最终单组询问时间复杂度 \Omicron(n \log n)，瓶颈为排序，常数显然比优先队列小很多。

算上试错和调试大约花了 50 分钟，5 分钟时间调整了一下状态开始写 T2。

::::info[题面]

题目描述

小 L 是学校算法协会的成员。在今年的学校社团招新中，小 L 一共招收了 n 个新成员，其中 n 为偶数。现在小 L 希望将他们分到协会不同的部门。

算法协会共设有三个部门，其中第 i (1 \leq i \leq n) 个新成员对第 j (1 \leq j \leq 3) 个部门的满意度为 a_{i,j}。定义一个分配方案的满意度为所有新成员对分配到的部门的满意度之和，也就是说，若将第 i (1 \leq i \leq n) 个新成员分配到了第 d_i \in \{1,2,3\} 个部门，则该分配方案的满意度为 \sum_{i=1}^{n} a_{i,d_i}。

小 L 不希望某一个部门的新成员数量过多。具体地，他要求在分配方案中，不存在一个部门被分配多于 \frac{n}{2} 个新成员。你需要帮助小 L 求出，满足他要求的分配方案的满意度的最大值。

输入格式

本题包含多组测试数据。

输入的第一行包含一个正整数 t，表示测试数据组数。

接下来依次输入每组测试数据，对于每组测试数据：

• 第一行包含一个正整数 n，表示新成员的数量。
• 第 i+1 (1 \leq i \leq n) 行包含三个非负整数 a_{i,1}, a_{i,2}, a_{i,3}，分别表示第 i 个新成员对第 1,2,3 个部门的满意度。

输出格式

对于每组测试数据，输出一行一个非负整数，表示满足小 L 要求的分配方案的满意度的最大值。

输入输出样例 #1

输入 #1

3
4
4 2 1
3 2 4
5 3 4
3 5 1
4
0 1 0
0 1 0
0 2 0
0 2 0
2
10 9 8
4 0 0

输出 #1

18
4
13

说明/提示

【样例 1 解释】

该样例共包含三组测试数据。

对于第一组测试数据，可以将四个新成员分别分配到第 1,3,1,2 个部门，则三个部门的新成员数量分别为 2,1,1，均不超过 \frac{4}{2} = 2，满意度为 4 + 4 + 5 + 5 = 18。

对于第二组测试数据，可以将四个新成员分别分配到第 1,1,2,2 个部门，则三个部门的新成员数量分别为 2,2,0，均不超过 \frac{4}{2} = 2，满意度为 0 + 0 + 2 + 2 = 4。

对于第三组测试数据，可以将两个新成员分别分配到第 2,1 个部门，则三个部门的新成员数量分别为 1,1,0，均不超过 \frac{2}{2} = 1，满意度为 9 + 4 = 13。

【样例 2】

见选手目录下的 \textbf{\textit{club/club2.in}} 与 \textbf{\textit{club/club2.ans}}。

该样例满足测试点 3,4 的约束条件。

【样例 3】

见选手目录下的 \textbf{\textit{club/club3.in}} 与 \textbf{\textit{club/club3.ans}}。

该样例满足测试点 5 \sim 8 的约束条件。

【样例 4】

见选手目录下的 \textbf{\textit{club/club4.in}} 与 \textbf{\textit{club/club4.ans}}。

该样例满足测试点 9 的约束条件。

【样例 5】

见选手目录下的 \textbf{\textit{club/club5.in}} 与 \textbf{\textit{club/club5.ans}}。

该样例满足测试点 15,16 的约束条件。

【数据范围】

对于所有测试数据，保证：

• 对于所有 1 \leq i \leq n，1 \leq j \leq 3，均有 0 \leq a_{i,j} \leq 2 \times 10^4。

::cute-table{tuack}

特殊性质 A：对于所有 1 \leq i \leq n，均有 a_{i,2} = a_{i,3} = 0。

特殊性质 B：对于所有 1 \leq i \leq n，均有 a_{i,3} = 0。

特殊性质 C：对于所有 1 \leq i \leq n，1 \leq j \leq 3，a_{i,j} 均在 [0, 2 \times 10^4] 中独立均匀随机生成。 ::::

::::info[Code(100pts)]

#include<bits/stdc++.h>
using namespace std;
struct Node
{
    int a,b,c,mu;
}x[100005];
bool cmp(Node a,Node b)
{
    return a.mu>b.mu;
}
Node t[4][100005];
int main()
{
    freopen("club.in","r",stdin);
    freopen("club.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T,n;
    cin>>T;
    while(T--)
    {
        cin>>n;
        int maxn=(n>>1);
        int i;
        long long ans=0;
        int cnt[4]={0,0,0,0};
        for(i=1;i<=n;i++)
        {
            cin>>x[i].a>>x[i].b>>x[i].c;
            if(x[i].a>=x[i].b&&x[i].a>=x[i].c)
            {
                ans+=x[i].a;
                x[i].mu=x[i].a-max(x[i].b,x[i].c);
                t[1][++cnt[1]]=x[i];
            }
            else if(x[i].b>=x[i].a&&x[i].b>=x[i].c)
            {
                ans+=x[i].b;
                x[i].mu=x[i].b-max(x[i].a,x[i].c);
                t[2][++cnt[2]]=x[i];
            }
            else
            {
                ans+=x[i].c;
                x[i].mu=x[i].c-max(x[i].a,x[i].b);
                t[3][++cnt[3]]=x[i];
            }
        }
        for(i=1;i<=3;i++)
        {
            if(cnt[i]>maxn)
            {
                sort(t[i]+1,t[i]+cnt[i]+1,cmp);
                int x=0;
                while(cnt[i]>maxn)
                    ans-=t[i][cnt[i]--].mu;
                break;
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}
//Happy,meow.I think this is right.

::::

T2

粗读了一下题意，感觉像最小生成树，思考了一下执行城市化对树上边权的影响，但并没有想到正解。看到特殊性质后决定把 c 当作一条边用，但受空间复杂度限制没有写出来，最后只写了一个接近板子的 Kruskal 求最小生成树（这居然也能拿 32pts，CCF 数据拿脚造的吧）。

T2 花的时间还挺多的，大概有 1 个小时，可惜最后特殊性质没调出来。

::::info[题面]

题目描述

C 国的交通系统由 n 座城市与 m 条连接两座城市的双向道路构成，第 i (1 \leq i \leq m) 条道路连接城市 u_i 和 v_i。任意两座城市都能通过若干条道路相互到达。

然而，近期由于一场大地震，所有 m 条道路都被破坏了，修复第 i (1 \leq i \leq m) 条道路的费用为 w_i。与此同时，C 国还有 k 个准备进行城市化改造的乡镇。对于第 j (1 \leq j \leq k) 个乡镇，C 国对其进行城市化改造的费用为 c_j。在城市化改造完第 j (1 \leq j \leq k) 个乡镇后，可以在这个乡镇与原来的 n 座城市间建造若干条道路，其中在它与第 i (1 \leq i \leq n) 座城市间建造一条道路的费用为 a_{j,i}。C 国可以在这 k 个乡镇中选择任意多个进行城市化改造，也可以不选择任何乡镇进行城市化改造。

为尽快恢复城市间的交通，C 国政 府希望以最低的费用将原有的 n 座城市两两连通，也即任意两座原有的城市都能通过若干条修复或新建造的道路相互到达。你需要帮助他们求出，将原有的 n 座城市两两连通的最小费用。

输入格式

输入的第一行包含三个非负整数 n, m, k，分别表示原有的城市数量、道路数量和准备进行城市化改造的乡镇数量。

输入的第 i+1 (1 \leq i \leq m) 行包含三个非负整数 u_i, v_i, w_i，表示第 i 条道路连接的两座城市与修复该道路的费用。

输入的第 j+m+1 (1 \leq j \leq k) 行包含 n+1 个非负整数 c_j, a_{j,1}, a_{j,2}, \ldots, a_{j,n}，分别表示将第 j 个乡镇进行城市化改造的费用与在该乡镇与原有的城市间建造道路的费用。

输出格式

输出一行一个非负整数，表示将原有的 n 座城市两两连通的最小费用。

输入输出样例 #1

输入 #1

4 4 2
1 4 6
2 3 7
4 2 5
4 3 4
1 1 8 2 4
100 1 3 2 4

输出 #1

13

说明/提示

【样例 1 解释】

C 国政 府可以选择修复第 3 条和第 4 条道路，然后将第 1 个乡镇进行城市化改造，并建造它与第 1,3 座城市间的道路，总费用为 5 + 4 + 1 + 1 + 2 = 13。可以证明，不存在比 13 更小的费用能使原有的 4 座城市两两连通。

【样例 2】

见选手目录下的 road/road2.in 与 road/road2.ans。

该样例满足测试点 11,12 的约束条件。

【样例 3】

见选手目录下的 road/road3.in 与 road/road3.ans。

该样例满足测试点 13,14 的约束条件。

【样例 4】

见选手目录下的 road/road4.in 与 road/road4.ans。

该样例满足测试点 15,16 的约束条件。

【数据范围】

对于所有测试数据，保证：

• 对于所有 1 \leq i \leq m，均有 1 \leq u_i, v_i \leq n, u_i \neq v_i 且 0 \leq w_i \leq 10^9;
• 对于所有 1 \leq j \leq k，均有 0 \leq c_j \leq 10^9;
• 对于所有 1 \leq j \leq k，1 \leq i \leq n, 均有 0 \leq a_{j,i} \leq 10^9;
• 任意两座原有的城市都能通过若干条原有的道路相互到达。

::cute-table{tuack}

特殊性质 A：对于所有 1 \leq j \leq k，均有 c_j = 0 且均存在 1 \leq i \leq n 满足 a_{j,i} = 0。 ::::

::::info[Code(32pts)]

/*#include<bits/stdc++.h>
using namespace std;
struct Edge
{
    int u,v,w;
}e[1000005];
bool cmp(Edge a,Edge b)
{
    return a.w<b.w;
}
int fa[10005];
int c[10005];
int a[10005];
int ee[10005][10005];
int fid(int a)
{
    if(fa[a]==a)
        return a;
    return fa[a]=fid(fa[a]);
}
void merge(int u,int v)
{
    u=fid(u);
    v=fid(v);
    fa[u]=v;
}
int main()
{
    //freopen("road3.in","r",stdin);
    //freopen("road.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m,k,i,j;
    long long ans=0;
    cin>>n>>m>>k;
    for(i=1;i<=n;i++)
        fa[i]=i;
    for(i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        e[i].u=u,e[i].v=v,e[i].w=w;
    }
    for(i=1;i<=k;i++)
    {
        int x=0;    
        cin>>c[i];
        for(j=1;j<=n;j++)
        {
            cin>>a[j];
            if(a[j]==0)
                x=j;
        }
        if(x)
        {
            for(j=1;j<=n;j++)
                ee[x][j]=a[j];
        }
    }
    sort(e+1,e+m+1,cmp);
    int cnt=n-1;
    for(i=1;i<=m;i++)
    {
        int u=e[i].u,v=e[i].v;
        if(fid(u)!=fid(v)
        {
            ans+=min(e[i].w,min(ee[u][v]?ee[u][v]:1000000007,ee[v][u]?ee[v][u]:1000000007));
            merge(u,v);
            if(!(--cnt))
                break;
        }
    }
    cout<<ans<<'\n';
    return 0;
}
*/
#include<bits/stdc++.h>
using namespace std;
struct Edge
{
    int u,v,w;
}e[1000005];
bool cmp(Edge a,Edge b)
{
    return a.w<b.w;
}
int fa[10005];
int c[10005];
int a[10005];
//int ee[10005][10005];
int fid(int a)
{
    if(fa[a]==a)
        return a;
    return fa[a]=fid(fa[a]);
}
void merge(int u,int v)
{
    u=fid(u);
    v=fid(v);
    fa[u]=v;
}
int main()
{
    freopen("road.in","r",stdin);
    freopen("road.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m,k,i,j;
    long long ans=0;
    cin>>n>>m>>k;
    for(i=1;i<=n;i++)
        fa[i]=i;
    for(i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        e[i].u=u,e[i].v=v,e[i].w=w;
    }
    for(i=1;i<=k;i++)
    {
        cin>>c[i];
        for(j=1;j<=n;j++)
            cin>>a[j];
    }
    sort(e+1,e+m+1,cmp);
    int cnt=n-1;
    for(i=1;i<=m;i++)
    {
        int u=e[i].u,v=e[i].v;
        if(fid(u)!=fid(v))//It was fid[u] here,haha.
        {
            ans+=e[i].w;
            merge(u,v);
            if(!(--cnt))
                break;
        }
    }//Kruskal
    cout<<ans<<'\n';
    return 0;
}
//Near to AC,but this might not be so easy,meow.

::::

T3

看到题目后确实想到过 KMP，但没想到怎么去用。看了一眼特殊性质 B 就直接开写了，对于每组 s 记录使用其作为替换所需的最小前缀和后缀，并记录每组 s 其将 b 字符移动的位数，对于每组 t 枚举所有 s 判断是否可行。想到了判 |t_1|\not= |t_2|，但没想到判 s_1=s_2。大概花了 40 分钟吧（特殊性质最后只过了一个喵）。

时间复杂度 \Omicron(L_1+L_2+nq)，但由于特判大样例差不多能水过。

接着开始写暴力，写的时候把 tx1 作为变量名出现了亿点点问题，调了 30 分钟改了变量名才发现。时间复杂度懒得算了反正肯定很大，暴力也没写最优的。我甚至以为考试 18:00 结束所以花了 15 分钟检查文件名和 freopen 这些，差点放弃了。最后 5 分钟才调完。

::::info[题面]

题目描述

小 W 是一名喜欢语言学的算法竞赛选手。在语言学中，谐音替换是指将原有的字词替换为读音相同或相近的字词。小 W 发现，谐音替换的过程可以用字符串来进行描述。具体地，小 W 将谐音替换定义为以下字符串问题：

给定 n 个字符串二元组，第 i (1 \leq i \leq n) 个字符串二元组为 (s_{i,1}, s_{i,2})，满足 |s_{i,1}| = |s_{i,2}|，其中 |s| 表示字符串 s 的长度。

对于字符串 s，定义 s 的替换如下：

• 对于 s 的某个子串 y，若存在 1 \leq i \leq n 满足 y = s_{i,1}，则将 y 替换为 y' = s_{i,2}。具体地，设 s = x + y + z，其中 x 和 z 可以为空，“+” 表示字符串拼接，则 s 的替换将得到字符串 s' = x + y' + z。

小 W 提出了 q 个问题，第 j (1 \leq j \leq q) 个问题会给定两个不同的字符串 t_{j,1}, t_{j,2}，她想知道有多少种字符串 t_{j,1} 的替换能够得到字符串 t_{j,2}。两种 s 的替换不同当且仅当子串 y 的位置不同或用于替换的二元组 (s_{i,1}, s_{i,2}) 不同，即 x, z 不同或 i 不同。你需要回答小 W 提出的所有问题。

输入格式

输入的第一行包含两个正整数 n, q，分别表示字符串二元组的数量和小 W 提出的问题的数量。

输入的第 i+1 (1 \leq i \leq n) 行包含两个字符串 s_{i,1}, s_{i,2}，表示第 i 个字符串二元组。

输入的第 j+n+1 (1 \leq j \leq q) 行包含两个字符串 t_{j,1}, t_{j,2}，表示小 W 提出的第 j 个问题。

输出格式

输出 q 行，其中第 j (1 \leq j \leq q) 行包含一个非负整数，表示替换后得到字符串 t_{j,2} 的字符串 t_{j,1} 的替换的数量。

输入输出样例 #1

输入 #1

4 2
xabcx xadex
ab cd
bc de
aa bb
xabcx xadex
aaaa bbbb

输出 #1

2
0

输入输出样例 #2

输入 #2

3 4
a b
b c
c d
aa bb
aa b
a c
b a

输出 #2

0
0
0
0

说明/提示

【样例 1 解释】

对于小 W 的第一个询问，共有 2 种 t_{1,1} 的替换能够得到 t_{1,2}:

1. 令 x, z 均为空串，y = \text{xabcx}, i = 1，则 y' = \texttt{xadex}，替换后得到 \text{xadex}；
2. 令 x = \texttt{xa}, y = \texttt{bc}, z = \texttt{x}, i = 3，则 y' = \texttt{de}，替换后得到 \texttt{xadex}。

【样例 3】

见选手目录下的 replace/replace3.in 与 replace/replace3.ans。

该样例满足测试点 11, 12 的约束条件。

【样例 4】

见选手目录下的 replace/replace4.in 与 replace/replace4.ans。

该样例满足测试点 15, 16 的约束条件。

【数据范围】

设 L_1 = \sum_{i=1}^{n} |s_{i,1}| + |s_{i,2}|, L_2 = \sum_{j=1}^{q} |t_{j,1}| + |t_{j,2}|。对于所有测试数据，保证:

• 对于所有 1 \leq i \leq n, s_{i,1}, s_{i,2} 均仅包含小写英文字母，且 |s_{i,1}| = |s_{i,2}|;
• 对于所有 1 \leq j \leq q, t_{j,1}, t_{j,2} 均仅包含小写英文字母，且 t_{j,1} \neq t_{j,2}。

::cute-table{tuack}

特殊性质 A：q = 1。

特殊性质 B：定义字符串 s 为特别的，当且仅当字符串 s 仅包含字符 a 和 b，且字符 b 在 s 中出现恰好一次。对于所有 1 \leq i \leq n, s_{i,1}, s_{i,2} 均为特别的，且对于所有 1 \leq j \leq q, t_{j,1}, t_{j,2} 均为特别的。 ::::

::::info[Code(15pts)]

#include<bits/stdc++.h>
using namespace std;
struct Node
{
    int l,mid,r;
};
vector<Node> tt;
bool check(string s1,string s2,string s3)
{
    int l=s1.size();
    for(int i=0;i<l;i++)
    {
        if(!((s1[i]=='$'&&s1[i]==s3[i])||s1[i]==s2[i]))
            return false;
    }
    return true;
}
int fid(string s1,string s2)
{
    int l=s1.size();
    int i,j;
    for(i=0,j=s2.size()-1;j<l;i++,j++)
    {
        bool flag=true;
        int x;
        for(int k=i;k<=j;k++)
        {
            if(s2[k-i]!=s1[k])
            {
                flag=false;
                break;
            }
        }
        if(flag)
            return i;
    }
    return -1;
}
void repla(string &s,int p,string s1)
{
    for(int i=p;i<p+s1.size();i++)
    {
        s[i]=s1[i-p];
    }
}
int main()
{
    freopen("replace.in","r",stdin);
    freopen("replace.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s1,s2;
    int n,q,i,j;
    cin>>n>>q;
    if(n<=100&&q<=100)
    {
        string t1[105],t2[105];
        for(i=1;i<=n;i++)
            cin>>t1[i]>>t2[i];
        while(q--)
        {
            cin>>s1>>s2;
            int l1=s1.size(),l2=s2.size();
            int ans=0;
            if(l1!=l2)
            {
                cout<<0<<'\n';
                continue;
            }
            for(i=1;i<=n;i++)
            {
                string ab=s1;
                while(fid(ab,t1[i])!=-1)
                {
                    string sbc=ab;
                    repla(ab,fid(ab,t1[i]),t2[i]);
                    if(check(ab,s2,s1))
                    {
                        ans++;
                        break;
                    }
                    else
                    {
                        ab=sbc;
                        ab[fid(ab,t1[i])]='$';
                    }
                }
            }
            cout<<ans<<'\n';
        }
        return 0;
    }
    for(i=1;i<=n;i++)
    {
        cin>>s1>>s2;
        int l1=s1.size(),l2=s2.size(),ll1,rr1,ll2,rr2,xx1,xx2,dl,dr,dm;
        for(j=0;j<l1;j++)
        {
            if(s1[j]=='b')
            {
                ll1=j;
                rr1=l1-j-1;
                xx1=j;
            }
        }
        for(j=0;j<l2;j++)
        {
            if(s2[j]=='b')
            {
                ll2=j;
                rr2=l2-j-1;
                xx2=j;
            }
        }
        if(xx1<xx2)
            dl=ll1,dr=rr2,dm=xx2-xx1;
        else
            dl=ll2,dr=rr1,dm=xx2-xx1;
        tt.push_back({dl,dm,dr});
    }
    int pp=tt.size();
    for(i=1;i<=q;i++)
    {
        cin>>s1>>s2;
        int ans=0;
        int l1=s1.size(),l2=s2.size();
        if(l1!=l2)
        {
            cout<<0<<'\n';
            continue;
        }
        int ll1,rr1,ll2,rr2,xx1,xx2,dl,dm,dr;
        for(j=0;j<l1;j++)
        {
            if(s1[j]=='b')
            {
                ll1=j;
                rr1=l1-j-1;
                xx1=j;
            }
        }
        for(j=0;j<l2;j++)
        {
            if(s2[j]=='b')
            {
                ll2=j;
                rr2=l2-j-1;
                xx2=j;
            }
        }
        if(xx1<xx2)
            dl=ll1,dr=rr2,dm=xx2-xx1;
        else
            dl=ll2,dr=rr1,dm=xx2-xx1;
        for(j=0;j<pp;j++)
        {
            if(dm==tt[j].mid&&dl>=tt[j].l&&dr>=tt[j].r)
                ans++;
        }
        cout<<ans<<'\n';
    }
    return 0;
}//Meow.Bad.

::::

T4

输出随机数。给 4pts 吧球球了。

::::info[题面]

题目描述

小 Z 和小 H 想要合伙开一家公司，共有 n 人前来应聘，编号为 1 \sim n。小 Z 和小 H 希望录用至少 m 人。

小 H 是面试官，将在接下来 n 天每天面试一个人。小 Z 负责决定应聘人前来面试的顺序。具体地，小 Z 可以选择一个 1 \sim n 的排列 p，然后在第 i (1 \leq i \leq n) 天通知编号为 p_i 的人前来面试。

小 H 准备了 n 套难度不一的面试题。由于 n 个前来应聘的人水平大致相同，因此对于同一套题，所有人的作答结果是一致的。具体地，第 i (1 \leq i \leq n) 天的面试题的难度为 s_i \in \{0,1\}，其中 s_i = 0 表示这套题的难度较高，没有人能够做出；s_i = 1 表示这套题的难度较低，所有人都能做出。小 H 会根据面试者的作答结果决定是否录用，即如果面试者没有做出面试题，则会拒绝，否则会录用。

然而，每个人的耐心都有一定的上限，如果在他面试之前未录用的人数过多，则他会直接放弃参加面试。具体地，编号为 i (1 \leq i \leq n) 的人的耐心上限可以用非负整数 c_i 描述，若在他之前已经有不少于 c_i 人被拒绝或放弃参加面试，则他也将放弃参加面试。

小 Z 想知道一共有多少种面试的顺序 p 能够让他们录用至少 m 人。你需要帮助小 Z 求出，能够录用至少 m 人的排列 p 的数量。由于答案可能较大，你只需要求出答案对 998\,244\,353 取模后的结果。

输入格式

输入的第一行包含两个正整数 n, m，分别表示前来应聘的人数和希望录用的人数。

输入的第二行包含一个长度为 n 的字符串 s_1 \dots s_n，表示每一天的面试题的难度。

输入的第三行包含 n 个非负整数 c_1, c_2, \dots, c_n，表示每个人的耐心上限。

输出格式

输出一行一个非负整数，表示能够录用至少 m 人的排列 p 的数量对 998\,244\,353 取模后的结果。

输入输出样例 #1

输入 #1

3 2
101
1 1 2

输出 #1

2

输入输出样例 #2

输入 #2

10 5
1101111011
6 0 4 2 1 2 5 4 3 3

输出 #2

2204128

说明/提示

【样例 1 解释】

共有以下 2 种面试的顺序 p 能够让小 Z 和小 H 录用至少 2 人:

【样例 3】

见选手目录下的 \textbf{\textit{employ/employ3.in}} 与 \textbf{\textit{employ/employ3.ans}}。

该样例满足测试点 6 ~ 8 的约束条件。

【样例 4】

见选手目录下的 \textbf{\textit{employ/employ4.in}} 与 \textbf{\textit{employ/employ4.ans}}。

该样例满足测试点 12 ~ 14 的约束条件。

【样例 5】

见选手目录下的 \textbf{\textit{employ/employ5.in}} 与 \textbf{\textit{employ/employ5.ans}}。

该样例满足测试点 18 ~ 21 的约束条件。

【数据范围】

对于所有测试数据，保证:

• 对于所有 1 \leq i \leq n，均有 s_i \in \{0,1\};
• 对于所有 1 \leq i \leq n，均有 0 \leq c_i \leq n。

::cute-table{tuack}

特殊性质 A: 对于所有 1 \leq i \leq n，均有 s_i = 1。

特殊性质 B: 在 s_1, s_2, \dots, s_n 中最多只有 18 个取值为 1，即 \sum_{i=1}^{n} s_i \leq 18。 ::::

::::info[Code(0pts 喵)]

#include<bits/stdc++.h>
using namespace std;
int main()
{
    freopen("employ.in","r",stdin);
    freopen("employ.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    srand(time(NULL));
    cout<<rand()<<endl;
    return 0;
}//Meow.4pts,please.

::::

赛后

出考场后听说很多童鞋 T1 没做出来，还有一些心态直接爆炸了（bjx 甚至没做 T3 和 T4 啊）。5 个同学一起吃了 KFC，只花了 89 就做到了每人一个汉堡、一杯饮料和一份鸡腿/鸡翅还有共享的一份鸡米花。真的太有性价比了。这不比黄焖鸡爽喵。

给同学打了把王者，超鬼了（

车上又看了会儿黑盒，玩了会儿游戏。bjx 睡醒后在玩 mc，居然还是生存大佬啊喵。22:00 到学校了，懒得拿东西直接回家了。

总结

如果 T1 没挂的话还是挺满意的，应该是第一次场切绿题（现在降黄了）。能进 NOIP 就行，几等奖已经无所谓了。和 bjx 贴贴开心喵。

其实 T2 写个暴力就一等了。

最终分数：100+32+15+0=147，还算不错吧，一等没希望了，但 6 级勾差不多稳了。