B
题目大意
你要传话给 \(n\) 个人，每传一下话需要花费 \(p\) ，当一个人被传话后，他可以最多传给 \(a_i\) 个人，每次花费 \(b_i\) 。问把话传给 \(n\) 个人的最小花费。
分析
首先传给第一个人只少要 \(p\)
下来贪心，每次让花费最小、且能够传话的人去传话。
考虑建一个堆，堆内的信息是花费 \(x\) 和能传的次数 \(y\) ，堆顶是最小的花费 \(x\) ，然后进行如下的 \(n\) 次操作：
- 取出堆顶，进行一次传话，其 \(y\) 减一
- 若 \(y\) 变为 \(0\) ，则将其从堆中弹出
一共会进行 \(n\) 次操作，复杂度 \(O(n~log~n)\)
Code (注意开 C++ 20)
#include<bits/stdc++.h>
#define IO ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
using ll = long long;
int n, p;
void solve() {
map<ll, ll> cnt;
cin >> n >> p;
vector<ll> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
cin >> b[i];
cnt[b[i]] += a[i];
}
cnt[p] += n;
ll ans = p;
for (int i = 1; i < n; i++) {
auto [x, y] = *cnt.begin();
ans += x;
if (y == 1)
cnt.erase(cnt.begin());
else
cnt[x]--;
}
cout << ans << endl;
}
int main() {
IO;
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
C
题目大意
要求你构造一个长度为 \(n+1\) 的数组，你可以给 \(a_{n+1}\) 赋一个 \([0,m]\) 之间的值，随后 \(\forall i \in [1,n],~a_i=a_{i+1} ~mod ~i\)
问最后数组中有 \(k\) 个不同数的方案数
分析
注意到无论赋的这个值 \(a_{n+1}\) 有多大，下一个数 \(a_n\) 一定满足 \(a_n<n\) ，且 \(a_1=0\)
假设 \(a_{n+1}=x+tn\) ，那么数组的情况如下：
| \(i\) | \(1\) | \(2\) | \(\cdots\) | \(x\) | \(\cdots\) | \(n\) | \(n+1\) |
|---|---|---|---|---|---|---|---|
| \(a_i\) | \(0\) | \(0\) | \(0\) | \(0\) | \(x\) | \(x\) | \(x+tn\) |
所以数组最多存在 \(3\) 种不同的数字 ，当 \(k>3\) ，\(ans=0\)
下面分情况讨论：
-
\(k=1\) ，那么 \(a_{n+1}=x+tn\) ，\(ans=1\)
-
\(k=2\) ，有两种情况：
- \(a_{n+1} \equiv a_n~mod~n\) ，即 \(a_{n+1}<n\) ，总共有 \(min(n-1,m)\) 种
- \(a_{n+1} \equiv 0~mod~n\) ，那么构造出来的数组是 \(\forall i\in[1,n],~a_i=0,~a_{n+1}=x\) ，总共有 \(\lfloor \frac{n}{m}\rfloor\) 种
-
\(k=3\) ，答案是 \(m-上面的答案之和\) 种
Code
#include<bits/stdc++.h>
#define IO ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
void solve() {
int n, m, k;
cin >> n >> m >> k;
if (k >= 4) {
cout << 0 << endl;
} else if (k == 3) {
if (m < n) cout << 0 << endl;
else cout << m - n - m / n + 1 << endl;
} else if (k == 2) {
if (m <= n) cout << m << endl;
else cout << n + m / n - 1 << endl;
} else {
cout << 1 << endl;
}
}
int main() {
IO;
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
D
题目大意
给出 \(n\) 个点的值，选择将一些点染成黑色，只少染一个。如果染黑了点 \(i\) ，那么 \(i\) 的所有倍数的点会被染成绿色。
每次染色后，答案是被染色的点的最大值
一共有 \(2^n-1\) 种染色方式，问所有染色方式的答案之和。
分析
考虑每一个点对整个答案的贡献：
首先这个点需要是所有选中点里最大的，才会产生贡献。
换句话说，只有比这个点大的点都都已经被计算完毕，排除掉后，它才会产生贡献。
那么考虑将点的值排序，从大往小考虑：
如果当前点 \(i\) 是最大的点，比 \(i\) 大的点已经被排除在外了，还剩下 \(k\) 个点，也就是点集 \(\{i_1,i_2,\cdots,i_k\}\)
-
假设这剩下的 \(k\) 个点中，是 \(a_i\) 的因数的点有 \(l\) 个，点集为 \(\{j_1,j_2,\cdots,j_l\}\) ，其中 \(i \in \{j_1,j_2,\cdots,j_l\}\)
那么 \(i\) 这个点产生的贡献值为 \(a_i \times (2^{k-1}+2^{k-2}+\cdots + 2^{k-l})\)
-
随后我们将属于 \(a_i\) 因数的点集 \(\{j_1,j_2,\cdots,j_l\}\) 从 \(\{i_1,i_2,\cdots,i_k\}\) 中删掉，继续考虑剩下的点中最大的那个数
下来考虑如何知道属于点 \(i\) 的因数有哪些？以及这些点有没有在考虑 \(i\) 之前被考虑到：
我的方法是建立一张图，如果点 \(u\) 是点 \(v\) 的倍数，那么建立一条 \(u\rightarrow v\) 边，建图的复杂度是 \(O(n\sqrt{n})\)
每次考虑点 \(i\) 就在这张图上从 \(i\) 顺着往下找。
Code
#include<bits/stdc++.h>
#define IO ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll mod = 998244353;
const int N = 1e5 + 5;
int n, cnt;
pll a[N];
ll ans;
vector<int> G[N];
ll qpow(ll x, ll y) {
ll res = 1;
while (y) {
if (y & 1) res = res * x % mod;
y >>= 1;
x = x * x % mod;
}
return res;
}
bool vis[N];
void init() {
for (int i = 1; i * i <= n; i++) {
for (int j = i * i; j <= n; j++) {
if (j % i == 0) {
G[j].push_back(i);
if (j != i * i && i != 1)
G[j].push_back(j / i);
}
}
}
}
void dfs(int now, ll val) {
cnt--;
ans += qpow(2, cnt) * val;
ans %= mod;
for (int son : G[now]) {
if (vis[son]) continue;
vis[son] = true;
dfs(son, val);
}
}
int main() {
IO;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].first;
a[i].second = i;
}
sort(a + 1, a + n + 1);
cnt = n;
init();
for (int i = n; i >= 1 && cnt > 0; i--) {
if (vis[a[i].second]) continue;
vis[a[i].second] = true;
dfs(a[i].second, a[i].first);
}
cout << ans;
return 0;
}