企业官网建设流程全解析

T1刘关张桃园结义

题意给定一个长度为 n的整数数组 a。 你需要统计有多少个不同的位置对 $(i,j)$（满足 $1≤i<j≤n$），使得 $a_i+a_j=0$。

解题思路

注意关键点：

• 是位置对，不是数值对！相同数值出现在不同位置就算不同对；
• 特殊：0+0=0；
• 根据$a_i$最大范围是 $[−100,100]$，使用桶数组统计时可以让数+100进行偏移下（也可以直接用map统计）

1.开个桶，统计一下每个数字的个数

2.遍历桶数组，每个数和其相反数的个数相乘

3.特殊处理下零（不能和自己组对）

极端情况（例如一半 1 一半 -1），答案可能会达到 $(n/2)×(n/2)=2.5×10^9$，

这超过了int的最大值（约$2.14×10^9$），所以统计答案的变量必须使用long long。

分段数据解决方法

1. 对于 20% 的数据（n≤50）：直接写两层for循环枚举i和j，判断 $a_i+a_j==0$ 即可，时间复杂度 $O(n^2)$。
2. 对于 $a_i=0$ 的特殊数据：直接计算组合数 $C_n^2 = \frac{n \times (n-1)}{2}$即可。
3. 对于 $a_i$∈{1,−1} 的数据：分别统计 1 和 -1 的个数，相乘即为答案。
4. 对于 100% 的数据：使用桶遍历一次数组，边统计边记录，复杂度$O(n)$。

参考代码（STD）：

#include <bits/stdc++.h> using namespace std; long long a[205],ans; int main() { int n; cin >> n; for(int i=1;i<=n;i++) { int x; cin>>x; a[x+100]++; } for(int i=1;i<=100;++i) {//桶是0~200范围 只看一半 ans+=a[i+100]*a[-i+100]; } ans+=a[100]*(a[100]-1)/2;//0特殊处理 cout<< ans; return 0; } /* #include<bits/stdc++.h> #define ll long long using namespace std; int n; map<int,ll> mp; ll cnt=0; int main(){ cin>>n; for(int i=1;i<=n;i++){ long long x; cin>>x; mp[x]++; } for(int i=1;i<=100;i++){ cnt+=mp[i]*mp[-i]; } cnt+=mp[0]*(mp[0]-1)/2; cout<<cnt; return 0; } */

T2字里行间的空间

题意是给定按顺序排列的 N 个单词长度 $L_i$，要把它们分成不超过 M个连续的行。

同一行中相邻单词之间至少有一个空格，因此一行放单词 个数为cnt个时，该行最小宽度为：

$\sum\limits_{i=l}^{r} L_i + cnt-1$

要求最大的行宽最小。

解题思路

是典型的“最大值最小化”问题，考虑二分答案。

（若宽度x 可行，那么更大的宽度一定也可行，答案具有单调性。)

二分范围，下限为最长单词长度，上限为所有单词长度和+N-1

设当前尝试的最大行宽为 x，判断是否能用不超过 M行放下所有单词。

$check$函数判断方法采用贪心：

• 从左到右依次遍历单词；
• 如果当前单词还能放入当前行，就放进去，累计当前总行宽；
• 否则新开一行，记录当前行宽；
• 最后统计行数是否不超过 M。

注意：

• 二分左边界不能从 0 开始，必须是最长单词，不然单个单词都放不下
• 单词顺序固定，贪心从左往右塞是正确的（尽量塞满，是最少行数）。
• 必须开 long long！$L_i\le10^9，N=2e5$，总和会爆 int。

分段数据解决方法

1. 30% 数据：暴力枚举答案 + 贪心校验（本质就是二分的朴素版本，不二分，从小到大暴力遍历，从下界（最长单词）开始，一点点 + 1，每次 check 能不能分≤M 行，第一个满足条件的 就是答案）。
2. 全部数据：二分+贪心判断。

STD:

#include<bits/stdc++.h> #define ll long long using namespace std; const int N=2e5+10; int a[N],n,m,maxx; ll sum=0; bool check(ll x){ ll s=a[1]; ll hs=1;//初始至少一行 for(int i=2;i<=n;i++){ if(s+1+a[i]<=x){ s+=a[i]+1; }else{//不能放在当前行 新开 hs++; s=a[i]; if(hs>m) return 0; } } return hs<=m; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; maxx=max(a[i],maxx); sum+=a[i]; } ll L=maxx,R=sum+n-1; while(L<R){ ll mid=(L+R)>>1; if(check(mid)){ R=mid; }else{ L=mid+1; } } cout<<R; return 0; }

