邢台网站优化建设_企业信息查询公示系统_电脑培训中心_会计培训班要多少钱一般要学多久

比赛链接

A. 智乃的天平

Solution

直接判断是否有 w ∈ { a , b , a + b , ∣ a − b ∣ } . w \in \lbrace a, b, a + b, |a - b| \rbrace. w∈{a,b,a+b,∣a−b∣}.

C++ Code

#include <bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using i80 = __int128_t;
using u80 = unsigned __int128_t;
using f64 = double;
using f80 = long double;
using i16 = short;
using u16 = unsigned short;constexpr f64 pi = std::numbers::pi;int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int a, b, w;std::cin >> a >> b >> w;std::array<int, 4> v{a, b, a + b, std::abs(a - b)};std::cout << (std::ranges::count(v, w) ? "Yes\n": "No\n");return 0;
}

B. 智乃爬山

Solution

直接按照题意模拟求最大值即可。

C++ Code

#include <bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using i80 = __int128_t;
using u80 = unsigned __int128_t;
using f64 = double;
using f80 = long double;
using i16 = short;
using u16 = unsigned short;constexpr f64 pi = std::numbers::pi;template<class T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {for (auto &x: v) {is >> x;}return is;
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n;std::cin >> n;std::vector<int> a(n);std::cin >> a;int ans = -1;for (int i = 1; i + 1 < n; i++) {if (a[i - 1] < a[i] and a[i] > a[i + 1]) {ans = std::max(ans, a[i] - (a[i - 1] + a[i + 1]) / 2);}}std::cout << ans << "\n";return 0;
}

C. 智乃放球

题目大意

给定 $m$ 个容量无限大的空桶（$\forall c_i=0$）以及一个正整数 $k$。现在做 $n$ 轮操作，每轮操作如下：

• 选定桶 $i$，它有 $c_i$ 个小球，现在放入一个小球，令 $c_i:=(c_i+1)(\mathrm{mod}k)$；

问是否存在一种方案，使得 $n$ 次操作结束后有 $$\sum _{i=1}^m{c}_i=q$$

数据范围

• $1\le T\le 10^5,$
• $1\le n,m,k\le 10^9,$
• $1\le q\le n.$

Solution

首先，$(n-q)$ 一定要是 $k$ 的倍数，因为我们最多只能 $k$ 个 $k$ 个干掉小球。

其次，$q\le m\cdot (k-1)$，因为一旦数量达到 $k$ 就会变为 $0$。

时间复杂度 $O(T)$

C++ Code

#include <bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using i80 = __int128_t;
using u80 = unsigned __int128_t;
using f64 = double;
using f80 = long double;
using i16 = short;
using u16 = unsigned short;constexpr f64 pi = std::numbers::pi;std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());void solve() {int n, m, k, q;std::cin >> n >> m >> k >> q;if ((n - q) % k == 0 and q <= static_cast<i64>(k - 1) * m) {std::cout << "Yes\n";} else {std::cout << "No\n";}
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout << std::fixed << std::setprecision(12);int T = 1;std::cin >> T;while (T--) {solve();}return 0;
}

D. 智乃的“K”叉树

题目大意

给定一棵 $n$ 个结点的树，设以第 $i\in [1,n]$ 个结点为根的树是 $k_i$ 叉树，求 $\underset{i=1}{\overset{n}{\min }}{k}_i$ 以及对应的 $i$。

• 一棵树为 $k$ 叉树，当且仅当存在一个结点 $u$ 有 $k$ 个儿子；
• 如果有多个结点满足要求，输出任意一个 $i$。

数据范围

• $2\le n\le 10^5.$

Solution

首先，如果这棵树只有两个结点，那么 $k=1$，根随便找 $1$ 或者 $2$ 都行。

对于 $n>2$ 的情况，记录每个结点的度，第 $i$ 个结点的度位为 $\mathrm{deg}[\mathrm{i}]$。

设 $\mathrm{m}=\underset{\mathrm{i}=1}{\overset{\mathrm{n}}{\max }}(\mathrm{deg}[\mathrm{i}])>1$，我们先把这个最大度对应的 $i$ 提到根节点，此时 $i$ 有 $m$ 个儿子，而剩下的结点最多只有 $m-1$ 个儿子，这是一棵 $m$ 叉树。

