2025牛客寒假算法基础集训营2 出题人题解

$\hspace{15pt}$ 非常感谢大家参与本次比赛，祝大家在新的一年里，身体健康，万事如意，心想事成，前程似锦！

$\hspace{15pt}$ 由于牛客各个页面使用的 CSS 不同，建议您在我的博客中打开本题解，以获得最优质的阅读体验，点击可跳转。

2025.1.23 20:48 更新

原题解中部分 $\LaTeX$ 公式渲染出错，已进行修正。

谢罪部分

$\hspace{15pt}$ 本场比赛的《C.字符串外串》与《D.字符串里串》在书写定义时没有考虑到空串情况，导致题面存在漏洞，且也没有针对这一个边界所构造的数据，在赛后我们已经进行了加强，所带来的不好体验非常抱歉。

$\hspace{15pt}$ 此外，在后台收到了大量询问《G.一起铸最好的剑！》、《J.数据时间？》和《K.可以分开吗？》三题题面问题的私信，经确认，几乎都是因为没有认真阅读题面所导致的，希望大家能够认真读题，不要错过题面中的重要信息。

$\hspace{15pt}$ 其余的出题趣闻附于文末，再次感谢大家参与！

总览

题号	题目名	知识点	Author	预估难度
A	一起奏响历史之音！	模拟	WIDA	*100
B	能去你家蹭口饭吃吗	排序/二分	WIDA	*600
C	字符串外串	贪心、思维、构造	WIDA	*1800
D	字符串里串	贪心、思维、构造	WIDA	*1500
E	一起走很长的路！	思维、前缀和、线段树/ST表	BingBong	*1700
F	一起找神秘的数！	位运算、拆位/打表规律	WIDA	*1000
G	一起铸最好的剑！	暴力、枚举	Silencer76	*900
H	一起画很大的圆！	几何、构造、数学	WIDA	*1700
I	一起看很美的日落！	拆位、树形dp	Bingbong	*2200
J	数据时间？	模拟、堆	WIDA	*1300
K	可以分开吗？	dfs/bfs/dsu	BingBong	*1500
L	还会再见吗？	虚树、换根dp、最短路	BingBong	*2600
M	那是我们的影子	组合数学、分类讨论	BingBong	*1800

A.一起奏响历史之音！

Author: WIDA

Prepared by WIDA

知识点：模拟

$\hspace{15pt}$ 打卡。检查给定的七个整数是否仅包含 $1,2,3,5,6$ 即可。为了便于书写，我们可以反过来，检查这七个整数是否不为 $4$ 和 $7$ 。 $\hspace{15pt}$ 时间 $\mathcal O(1)$ ；空间 $\mathcal O(1)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;

signed main() {
    bool flag = true;
    for (int i = 1; i <= 7; i++) {
        int x;
        cin >> x;
        if (x == 4 || x == 7) {
            flag = false;
        }
    }
    cout << (flag ? "YES" : "NO") << "\n";
}

B.能去你家蹭口饭吃吗

Author: WIDA

Prepared by WIDA

知识点：排序/二分

解法一：排序

$\hspace{15pt}$ 按照题意，对数组从小到大排序。

$\hspace{23pt}\bullet\,$ 当 $n$ 为偶数时，应当输出 $a_{{n\over 2}+1} -1$ ;
$\hspace{23pt}\bullet\,$ 当 $n$ 为奇数时，应当输出 $a_{\lfloor {n\over 2 }\rfloor+1 }-1$ ;

$\hspace{15pt}$ 由于整型除法的运算性质，上面两步可以合并，即直接输出 $a_{{n\over 2}+1} -1$ 。

$\hspace{15pt}$ 时间 $\mathcal O(n\log n)$ ；空间 $\mathcal O(n)$ 。

解法二：二分

$\hspace{15pt}$ 由于答案具有单调性，枚举当前 $mid$ 值对于数组 $a$ 是否至少存在一半的值大于 $mid$ ，根据情况更新答案。

$\hspace{15pt}$ 时间 $\mathcal O(n\log n)$ ；空间 $\mathcal O(n)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;

signed main() {
    int n;
    cin >> n;
    vector<int> in(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> in[i];
    }
    sort(in.begin(), in.end());
    cout << in[n / 2 + 1] - 1 << "\n";
}

C.字符串外串

Author: WIDA

Prepared by WIDA & Bingbong & bandiaoz

知识点：贪心、思维、构造

$\hspace{15pt}$ 本题基于《D.字符串里串》，推荐您在此基础上阅读本题题解。

$\hspace{15pt}$ 继续此前的推导，我们容易发现，对于每一个字母，只有其第二次出现和倒数第二次出现的位置才能有效更新答案，因为可爱度的大小只与 $a,b$ 重复段的长度相关。

步骤一：构造 $k$ 最小的字符串

