2020 Multi-University Training Contest 5
施工中。。。
1001 Tetrahedron
已知 (a imes b imes c) 的四面体，以 (a) 为 (x) 轴，(b) 为 (y) 轴， (c) 为 (z) 轴
以 (z) 为轴做切面，为 (c imes frac{a imes b}{sqrt{a^2+b^2}}) 的三角形
则易知 (h= frac{abc}{sqrt{a^2b^2+a^2c^c+b^2c^2}})
(frac{1}{h^2}=frac{1}{a^2}+frac{1}{b^2}+frac{1}{c^2})，(O(nlog n)) 求 (frac{3}{n^2}) 的期望即可
比赛时一发过。
#include<bits/stdc++.h>
#define ll long long
#define maxn 6000010
#define mod 998244353
using namespace std;
ll pe[maxn], sum[maxn];
ll po(ll x) {
ll bas = 1, y = mod - 2;
while (y) {
if (y % 2) bas = bas * x % mod;
x = x * x % mod;
y /= 2;
}
return bas;
}
int main() {
for (int i = 1; i < maxn; i++) {
pe[i] = po(i);
sum[i] = (sum[i - 1] + pe[i] * pe[i] % mod) % mod;
}
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
printf("%lld
", 3 * sum[n] * pe[n] % mod);
}
return 0;
}
1003 Boring Game
手模一下一张纸的情况，多折几次就基本明白了。
每一次折纸实际上就是将当前的状态复制一份，然后翻转。
比赛时一发过。
#include <bits/stdc++.h>
using namespace std;
vector<int> p[12];
void init() {
p[0] = vector<int>{ 1, 1 };
for (int i = 1; i <= 10; i++) {
p[i] = vector<int>((1 << i) + 1);
p[i][0] = (1 << i);
for (int j = 1; j <= (1 << (i - 1)); j++)
p[i][(1 << (i - 1)) + j] = p[i][(1 << (i - 1)) - j + 1] = (p[i - 1][j] << 1);
for (int j = (int)p[i].size() - 1; j >= 1; j--)
if (j & 1)
p[i][j]--;
}
}
int a[500][2000];
int b[500 * 2000];
int col[2000];
int main() {
init();
int t;
scanf("%d", &t);
while (t--) {
int n, k;
scanf("%d%d", &n, &k);
for (int i = 1; i <= 2 * n * (1 << k); i++)
scanf("%d", &b[i]);
for (int i = 1; i <= (1 << k); i++)
col[p[k][i]] = i;
bool flag = false;
int now = 0;
for (int i = 1; i <= (1 << k); i++) {
int g = col[i];
if (!flag) {
for (int j = 2 * n; j >= 1; j--)
a[j][g] = ++now;
}
else {
for (int j = 1; j <= 2 * n; j++)
a[j][g] = ++now;
}
flag ^= true;
}
for (int i = 1; i <= 2 * n - 1; i++) {
for (int j = 1; j <= (1 << k); j++)
printf("%d ", b[a[i][j]]);
}
for (int j = 1; j <= (1 << k) - 1; j++)
printf("%d ", b[a[2 * n][j]]);
printf("%d
", b[a[2 * n][1 << k]]);
}
return 0;
}
1007 Tree
题意为求一个树上的子图，使得子图全连通、子图上度数大于 (k) 的点至多为 (1) 个、子图边权值和最大
我们任取一点为根，做树形 (dp)，令 (dp[i][j]) 表示
- 以 (i) 为根的子树，度数大于 (k) 的点为 (j) ，
- (i) 的度数小于等于 (k-1) 或 (i) 为度数大于 (k) 的那个点
(dp[i][0]) 为子树中最大的 (k-1) 个 (dp[j][0])
(dp[i][1]) 为所有子树的 (dp[j][0]) 之和或 (dp[i][0]) 删除一个子树换成 (dp[j][1])
对于每个 (i) 容易由 (dp[i][0]) 和 (dp[i][1]) 得到以 (i) 为根的子图的最大值，求最值即可
比赛时一发过。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, LL> pii;
typedef pair<LL, LL> pll;
const int maxn = 2e5 + 5;
LL dp[maxn][2];
vector<pii> E[maxn];
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n, k;
scanf("%d%d", &n, &k);
int u, v, w;
for (int i = 1; i <= n; i++)
E[i].resize(0);
for (int i = 1; i < n; i++) {
scanf("%d%d%d", &u, &v, &w);
E[u].push_back(make_pair(v, w));
E[v].push_back(make_pair(u, w));
}
if (k == 0) {
printf("0
");
continue;
}
LL ans = 0;
function<void(int, int)> dfs;
dfs = [&](int now, int fa) {
dp[now][0] = dp[now][1] = 0;
int g = 0;
vector<pll> a;
a.push_back(make_pair(0, 0));
for (auto it : E[now]) {
if (it.first == fa)
continue;
dfs(it.first, now);
a.push_back(make_pair(it.second + dp[it.first][0],
it.second + dp[it.first][1]));
g++;
}
LL ansl = 0, ansr = 0;
sort(a.begin() + 1, a.begin() + 1 + g,
[](const pll& a, const pll& b) { return a.first > b.first; });
for (int i = 1; i <= min(k - 1, g); i++)
dp[now][0] += a[i].first;
if (g >= k)
ansl = dp[now][0] + a[k].first;
else
ansl = dp[now][0];
ans = max(ans, ansl);
for (int i = 1; i <= g; i++)
dp[now][1] += a[i].first;
ansr = dp[now][1];
for (int i = 1; i <= min(k - 1, g); i++)
dp[now][1] =
max(dp[now][1], dp[now][0] - a[i].first + a[i].second);
for (int i = k; i <= g && (k - 1 > 0); i++)
dp[now][1] =
max(dp[now][1], dp[now][0] - a[k - 1].first + a[i].second);
for (int i = 1; i <= min(k, g); i++)
ansr = max(ansr, ansl - a[i].first + a[i].second);
for (int i = k + 1; i <= g && (k > 0); i++)
ansr = max(ansr, ansl - a[k].first + a[i].second);
ans = max(ans, ansr);
};
dfs(1, 0);
printf("%lld
", ans);
}
return 0;
}
1008 Set2
该题为 (1012) 的变式，由于 (nleq 5000)，所以可以用 (O(n^2)) 的 (dp) 解决。
(dp[i]) 表示倒数第 (i) 个存活的几率，首先要计算最后剩余数，将其 (dp) 值赋为 (1) 。
然后加入人数，直到 (n) 个人。如果这个数不是一定被取出，就做更新一次 (dp)，否则 (dp[i]=0) 。
[egin{aligned}dp[i]=dp[i] imes frac{j-i}{j}+dp[i-1] imes frac{i-1}{j}，j 为当前数字全部数量end{aligned}
]
比赛时对剩余人数处理和题目表达的方式有出入，导致WA1，理清处理方法后就过了。
#include<bits/stdc++.h>
#define ll long long
#define maxn 100010
#define mod 998244353
using namespace std;
ll inv[maxn], ans[maxn];
ll qpow(ll x, ll y) {
ll bas = 1;
while (y) {
if (y % 2) bas = bas * x % mod;
x = x * x % mod;
y /= 2;
}
return bas;
}
ll po(ll x) {
ll bas = 1, y = mod - 2;
while (y) {
if (y % 2) bas = bas * x % mod;
x = x * x % mod;
y /= 2;
}
return bas;
}
int main() {
for (int i = 1; i <= 5100; i++) {
inv[i] = po(i);
}
int t;
scanf("%d", &t);
while (t--) {
int n, k;
scanf("%d%d", &n, &k);
int res = n % (k + 1);
for (int i = 0; i < res; i++) {
ans[i] = 1;
}
for (int i = res; i < n; i++) {
ans[i] = 0;
if ((n - i) % (k + 1) == 1) continue;
for (int j = i; j >= 0; j--) {
if (j == 0) {
ans[j] = ans[j] * (i - j) % mod * inv[i + 1] % mod;
ans[j] %= mod;
}
else {
ans[j] = ans[j] * (i - j) % mod * inv[i + 1] % mod + ans[j - 1] * (j) % mod * inv[i + 1] % mod;
ans[j] %= mod;
}
}
}
for (int i = n - 1; i > 0; i--) printf("%lld ", ans[i]);
printf("%lld
", ans[0]);
}
return 0;
}
1009 Paperfolding
纯粹找规律(大雾)
期望为(1+2^n+(3^n)/(2^{n-1}))
比赛时一发过。
#include<bits/stdc++.h>
#define ll long long
#define maxn 1000010
#define mod 998244353
using namespace std;
ll qpow(ll x, ll y) {
ll bas = 1;
while (y) {
if (y % 2) bas = bas * x % mod;
x = x * x % mod;
y /= 2;
}
return bas;
}
ll po(ll x) {
ll bas = 1, y = mod - 2;
while (y) {
if (y % 2) bas = bas * x % mod;
x = x * x % mod;
y /= 2;
}
return bas;
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
ll n;
scanf("%lld", &n);
if (n == 0) {
printf("4
");
continue;
}
ll ans = qpow(2, n) + 1;
ans %= mod;
ans = ans + qpow(3, n) * po(qpow(2, n - 1)) % mod;
ans %= mod;
printf("%lld
", ans);
}
return 0;
}
1012 Set1
由 (1008) 的 (dp) 式可以得到正解，但 (O(n^2)) 的 (dp) 会 ( ext{T})，所以找找规律。不难得出规律：
[egin{gather*}对于任意一个合法的n，前 lfloor frac{n}{2}
floor 个数都是 0 \dp[frac{n+1}{2}]=frac{1}{2^{frac{n}{2}}} \dp[i+1]=dp[i] imes frac{frac{n}{2}+i}{2i} (i<n-1) \ dp[n]=dp[n-1]\end{gather*}
]
比赛时一发过。
#include<bits/stdc++.h>
#define ll long long
#define maxn 1000010
#define mod 998244353
using namespace std;
ll qpow(ll x, ll y) {
ll bas = 1;
while (y) {
if (y % 2) bas = bas * x % mod;
x = x * x % mod;
y /= 2;
}
return bas;
}
ll po(ll x) {
ll bas = 1, y = mod - 2;
while (y) {
if (y % 2) bas = bas * x % mod;
x = x * x % mod;
y /= 2;
}
return bas;
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
if (n == 1) {
printf("1
");
continue;
}
for (int i = 1; i <= n / 2; i++) printf("0 ");
ll ans = po(qpow(2, n / 2));
printf("%lld ", ans);
for (int i = 1; i < n / 2; i++) {
ans = ans * (n / 2 + i) % mod * po(2 * i) % mod;
printf("%lld ", ans);
}
printf("%lld
", ans);
}
return 0;
}