• 如果存在一个非根节点 $j$ 有 $m$ 个儿子，那么加上 $j$ 到 $j$ 父亲的那条边，$j$ 的度就是 $m+1$ 了，矛盾。

现在找一个结点 $j$ 提上来作为新的根结点，要求 $\mathrm{deg}[\mathrm{j}]<\mathrm{m}$， 那么这棵新树的度就是 $m-1$，答案就是 $m-1$ 和 $j$。

• 首先，这样的结点一定可以找到，比如叶节点；
• 其次，现在我把 $j$ 提上来作为新的根结点，会变化的只有原来的根结点 $i$ 到 $j$ 这条简单路径上的结点，我们把这个点集记为 $S$。
  • 对 $j$ 来说，所有与其相连的都成为了它的儿子，因为 $j$ 是新的根，这样儿子数量就是 $\mathrm{deg}[\mathrm{j}]<\mathrm{m}$；
  • 对于 $i$ 来说，它在简单路径上的儿子变成了 $i$ 的父亲，损失一个儿子，儿子数量变为 $m-1$；
  • 对于 ∀ u ∈ ( S ∖ { j , i } ) \forall u \in (S \setminus \{ j, i \}) ∀u∈(S∖{j,i})，都是 $u$ 在简单路径上的儿子变成 $u$ 的父亲，损失一条儿子边，其他儿子仍然是 $u$ 的儿子，而 $u$ 在简单路径上的父亲成为 $u$ 的儿子，加了一条儿子边，这样总的儿子数保持不变，且由之前的条件可知，$u$ 的儿子数均 $<m$。

时间复杂度 $O(n)$

C++ Code

#include <bits/stdc++.h>int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n;std::cin >> n;std::vector<int> deg(n);for (int i = 1; i < n; i++) {int u, v;std::cin >> u >> v;u--, v--;deg[u]++;deg[v]++;}int m = std::ranges::max(deg);if (m == 1) {std::cout << 1 << " " << 1 << "\n";return 0;}int p = std::ranges::find_if(deg, [&](int d) {return d < m;}) - deg.begin();std::cout << m - 1 << " " << p + 1 << "\n";return 0;
}

E/F. 智乃的“凑数”题

题目大意

给定长度为 $n$ 的正整数数组 $k$ 、正整数 $x$ 以及询问次数 $m$，每个询问给出一个 $x$，要求将 $k$ 分成两个非空数组 $a,b$，设长度分别是 $n_a,n_b$，使得 $$\sum _{i=1}^{n_a}\sum _{j=1}^{n_b}(a_i\cdot b_j)=x,$$ 问能否实现，如果可以，输出其中一种方案。

数据范围

• 这里直接上 $\mathrm{hard}$ 版本的数据范围；
• $1\le n\le 500,$
• $1\le m\le 1000,$
• $1\le k_i\le 10^4,$
• $1\le x\le 10^4.$

Solution

首先题目要求的双层求和其实可以化简。

$$\sum _{i=1}^{n_a}\sum _{j=1}^{n_b}{a}_i\cdot b_j=\left(\sum _{i=1}^{n_a}{a}_i\right)\left(\sum _{j=1}^{n_b}{b}_j\right)={\mathrm{s}}_{\mathrm{a}}\cdot {\mathrm{s}}_{\mathrm{b}}=x.$$

其中 $s_a,s_b$ 分别表示 $a$ 数组的和以及 $b$ 数组的和。

$s_a\cdot s_b=x$，意味着 $s_a$ 是 $x$ 的因数，所以我们只要考虑枚举 $x$ 的因数作为 $a$ 数组的和。

设 $\mathrm{dp}[{\mathrm{s}}_{\mathrm{a}}][{\mathrm{s}}_{\mathrm{b}}]$ 表示能否给 $a$ 数组和为 $s_a$ 的若干个整数，给 $b$ 数组和为 $s_b$ 的若干个整数。

对于当前遍历到的 $k_i$ 进行状态转移：