$\hspace{15pt}$ 我们不妨使用刚刚的第一种构造方案“ $b$ 的第一段仅包含一个字符，即 $a$ 的第一个字母，需要去位置 $i$ 前寻找；第二段包含 $a$ 的剩余部分，可以共用这部分”来进行本题的构造。记 $a$ 取自字符串最后 $m$ 个字符且第一个字母为 $\texttt{`a'}$ ， $b$ 的第一个字母位于位置 $1$ ，构造出的字符串框架如下：

$\Bigg\{\overbrace{ \texttt{a}}^{b \text{ 的第一段} }\Bigg\} \Bigg\{\cdots \Bigg\} \Bigg\{\underbrace{ \texttt{a} \overbrace{\cdots}^{b \text{ 的第二段}}}_{\text{字符串 }a }\Bigg\}$

$\hspace{15pt}$ 此时，得出第一个无解条件，即 $m=n$ 。同时，为了确保不会存在更优的选择，两个 $\texttt{`a'}$ 之间不应当存在相同字母、字符串末尾也不应当出现相同的字母，框架进一步明确如下：

$\Bigg\{\overbrace{ \texttt{a} }^{b \text{ 的第一段}}\texttt{-z} \Bigg\} \Bigg\{\underbrace{ \texttt{a} \overbrace{\cdots}^{b \text{ 的第二段}} \texttt{a-z} }_{\text{字符串 }a }\Bigg\}$

$\hspace{15pt}$ 此时，达到所能构造的最优情况，其中，省略号部分填入任意字符均不会再影响 $k$ 的大小，不妨全部统一为 $\texttt{a} \sim \texttt{z}$ ，得到终极构造方案如下。

$\Bigg\{\overbrace{ \texttt{a} }^{b \text{ 的第一段}}\texttt{-z} \Bigg\} \Bigg\{\underbrace{ \texttt{a} \overbrace{ \texttt{a-z} \texttt{a-z} \cdots \texttt{a-z} }^{b \text{ 的第二段}} \texttt{a-z} }_{\text{字符串 }a }\Bigg\}$

$\hspace{15pt}$ 至此为止，可以得到其中一个无解的条件，即 $n-26 \geq m$ 。

步骤二：构造特定 $k$ 的字符串

$\hspace{15pt}$ 由刚刚的分析得到，所构造的答案只与前后两侧的 $\texttt{a-z}$ 强相关，只要这两个部分确定，中间只需要一味的塞入 $\texttt{a-z}$ 即可；而前侧的 $\texttt{a-z}$ 长度固定为 $n-m$ ，后侧的 $\texttt{a-z}$ 长度需要小于前侧。

$\hspace{15pt}$ 于是，我们联想到取模，只需要不停的塞入长度为 $n-m$ 的 $\texttt{a-z}$ 即可。

$\hspace{15pt}$ 时间 $\mathcal O(n)$ ；空间 $\mathcal O(n)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;

signed main() {
    int Task = 1;
    for (cin >> Task; Task; Task--) {
        int n, m;
        cin >> n >> m;
        if (n == m || n - m > 26) {
            cout << "NO\n";
            continue;
        }
        
        cout << "YES\n";
        for (int i = 0; i < n; i++) {
            cout << (char)('a' + i % (n - m));
        }
        cout << "\n";
    }
}

D.字符串里串

Author: WIDA

Prepared by WIDA & Bingbong & bandiaoz

知识点：贪心、思维、构造

$\hspace{15pt}$ 延续题干定义，记选中的子串为 $a=s[i..j]$ ，那么 $b$ 的最优构造方案为以下两个中的其中一个：

$\hspace{23pt}\bullet\,$ 第一段仅包含一个字符，即 $a$ 的第一个字母，需要去位置 $i$ 前寻找；第二段包含 $a$ 的剩余部分，可以共用这部分；
$\hspace{23pt}\bullet\,$ 第二段仅包含一个字符，即 $a$ 的最后一个字母，需要去位置 $j$ 后寻找；第一段包含 $a$ 的剩余部分，可以共用这部分；

$\hspace{15pt}$ 这样的选择方式最大程度的重复利用了字符，为最佳贪心策略。所以，我们只需要判定是否存在相同的字符，如果是，则更新答案。具体到代码层面上，对于每一种字符，找到其出现的全部位置，依次枚举检查更新答案。虽然依旧存在非常多优化（与 C 的解法相关），但是这样朴素的贪心策略已经可以通过本题，且没有复杂度上的本质差异，所以这里不再赘述其他做法。

$\hspace{15pt}$ 需要注意的是，由于不允许选取空串，所以答案不存在 $1$ 的情况。

$\hspace{15pt}$ 时间 $\mathcal O(26n)$ ；空间 $\mathcal O(n)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;

signed main() {
    int n;
    string s;
    cin >> n >> s;
    s = "#" + s;
    
    int ans = 0;
    for (int ch = 0; ch < 26; ch++) {
        int pre = 0, net = 0;
        for (int i = 1; i <= n; i++) {
            if (s[i] - 'a' != ch) continue;
            if (pre != 0) {
                ans = max(ans, n - i + 1);
            }
            pre = i;
        }
        for (int i = n; i >= 1; i--) {
            if (s[i] - 'a' != ch) continue;
            if (net != 0) {
                ans = max(ans, i);
            }
            net = i;
        }
    }
    cout << (ans == 1 ? 0 : ans) << "\n";
}

E. 一起走很长的路！

Author: BingBong

Prepared by BingBong

知识点：思维、前缀和、线段树/ST表

$\hspace{15pt}$ 考虑每个减法是局部的负贡献，而加法是局部的正贡献，若想将每一步的加法变为全局正贡献，只需要把加法操作使用在 $i=l$ ，便可以对 $i\in[l,r]$ 起正贡献。

$\hspace{15pt}$ 对于每个询问 $[l,r]$ 可以发现本质上是求对于任意的 $\displaystyle\max_{i=l+1}^{r}(0,a_i-\sum\limits_{j=l}^{i-1}a_j)$ ，那么就可以考虑用前缀和、 $ST$ 表或者线段树维护区间最大值即可，特别的由于 $i=l$ 是手推，不需要贡献，所以特判 $l=r$ 时不需要操作的情况。

$\hspace{15pt}$ 时间 $\mathcal O(n\times logn q)$ 。

参考代码

#include<bits/stdc++.h>
using namespace std;
using i64=long long;
template<typename T>
struct RMQ {
  int n;
  vector<T>a;
  RMQ(vector<T>_a,int _n):a(_a),n(_n){
    stmin.resize(n + 5);
    for (int i = 0; i <= n; i++) {
      stmin[i].resize(21, 0);
    }
    solve();
  }
  vector<vector<T>> stmin;
  void solve() {
    for (int i = 1; i <= n; i++) {
      stmin[i][0] = a[i];
    }
    for (int i = 1; (1 << i) <= n; i++) {
      int len = (1 << i);
      for (int j = 1; j + len - 1 <= n; j++) {
        stmin[j][i] = min(stmin[j][i - 1], stmin[j + (1 << (i - 1))][i - 1]);
      }
    }
  }
  T askmin(int l, int r) {
    int len = log2(r - l + 1);
    return min(stmin[l][len],stmin[r - (1 << len) + 1][len]);
  }
 
};
void solve(){
    int n,q;
    cin>>n>>q;
    vector<i64>a(n+1),s(n+2);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    vector<i64>cz(n+2);
    for(int i=1;i<=n;i++){
        cz[i]=s[i-1]-a[i];
    }
    RMQ<i64> T(cz,n);
    while(q--){
        int l,r;
        cin>>l>>r;
        if(l==r){
            cout<<0<<"\n";
            continue;
        }
        i64 ts=s[l-1];
        cout<<abs(min(0LL,T.askmin(l+1,r)-ts))<<"\n";
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    while(t--) {
        solve();
    }
    return 0;
}

F. 一起找神秘的数！

Author: WIDA

Prepared by WIDA

知识点：位运算、拆位/打表规律

$\hspace{15pt}$ 对于任意两个数 $x$ 和 $y$ ，我们可以从二进制的角度来看，对于第 $i$ 位，记为 $\bar x$ 和 $\bar y$ ，有以下四种情况：
$\hspace{23pt}\bullet\,$ 当 $\bar x=0, \bar y=0$ 时： $(\bar x \operatorname{and} \bar y) = 0$ ， $(\bar x \operatorname{or} \bar y) = 0$ ， $\bar x + \bar y = 0$ 。所以 $(\bar x \operatorname{and} \bar y) + (\bar x \operatorname{or} \bar y) = \bar x + \bar y$ ；
$\hspace{23pt}\bullet\,$ 当 $\bar x=0, \bar y=1$ 时： $(\bar x \operatorname{and} \bar y) = 0$ ， $(\bar x \operatorname{or} \bar y) = 1$ ， $\bar x + \bar y = 1$ 。所以 $(\bar x \operatorname{and} \bar y) + (\bar x \operatorname{or} \bar y) = \bar x + \bar y$ ；
$\hspace{23pt}\bullet\,$ 当 $\bar x=1, \bar y=0$ 时： $(\bar x \operatorname{and} \bar y) = 0$ ， $(\bar x \operatorname{or} \bar y) = 1$ ， $\bar x + \bar y = 1$ 。所以 $(\bar x \operatorname{and} \bar y) + (\bar x \operatorname{or} \bar y) = \bar x + \bar y$ ；
$\hspace{23pt}\bullet\,$ 当 $\bar x=1, \bar y=1$ 时： $(\bar x \operatorname{and} \bar y) = 1$ ， $(\bar x \operatorname{or} \bar y) = 1$ ， $\bar x + \bar y = 2$ 。所以 $(\bar x \operatorname{and} \bar y) + (\bar x \operatorname{or} \bar y) = \bar x + \bar y$ ；
$\hspace{15pt}$ 综上，我们证明了 $(x \operatorname{and} y)+(x \operatorname{or} y)=x+y$ 。

$\hspace{15pt}$ 故题意转化为求 $x \operatorname{xor} y = 0$ 的对数，根据异或性质可得，当且仅当 $x=y$ 时等式成立，故答案为区间长度，即 $r-l+1$ 。

$\hspace{15pt}$ 时间 $\mathcal{O(T)}$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
 
signed main() {
    int Task = 1;
    for (cin >> Task; Task; Task--) {
        i64 l, r;
        cin >> l >> r;
        cout << (r - l + 1) << "\n";
    }
}

G. 一起铸最好的剑！

Author: Silencer76

Prepared by Silencer76

知识点：暴力、枚举

$\hspace{15pt}$ 考虑幂次运算的增长性，最多枚举 $32$ 次即可，因为 ${10}^9 \lt 2^{32}$ ，但是在计算过程中需要使用一个长整型预判断，防止溢出。特别需要注意的是，根据不同人的代码而异，当 $m=1$ 时，为边界情况，你可能需要额外特判（在下方示例代码中不需要这样做，全部囊入了循环）。

$\hspace{15pt}$ 时间 $\mathcal{O(T\times 32)}$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
const i64 inf = 1e18;

signed main() {
    int Task = 1;
    for (cin >> Task; Task; Task--) {
        int n, m;
        cin >> n >> m;
        i64 Min = 1e18, ans, now = 1;
        for (int i = 1; i <= 32; i++) {
            if (now >= inf / m) break;
            now *= m;
            if (abs(n - now) < Min) {
                Min = abs(n - now);
                ans = i;
            }
        }
        cout << ans << '\n';
    }
}

H. 一起画很大的圆！

Author: WIDA

Prepared by WIDA

知识点：几何、构造、数学

$\hspace{15pt}$ 首先，我们知道，当三点共线时，可以看作是画出了一个半径为无穷大的圆。所以，当给定的三个点越接近共线，绘制出的圆也就越大。

$\hspace{15pt}$ 考虑在给定的矩形边界上选取三个点，使得他们之间最接近共线，显然，我们可以得到两个构造的方向：
$\hspace{23pt}\bullet\,$ 长边上选取两个点，短边上选取一个点，且尽可能的靠近长边；
$\hspace{23pt}\bullet\,$ 短边上选取两个点，长边上选取一个点，且尽可能的靠近短边；

$\hspace{15pt}$ 不妨设长边平行于 $x$ 轴，短边平行于 $y$ 轴，我们先讨论第一种构造方向。不妨设在矩形上边界长边上选取两个点 $A,B$ ，右边界短边上选取一个点 $C$ 。

$\hspace{15pt}$ 根据正弦定律，我们知道三角形的外接圆半径由 $2R=\tfrac{{\rm len}(A)}{\sin a}=\tfrac{{\rm len}(B)}{\sin b}=\tfrac{{\rm len}(C)}{\sin c}$ 提供。所以，我们应当使得斜边尽可能的大，同时斜边所对的角尽可能的接近 $0 ^{\circ}$ 或 $180 ^{\circ}$ 。前者很好实现，令长边上的一点位于角落（如图中点 $A$ ），短边上的点尽可能的靠近角落（如图中点 $C$ ），此时斜边 $AC$ 取到最大。

$\hspace{15pt}$ 在此基础上考虑点 $B$ 的位置，显然，我们注意到，点 $B$ 越接近点 $A$ ， $\angle ABC$ 越接近 $180 ^{\circ}$ 。所以我们有结论，长边上一点位于左上角，另一点尽可能与之贴近；短边上一点尽可能贴近右上角，形态如下图：

$\hspace{15pt}$ 随后我们考虑第二种构造方式，结论一致，问题在于这两个方案谁画出来的圆更大，答案显然是第一种构造方式更大，依旧通过正弦定理，在长边上选取两点，不仅角更大，斜边也更长，完爆第二种构造方式。

$\hspace{15pt}$ 另外需要注意的是，本题卡 long double。答案非常大，远超想象。

$\hspace{15pt}$ 时间 $\mathcal{O(T)}$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;

signed main() {
    int T;
    cin >> T;
    while (T--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        if (b - a < d - c) {
            cout << a << " " << c << "\n";
            cout << a << " " << c + 1 << "\n";
            cout << a + 1 << " " << d << "\n";
        } else {
            cout << a << " " << d << "\n";
            cout << a + 1 << " " << d << "\n";
            cout << b << " " << d - 1 << "\n";
        }
    }
}

I. 一起看很美的日落！

Author: Bingbong

Prepared by Bingbong

知识点：拆位、树形dp

$\hspace{15pt}$ 考虑当前枚举二进制位为第 $w$ 位。我们用 ${\rm dp}_{u}$ 表示当前结点 $u$ 的答案总和， $f_{u,0}$ 包含结点 $u$ 且 $0$ 所贡献的次数 , $f_{u,1}$ 为包含结点 $u$ 且 $1$ 所贡献的次数， $g_u$ 表示包含 $u$ 的连通块个数。

$\hspace{15pt}$ 那么每当扫描 $u$ 的子节点时，由于此时 $u$ 的父节点还没扫描，所以每次计算的答案都属于满足题意的答案，故可以直接累加。

$\hspace{15pt}$ 计算每个结点 $u$ 时考虑预处理 $g_u =1$ , $f_{u,a_u>>w (\operatorname{and}) 1}=1$ 。考虑计算 $v$ 且 $v$ 为 $u$ 的子节点，那么可得：

${\rm dp}_u = {\rm dp}_u + {\rm dp}_u \times g_v + {\rm dp}_v \times g_u\\ {\rm dp}_u={\rm dp}_u+f_{u,0} \times f_{v,1} +f_{u,1} \times f_{v,0}\\ f_{u,0} =f_{u,0} +f_{u,0} \times g_v + f_{v,0} \times g_u\\ f_{u,1}=f_{u,1} +f_{u,1}\times g_v +f_{v,1} \times g_u\\ g_u=g_u+g_u\times g_v\\$

$\hspace{15pt}$ 最后用 $ans$ 加上每个结点当前运算第 $w$ 位时的答案，由于两两结点运算，最后输出 $ans \times 2$ 即可。

$\hspace{15pt}$ 进行 $\text{log}$ 次递归和取模常数可能很大，可以考虑优化，多开一个维度的数组来维护二进制的位，当然两种方法都可以通过本题。

$\hspace{15pt}$ 时间 $\mathcal{O(n \times \log n)}$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define i64 long long
const int mod = 1e9 + 7;
const int N = 1e5 + 1;
i64 dp[N];
i64 f[2][30][N];
i64 g[N];
void solve() {
    int n;
    cin >> n;
    vector<i64> a(n + 1);
    vector<vector<int>> e(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i], assert(a[i] >= 1 && a[i] <= 1e9);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    i64 ans = 0;
    auto dfs = [&](auto&& self, int u, int fa) -> void {
        for (int w = 0; w < 30; w++) {
            if ((a[u] >> w) & 1) {
                f[1][w][u] = 1;
            } else {
                f[0][w][u] = 1;
            }
        }
        g[u] = 1;
        for (auto v : e[u]) {
            if (v == fa) continue;
            self(self, v, u);
            dp[u] = (dp[u] + dp[v] * g[u] + dp[u] * g[v]) % mod;
            for (int w = 0; w < 30; w++) {
                dp[u] = (dp[u] + (1LL << w) * f[0][w][u] % mod * f[1][w][v] +
                         (1LL << w) * f[1][w][u] % mod * f[0][w][v] ) % mod;
                f[0][w][u] = (f[0][w][u] + f[0][w][u] * g[v] + f[0][w][v] * g[u]) % mod;
                f[1][w][u] = (f[1][w][u] + f[1][w][u] * g[v] + f[1][w][v] * g[u]) % mod;
            }
            g[u] = (g[u] + g[v] * g[u]) % mod;
        }
        ans = ans + dp[u];
    };
    dfs(dfs, 1, 0);
    cout << ans * 2 % mod;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while (t--) solve();
    return 0;
}

J. 数据时间？

Author: WIDA

Prepared by WIDA

知识点：模拟、堆

$\hspace{15pt}$ 题目读懂了很简单，读入后去重即可。在这里，考察到了一些基础的语法知识，如果您使用的是 C++，那么便捷的格式化输入 scanf 可以帮您节省很多时间；如果您精通字符串切片技术，也可以很快的完成输入。

$\hspace{15pt}$ 时间 $\mathcal{O(n)}$ ，空间 $\mathcal{O(n)}$ 。

$\hspace{15pt}$ 再次为糟糕的题面描述致歉，非常抱歉。

参考代码

#include <bits/stdc++.h>
using namespace std;

signed main() {
    int n, h, m;
    cin >> n >> h >> m;
    
    string Date = to_string(h) + "-";
    if (m < 10) {
        Date += "0" + to_string(m);
    }else {
        Date += to_string(m);
    }
    
    set<string> A, B, C;
    while (n--) {
        string user, date, time;
        cin >> user >> date >> time;
        
        if (date.substr(0, 7) != Date) {
            continue;
        }
        string h = time.substr(0, 2);
        if (h == "07" || h == "08" || time == "09:00:00" ||
            h == "18" || h == "19" || time == "20:00:00") {
            A.insert(user);
        }
        if (h == "11" || h == "12" || time == "13:00:00") {
            B.insert(user);
        }
        if (h == "22" || h == "23" || h == "00" || time == "01:00:00") {
            C.insert(user);
        }
    }
    cout << A.size() << " " << B.size() << " " << C.size() << "\n";
}

K. 可以分开吗？

Author: BingBong

Prepared by BingBong

知识点：dfs/bfs/dsu

$\hspace{15pt}$ 考虑最简单的做法，直接对每一个蓝色极大连通块编号，这步可以用 dsu 或者 dfs 实现。

$\hspace{15pt}$ 然后把每个 $0$ 贡献给它所在位置的四个方向存在的蓝色极大联通编号，这里需要注意的是不能对一个蓝色极大连通块重复贡献。然后最后输出所有蓝色极大连通块中被贡献次数的最小值，这一步可以直接 $\text{sort}$ ，也可以每次直接比较，都不会超时。

$\hspace{15pt}$ 时间 $\mathcal{O(n\times m \times \log(n\times m))}$

参考代码

#include <bits/stdc++.h>
using namespace std;
#define i64 long long
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
void solve() {
  int n, m;
  cin >> n >> m;
  vector<string> s(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> s[i];
    s[i] = "%" + s[i];
  }
  vector<int> g(m * n + 1);
  int idx = 0;
  vector<vector<bool>> v(n + 1, vector<bool>(m + 1, false));

  vector<vector<int>> num(n + 1,
                          vector<int>(m + 1, 0));  // 每一个红色属于哪个连通块
  auto dfs = [&](auto &&self, int x, int y, int id) -> void {
    num[x][y] = id;

    v[x][y] = true;
    for (int i = 0; i < 4; i++) {
      int nx = dx[i] + x;
      int ny = dy[i] + y;
      if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !v[nx][ny] &&
          s[nx][ny] == '1') {
        self(self, nx, ny, id);
      }
    }
  };
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (!v[i][j] && s[i][j] == '1') {
        ++idx;
        dfs(dfs, i, j, idx);
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (s[i][j] == '0') {
        map<int, bool> ex;
        for (int k = 0; k < 4; k++) {
          int nx = i + dx[k];
          int ny = j + dy[k];
          if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && s[nx][ny] == '1' &&
              !ex[num[nx][ny]]) {
            g[num[nx][ny]]++;
            ex[num[nx][ny]] = true;
          }
        }
      }
    }
  }

  sort(g.begin() + 1, g.begin() + idx + 1);
  cout << g[1];
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  while (t--) solve();
  return 0;
}

