2026 牛客五一集训派对（一）

（本题解按照题目难度排序，仅用作补题记录）

A. World Fragments I

解题思路

给出两个二进制数 $x , y$
由于 $x$ 是二进制数，每一次最多只能 $+1$ 或 $-1$ , 所以最少次数为 $abs(y_{(10)} - x_{(10)})$
当 $x$ 为 $0$ 时，无法改变，特判一下
由于 $x$ 和 $y$ 比较大，我用了 $int128$ 存的十进制，也可以直接在 $2进制$ 上记录答案，然后直接计算最终的十进制答案。

H. Until the Blue Moon Rises

解题思路

1.强哥德巴赫猜想：即任一大于2的偶数都可写成两个质数之和；（未被证明，但在本题的范围内全部成立）
2.弱哥德巴赫猜想: 任何一个大于5的奇数都能被表示成三个奇质数的和。（已经被证明）
本题有三种情况：
$sum = \sum a_i$
当 $n==1$ 时，直接试除法 $\sqrt n$ 判断即可.
当 $n==2$ 时，当 $sum$ 为偶数, $sum>=4$ 时成立; $\ \ sum$ 为奇数,拆分为一偶一奇，偶数只能为 $2$ ，另外判断一下 $sum-2$ 即可
当 $n>=3$ 时, $n-3$ 个数字都变成 $2$ ，剩下的 $sum-(n-3)*2$ 只要大于等于 $6$ 即可，综上 $sum >= 2 * n$ 即可

J. Fine Logic

解题思路

如果所有的关系不冲突，从入度为0的点开始找，会构成一个拓扑序列，直接遍历即可
存在冲突关系，两个序列就能包含所有的关系，所以直接写一遍正序，一遍反序即可。

E.Koraidon, Miraidon and DFS Shortest Path. Absolute Cinema

解题思路

先跑一遍作为标准距离 $dist$
然后随机打乱邻接表，跑个 $50$ 次 $DFS$ ，跑完和标准距离比较一下
我也想用支配树写，但我不会写支配树 TvT

D - Ama no Jaku

解题思路

注意到 $min(r_i)>=max(c_i)$ 的条件很难满足，只有 $min(r_i)=max(c_i)$ 的合法情况
问题转化成把矩阵转化成全 $0$ 或者全 $1$
由于矩阵转换的顺序是不影响的，所以必须在行变换之后，所有的行都变成相同的，才能使用列变换转成全 $0$ 全 $1$ 矩阵，最后只需要计算转换成哪种更小即可

B - Auspiciousness

解题思路

枚举猜对了 $i$ 张牌，其中有 $k1$ 张 $<=n$ 的牌，有 $i-k1$ 张 $>=n+1$ 的牌。
相同集合的牌连续的话， $<=n$ 的牌必须严格递增， $>=n+1$ 的牌必须严格递减。
必须两个集合的连续段交错排列才合法。
设 $k1$ 张 $<=n$ 的牌有 $num1$ 个连续段，设 $i-k1$ 张 $>=n+1$ 的牌有 $num2$ 个连续段。合法情况有三种：
$1.num1=num2$ :段数相同两个集合都可以作为开头
$2.num1=num2+1$ :小牌段作为开头
$3.num2=num1+1$ :大牌段作为开头

计算时：
$1.$ 把 $k1$ 张牌划分为 $num1$ 个段，可以使用第二类斯特林数（ $S[n][m]$ 表示把 $n$ 个不同元素划分为 $m$ 个非空集合的方案数）
$2.$ 模数不一定是质数，不能使用乘法逆元，使用三角递推求组合数，避免除法

F[0]=1;
for(int i=1;i<=2*n;i++)F[i]=F[i-1]*i%mod;


for(int i=0;i<=n;i++){
  C[i][0]=1;
  for(int j=1;j<=i;j++){
    C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
  }
}


S[0][0]=1;
for(int i=1;i<=n;i++){
  for(int j=1;j<=i;j++){
    S[i][j]=(S[i-1][j-1]+1LL*j%mod*S[i-1][j]%mod)%mod;
  }
}


int ans=0;
for(int i=1;i<2*n;i++){
  for(int k1=max(0ll,i-n);k1<=min(i,n);k1++){
    int k2=i-k1;
    for(int num=1;num<=max(k1,k2);num++){
      if(k1>=num&&k2>=num){}
      if(k1>=num&&k2>=num-1){}
      if(k1>=num-1&&k2>=num){}
    }
  }
}
ans=(ans+F[2*n])%mod;
cout<<ans<<"\n";