T3量子跃迁：机器人觉醒

题意是给定一棵 n 个节点的树。定义度数为 2的节点为“特殊点”。 初始时，每个特殊点上有一个机器人。每次操作，所有机器人都会向其相邻的节点移动一步。 对于树上的每一个节点，求最少经过多少次操作，会有一个机器人到达该节点。

（注：“最少操作次数”即求每个节点到所有特殊点的最短距离。）

解题思路：

这是一个典型的多源最短路问题。由于树上的边权均为 1，因此可以直接使用多源 BFS（广度优先搜索）来解决。

• 首先，在读入边的时候统计每个节点的度数。
• 遍历所有节点，将度数等于 2 的节点（特殊点）作为起点加入队列，并将其距离初始化为 0。
• 接着进行正常的 BFS 扩展。每次取出队头节点，遍历其相邻节点；如果相邻节点未被访问过，则将其距离设为当前节点距离 +1，并加入队列。
• BFS 结束后，每个节点的最短距离即为答案。

时间复杂度：O(n)，每个节点和每条边最多被访问一次。 空间复杂度：O(n)，需要存储图结构、距离数组和队列。

分段数据解决方法

• 20% 数据（n≤100，一个特殊点）： 直接以这个唯一的特殊点为起点，跑一遍普通的单源 BFS 即可。
• 另外 20% 数据（n≤100，多个特殊点）： 可以跑单源 BFS（对每个特殊点跑一次 BFS，取最小值，时间复杂度 O($n^2$)）
• 另外 20% 数据（n≤$10^6$，一个特殊点）： 单源 BFS 跑满 $10^6$个节点。由于 n较大，需要用链式前向星（或vector数组）存图，并加上输入输出优化以防止超时或内存超限。
• 100% 数据（n≤$10^6$，多个特殊点）： 多源 BFS。将所有的特殊点同时入队（距离均为 0），其余点距离初始化为 -1。这样可以确保每个节点第一次被访问时，算出的距离就是距离它最近的特殊点的距离。

STD:

#include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e6+10; vector<int>g[N]; int dis[N],du[N]; queue<int>q; int n; void bfs(){ while(!q.empty()){ int x=q.front(); q.pop(); for(int i=0;i<g[x].size();i++){ int y=g[x][i]; if(dis[y]==-1){ dis[y]=dis[x]+1; q.push(y); } } } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n; for(int i=1;i<=n-1;i++){ int x,y; cin>>x>>y; g[x].push_back(y); g[y].push_back(x); du[x]++; du[y]++; } for(int i=1;i<=n;i++){ dis[i]=-1; if(du[i]==2){ q.push(i); dis[i]=0; } } bfs(); for(int i=1;i<=n;i++){ cout<<dis[i]<<" "; } return 0; }

T4数字王国的冒险团选拔

题意给定 n 个正整数 ，从中选出m 个数，使得这 m 个数的乘积末尾 0 的个数最多。 （乘积末尾 0 的个数取决于乘积中因子2 的总数和因子 5 的总数中的较小值。）

解题思路：

一个数乘积末尾 0 的个数，等于这个数中因子 2 的个数和因子 5 的个数的较小值（因为 10=2×5）。 目标：在选出 m 个数的前提下，使得选出的数中，因子 2 总数和因子 5 总数尽可能多，且两者尽量平衡（取较小值最大化）。

1.模型抽象（二维费用的01背包 ）:

把它看作一个背包问题：

• 物品：n 个数字。

• 限制条件 1（第一维费用）：只能选 m 个数。

• 限制条件 2（第二维费用）：选出的数包含的因子 5 总数。

• 物品价值：该数字包含的因子 2 个数。

  考虑数据范围n≤200，$a_i≤10^{18}$：

  $5^{26}$≈1.49×$10^{18}$>$10^{18}$，所以一个数最多只有 26个因子 5

  $2^{60}$≈1.15×$10^{18}$>$10^{18}$，所以一个数最多有 60 个因子 2。

  因此所有数的因子 5 总数最多为 200×25=5000，所有数的因子 2 总数最多为 200×60=12000。

