A 接木成三角

根据题意模拟依次判断三个三角形是否合法即可。三角形合法判定：判断三角形短的两边之和大于第三边即可。

#include <stdio.h>
#include <bits/stdc++.h>
#define yes printf("Yes\n")
#define no printf("No\n")
#define ll long long
#define all(x) x.begin(),x.end()
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

bool if_ok(ll a,ll b,ll c){
	if(a>b)swap(a,b);if(b>c)swap(b,c);if(a>b)swap(a,b);
	return (a+b>c);
}

int main(){
	long long a,b,c,x; cin>>a>>b>>c>>x;
	if(if_ok(a+x,b,c) || if_ok(a,b+x,c) || if_ok(a,b,c+x)) yes;
	else no;
	return 0;
}

B 开盒有风险

用到了数学期望的性质。第 $i$ 种卡包的其中 $1$ 张卡是第 $j$ 个卡片的概率是 $p_{ij}$ ，那么可以理解为：

$1$ 包第 $i$ 种卡包的 $1$ 张卡期望得到 $p_{ij}$ 张第 $j$ 个卡片。

$1$ 包第 $i$ 种卡包的 $k$ 张卡期望得到 $k * p_{ij}$ 张第 $j$ 个卡片。

$a_i$ 包第 $i$ 种卡包的 $k$ 张卡期望得到 $a_i * k * p_{ij}$ 张第 $j$ 个卡片。

期望可以累加，所以把每包卡包期望得到每种卡片的张数累加一下即可。

#include <stdio.h>
#include <bits/stdc++.h>
#define yes printf("Yes\n")
#define no printf("No\n")
#define ll long long
#define all(x) x.begin(),x.end()
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

int main(){
	int n,m,k; cin>>n>>m>>k;
	vector<vector<double>> pij(n,vector<double>(m));
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++) cin>>pij[i][j];
	}
	vector<int>bao(n);
	for(int i=0;i<n;i++)cin>>bao[i];
	vector<double>ans(m,0);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++) ans[j] += pij[i][j] * bao[i] * k;
	}
	for(int i=0;i<m;i++) printf("%.2f ",ans[i]);
	return 0;
}

C 诛伏赐死

先不考虑禁用某个砝码的情况。

由于砝码重量都是3的幂，那么初始状态只有重量为1的砝码满足模3余1，其他砝码都满足模3余0。所以我们必须在放好重量为1的砝码后使得天平左右两边质量之差满足模3余0,否则永远无法平衡（其他砝码都不能改变天平左右两边重量之差模3后的值）。

现在我们看重量为1的砝码应该放在哪里。记天平左右两边重量之差为 $diff$ 。

若 $diff$ 模3余0：不需要放置重量为1的砝码。否则会破坏 $diff$ 模3的值。
若 $diff$ 模3余1：重量为1的砝码放能使 $diff$ -1 的一边。
若 $diff$ 模3余2：重量为1的砝码放能使 $diff$ +1 的一边。

处理好该砝码后，我们发现：现在所有剩余砝码重量都是3的倍数， $diff$ 也是3的倍数。我们对 $diff$ 和所有砝码重量都除以3，就又回到了有一个重量为1的砝码的情况，可以递归讨论。 同时，我们也可以注意到这种砝码安排方式是唯一的。

现在考虑禁用某个砝码的情况。我们只需要记录以上过程用到了哪些砝码，判断有没有用到禁用砝码。若用到禁用砝码，直接输出 $No$ 。

#include <stdio.h>
#include <bits/stdc++.h>
#define yes printf("Yes\n")
#define no printf("No\n")
#define ll long long
#define all(x) x.begin(),x.end()
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

int main(){
	int testcases;
	cin >> testcases; //REMEMBER THE Initialization !
	while(testcases--){
		int M,k; cin>>M>>k;
		int flag = 1 ;
		for(int i=0;i<=20;i++){
			if(M%3==0);
			if(M%3==1){
				if(k==i) flag = 0;	
			} 
			if(M%3==2){
                M++;
				if(k==i)flag = 0;
			}
			M/=3;		
		}
		if(flag)yes;
		else no;
	}
	return 0;
}

D 书架整理

一开始没注意到不能重排书本的顺序，所以这题要用dp来解。我的dp是三维的，可能稍微复杂一点，可以看看别的选手的二维dp。

