初二新初三集训 Week 3

8月27日模拟赛

T1 友谊赛

Link

思路

考虑贪心。找到整棵树的最长链，分配给 \(m\) ，然后删掉这条链，再找最长链，分配给 \(m - 1\) ，以此类推，就是一个长链剖分。

代码

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 5e5 + 5;
vector<int> g[N];
vector<int> tmp;
int n, dep[N], son[N], m, mx[N];
void dfs1(int u, int ff) {int cnt = 0;dep[u] = dep[ff] + 1;mx[u] = dep[u]; for (auto v : g[u]) {if (v == ff) continue;cnt ++;dfs1(v, u);if (mx[u] < mx[v]) {mx[u] = mx[v];son[u] = v;}}if (!cnt) ++m;
}
void dfs2(int u, int ff, int tp) {if (son[u]) dfs2(son[u], u, tp);else tmp.push_back(dep[u] - dep[tp] + 1);for (auto v : g[u]) {if (v == ff || v == son[u]) continue;dfs2(v, u, v);}
}
int main() {FASTIO;freopen("race.in", "r", stdin);freopen("race.out", "w", stdout);cin >> n;for (int i = 1; i < n; ++i) {int u, v; cin >> u >> v;g[u].push_back(v), g[v].push_back(u); }dfs1(1, 0);dfs2(1, 0, 1);sort(tmp.begin(), tmp.end(), greater<int>());ll ans = 0;for (int i = 0; i < tmp.size(); ++i) {ans += 1ll * tmp[i] * (m - i);}cout << ans << '\n';return 0;
}

T2 数数

Link

题意

给你 \(a\) 个 \(-2\)，\(b\) 个 \(-1\)，\(c\) 个 \(1\)，\(d\) 个 \(2\)，求有多少种不同的排列数，使得不存在任何一个子数组，它的和是 \(0\)。

思路

首先我们考虑 \(Sub4\) 没有 \(-2\) 的情况。
可以将整个过程具象成在数轴上跳，最开始在 \(0\)，要向左跳 \(b\) 次 \(1\) 格，向右跳 \(c\) 次 \(1\) 格，向右跳 \(d\) 次 \(2\) 格，且不能经过之前经过的点。
发现性质：中间跳的过程只有 \(3\) 种，\(+1,+2,(+2-1+2)\)。
然后再考虑开始和结束，开始有两种：不动和 \(-1+2\)。
结束也有两种：不动和 \(+2-1\)。
考虑枚举开始和结尾的情况，然后直接组合数学计算中间的方案数。

考虑有 \(-2\)的情况。
发现 \(-2\) 不能放在中间的位置上，那么考虑它对开头、结尾的影响。
开头和结尾就多了两种情况。

代码

#include <bits/stdc++.h>
#define FASTIO                   \ios::sync_with_stdio(false); \cin.tie(0);                  \cout.tie(0);
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 4e6 + 5;
const int Md = 998244353;
ll fac[N], rev[N];
ll qpow(ll a, ll b) {ll ret = 1;while (b) {if (b & 1)ret = (ret * a) % Md;a = (a * a) % Md;b >>= 1;}return ret;
}
void init(void) {fac[0] = rev[0] = 1;for (int i = 1; i < N; ++i) {fac[i] = (fac[i - 1] * i) % Md;rev[i] = (rev[i - 1] * qpow(i, Md - 2)) % Md;}
}
// start 0：do nothing
// start 1：-1 * 1 + 2 * 1
// start 2：-2 * k + -1 * 1 + 2 * (k + 1)
// start 3：-2 * k + 1 * 1 + 2 * k// end 0：do nothing
// end 1：2 * 1 + -1 * 1
// end 2：2 * k + 1 * 1 + -2 * k
// end 3：2 * (k + 1) + -1 * 1 + -2 * k
int A, B, C, D, S, a, b, c, d
void solve(void) {cin >> a >> b >> c >> d;S = -2 * a - b + c + d * 2;if (S < 0) {swap(a, d);swap(b, c);}if (S == 0) {cout << 0 << '\n';return;}ll ret = 0;for (int i = 0; i < 4; ++i) {A = a, B = b, C = c, D = d;//		cout << A << ' ' << B << ' ' << C << ' ' << D << '\n';if (!A && i >= 2)continue;for (int j = 0; j < 4; ++j) {A = a, B = b, C = c, D = d;if (!A && j >= 2)continue;if (A && i < 2 && j < 2)continue;if ((i == 1 || i == 2) && !B)continue;int need = A + (j == 3) + (i == 2) + (i == 1) + (j == 1);if (D < need)continue;D -= need;if (i == 1)B--;if (i == 2)B--;if (j == 1)B--;if (j == 3)B--;//			if (i == 2 && j == 2) {//				cerr << "Error : " << B << '\n';//			}if (B < 0)continue;if (i == 3)C--;if (j == 2)C--;if (C < 0)continue;if (B * 2 > D)continue;D -= B * 2;ll add = fac[C + D + B] * rev[C] % Md * rev[D] % Md * rev[B] % Md * ((i >= 2 && j >= 2) ? A - 1 : 1) % Md;ret = (ret + add) % Md;}}cout << ret << '\n';
}
int main() {FASTIO;freopen("count.in", "r", stdin);freopen("count.out", "w", stdout);init();int t;cin >> t;while (t--) solve();return 0;
}