目录
- C. Factorials and Powers of Two / 阶乘数与二的幂
- D. Weight the Tree / 树上赋权
- E. Power Board / 乘方表
- F. Playing Around the Table / 圆桌打牌
C. Factorials and Powers of Two / 阶乘数与二的幂
题意简述
给出一个 \(n\)，定义“好数集合 \(\mathbb{X}\)”为某个数的阶乘或 \(2\) 的次幂，求最小的数 \(k\) 使得 \(\sum\limits_{S\subseteq \mathbb{X}}S_i=n\) 且 \(|S|=k\)。
\(n\le 10^{12}\)。
解题思路
注意到，\(\le 10^{12}\) 的阶乘数只有不到 \(20\) 个，所以可以直接枚举构成 \(n\) 的阶乘数。设构成 \(n\) 的阶乘数部分和为 \(m\)，则剩下的次幂数部分个数最小值显然为 \(\operatorname{popcount}(n-m)\)。
代码
#define int long long
int n, cnt, fac[21] = {1, 0}, ans;
void dfs(int x, int y, int z) {ans = min(ans, y + __builtin_popcountll(n - z));for (int i = x; i >= 1; i--) {if (z + fac[i] > n) continue;dfs(i - 1, y + 1, z + fac[i]);}
}
D. Weight the Tree / 树上赋权
题意简述
给定有 \(n\) 个顶点的树。如果某个顶点的权值等于其所有相邻顶点权值之和，则称该顶点为“好顶点”。为每个顶点分配正整数权值，使得“好顶点”数量最大，再使得权值和最小。
\(n\le 2\times 10^5\)。
解题思路
注意到，当 \(n\ge2\) 时，相邻点不能同时是“好顶点”，于是最大数量的做法参考 P1352 没有上司的舞会。输出方案的话，把树形 DP 稍微改一下就行。
代码
void dp(int u, int fa) {f[u][0] = 0; g[u][0] = 1;f[u][1] = 1; g[u][1] = z[u].size();for (int i = 0; i < z[u].size(); i++) {int v = z[u][i];if (v == fa) continue;dp(v, u);f[u][1] += f[v][0]; g[u][1] += g[v][0];if (f[v][0] > f[v][1] || f[v][0] == f[v][1] && g[v][0] < g[v][1]) {f[u][0] += f[v][0]; g[u][0] += g[v][0];} else {f[u][0] += f[v][1]; g[u][0] += g[v][1];}}
}
E. Power Board / 乘方表
题意简述
有 \(n\times m\) 的表格，第 \(i\) 行 \(j\) 列的数是 \(i^j\)。问表格中数字有多少种。
\(n,m\le 10^6\)。
解题思路
这道题有多种解法。这里介绍一种比较好理解的。
约定：第 \(i\) 行有冲突当且仅当存在 \(j\le i\) 且第 \(j\) 行和第 \(i\) 行有相同的元素。
注意到，对于没有冲突的两行 \(a,b\)，如果 \(\log_an=\log_bn\)，那么表格中形如 \(a^k\) 的数种类数与形如 \(b^k\) 的数种类数一致。于是暴力求出每种 \(\log\) 值的答案就做完了。
代码
for (int i = 1; i <= 20; i++) {a[i] = a[i - 1];for (int j = 1; j <= m; j++) {if (!p[i * j]) {a[i]++;p[i * j] = 1;}}
}
long long ans = 1;
for (int i = 2; i <= n; i++) {if (!vis[i]) {long long j = i, cnt = 0;while (j <= n) {cnt++;vis[j] = 1;j *= i;}ans += a[cnt];}
}
F. Playing Around the Table / 圆桌打牌
题意简述
有 \(n\) 个玩家，从 \(1\) 到 \(n\) 编号，\(i\) 的右边是 \(i + 1\)，特别地，\(n\) 的右边是 \(1\)。现在有 \(n^2\) 张牌，每张 \(i\) 号牌有 \(n\) 张。每次操作每个玩家选择一张牌给右边的人。想让玩家 \(i\) 得到 \(n\) 张 \(i\) 号牌。要构造方案，不超过 \((n ^ 2 - n)\) 次操作。
\(2 \leq n \leq 100\)。
解题思路
直接转化不好做，考虑先把每个人手里的牌变成 \([1,2,3,\cdots,n]\)，再经过转化变成 \([i,i,i,\cdots,i]\)。
对于第一种操作，考虑每个人把自己手里多的牌传出去。