2.数据预处理

对于输入的每一个数，不断除以2，统计能得到几个因子2，记为c2[i]，同理得到c5[i]。

3.定义状态与初始化

dp[i][j][k]表示：在前 i 个数字中，挑选了 j个数字，且这些数字的总因子 5 数量恰好为 k时，所能得到的最大总因子 2 数量。

面对第 i 个数，有两种选择：

1. 不选这个数：dp[i][j][k] = dp[i-1][j][k]
2. 选这个数（前提是 j≥1 且 k≥c5[i]）：dp[i][j][k] = dp[i-1][j-1][k-c5[i]] + c2[i]

所以状态转移方程是：dp[i][j][k] = max(不选, 选)

三维 DP 代码（方便理解，会 MLE 超内存）dp[i][j][k]的内存： 200×200×5000=2×$10^8$

dp数组优化成二维，循环倒序遍历：dp[j][k]=max(dp[j][k],dp[j-1][k-c5[i]]+c2[i]);

初始化：

dp数组初始化极小的负数（状态不可达），dp[0][0]=0

4.状态转移（0-1 背包核心）

遍历每一个物品 i，并在循环内部倒序遍历两个容量维度：

• 倒序枚举选数个数 j：从 m 递减到0。
• 倒序枚举因子 5 数量 k：从当前因子 5 总数递减到 0。
• 转移方程：dp[j][k]=max(dp[j][k],dp[j-1][k-c5[i]]+c2[i]);

5.统计答案：

遍历所有可能的因子 5 总数 （k：从 0 到 因子5的总数）：

• 如果dp[m][k]是合法的（大于等于 0），说明成功选出了 m个数。
• 此时这 m 个数能组成的末尾 0的个数为min(k, dp[m][k])。
• 在所有合法的 k中，取min(k, dp[m][k])的最大值作为最终答案输出。

复杂度：O(n⋅m⋅∑c5)，即 200×200×5000≈2×$10^8$ 次运算，配合动态上界优化和常数优化，可以稳过。

分段数据解决方法

• 20% 数据（n≤15）：二进制枚举 / DFS 暴搜。

  可以用一个二进制数（状态压缩）来表示 n个数的选取状态，或者直接写一个 DFS 搜索。如果当前状态选了恰好 m 个数，就统计这 m 个数的总因子 2 数量和总因子 5 数量，两者取较小值（即末尾 0 的个数），然后更新全局最大值。复杂度：O($2^n$×n)，在 n=15 时瞬间跑完。

  #include <bits/stdc++.h> using namespace std; const int MAXN = 205; int n, m; int x[MAXN]; // x[i]：第 i 个数的因子 2 个数 int y[MAXN]; // y[i]：第 i 个数的因子 5 个数 int ans = 0; // 全局最优答案，初始为 0（最差情况乘积末尾 0 个 0） void dfs(int idx, int chosen, int sum2, int sum5) // ---------- 终止条件 1：已经选满 m 个数 ---------- if (chosen == m) { // 当前组合的战斗力 = min(总因子2, 总因子5) ans = max(ans, min(sum2, sum5)); return; // 选够了，回溯 } // ---------- 终止条件 2：剪枝 ---------- // 下标从 1 开始，当前考虑 idx，剩余可选的是 idx..n，共 n - idx + 1 个 // 还需要再选 m - chosen 个 // 如果剩余数量不够，直接返回（这条路径不可能凑满 m 个，没必要继续搜） if (n - idx + 1 < m - chosen) return dfs(idx + 1, chosen, sum2, sum5) dfs(idx + 1, chosen + 1, sum2 + x[idx], sum5 + y[idx]) ​ int main() { cin >> n >> m; // 读入总个数 n 和要选的个数 m for (int i = 1; i <= n; i++) { // 下标从 1 开始，到 n 结束 long long a; cin >> a; // a_i 最大 10^18，必须用 long long int c2 = 0, c5 = 0; // 分别统计因子 2、5 的个数 // 不断除以 2，每除一次 c2 + 1 while (a % 2 == 0) { c2++; a /= 2; } // 不断除以 5，每除一次 c5 + 1 while (a % 5 == 0) { c5++; a /= 5; } x[i] = c2; // 存下第 i 个数的因子 2 个数 y[i] = c5; // 存下第 i 个数的因子 5 个数 // 从第 1 个数开始搜，目前一个都没选，sum2 = sum5 = 0 dfs(1, 0, 0, 0); cout << ans << '\n'; // 输出最终答案 return 0; }