怎么考虑dp转移和状态？那就看在末尾添加一本书时会有哪些情况。

1.添加的一本书单独放一层（加一个新的层）
2.添加的书和前面的书一起放最后一层

对于情况1，我们发现需要维护层数。对于情况2，我们发现：若添加的书不是最后一层最高的书，那么最后一层的高度不会发生变化，总代价也不变。否则，最后一层的高度需要变化。基于此考虑，我们需要在dp过程中记录最后一层最高的书是哪一本。

所以，dp状态可以设为

$dp[floor][i][j] : 当前有 floor 层，已经放了前 i 本书，最后一层最高的书是第j本$

那么答案就是 $\min_{i}dp[m][n][i]$ 。

实现如下：

#include <stdio.h>
#include <bits/stdc++.h>
#define yes printf("Yes\n")
#define no printf("No\n")
#define ll long long
#define all(x) x.begin(),x.end()
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

ll dp[201][201][201]; //f[k][i][j] : to ith , premax=j , k-th floor

int main(){
	int n,m; cin>>n>>m;
	vector<int>h(n+1);
	for(int i=1;i<=n;i++)cin>>h[i];
	h[0] = 0;
	
	for(int k=0;k<=m;k++)
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			if(!k && !i && !j)dp[k][i][j] = 0;
			else dp[k][i][j] = 999999999999999;	
		}
	}
	
	for(int k=1;k<=m;k++){
		for(int i=1;i<=n;i++){
			// add 1 floor
			for(int j1=0;j1<=i;j1++){
				dp[k][i][i] = min(dp[k][i][i], dp[k-1][i-1][j1] + h[i]);	
			}
			// merg i
			for(int j1=0;j1<=i;j1++){
				if(h[i]<h[j1])dp[k][i][j1] = min(dp[k][i][j1] , dp[k][i-1][j1]);
				else dp[k][i][i] = min(dp[k][i][i] , dp[k][i-1][j1] + (h[i] - h[j1])) ;
			}
		}	
	}
	
	ll ans = 99999999999999;
	for(int j=1;j<=n;j++) ans = min(ans , dp[m][n][j]);
	cout << ans;
	return 0;
}

E MuQ 的难题

如果你注意到了哥德巴赫猜想，那么就会发现序列至多只有3个数。

如果没注意到，可以像我写一个小范围 (<B) 内的 $n^2$ dp 求解最短序列长度。然后 $x$ 较大时在 $(x-B,x]$ 范围内挑一个质数出来，然后结合dp结果求解。

写个埃氏筛预处理判断质数，时间复杂度 $O(B^2 + AlogA + T*B)$ ，其中 $A = 1e7$ 为 x 的最大值。

#include <stdio.h>
#include <bits/stdc++.h>
#define yes printf("Yes\n")
#define no printf("No\n")
#define ll long long
#define all(x) x.begin(),x.end()
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

const int B = 5e3;
const int BB = 1e7+2;

bool prfun(int x){
	if(x<=1) return false;
	if(x==2 || x==3) return true;
	for(int i=2;i<=sqrt(x+1);i++){
		if(x%i==0)return false;
	}
	return true;
}

int main(){

	int isprime[BB];
	for(int i=0;i<BB;i++){
		isprime[i] = 1;	
	}
	isprime[0] = isprime[1] = 0;
	for(int i=2;i<BB;i++){
		if(isprime[i]) for(int j=2*i;j<BB;j+=i) isprime[j] = 0;
	}


	int dp[B];
	dp[0] = 0 , dp[1] = 99999999 , dp[2] = dp[3] = 1;
	for(int i=4;i<B;i++){
		dp[i] = 99999999;
		for(int mi=2;mi<=i;mi++){
			if(isprime[mi])	dp[i] = min(dp[i] , dp[i-mi]+1);
		}
		//cerr << "i " << i<< " " <<dp[i] << endl;
	}
	
	int testcases;
	cin >> testcases;
	while(testcases--){
		int x; cin>>x;
		if(x==1) { cout << "-1\n"; continue;}
		if(x<B){cout << dp[x] << "\n" ; continue;}
		
		int an = 99999999;
		for(int mi=0;mi<B;mi++){
			if(isprime[x-mi]) an = min(an,dp[mi]+1);	
		}
		cout << an << "\n";	
	}
	

	return 0;
}