• 若 $s_a\ge k_i$，则 $\mathrm{dp}[{\mathrm{s}}_{\mathrm{a}}][{\mathrm{s}}_{\mathrm{b}}]=\mathrm{dp}[{\mathrm{s}}_{\mathrm{a}}][{\mathrm{s}}_{\mathrm{b}}]\mid \mid \mathrm{dp}[{\mathrm{s}}_{\mathrm{a}}-{\mathrm{k}}_{\mathrm{i}}][{\mathrm{s}}_{\mathrm{b}}]$；
• 若 $s_b\ge k_i$，则 $\mathrm{dp}[{\mathrm{s}}_{\mathrm{a}}][{\mathrm{s}}_{\mathrm{b}}]=\mathrm{dp}[{\mathrm{s}}_{\mathrm{a}}][{\mathrm{s}}_{\mathrm{b}}]\mid \mid \mathrm{dp}[{\mathrm{s}}_{\mathrm{a}}][{\mathrm{s}}_{\mathrm{b}}-{\mathrm{k}}_{\mathrm{i}}]$。

为了最终输出具体的 $a,b$数组，我们还需要开一个 $\mathrm{pre}[{\mathrm{s}}_{\mathrm{a}}][{\mathrm{s}}_{\mathrm{b}}]$ 数组记录当前状态是由哪个状态 $(s_a^{\prime },s_b^{\prime })$ 转移而来的。

初值条件：$\mathrm{dp}[0][0]=\mathrm{true}$。

当然，如果直接这样 $\mathrm{dp}$ 只能通过 $E$，但在 $F$ 题里，$x$ 的范围直达 $10^4$，如果开一个 $10^4\cdot 10^4$ 的数组肯定爆空间了，而且大概率超时，因此要考虑优化。

经过观察，我们发现 $s_a\cdot s_b=x$ 是在提示我们可以将第二维空间开小一点，例如：

• $s_a=1$ 时，$s_b=x$；
• $s_a=2$ 时，$s_b=\frac{x}{2}$；
• $s_a=3$ 时，$s_b=\frac{x}{3}$；
• $\cdots$；

根据级数的知识，当 $n$ 较大时，$\sum _{i=1}^{n}i\approx \mathrm{lnn}$，于是我们可以让第二维 $s_b$ 动态开，最终的所占总空间的大小大约是 $O(10^4\log 10^4)$，时间上也够用。

时间复杂度 $O(nV\log V+m\sqrt{x}+mn)=O(nV\log V)$

• $V=10^4$；
• $nV\log V$ 表示对每个数都要做一次上述状态转移；
• $m\sqrt{x}$ 表示每次询问都要求 $x$ 的因数；
• $mn$ 表示如果找到了满足条件的 $s_a,s_b$，需要根据 $\mathrm{pre}$ 看选了哪些数给 $a$，哪些给 $b$，花费 $O(n)$。

C++ Code

#include <bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using i80 = __int128_t;
using u80 = unsigned __int128_t;
using f64 = double;
using f80 = long double;
using i16 = short;
using u16 = unsigned short;constexpr f64 pi = std::numbers::pi;template<class T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {for (auto &x: v) {is >> x;}return is;
}
template<class T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {os << v[0];for (size_t i = 1; i < v.size(); i++) {os << " " << v[i];}return os;
}constexpr int U = 10000;int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n, m;std::cin >> n >> m;std::vector<int> k(n);std::cin >> k;std::array<std::vector<std::pair<int, int>>, U + 1> pre{};std::array<std::vector<bool>, U + 1> dp{};for (int r = 0; r <= U; r++) {dp[r].assign(U / std::max(r, 1) + 1, false);pre[r].assign(U / std::max(r, 1) + 1, {});}dp[0][0] = true;for (int v: k) {for (int r = U; r >= 0; r--) {for (int c = U / std::max(r, 1); c >= 0; c--) {if (not dp[r][c]) {continue;}for (auto [dr, dc]: {std::pair {v, 0}, {0, v}}) {if (r + dr <= U and c + dc <= U / std::max(r + dr, 1) and not dp[r + dr][c + dc]) {dp[r + dr][c + dc] = true;pre[r + dr][c + dc] = {r, c};}}}}}while (m--) {int x;std::cin >> x;auto work = [&](int x) {for (int c = 1; c * c <= x; c++) {if (x % c) {continue;}int r = x / c;if (not dp[r][c]) {continue;}std::cout << "Yes\n";std::vector<int> row;std::vector<int> col;for (int x = r, y = c; x > 0 or y > 0; ) {auto [nx, ny] = pre[x][y];if (x != nx) {row.push_back(x - nx);} else {col.push_back(y - ny);}x = nx;y = ny;}std::cout << row.size() << " " << col.size() << "\n";std::cout << row << "\n";std::cout << col << "\n";return true;}return false;};if (not work(x)) {std::cout << "No\n";}}return 0;
}