• 另外 20% 数据（m=n）：直接模拟统计。

  直接遍历所有 $a_i$，统计所有数包含的总因子 2 数量和总因子 5 数量，最后输出它们的较小值即可。复杂度：O(n)

  #include <bits/stdc++.h> using namespace std int main() { int n, m; cin >> n >> m; int sum2 = 0, sum5 = 0; for (int i = 0; i < n; i++) { long long a; cin >> a; int c2 = 0, c5 = 0; while (a % 2 == 0) { c2++; a /= 2; } while (a % 5 == 0) { c5++; a /= 5; } sum2 += c2; sum5 += c5; } cout << min(sum2, sum5) << '\n'; return 0; }

• 另外 20% 数据（仅包含 10 的幂乘1或大于 5 的质数）：

  每个 $a_i$ 都是：$10^p$或者：$10^p$×q，其中 q>5且 q是质数。

  此时每个数提供的因子 2 和因子 5的个数相同，都为 p。

  所以选 m个数后，总因子 2 数一定等于总因子 5 数，答案就是总 p 的和。

  要最大化答案，只需要选择 p最大的 m个数。

  #include <bits/stdc++.h> using namespace std; int main() { int n, m; cin >> n >> m; vector<int> p(n); for (int i = 0; i < n; i++) { long long a; cin >> a; int cnt = 0; // a = 10^cnt * q，其中 q 为 1 或大于 5 的质数 while (a % 10 == 0) { cnt++; a /= 10; } p[i] = cnt; } sort(p.rbegin(), p.rend());//从大到小排 long long ans = 0; for (int i = 0; i < m; i++) { ans += p[i]; } cout << ans << '\n'; return 0; }

• 100% 数据：二维费用01背包

STD:

#include<bits/stdc++.h> #define ll long long using namespace std; //二维费用的01背包 有两个限制条件 const int N=2e2+10; const int M=5e3+10 ; int c2[N],c5[N]; int dp[N][M]; //dp[j][k]：恰好选了 j 个数，且这 j个数的因子 5总数为k 时，所能获得的最大因子 2 的总数。 int main() { // 优化输入输出 ios::sync_with_stdio(false); cin.tie(0); int n,m,sum5=0; cin>>n>>m; for(int i=1;i<=n;i++){ ll x; cin>>x; while(x%2==0){ c2[i]++; x=x/2; } while(x%5==0){ c5[i]++; x=x/5; } sum5+=c5[i]; } memset(dp,-0x3f,sizeof dp); dp[0][0]=0; int total=0; for(int i=1;i<=n;i++){ //01背包倒序遍历 for(int j=min(m,i);j>=0;j--){// 选出的数的个数 j，保证 0-1 背包的性质 for(int k=total+c5[i];k>=0;k--){ if(j>=1&&k>=c5[i]){//第i个数不选 第i个数选 dp[j][k]=max(dp[j][k],dp[j-1][k-c5[i]]+c2[i]); } } } total+=c5[i];// 更新当前已遍历数字的因子5总和上限 } int ans=0; // 遍历所有可能的因子5数量 k for(int k=0;k<=total;k++){ if(dp[m][k]>=0){// ans=max(ans,min(k,dp[m][k])); }// 如果选 m 个数，凑出 k 个因子5，对应的因子2数量为 dp[m][k] }// 那么这一组能产生的末尾 0 的数量就是 min(k, dp[m][k]) cout<<ans; return 0; }

T5深渊卡牌与绝对极差

题意将 n张卡牌任意划分为若干卡组，求所有卡组（基础战力 $a_k$ + 组内极差）总和的最大值。

解题思路

第一步：识别核心（贪心思想）

卡牌可以任意打乱分组，为了让所有组的“极差（最大值 - 最小值）”之和尽可能大，最优策略一定是把卡牌从小到大排序，从两端往中间取数。

• 第 1 个大小 ≥2 的组，拿走两端最大的极差：c[n] - c[1]
• 第 2 个大小 ≥2 的组，拿走第二大的极差：c[n-1] - c[2]
• ……
• 第 j个大小 ≥2 的组，拿走极差：c[n-j+1] - c[j]
• 中间剩下的数字随便塞进这些组都不会影响极差，只会把卡组大小变大，从而享受更高的a[k]。

