20260401 刷了一堆算法题

2026-04-02 2026-10-16 约 3000 字预计阅读 6 分钟

完美对计数问题

有 $n$ 个物品，每个物品有 $k$ 个属性。第 $i$ 件物品的第 $j$ 个属性用一个正整数表示，记为 $a_{i,j}$ 。

两个不同的物品 $i, j$ 被称为完美对，当且仅当满足以下条件：

a_{i,1} + a_{j,1} = a_{i,2} + a_{j,2} = \dots = a_{i,k} + a_{j,k}

问题： 求完美对的总个数。

解

a_{i,1} + a_{j,1} = a_{i,2} + a_{j,2}

则有：

a_{i,1}-a_{i,2}=a_{j,2}-a_{j,1}

因此我们定义补全序列：

T=\Sigma_{i=0}^n(a_{k,i}-a_{k,0})

差分序列：

S=\Sigma_{i=0}^n(a_{k,0}-a_{k,i})

对每个物品，我们求它的补全序列，在哈希表里找该序列出现的次数并累加，然后把它的差分序列计数+1，哈希表用map<vector<int>, int>实现

2. 选择物品

题目描述 有 $n$ 个物品可供选择，必须从中选择 $m$ 个物品。请按字典序顺序输出所有选取方案的物品编号。

注意事项

组合去重：例如 $\{1, 2, 3\}$ 、 $\{3, 1, 2\}$ 与 $\{3, 2, 1\}$ 被认为是同一种方案。
格式要求：仅输出每种方案中字典序最小的排列（如 1 2 3）。

数据范围

$1 \le m \le n \le 10$

复杂度要求

时间复杂度： $O(n!)$
空间复杂度： $O(n)$

解

简单的组合数问题，我们用递归combine(int n, int m, int start, vector<int>& a)解决问题：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
void combine(int n, int m, int start, vector<int>& a){
  if(a.size() == m){
    //我们可以输出了
    for(auto i:a){
      cout<<i<<" ";
    }
    cout<<endl;
    return;
  }
  for(int i=start; i<=m; i++){
    //保证字典序，因此我们最小只能从start开始取
    a.push_back(i);
    combine(n,m,i+1,a);
    a.pop_back();
  }
}

4. 比例问题

题目描述 小强想要从区间 $[1, A]$ 中选出一个整数 $x$ ，从区间 $[1, B]$ 中选出一个整数 $y$ 。

在满足以下比例条件的前提下，寻找使 $x$ 和 $y$ 的乘积最大的数值对：

\frac{x}{y} = \frac{a}{b}

输入要求

如果存在满足条件的 $x$ 和 $y$ ，输出使得 $x \cdot y$ 最大的那一组结果。
如果不存在这样的 $x$ 和 $y$ ，请输出 0 0。

解

我们首先通过gcd对 $\frac{a}{b}$ 进行化简：

a'=\frac{a}{g}, b'=\frac{b}{g}

接着，对x和y的等式，我们引入一个 $k$ 来表示：

\begin{align} x &= ka' \\ y &= kb' \\ \end{align}

那么， $x\cdot y$ 就变成了 $k^2\cdot a'\cdot b'$ ，由于此时 $a'$ 和 $b'$ 是常数，由此我们的问题就转变成了找最大的 $k$ 。 $k$ 的上下限我们观察x和y的区间得到：

\begin{align} k\in[\frac{1}{a'}, \frac{A}{a'}] \\ k\in[\frac{1}{b'}, \frac{B}{b'}] \end{align}

由于我们只关心上界，因此我们的问题变成了：是否能找到一个整数 $k$ ，满足 $k <= min(\frac{A}{a'}, \frac{B}{b'})$ 如果找不到，我们就说无解，如果找到了，就按照上面的公式求解x和y

5. 小强修水渠

题目描述 在一张 2D 地图上，小强拥有 $n$ 座房子。由于地理位置限制，无法直接为每座房子提供水源。因此，小强打算修建一条无限长且平行于 $y$ 轴的水渠。

这条水渠可以看作是一条直线 $x = k$ 。现在小强需要确定水渠的具体位置（即确定 $k$ 的值），使得这 $n$ 座房子到水渠的垂直距离之和最小。

输出要求 输出计算得到的最小距离总和。

由于水渠平行于y轴，因此y坐标与水渠距离无关，我们不用考虑，那么此时问题变成了：

ans=min(\sum_i^n{|x_i-x'|})

其中 $x'$ 为水渠坐标。首先一眼看出水渠如果在所有房子的左边or右边都不是最优解，那么在中间应该如何取舍呢？我们找几个简单的例子看看：

房子总共有偶数个（例如，就是2 or 4个，没关系）此时水渠如果在正中间，无论怎么移动，都不影响最终结果（你可以将上面的式子按左侧右侧展开绝对值看看，最终 $x'$ 会被抵消）
房子总共有奇数个（例如，3个）此时水渠必须在中位数的位置上，因为假设我们把这个中位数去掉，就变成偶数个的情况，此时水渠在中间怎么移动都行，但是加入中位数以后为了将这个距离对答案的贡献降到最小（也就是0），我们把水渠建在这个位置最合适。

在C++中，有一个很好的函数可以解决这件事： nth_element(a.begin(), a.begin() +mid, a.end()) 可以将整个数组的中位数放在mid的位置上。

6. 国际交流会

题目描述 小强主办了一场国际交流会，所有参会人员围坐在一张圆桌旁。为了让不同国家的人充分感受异域气息，小强希望最大化邻座两人之间的差异程度之和。

已知每两人之间都存在一个衡量“差异程度”的数值，请你为他安排座位次序，使得圆桌上相邻两人差异程度的总和达到最大。

注意事项

这是一个环形排列问题，首尾两人也属于相邻关系。
目标是求得一个排列，使得 $\sum \text{diff}(\text{person}_i, \text{person}_{i+1})$ 最大。

解

没什么好说的，本来以为需要 $O(n^2)$ 建图然后跑最大生成树，但是最大生成树也可能是个星形结构无法成环，或者最大权哈密顿回路问题？它和旅行商问题正好相反，但是它们是NP-Hard问题，无法求解。其实是想复杂了，这道题由于它只是数值大小的关系，没那么复杂。我们可以想象每个数字在数轴上是一个点，我们希望走过的步长最长，那么就每次从最右边走到最左边就可以了。写成算法就是：

先排序
维护两个指针从两头双向往中间走（保证 $i<j$ ），然后把值交替写到新数组里
如果n为奇数，把中位数写到新数组的最后
计算新数组的前缀差和

7. 小强的神奇矩阵

题目描述 小强有一个大小为 $3 \times n$ 的矩阵 $a$ 。他计划从矩阵的每一列中各取出一个数字，按照原始列的顺序组成一个长度为 $n$ 的新数组 $b$ 。

即对于数组中的第 $i$ 个元素 $b_i$ ，它可以是 $a_{1,i}, a_{2,i}, a_{3,i}$ 中的任意一个。

问题请问如何选择每列的数字，才能使得相邻元素之差的绝对值之和最小？即求以下表达式的最小值：

\sum_{i=1}^{n-1} |b_i - b_{i+1}|

解

一个dp,只不过分了三个维度

dp[i,j]=\min_{k=0}^3{dp[i-1,k]}

每一列的三个数字都尝试和前一列的三个数字进行计算，然后维护 $dp[i,x]$ 的最小值，最后从 $dp[n,x]$ 里找最小值就行了。