比那名居的桃子

发布于 02-07 18:00 北京

+ 关注

【题解】2026牛客寒假算法基础集训营3题解

整场评价与题目分类

这场题整体梯度较平滑：前半段以思维/实现成本很低的题为主，后半段逐步过渡到需要构造与证明的中高档题。

题目分类（按 CF 难度粗略估计，仅供训练安排）：

签到：A(300)、G(600)、B(800)
easy：J(1000)、H(1200)
mid：C(1500)、F(2000)
hard：I(2100)、D(2200)、E(2400)

（以上为赛前估的难度，赛后更正：H->1400 C->1800 F->1800 E->2200，其余题不变）

具体难度细表：

题目	综合难度（CF）	思维难度	代码难度	知识点难度	出题人
A	300	0	1	0	神崎兰子
B	800	3	1	2	神崎兰子
C	1800	6	4	4	TRfirst
D	2200	8	6	7	神崎兰子
E	2200	10	8	7	TRfirst
F	1800	8	2	4	神崎兰子
G	600	1	2	2	神崎兰子
H	1400	4	3	4	神崎兰子
I	2100	6	6	8	神崎兰子
J	1000	2	3	3	神崎兰子

A. 宙天

难度：CF 300

知识点：枚举、简单数学

思路：

题目要求判断给定正整数 $x(1\le x\le 100)$ 是否能表示为两个连续自然数的乘积，即是否存在自然数 $k$ 使得 $x=k(k+1)$ 。

由于 $x$ 很小，直接枚举 $k$ 即可。注意 $k(k+1)\le 100$ 时 $k\le 9$ ，所以枚举 $k=1..9$ 判断是否存在即可。

参考代码：

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

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int x;
    cin>>x;
    for(int i=1;i<=9;i++){
        if(i*(i+1)==x){
            cout<<"YES\n";
            return 0;
        }
    }
    cout<<"NO\n";
    return 0;
}

G. スピカの天秤

难度：CF 600

知识点：贪心、排序、前缀和

思路：

设左侧总重量为 $S_A=\sum a_i$ ，右侧总重量为 $S_B=\sum b_i$ 。当前状态只由 $S_A$ 与 $S_B$ 的大小关系决定。每次“拿走砝码”就是从某一侧删掉若干个元素，使对应总和减少。目标是让新状态与旧状态不同。

若 $S_A=S_B$ ：删掉任意一个砝码都会打破平衡，答案为 $1$ 。
若 $S_A\ne S_B$ ：不妨设 $S_A>S_B$ ，记 $\Delta=S_A-S_B>0$ 。要让状态不再是“左大于右”，只能通过从左侧拿走一些砝码使左侧总和减少到不超过右侧：

S_A-\text{removed}\le S_B\ \Longleftrightarrow\ \text{removed}\ge \Delta.

因此问题变为：从左侧选若干个数，使它们的和至少为 $\Delta$ ，并让选的个数最少。因为所有砝码重量为正数，为了最小化个数，显然应当优先拿走最大的砝码：
把较重一侧的砝码按从大到小排序，取最大的若干个，直到前缀和 $\ge\Delta$ ，这个最小前缀长度就是答案。

证明（为什么取最大的是最少个数）：对于固定个数 $k$ ，能拿走的最大总重量就是“取 $k$ 个最大值”的和。若这都凑不够 $\Delta$ ，则任何 $k$ 个都不够；反之第一个满足的 $k$ 一定可行且最小。

参考代码：

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

int a[202020],b[202020];

