跳转至

算法周赛round29

T1

问题拆解

本题分为两轮比赛，需要按顺序处理：

  1. 团体赛： 比较每一列同学的知识水平总和，选出总和最大的那一列

  2. 若有多列总和相同，选择最右边的一列

  3. 个人赛： 在第一轮胜出的那一列中：

  4. 找出最大的知识水平

  5. 统计该最大值出现的次数

最终输出这两个结果。

第一轮：确定胜出列

设第 $j$ 列同学的知识水平总和为：

\[ S_j = \sum_{i=1}^{n} a_{i,j} \]

遍历所有列，维护：

  • 当前最大总和 $maxSum$
  • 对应的列编号 $col$

更新规则为：

  • 若 $S_j > maxSum$，更新
  • 若 $S_j = maxSum$，选择编号更大的列，即更靠右的一列

这样即可满足题目中的判定规则。

第二轮：确定最终赢家

在第一轮胜出的列 $col$ 中，考虑该列的所有元素：

\[ a_{1,col},a_{2,col},\ldots,a_{n,col} \]

需要做两件事：

  1. 求出这一列中的最大值：

$$ maxVal = \max_{1 \le i \le n} a_{i,col} $$

  1. 统计该最大值出现的次数，记为 $cnt$

算法步骤

  1. 读入 $n,m$ 和矩阵 $a$
  2. 初始化 $maxSum=-1$，$col=0$
  3. 对每一列 $j=1$ 到 $m$：
    • 计算该列的总和 $S_j$
    • 按规则更新 $maxSum$ 和 $col$
  4. 在第 $col$ 列中遍历所有行：
    • 计算最大值 $maxVal$
    • 统计其出现次数 $cnt$
  5. 输出 $maxVal$ 和 $cnt$

T2

一个完全平方数中所有质因子的次幂均为偶数。

因此若一个完全平方数是 $3$ 的倍数，则其算术平方根也是 $3$ 的倍数。

因此答案是 $1\sim \sqrt{n}$ 中有多少个 $3$ 的倍数。

答案为：$\left\lfloor \dfrac{\lfloor\sqrt{n} \rfloor}{3} \right\rfloor$

特别地：由于 $n\leq 10^{18}$，为避免精度误差，建议用 sqrtl 或使用二分法计算 $\lfloor\sqrt{n} \rfloor$。

T3

根据异或的计算规则：相同为 $0$ 不同为 $1$。

因此若 $a,b$ 在二进制下第 $i$ 位不同（$i\in [0,30]$），则说明要么 $a$ 的第 $i$ 位为 $1$，$b$ 的第 $i$ 位为 $0$，要么 $a$ 的第 $i$ 位为 $0$，$b$ 的第 $i$ 位为 $1$。

若第 $i$ 位相同，则说明要么 $a,b$ 的第 $i$ 位都为 $1$，要么 $a,b$ 的第 $i$ 位都为 $0$。

由于题目要求最大化 $a+b$ 的值，因此若第 $i$ 位相同时，显然 $a,b$ 的第 $i$ 位尽量取 $1$ 是更优的。

但题目要求 $a,b\leq n$，因此可能无法无限制的让 $a,b$ 的第 $i$ 位都为 $1$。

因此需要一些贪心的处理，显然高位优先处理，低位滞后处理。

具体实现步骤如下：

  • 首先构造 $a,b$ 的二进制表示，以满足 $a\oplus b=n$。

具体来说记 $i$ 为满足最大的 $i$ 使得 $n$ 的第 $i$ 位为 $1$。

则更新 $a=2^i$，$b=n\oplus a$。

此时满足 $a\oplus b=n$，且 $a,b\leq n$。

  • 紧接着从高位枚举 $i$，当满足 $n$ 的二进制第 $i$ 位为 $0$ 时，且 $a+2^i\leq n$，则更新：$a\gets a+2^i,b\gets b+2^i$。

以此构造出来的 $a,b$ 满足 $a\oplus b=n$，且 $a,b\leq n$ 且 $a+b$ 最大。

时间复杂度：$O(30T)$。

T4

首先不难想到当 $p$ 取 $\max{a_i}+1$ 时，答案为 $\max{a_i}-\min{a_i}$。

但不一定是最优的（从第四组测试数据可以看出）

实际上另一个更优的 $p$ 是令 $p=\max{a_i}$，此时序列中所有的 $\max{a_i}\bmod p$ 都会变成 $0$，因此答案为序列中的严格次大值。

可以证明不存在其余更优的答案。

因此答案就是 最大值减去最小值或者严格次大值这二者中的较大值。

时间复杂度：$O(Tn)$，使用排序求最大值最小值和严格次大值可以做到 $O(Tn\log{n})$ 也可以通过。

T5

考虑 DP。

显然 $f_1=a$。对于 $f_i$ 有两种转移：

  • 加法：$f_i=f_{j}+f_{i-j}+b$，其中 $j\in [1,i-1]$。
  • 乘法：$f_{i}=f_{j}+f_{\frac{i}{j}}+c$，其中 $j\in[2,\sqrt{i}]$，且 $j\mid i$。

时间复杂度：$O(n^2)$。