F 文艺平衡树

没见过，不会。

G 生成树问题

接下来我会以 “ $a_ib_i$ ” 的形式称呼一个点。那么根据题意，我们有四类点： $00,01,10,11$ 。其中，只有 $00,11$ 可以作为根！（我一开始读错题了以为是 $00,10$ 做根）。

那么，根据根节点的不同，我们进行分类讨论：

若 $00$ 为根，那么它自己可以有若干个 $00$ 和 $11$ 作为儿子。但 $01,10$ 不能是根节点的儿子。而如果 $00$ 根有 $11$ 儿子，那么 $01,10$ 都能接在这个 $11$ 儿子上。
若 $11$ 为根，那么它自己可以有若干个 ......<请读者自行补全>

统计四类节点个数，然后写代码讨论即可。

#include <stdio.h>
#include <bits/stdc++.h>
#define yes printf("Yes\n")
#define no printf("No\n")
#define ll long long
#define all(x) x.begin(),x.end()
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

int main(){
	int n; cin>>n;
	vector<int>a(n),b(n);
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<n;i++)cin>>b[i];
	int c00=0,c01=0,c10=0,c11=0;
	for(int i=0;i<n;i++){
		if(a[i]==0&&b[i]==0)c00++;
		if(a[i]==0&&b[i]==1)c01++;
		if(a[i]==1&&b[i]==0)c10++;
		if(a[i]==1&&b[i]==1)c11++;
	}
	//cerr << c00 << " " << c01 << " " << c10 << " " << c11;
	bool flg1 = false;
	if(c00){
		if(c11)flg1=true;
		else if(!c01 && !c10) flg1 = true;
	}
	bool flg2 = false;
	if(c11){
		if(c10)flg2 = true;
		else if(!c00 && c11==1) flg2 = true;		
	}
	
	if(flg1 || flg2) yes;
	else no;
	
	return 0;
}

H 最长公共前缀

据说正解是字典树莫队，但由于本题数据比较水，写 $O(n^2)$ 的暴力也是能通过的。查询的时候写一个前缀和就可以快速查询。

$O(n^2)$ 暴力难点在于卡空间。本题空间上限是256MB ，开 $n^2$ 个int会爆，需要控制好开 $n^2/2$ 左右个int。最后AC代码空间占用为 197 MB。

#include <stdio.h>
#include <bits/stdc++.h>
#define yes printf("Yes\n")
#define no printf("No\n")
#define ll long long
#define all(x) x.begin(),x.end()
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

int lcp(string &a, string &b){
	int res = 0;
	int n = min(a.size(),b.size());
	for(int i=0;i<n;i++){
		if(a[i]==b[i])res++;
		else break;
	}
	return res;
}

int idx(int i,int j){
	return (j+1)*(j+2)/2 + i;
}

// 这里开res[10001][10001]会 MLE
int res[50100000];

int main(){
	int n,q; cin>>n>>q;
	//vector<vector<int>>res(n+1,vector<int>(n+1,0));
	vector<string>ss(n);
	for(int i=0;i<n;i++) cin>>ss[i];
	
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++) res[idx(i,j)] = lcp(ss[i],ss[j]);
	}
	
	
	for(int i=0;i<n;i++){
		for(int j=i+2;j<n;j++){
			res[idx(i,j)] += res[idx(i,j-1)];
			
		}
	}
	
	while(q--){
		int l,r; cin>>l>>r;
		l--;r--;
		ll ans = 0;
		for(int i = l;i < r;i++){
			ans += res[idx(i,r)];
		}
		cout << ans << endl;
	}
	
	
	return 0;
}

I 安魂曲

给每个点记“当前有哪些权限卡”和“当前电源开关情况” 这两类状态（共32*2=64种状态），然后写个bfs全图搜索就行。复杂度 $O(64*m*n)$ 显然能过，考验选手耐心和debug能力。我赛时倒闭了没写出来，因为我没注意到 $P,a,b,c,d,e$ 这些位置可以不止出现一个，然后写了一点神秘东西...

选手题解（不会F题） | 2026年安徽大学第十八届大学生程序设计竞赛