L. 还会再见吗？

Author: BingBong

Prepared by BingBong & bandiaoz & 嘤嘤

知识点：虚树、换根dp、最短路

$\hspace{15pt}$ 我们可以考虑先把所有包含同一种颜色的结点拿出来建立虚树，记当前颜色为 $col$ 。

$\hspace{15pt}$ 对于当前 $col$ 所对应的虚树上做换根 $dp$ ，把所有结点从下到 $u$ 和从上到 $u$ 的最近关键结点的距离全部找出来，然后便可以更新关键结点的 $ans_u$ 。

$\hspace{15pt}$ 最后每个结点都会有自己的最小答案，对所有已经更新过答案的关键结点跑一遍最短路即可。

$\hspace{15pt}$ 由于查询次数较多，建立虚树的过程需要使用效率更高的树剖或者欧拉序。

$\hspace{15pt}$ 时间复杂度： $\mathcal{O(n\times \log n)}$

参考代码

#include<bits/stdc++.h>
using namespace std;
using i64=long long;
const int INF=1e9;
const int N=5e5+10;
int stk[N];
int ok[N];
int ans[N];
int dp[3][N];
int dp_from[3][N];
int dfn[N],dep[N];
int jump[21][N];
int s[N];
int fa[N];
int heav[N];
int Top[N];
int top=0;
int n,q;
int a,col;
void solve(){
    cin>>n>>q;
    vector<vector<int>>e(n+1);
    vector<int>color;
    vector<vector<int>>points_col(n+1);
    for(int i=1;i<=n;++i){
        ans[i]=1e9;
        cin>>a;
        map<int,int>cnt;
        for(int j=1;j<=a;++j){
            cin>>col;
            if(cnt[col]>=1){
                ans[i]=0;
            }else{
                points_col[i].push_back(col);
                color.push_back(col);
            }
            cnt[col]++;
        }
    }
    sort(color.begin(),color.end());
    color.erase(unique(color.begin(),color.end()),color.end());
    auto find=[&](int x)->int {
        return lower_bound(color.begin(),color.end(),x)-color.begin()+1;
    };
    vector<vector<int>>col_point(color.size()+1);
    for(int i=1;i<=n;++i){
        for(auto col:points_col[i]){
            int x=find(col);
            col_point[x].push_back(i);
        }
    }
    int u,v;
    for(int i=1;i<=n-1;++i){
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    int dfs_idx=0;
    auto dfs1=[&](auto &&self,int u,int father)->void {
        dfn[u]=++dfs_idx;
        dep[u]=dep[father]+1;
        fa[u]=father;
        s[u]=1;
        int k=0;
        for(auto v:e[u]){
            if(v==father)continue;
            self(self,v,u);
            s[u]+=s[v];
            if(s[v]>k||k==0){
                heav[u]=v;
                k=s[v];
            }
        }
        if(k==0) heav[u]=u;
    };
    dfs1(dfs1,1,0);
    auto dfs2=[&](auto &&self,int u,int father){
        Top[u]=father;
        if(heav[u]==0||heav[u]==u) return ;
        self(self,heav[u],father);
        for(auto v:e[u]){
            if(v==fa[u]||v==heav[u]) continue;
            self(self,v,v);
        }
    };
    dfs2(dfs2,1,1);

    auto get_lca=[&](int u,int v)->int {
        while(Top[u]!=Top[v]){
            if(dep[Top[u]]<dep[Top[v]]) swap(u,v);
            u=fa[Top[u]];
        }
        return dep[u]<dep[v]?u:v;
    };
    // 在每个颜色点建立虚树
    for(int k=1;k<=color.size();++k){
        vector<int>points=col_point[k];
        sort(points.begin(),points.end(),[&](int a,int b){
            return dfn[a]<dfn[b];
        });
        stk[top=1]=points[0];
        dp[0][points[0]]=dp[1][points[0]]=dp[2][points[0]]=INF;
        dp_from[0][points[0]]=dp_from[1][points[0]]=-1;
        ok[points[0]]=1;
        vector<tuple<int,int,int>>edge;
        for(int i=1;i<points.size();++i){
            int u=points[i];
            ok[u]=1; 
            dp[0][u]=dp[1][u]=dp[2][u]=INF;
            dp_from[0][u]=dp_from[1][u]=-1;
            int lca=get_lca(stk[top],u);
            dp[0][lca]=dp[1][lca]=dp[2][lca]=INF;
            dp_from[0][lca]=dp_from[1][lca]=-1;
            if(lca==stk[top]){
                stk[++top]=u;
            }else{
                while(top>1&&dfn[stk[top-1]]>=dfn[lca]){
                    int dis=dep[stk[top]]-dep[stk[top-1]];
                    edge.emplace_back(stk[top-1],stk[top],dis);
                    top--;
                }
                if(stk[top]!=lca){
                    int dis=dep[stk[top]]-dep[lca];
                    edge.emplace_back(lca,stk[top],dis);
                    stk[top]=lca;
                }
                stk[++top]=u;
            }
        }
        while(top>1){
            int dis=dep[stk[top]]-dep[stk[top-1]];
            edge.emplace_back(stk[top-1],stk[top],dis);
            top--;
        }
        // 在该虚树上换根dp 
       for(auto [u,v,dis]:edge){
            if(ok[v]){
              //  assert(u!=2);
                dp[0][v]=0;
                dp_from[0][v]=v;
            }
            if(ok[u]){
                dp[0][u]=0;
                dp_from[0][u]=u;
            }
            if(dp[0][v]+dis<=dp[0][u]){
                    //可以更新第一小
                    dp[1][u]=dp[0][u];
                    dp_from[1][u]=dp_from[0][u];
                    dp[0][u]=dp[0][v]+dis;
                    dp_from[0][u]=v;
            }else if(dp[0][v]+dis<dp[1][u]){
                    //可以更新第二小
                    dp[1][u]=dp[0][v]+dis;
                    dp_from[1][u]=v;
                }
        }
        for(int i=edge.size()-1;i>=0;i--){
            auto [u,v,dis]=edge[i];
                if(dp_from[0][u]==v){
                    // 此时更新儿子向上的最短路
                    dp[2][v]=min(dp[2][u],dp[1][u])+dis;
                }else{
                    dp[2][v]=min(dp[2][u],dp[0][u])+dis;
                }
        }
        for(int i=0;i<points.size();++i){
            int u=points[i];
            //关键结点
            ans[u]=min(ans[u],dp[0][u]+dp[2][u]);
            ans[u]=min(ans[u],dp[0][u]+dp[1][u]);
            ok[u]=0;//取消关键结点
        }
    }
    priority_queue<pair<int,int>>qq;
    for(int i=1;i<=n;++i){
        qq.push({-ans[i],i});
    }
    while(qq.size()){
        int u=qq.top().second;
        int d=qq.top().first;
        qq.pop();
        for(auto v:e[u]){
            if(ans[v]>ans[u]+1){
                ans[v]=ans[u]+1;
                qq.push({-ans[v],v});
            }
        }
    }
    while(q--){
        int u;
        cin>>u;
        if(ans[u]>=1e9){
            cout<<"IMPOSSIBLE!\n";
        }else{
            cout<<ans[u]<<"\n";
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    while(t--) {
        solve();
    }
    return 0;
}

M. 那是我们的影子

Author: BingBong

Prepared by BingBong

知识点：组合数学、分类讨论

$\hspace{15pt}$ 由于每个 $3\times 3$ 的连续子矩阵都需要满足数独性质，所以可以观察到所有列的标号 $j$ 在 $\bmod 3$ 之后的数字集合是一致的。

$\hspace{15pt}$ 首先考虑无解情况（三种情况，以下的列指对 $3$ 取模后的列编号）：

$\hspace{23pt}\bullet\,$ 列出现超过 $3$ 个不同的数字,例如同时存在 $1,2,3,4,5$ ；

$\hspace{23pt}\bullet\,$ 一个数同时在不同的列；

$\hspace{23pt}\bullet\,$ 同一列出现了多个重复数字，例如同时存在 $1,1$ ；

$\hspace{15pt}$ 然后对于有解的情况，只需要先算出每列的问号个数，记作 $f_j$ 。把 $j \bmod 3$ 之后的列集所缺的数字个数记作 $ne_j$ 。把剩余 $1\sim 9$ 没有出现过的数字个数记为 $num$ 。最后的答案便是（其中 $C$ 表示组合数， $A$ 表示排列数）：

$C_{num}^{ne_0} \times C_ {num-ne_0} ^{ne_1} \times C_{num-ne_0-ne_1}^{ne_2} \times \prod _ {j=1} ^{n} A_{f_j} ^{f_j}$

$\hspace{15pt}$ 时间复杂度： $\mathcal{O(3\times n)}$

参考代码

#include <bits/stdc++.h>
using namespace std;
#define i64 long long
const int mod = 1e9 + 7;
struct Comb { 
  const int P = 13331; 
  i64 qmi(i64 a, i64 b) {
    i64 ans = 1;
    while (b) {
      if (b & 1)
        ans = ans * a % mod;
      a = a * a % mod;
      b >>= 1;
    }
    return ans;
  };
  void init(int M) {
    fac.resize(M + 10, 1);
    inv.resize(M + 10, 1);
    finv.resize(M + 10, 1);
    for (int i = 2; i <= M; i++)
      fac[i] = fac[i - 1] * i % mod;
    finv[M]=qmi(fac[M],mod-2);
    for(int i=M-1;i>=0;i--){
      finv[i]=finv[i+1]*(i+1)%mod;
    }
    inv[1] = qmi(P, mod - 2);
    for (int i = 2; i <= M; i++) {
      inv[i] = inv[i - 1] * P % mod;

    }
  };
  i64 C(i64 n, i64 m) {
    assert(n>=0 && m>=0 && n<=m);
    if (n == 0 || m == 0)
      return 1ll;
    i64 c = fac[m - n] * fac[n] % mod;
    return fac[m] *finv[n]% mod * finv[m-n] % mod;
  };
  i64 A(int n, int m) { return fac[n] * C(n, m) % mod; }
  vector<i64> fac, inv,finv;
};
void solve() {
  Comb T;
  int n;
  cin >> n;
  T.init(15);
  vector<string> s(4);
  for (int i = 1; i <= 3; i++) {
    cin >> s[i];
    assert(s[i].size() == n);
    s[i] = '#' + s[i];
  }
  set<int> v[3];
  for (int i = 1; i <= 3; i++) {
    for (int j = 1; j <= n; j++) {
      if (s[i][j] != '?') v[j % 3].insert(s[i][j] - '0');
    }
  }
  // 无解情况
  // 1.列出现超过3个数
  if (v[0].size() > 3 || v[1].size() > 3 || v[2].size() > 3) {
    cout << "0" << endl;
    return;
  }
  // 2.一个数同时在不同的列
  for (int i = 1; i <= 9; i++) {
    bool ok = false;
    for (int j = 0; j < 3; j++) {
      if (v[j].find(i) != v[j].end() && ok) {
        cout << 0 << endl;
        return;
      } else if (v[j].find(i) != v[j].end()) {
        ok = true;
      }
    }
  }
  // 3.同一列出现了多个重复数字
  for (int i = 1; i <= n; i++) {
    vector<bool> OK(10, false);
    for (int j = 1; j <= 3; j++) {
      if (s[j][i] == '?') continue;
      if (OK[s[j][i] - '0']) {
        cout << "0" << endl;
        return;
      }
      OK[s[j][i] - '0'] = true;
    }
  }
  // 每列位置排列位置的个数
  vector<i64> f(n + 1);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= 3; j++) {
      if (s[j][i] == '?') f[i]++;
      f[i] %= mod;
    }
  }
  // 数字分配
  vector<i64> ne(3);
  int now_use = 0;
  for (int j = 0; j < 3; j++) {
    ne[j] = 3 - v[j].size();
    now_use += (3 - v[j].size());
  }
  // 第一列缺多少个数字
  i64 ans = T.C(ne[0], now_use) * T.C(ne[1], now_use - ne[0]) % mod;
  for (int i = 1; i <= n; i++) ans = ans * T.A(f[i], f[i]) % mod;
  cout << ans << endl;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  cin >> t;
  while (t--) solve();
  return 0;
}

趣闻

$\hspace{15pt}$ 在今天凌晨其实本场是没有《J. 数据时间？》这个题的，另外还有一个定位 middle 的构造，嘤嘤突然跑过来说觉得前期题太少了，而且第一场难度已经很劝退萌新了，于是在综合考虑之后，我们连夜补出了这个题。就通过人数来看，这个题的定位还算不错，补全了本场前期题没有模拟的问题，补充了 easy 分段的由于时间仓促，导致题面打磨欠佳，所以导致了一大堆人来提问，在这里向大家表示歉意。

$\hspace{15pt}$ 在出题阶段，我们的出题人 Bingbong 一直觉得自己的《L.还会再见吗？》是 *2200 水平，自己的《M.那是我们的影子》是 div2.C，这对吗？这不对~~是不是该挨打！~~。

Prepared by WIDA & BingBong & bandiaoz & Silencer76。