void solve(){
    int n,m;
    cin>>n>>m;
    int sa=0,sb=0;
    for(int i=1;i<=n;i++){cin>>a[i];sa+=a[i];}
    for(int i=1;i<=m;i++){cin>>b[i];sb+=b[i];}
    if(sa==sb){cout<<1<<"\n";return;}
    vector<int>v;
    int d;
    if(sa>sb){
        d=sa-sb;
        v.assign(a+1,a+n+1);
    }else{
        d=sb-sa;
        v.assign(b+1,b+m+1);
    }
    sort(v.begin(),v.end(),greater<int>());
    int s=0;
    for(int i=0;i<(int)v.size();i++){
        s+=v[i];
        if(s>=d){cout<<i+1<<"\n";return;}
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _;
    cin>>_;
    while(_--)solve();
    return 0;
}

B. Random

难度：CF 800

知识点：暴力、概率（随机数据）、gcd

思路：

题目保证数组元素为 $[1,10^9]$ 的随机生成数据，因此可以用“暴力 + 小范围枚举”的方式近似必过。

做法：对每个位置 $i$ ，只检查后面固定数量的元素（例如 30 个）：

\text{for }j=i+1.. \min(n,i+30),\ \text{若 }\gcd(a_i,a_j)>1\ \text{就输出这对。}

总 gcd 次数为 $O(30n)$ ，当 $n=2\times 10^5$ 时约为 $6\times 10^6$ ，非常快。

对于一个“失败概率”下确界的理解：先只看“偶数”。随机生成时每个数为偶数的概率约为 $1/2$ ，设偶数个数为 $E$ ，则 $E\sim \mathrm{Binom}(n,1/2)$ ，期望为 $n/2$ 。

如果某个长度为 $31$ 的连续区间里出现了两个偶数，那么这两个偶数位置差不超过 $30$ ，而 $\gcd(\text{偶数},\text{偶数})\ge 2$ ，我们就一定能在枚举窗口时找到答案。

反过来，若所有长度为 $31$ 的区间里至多一个偶数，则偶数总数至多为 $\lceil n/31\rceil$ 。因此只要

E>\frac{n}{31},

就必然存在两偶数距离 $\le 30$ ，算法必然输出答案。

而由 Chernoff 界（或二项分布尾界），

\Pr\left(E\le \frac{n}{31}\right) =\Pr\left(E\le \left(1-\delta\right)\frac{n}{2}\right) \le \exp\left(-\frac{\delta^2}{4}n\right),\ \delta=1-\frac{2}{31}=\frac{29}{31}.

这里 $\delta^2/4\approx 0.218$ ，当 $n=2\times 10^5$ 时上界约为 $\exp(-43600)$ ，几乎为 0。也就是说仅靠“找两偶数”这一条直觉，就足以解释为什么窗口暴力在随机数据上极稳。

（以下是严格概率证明）

失败概率（随机模型估算）：对两独立随机整数，经典结论

\Pr(\gcd(u,v)=1)=\frac{6}{\pi^2}\approx 0.6079,

一个简短推导（容斥/莫比乌斯反演）：令事件 $A_p$ 表示“素数 $p$ 同时整除 $u,v$ ”，则 $\Pr(A_p)=1/p^2$ 。利用容斥可得

\Pr(\gcd(u,v)=1)=\sum_{d\ge 1}\mu(d)\Pr(d\mid u\ \text{且}\ d\mid v) =\sum_{d\ge 1}\frac{\mu(d)}{d^2},

其中 $\mu$ 为莫比乌斯函数（容斥系数）。另一方面

\sum_{d\ge 1}\frac{\mu(d)}{d^2} =\prod_p\left(1-\frac{1}{p^2}\right) =\frac{1}{\zeta(2)} =\frac{6}{\pi^2}.

因此一次检查命中 $\gcd>1$ 的概率约为 $p\approx 1-6/\pi^2\approx 0.3921$ 。把每次 gcd 检查近似看作独立，则做 $M=30n$ 次检查仍未命中的概率近似为

(6/\pi^2)^M.

当 $n=2\times 10^5$ 时 $M=6\times 10^6$ ，有

\log_{10}(6/\pi^2)\approx -0.2163\ \Rightarrow\ (6/\pi^2)^M \approx 10^{-0.2163\cdot 6\times 10^6}\approx 10^{-1.3\times 10^6},

几乎不可能失败。

注：这是基于“随机生成数据”的题面特性给出的概率性做法；对最坏情况排列并不保证一定找到解。本题保证了数据随机，所以可以用该做法。

参考代码：

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

int a[202020];

void solve(){
    int n,i,j;
    cin>>n;
    for(i=1;i<=n;i++)cin>>a[i];
    for(i=1;i<=n;i++){
        for(j=i+1;j<=n&&j<=i+30;j++){
            if(__gcd(a[i],a[j])>1){
                cout<<a[i]<<" "<<a[j]<<"\n";
                return;
            }
        }
    }
    cout<<-1<<"\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

J. Branch of Faith

难度：CF 1000

知识点：完全二叉树编号、位运算、二进制分段

思路：

题目给出一棵有 $n$ 个点的完全二叉树，根为 $1$ ，点 $i$ 的左儿子为 $2i$ ，右儿子为 $2i+1$ 。对每个询问给出 $x$ ，问与 $x$ 深度相同的点有多少个（包含 $x$ ），但树只有编号 $1..n$ 的点存在。

关键性质：编号的二进制最高位决定深度。设 $x$ 的最高位为 $2^d$ ，则 $x$ 的深度为 $d$ ，这一层的节点编号范围为

[2^d,\ 2^{d+1}-1].

但由于树只到 $n$ ，实际存在的同层节点是

[L,R],\quad L=2^d,\ R=\min(n,2^{d+1}-1).

答案就是

R-L+1.

实现时只要取 $L$ 为不超过 $x$ 的最大 $2$ 的幂（highest power of two），然后 $R=\min(n,2L-1)$ 即可，单次询问 $O(1)$ 。

参考代码：

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

void solve(){
    unsigned long long n;
    int q;
    cin>>n>>q;
    while(q--){
        unsigned long long x;
        cin>>x;
        unsigned long long L=1ULL<<(63-__builtin_clzll(x));
        unsigned long long R=min(n,L*2-1);
        cout<<(long long)(R-L+1)<<"\n";
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _;
    cin>>_;
    while(_--)solve();
    return 0;
}

H. Tic Tac DREAMIN'

难度：CF 1200

知识点：解析几何、三角形面积、方程、二分

思路：

给定 $A(x_a,y_a)$ 、 $B(x_b,y_b)$ ，要在 $x$ 轴上找点 $O(x,0)$ 使得三角形 $ABO$ 面积为 $2$ ，即

\frac12\left| (B-A)\times(O-A)\right|=2.

令 $u=B-A=(x_b-x_a,\ y_b-y_a)$ ， $v=O-A=(x-x_a,\ -y_a)$ ，则二维叉积为

u\times v=(x_b-x_a)(-y_a)-(y_b-y_a)(x-x_a).

把它写成关于 $x$ 的一次函数：

g(x)=-(y_b-y_a)\,x + (y_b-y_a)x_a-(x_b-x_a)y_a.

目标是

|g(x)|=4.

特判

若 $y_b=y_a$ ，则 $g(x)=-(x_b-x_a)y_a$ 为常数：
- 若 $|(x_b-x_a)y_a|=4$ ，任意 $x$ 都行（输出 $0$ 即可）；
- 否则无解，输出 no answer。
若 $y_b\ne y_a$ ，则 $g(x)$ 为严格单调一次函数， $|g(x)|=4$ 必有解（甚至有两解），输出任意一个即可。

做法一（二分答案）：先找到“面积为 $0$ 的交点”，也就是解 $g(x)=0$ 得到 $x_0$ 。
因为 $g(x)$ 是一次函数， $\lvert g(x)\rvert$ 在 $x_0$ 两侧单调递增且趋于无穷。题目坐标范围很小，因此直接取一个足够远的上界（如 $10^{18}$ ）即可保证 $\lvert g(r)\rvert\ge 4$ ，从而在区间 $[x_0,10^{18}]$ 内对 $x$ 二分找到满足 $\lvert g(x)\rvert=4$ 的解。

坑点（精度）：判定条件是“面积误差 $\le 0.001$ ”，但面积对 $x$ 的变化率是 $\frac12|y_b-y_a|$ ，最大可到 $10^4$ 量级；因此为了让面积误差在 $10^{-3}$ 内， $x$ 往往需要精确到 $10^{-7}$ 甚至更小，只保留 3 位小数会直接 WA。直接输出 10 位小数最稳。

参考代码（做法一，二分）：

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

double xa,ya,xb,yb;

double g(double x){
    return -(yb-ya)*x + (yb-ya)*xa - (xb-xa)*ya;
}

void solve(){
    cin>>xa>>ya>>xb>>yb;
    if(yb==ya){
        double t=fabs((xb-xa)*ya);
        if(fabs(t-4.0)<=1e-9) cout<<0.0<<"\n";
        else cout<<"no answer\n";
        return;
    }
    double A=-(yb-ya);
    double B=(yb-ya)*xa-(xb-xa)*ya;
    double x0=-B/A;
    double l=x0,r=1e18;
    for(int i=0;i<200;i++){
        double mid=(l+r)/2;
        if(fabs(g(mid))<4.0) l=mid;
        else r=mid;
    }
    cout<<fixed<<setprecision(10)<<((l+r)/2)<<"\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

做法二（推式子）：直接解 $|g(x)|=4$ 。当 $y_b\ne y_a$ 时，取 $g(x)=4$ 的一个解即可：

x=\frac{4-\big((y_b-y_a)x_a-(x_b-x_a)y_a\big)}{-(y_b-y_a)}.

参考代码（做法二，公式）：

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

void solve(){
    double xa,ya,xb,yb;
    cin>>xa>>ya>>xb>>yb;
    if(yb==ya){
        double t=fabs((xb-xa)*ya);
        if(fabs(t-4.0)<=1e-9) cout<<0.0<<"\n";
        else cout<<"no answer\n";
        return;
    }
    double A=-(yb-ya);
    double B=(yb-ya)*xa-(xb-xa)*ya;
    double x=(4.0-B)/A;
    cout<<fixed<<setprecision(10)<<x<<"\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

C. Inverted World

难度：CF 1500 （本题出题人TRfirst估1600）

知识点：构造、前缀和、Kadane（最大子段和）

思路：

目标是把串变成交替串（0101... 或 1010...）。操作是：选择一个子序列 $t$ ，要求 $t$ 中相邻字符不同（0/1 交替），然后把 $t$ 中所有字符翻转。

先固定目标为 0101...（0 下标偶位为 0，奇位为 1）。把所有已经在正确位置上的字符按原顺序抽出来形成一个新串 mid：

偶位正确意味着该位是 0；奇位正确意味着该位是 1。

接下来只需在 mid 上计算一个值：把 1 记为 +1，0 记为 -1，求该序列的最大子段和与最小子段和，答案就是二者绝对值的最大值：

\max\Big(\max\_{\text{sub}} \sum v,\ \big|\min\_{\text{sub}} \sum v\big|\Big).

直观理解：mid 中的 1 表示“奇位已经对了”，0 表示“偶位已经对了”。一次合法操作相当于在某一段上把“奇位对/偶位对”的优势反转，因此每次最多把某段的优势差缩小 1；最少次数就是全局最大优势差（也就是最大绝对子段和）。

同理再对目标 1010... 计算一次，取两者最小值即可。

参考代码：

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

int f(string s){
    int mx=0,mn=0,now=0;
    for(int i=0;i<(int)s.size();i++){
        if(s[i]=='1')now++;
        else now--;
        if(now<0)now=0;
        mx=max(mx,now);
    }
    now=0;
    for(int i=0;i<(int)s.size();i++){
        if(s[i]=='1')now++;
        else now--;
        if(now>0)now=0;
        mn=min(mn,now);
    }
    return max(mx,abs(mn));
}

void solve(){
    int n,i;
    string s,t;
    cin>>n>>s;
    t="";
    for(i=0;i<n;i++){
        if((i&1)&&s[i]=='1')t+=s[i];
        if(!(i&1)&&s[i]=='0')t+=s[i];
    }
    int ans=f(t);
    t="";
    for(i=0;i<n;i++){
        if((i&1)&&s[i]=='0')t+=s[i];
        if(!(i&1)&&s[i]=='1')t+=s[i];
    }
    ans=min(ans,f(t));
    cout<<ans<<"\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _;
    cin>>_;
    while(_--)solve();
    return 0;
}

F. Energy Synergy Matrix

难度：CF 2000

知识点：博弈、最短路、构造

思路：

把每个格子看成点，相邻格子连边；“放障碍”就是删点，但要求删完后从起点 $(1,1)$ 仍能到达第 $n$ 列。双方轮流删点直到无点可删，最后在最终障碍布局下，小红走最短路到第 $n$ 列。

关键观察

游戏结束时，剩余可走格子一定构成一条简单路：如果还存在某个格子不在“所有 $s\to t$ 路径”上，那么删掉它仍然不会断开到第 $n$ 列的连通性，游戏就不会结束。
在 $2\times n$ 网格里，从第 $1$ 列走到第 $n$ 列，最短路必然至少走 $n-1$ 次向右；额外步数只来自上下换行。因此最终最短步数可以写成

(n-1)+r,

其中 $r$ 是最短路中“换行”的最小次数（每换行一次多走 $1$ 步）。

结论： $r=\left\lfloor \dfrac{n}{5}\right\rfloor$

在 $2\times n$ 的“梯子图”上，要让换行变成不可避免，必须制造一个最小的“强制换行结构”，它至少要占用连续 $5$ 列（否则总能通过删点把其中一行打通成直走，不产生换行）。

同时，小紫（想让最短路尽量长）可以把这些结构放进互不重叠的 $5$ 列块里：每 $5$ 列至少逼出一次换行；而小红（想让最短路尽量短）也能通过优先把局部删成“一条走廊”，保证每 $5$ 列最多只会被逼出一次换行。

因此最终恰有

r=\left\lfloor \frac{n}{5}\right\rfloor,

答案为

(n-1)+\left\lfloor \frac{n}{5}\right\rfloor.

参考代码：

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

void solve(){
    int n;
    cin>>n;
    cout<<n-1+n/5<<"\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _;
    cin>>_;
    while(_--)solve();
    return 0;
}

I. BenzenE

难度：CF 2100

知识点：位运算（ $\oplus$ ）、XOR 线性基、构造（回溯）

思路：

给定 $n$ ，数组 $a,b$ 。要输出 $c$ 满足 $c_i\in\{a_i,b_i\}$ 且

c_1\oplus c_2\oplus\cdots\oplus c_n=0.

1）转化成“子集异或等于目标”

先令初始方案全选 $a$ ，记

X=a_1\oplus a_2\oplus\cdots\oplus a_n.

若 $X=0$ ，直接输出 $a$ 即可。

否则，若把第 $i$ 位从 $a_i$ 换成 $b_i$ ，整体异或会变化

d_i=a_i\oplus b_i.

设你最终换掉的下标集合为 $S$ ，则新异或为

X\oplus\bigoplus_{i\in S}d_i.

要它变成 0，等价于

\bigoplus_{i\in S}d_i=X.

因此问题变成：从 $\{d_i\}$ 里选一子集异或出目标 $X$ ，并回溯出这个子集。

2）XOR 线性基 + 回溯方案

对所有 $d_i$ 建 XOR 线性基。因为 $a_i,b_i\le 10^9$ ，只需要维护 0..30 共 31 位，线性基维度最多 31。

为了能输出具体换哪些位置：对每个“插入进基的向量”编号为 $0..cnt-1$ ，用一个 unsigned long long 掩码记录线性组合（第 $k$ 位为 1 表示选了第 $k$ 个插入向量），同时用 idd[k] 记录该插入向量对应原数组的下标 $i$ 。

用线性基去表示目标 $X$ ：

若某一位需要消掉但基里没有对应向量，则无解输出 -1。
否则得到掩码 pick，把 pick 里为 1 的那些 idd[k] 位置改选 $b_i$ ，其余保持 $a_i$ ，即可保证最终异或为 0。

复杂度：每个测试用例 $O(n*31)$ 。

参考代码：

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

int a[202020],b[202020];
int bas[35];
unsigned long long msk[35];
int idd[70];
char use[202020];

void solve(){
    int n,i,j;
    cin>>n;
    int X=0;
    for(i=1;i<=n;i++){cin>>a[i];X^=a[i];}
    for(i=1;i<=n;i++)cin>>b[i];
    if(X==0){
        for(i=1;i<=n;i++)cout<<a[i]<<(i==n?'\n':' ');
        return;
    }
    for(i=0;i<=30;i++)bas[i]=0,msk[i]=0;
    int cnt=0;
    for(i=1;i<=n;i++){
        int v=a[i]^b[i];
        if(!v)continue;
        int cur=v;
        unsigned long long curm=1ull<<cnt;
        for(j=30;j>=0;j--){
            if(((cur>>j)&1)==0)continue;
            if(!bas[j]){
                bas[j]=cur;
                msk[j]=curm;
                idd[cnt]=i;
                cnt++;
                break;
            }
            cur^=bas[j];
            curm^=msk[j];
        }
    }
    unsigned long long pick=0;
    int cur=X;
    for(j=30;j>=0;j--){
        if((cur>>j)&1){
            if(!bas[j]){cout<<-1<<"\n";return;}
            cur^=bas[j];
            pick^=msk[j];
        }
    }
    for(i=1;i<=n;i++)use[i]=0;
    for(i=0;i<cnt;i++)if((pick>>i)&1)use[idd[i]]=1;
    for(i=1;i<=n;i++)cout<<(use[i]?b[i]:a[i])<<(i==n?'\n':' ');
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _;
    cin>>_;
    while(_--)solve();
    return 0;
}

D. 系ぎて

难度：CF 2200

知识点：网格 BFS、最短路、构造

思路：

题意：在 $n\times m$ 网格里只有两个 1 和两个 2。要分别连通 1-1 与 2-2，两条路径都只能走上下左右相邻格，且两条路径不能共用任何格子；并且 1 的路径不能经过 2 的信号点，2 的路径不能经过 1 的信号点；0 格最多被一条路径使用一次。

做法一（贪心+特判）：

用一些局部结构（角点被异类完全堵死、2x2 交叉块等）先判 NO；
若存在信号点在内部则直接 YES；
若四个点都在边界，沿边界顺时针读出遇到的信号序列（长度 4），若呈交替 1,2,1,2 则 NO，否则 YES。

这种写法实现简单，但依赖于对平面拓扑的观察与特判。

参考代码（做法一）：

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

int n,m;
vector<string>g;

int f(int r,int c){return r==0||r==n-1||c==0||c==m-1;}

int bc(int r,int c,int r1,int c1,int r2,int c2){
    char x=g[r][c];
    if(x!='1'&&x!='2')return 0;
    char y=(x=='1'?'2':'1');
    return g[r1][c1]==y&&g[r2][c2]==y;
}

void gao(){
    cin>>n>>m;
    g.assign(n,"");
    vector<pair<int,int>>p;
    for(int i=0;i<n;i++){
        cin>>g[i];
        for(int j=0;j<m;j++){
            if(g[i][j]=='1'||g[i][j]=='2')p.push_back({i,j});
        }
    }
    if(bc(0,0,0,1,1,0)||bc(0,m-1,0,m-2,1,m-1)||bc(n-1,0,n-2,0,n-1,1)||bc(n-1,m-1,n-2,m-1,n-1,m-2)){
        cout<<"NO\n";
        return;
    }
    for(int i=0;i+1<n;i++){
        for(int j=0;j+1<m;j++){
            char a=g[i][j],b=g[i][j+1],c=g[i+1][j],d=g[i+1][j+1];
            if((a=='1'||a=='2')&&a==d&&(b=='1'||b=='2')&&b==c&&a!=b){
                cout<<"NO\n";
                return;
            }
        }
    }
    for(auto &q:p){
        if(!f(q.first,q.second)){
            cout<<"YES\n";
            return;
        }
    }
    vector<int>s;
    for(int j=0;j<m;j++){
        char c=g[0][j];
        if(c=='1'||c=='2')s.push_back(c-'0');
    }
    for(int i=1;i<n;i++){
        char c=g[i][m-1];
        if(c=='1'||c=='2')s.push_back(c-'0');
    }
    for(int j=m-2;j>=0;j--){
        char c=g[n-1][j];
        if(c=='1'||c=='2')s.push_back(c-'0');
    }
    for(int i=n-2;i>=1;i--){
        char c=g[i][0];
        if(c=='1'||c=='2')s.push_back(c-'0');
    }
    if((int)s.size()==4&&s[0]==s[2])cout<<"NO\n";
    else cout<<"YES\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _;
    cin>>_;
    while(_--)gao();
    return 0;
}

做法二（最短路优先 + 另一对联通性检查）：

分别尝试两种顺序，只要一种成功就是 YES：

先在不经过 2 的前提下，求 1-1 的一条最短路（BFS+前驱回溯）。把这条路上用到的 0 格标记为已占用；然后检查在避开这些已占用 0 且不经过 1 的前提下，2-2 是否仍然联通（BFS）。
反过来，先求 2-2 最短路并占用其 0，再检查 1-1 是否联通。

实现上，最短路只需要记录前驱并回溯出路径，然后把路径上的 0 置为已占用即可。

参考代码（做法二）：

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

int n,m;
string g[505];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};

int id(int x,int y){return x*m+y;}

vector<int>sp(int s,int t,char ban,vector<char>&u){
    int N=n*m;
    vector<int>pre(N,-1);
    queue<int>q;
    pre[s]=s;
    q.push(s);
    while(!q.empty()){
        int v=q.front();q.pop();
        int x=v/m,y=v%m;
        for(int k=0;k<4;k++){
            int nx=x+dx[k],ny=y+dy[k];
            if(nx<0||nx>=n||ny<0||ny>=m)continue;
            int w=id(nx,ny);
            if(pre[w]!=-1)continue;
            if(w!=t&&w!=s){
                if(g[nx][ny]==ban)continue;
                if(g[nx][ny]!='0')continue;
                if(u[w])continue;
            }else{
                if(g[nx][ny]==ban)continue;
            }
            pre[w]=v;
            q.push(w);
        }
    }
    if(pre[t]==-1)return {};
    vector<int>p;
    for(int v=t;;v=pre[v]){
        p.push_back(v);
        if(v==s)break;
    }
    reverse(p.begin(),p.end());
    return p;
}

int ok(int s,int t,char ban,vector<char>&u){
    int N=n*m;
    vector<char>vis(N);
    queue<int>q;
    vis[s]=1;
    q.push(s);
    while(!q.empty()){
        int v=q.front();q.pop();
        if(v==t)return 1;
        int x=v/m,y=v%m;
        for(int k=0;k<4;k++){
            int nx=x+dx[k],ny=y+dy[k];
            if(nx<0||nx>=n||ny<0||ny>=m)continue;
            int w=id(nx,ny);
            if(vis[w])continue;
            if(w!=t&&w!=s){
                if(g[nx][ny]==ban)continue;
                if(g[nx][ny]!='0')continue;
                if(u[w])continue;
            }else{
                if(g[nx][ny]==ban)continue;
            }
            vis[w]=1;
            q.push(w);
        }
    }
    return 0;
}

vector<char>u;

int go(int s1,int t1,char ban1,int s2,int t2,char ban2){
    fill(u.begin(),u.end(),0);
    vector<int>p=sp(s1,t1,ban1,u);
    if(p.empty())return 0;
    for(int v:p){
        int x=v/m,y=v%m;
        if(g[x][y]=='0')u[v]=1;
    }
    return ok(s2,t2,ban2,u);
}

int solve2(){
    vector<pair<int,int>>p1,p2;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(g[i][j]=='1')p1.push_back({i,j});
            if(g[i][j]=='2')p2.push_back({i,j});
        }
    }
    int a1=id(p1[0].first,p1[0].second),b1=id(p1[1].first,p1[1].second);
    int a2=id(p2[0].first,p2[0].second),b2=id(p2[1].first,p2[1].second);
    u.assign(n*m,0);
    if(go(a1,b1,'2',a2,b2,'1'))return 1;
    if(go(a2,b2,'1',a1,b1,'2'))return 1;
    return 0;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _;
    cin>>_;
    while(_--){
        cin>>n>>m;
        for(int i=0;i<n;i++)cin>>g[i];
        cout<<(solve2()?"YES\n":"NO\n");
    }
    return 0;
}

E. 躯树の墓守

难度：CF 2400 （本题出题人TRfirst估本题1800）

知识点：最小生成树、Kruskal、构造、贪心

思路：

要构造一个含 $n$ 点、 $m$ 边的简单连通无向图，所有边权互不相同且都在 $[1,m]$ ，并且整张图的最小生成树（MST）边权和恰好为 $k$ 。

核心想法：先固定 MST 的形状为一条链 $1-2-\cdots-n$ ，然后通过“跳过”一些小权值来调节 MST 和，同时保证被跳过的小权值只能出现在“已经连通的前缀组件”内部，从而不会破坏 Kruskal 选出的 MST。

1）固定 MST 权值形式

把 MST 的第 $i$ 条边（连接 $i$ 与 $i+1$ ）权值设为

s_i=i+x_i\qquad (1\le i\le n-1),

其中 $x_1\le x_2\le\cdots\le x_{n-1}$ 且 $x_i\ge 0$ 。

最小的 MST 和是

\sum_{i=1}^{n-1} i=\frac{n(n-1)}{2}.

若 $k$ 更小则直接输出 NO。令

\Delta = k-\frac{n(n-1)}{2},

则我们需要

\sum_{i=1}^{n-1} x_i=\Delta.

另外因为边权必须在 $[1,m]$ 且互不相同，最大那条 MST 边满足 $s_{n-1}\le m$ ，即

x_{n-1}\le m-n+1,

由于 $x$ 单调不降，所有 $x_i$ 都有同样上界。

2）“结构容量”约束（保证 MST 不被更小边替换）

考虑 Kruskal 扫描到权值 $s_i$ 之前，链上的前 $i$ 个点 $1..i$ 已经通过 $s_1..s_{i-1}$ 连成一个连通块。

在 $s_i$ 之前一共会出现多少“非 MST 的小边权”？恰好是被跳过的那些权值个数：

x_i = |\{w\in[1,s_i): w\notin\{s_1,\dots,s_{i-1}\}\}|.

为了不让这些更小的边把第 $i+1$ 个点提前连进来（从而改变 MST），我们把所有这些小权边都放在点集 $1..i$ 的内部边上。

点集 $1..i$ 内部一共有 $\binom{i}{2}$ 条边，其中链上已经用了 $i-1$ 条，所以可放置的“非树边槽位”数量为

\binom{i}{2}-(i-1)=\frac{(i-1)(i-2)}{2}.

因此必须满足

x_i\le \frac{(i-1)(i-2)}{2}.

3）构造 $x$ （从后往前贪心）

我们要找一组单调不降的 $x_i$ ，同时满足上述每个位置的上界、以及总和为 $\Delta$ 。做法：从 $i=n-1$ 到 $1$ 逆序贪心，令

$cap_i=\min\!\left(\frac{(i-1)(i-2)}{2},\ m-n+1\right)$ ；
维护右侧的上界 $x_i\le x_{i+1}$ （逆序时就是“当前不能超过 next”）。

每一步取

x_i=\min(cap_i,\ next,\ \Delta),

并让 $\Delta\leftarrow \Delta-x_i$ ，更新 $next\leftarrow x_i$ 。若最后 $\Delta>0$ ，说明无论如何都凑不出目标和，输出 NO。

4）把剩余权值塞进非树边

MST 边已经占用了一些权值 $s_i$ ，其余未用的权值按从小到大收集成数组 $R$ 。
然后枚举所有非相邻点对 $(u,v)$ （即 $v\ge u+2$ ），按 $v$ 从小到大、 $u$ 从小到大输出，并依次赋予权值 $R$ 。

由于前缀容量约束 $x_i\le \frac{(i-1)(i-2)}{2}$ 保证了所有小于 $s_i$ 的非 MST 权值都能完全放在点集 $1..i$ 内部，因此在 Kruskal 过程中，连接新点 $i+1$ 的最小跨割边仍然是链边 $(i,i+1)$ （权值 $s_i$ ），MST 形状与权值和就被锁死为我们想要的。

参考代码：

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

void solve(){
    int n,m,k;
    cin>>n>>m>>k;
    int mn=n*(n-1)/2;
    if(k<mn){cout<<"NO\n";return;}
    int d=k-mn;
    vector<int>x(n+1);
    int nxt=(1LL<<62);
    for(int i=n-1;i>=1;i--){
        int s=(i-1)*(i-2)/2;
        int v=m-n+1;
        int cap=min(s,v);
        int val=min(cap,min(nxt,d));
        x[i]=val;
        d-=val;
        nxt=val;
    }
    if(d>0){cout<<"NO\n";return;}
    cout<<"YES\n";
    vector<char>used(m+1);
    vector<int>R;
    for(int i=1;i<n;i++){
        int w=i+x[i];
        used[w]=1;
        cout<<i<<" "<<i+1<<" "<<w<<"\n";
    }
    for(int w=1;w<=m;w++)if(!used[w])R.push_back(w);
    int need=m-(n-1),id=0;
    for(int v=3;v<=n&&id<need;v++){
        for(int u=1;u<=v-2&&id<need;u++){
            cout<<u<<" "<<v<<" "<<R[id++]<<"\n";
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _;
    cin>>_;
    while(_--)solve();
    return 0;
}

2026最新求职资料大礼包领取

大家都在关注

校招日程表笔试日历 ai模拟面试面试宝典剑指offer 知识点专项练习

已采纳

采纳

精彩回帖

精彩

全部评论

(6) 回帖

加载中...

话题同步到我的动态回帖

【题解】2026牛客寒假算法基础集训营3题解

整场评价与题目分类

A. 宙天

G. スピカの天秤

B. Random

J. Branch of Faith

H. Tic Tac DREAMIN'

特判

C. Inverted World

F. Energy Synergy Matrix

关键观察

结论： $r=\left\lfloor \dfrac{n}{5}\right\rfloor$

I. BenzenE

1）转化成“子集异或等于目标”

2）XOR 线性基 + 回溯方案

D. 系ぎて

E. 躯树の墓守

1）固定 MST 权值形式

2）“结构容量”约束（保证 MST 不被更小边替换）

3）构造 $x$ （从后往前贪心）

4）把剩余权值塞进非树边

已采纳

精彩回帖

全部评论

本文相关内容

等你来战

热门推荐

【题解】2026牛客寒假算法基础集训营3题解

整场评价与题目分类

A. 宙天

G. スピカの天秤

B. Random

J. Branch of Faith

H. Tic Tac DREAMIN'

特判

C. Inverted World

F. Energy Synergy Matrix

关键观察

结论：

I. BenzenE

1）转化成“子集异或等于目标”

2）XOR 线性基 + 回溯方案

D. 系ぎて

E. 躯树の墓守

1）固定 MST 权值形式

2）“结构容量”约束（保证 MST 不被更小边替换）

3）构造 （从后往前贪心）

4）把剩余权值塞进非树边

已采纳

精彩回帖

全部评论

本文相关内容

等你来战

热门推荐

结论： $r=\left\lfloor \dfrac{n}{5}\right\rfloor$

3）构造 $x$ （从后往前贪心）