第二步：定义状态与转移方程

1. 状态定义：dp[i][j]表示使用前i张卡牌（注意这里i是总牌数），划分为j个卡组时的最大综合战力。

2. 转移方程：枚举最后一组的大小k。前驱状态就是dp[i - k][j - 1]。

   • 如果最后一组大小k == 1，它没有极差贡献，只加a[1]。
   • 如果最后一组大小k > 1，因为它是第j组，极差贡献就是c[n - j + 1] - c[j]。

第三步：统计答案

最后，所有牌必须被用完，所以遍历所有可能的分组数 i，取dp[n][i]的最大值即为最终答案。

STD:

#include <bits/stdc++.h> using namespace std; const int N = 305; int n; int c[N], a[N]; int dp[N][N]; int main(){ cin >> n; for (int i = 1; i <= n; i++) cin >> c[i]; for (int i = 1; i <= n; i++) cin >> a[i]; sort(c + 1, c + n + 1); memset(dp,-0x3f,sizeof dp); dp[0][0]=0; // 用 0 张牌分 0 组，收益为 0 for (int i = 1; i <=n; i++)// 枚举总牌数 for (int j = 1; j <= i; j++) //枚举组数 j 的上限只能是 i（最多每张牌单独成一组） for (int k = 1; k <= i; k++){ //枚举最后一组的大小 k if (k == 1) // 大小为1的卡组，没有极差贡献 dp[i][j] = max(dp[i][j], dp[i-k][j-1] + a[1]); else// 大小>=2的卡组，极差贡献为 c[n - j + 1] - c[j] dp[i][j] = max(dp[i][j], dp[i-k][j-1] + a[k] + c[n - j + 1] - c[j]); } ​ int ans = 0; for (int i = 1; i <= n; i++) ans = max(ans, dp[n][i]); // 答案在用完 n 张牌，分成 1~n 组的所有情况中取最大值 cout << ans; return 0; }

T6 盛大的魔法仪式

题意有 n种物品，每种物品有魔力值$p_i$ 和花费$c_i$从中选择若干物品，要求总魔力值不小于 P 且总花费不超过 Q，求满足条件的最小花费。若不存在合法方案，输出-1。

解题思路

这是一道经典的0-1 背包变种题。

转化下问题：现有n个物品，第i个物品价值为$p_i$，重量为$c_i$，当重量小于等于Q，并且价值大于等于P时，输出最小的重量，如果无解，输出 −1。

这就是一个 01 背包板子题，背包容量为Q，然后求解完当背包容量为 1 到Q时的最大价值，最后从 1 遍历到Q，如果当前这个最大价值大于等于P时，输出，结束遍历。

特别的，我们还要定一个标记变量，用来标记是否有输出，如果没有，则就是无解，输出 −1。

STD:

#include<bits/stdc++.h> using namespace std; #define ll long long int dp[50005]; int main(){ int t; cin>>t; while(t--){ memset(dp,0,sizeof dp); int n,P,Q; cin>>n>>P>>Q; int p[105],c[105]; for(int i=1; i<=n; i++){ cin>>p[i]>>c[i]; } for(int i=1; i<=n; i++){ for(int j=Q; j>=c[i];j--){ dp[j]=max(dp[j],dp[j-c[i]]+p[i]); } } int flag=1; for(int i=1; i<=Q; i++){ if(dp[i]>=P){ cout<<i<<"\n"; flag=0; break; } } if(flag==1) cout<<"-1\n"; } return 0; }

六题复杂度与算法对比

下面把 T1~T6 六道题的核心算法、复杂度与易错点汇总成一张表，方便对照复习。表中 n 为各题输入规模，m 为 T2 的行数上限或 T4 的选取个数，∑c5 为 T4 中所有数的因子 5 总数。

从表中可以看出，六道题虽然背景各异，但核心都落在几类常见套路上：计数与桶（T1）、二分答案（T2）、多源 BFS（T3）、0-1 背包及其二维费用变种（T4、T6）、排序贪心加区间 DP（T5）。真正拉开差距的往往不是思路本身，而是long long溢出、二分边界、多源入队初始化、dp 倒序、极差取法和无解输出 -1 这些细节。