240 pts, 100 + 100 + 40, rk 2
不会 T3 自闭了
难度大概是三道 PJ T3 + PJ T2 + PJ T3?
我菜死了
A. 积木
有
一种方案之后的扩展只和最上面有关。
则我们记
dp 明显,枚举状态,枚举下一个积木。
注意判断可行时,不仅是考虑置换,还要考虑对换。
时间复杂度
#include <bits/stdc++.h>
#define in(S, i) (S & (1 << (i - 1)))
using namespace std;
typedef long long ll;
const int MAXN = 15 + 10, MAXSTATUS = (1 << 15) + 10;
int n, arr[MAXN][3];
ll f[MAXSTATUS][MAXN][3], ans;
void chkmax(ll& a, ll b) { if (a < b) a = b; }
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) for (int _ = 0; _ < 3; ++_) scanf("%d", &arr[i][_]);
int MAXS = (1 << n) - 1;
for (int i = 1; i <= n; ++i) {
for (int _ = 0; _ < 3; ++_) {
f[1 << (i - 1)][i][_] = arr[i][(_ + 2) % 3];
}
}
for (int S = 0; S <= MAXS; ++S) {
for (int i = 1; i <= n; ++i) {
if (!in(S, i)) continue;
for (int j = 1; j <= n; ++j) {
if (in(S, j)) continue;
for (int _ = 0; _ < 3; ++_) {
for (int __ = 0; __ < 3; ++__) {
if ((arr[i][_ % 3] >= arr[j][__ % 3] && arr[i][(_ + 1) % 3] >= arr[j][(__ + 1) % 3]) || (arr[i][_ % 3] >= arr[j][(__ + 1) % 3] && arr[i][(_ + 1) % 3] >= arr[j][__ % 3])) {
chkmax(f[S | (1 << (j - 1))][j][__], f[S][i][_] + arr[j][(__ + 2) % 3]);
}
}
}
}
}
}
for (int S = 0; S <= MAXS; ++S) {
for (int i = 1; i <= n; ++i) {
for (int _ = 0; _ < 3; ++_) chkmax(ans, f[S][i][_]);
}
}
printf("%lld", ans);
return 0;
}
B. 快速荷叶叶变换
求
整除分块。
时间复杂度
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P = 1e9 + 7;
ll n, m, sum, ans;
void add(ll& a, ll b) { a = (a + b) % P; }
int main() {
scanf("%lld %lld", &n, &m);
for (ll l = 1; l <= m; ) {
ll r = min(m / (m / l), m);
ll val = m / l;
add(sum, (1ll * (r - l + 1) * m - 1ll * val * (l + r) * (r - l + 1) / 2) % P);
l = r + 1;
}
for (ll l = 1; l <= n; ) {
ll r = min(n / (n / l), n);
ll val = n / l;
ans = (ans + 1ll * (1ll * (r - l + 1) * n - 1ll * val * (l + r) * (r - l + 1) / 2) % P * sum % P) % P;
l = r + 1;
}
printf("%lld\n", ans);
return 0;
}
C. 树上摩托
给出一棵树,求断边方案数,使得断边后各连通块大小相同。
显然各连通块仍是树。
显然各新树大小为
且当固定大小之后,断边的方式是唯一确定的。
考虑一种合法的方案,最终是
时间复杂度
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
int n, sz[MAXN];
vector<int> e[MAXN];
void dfs(int u, int fa) {
sz[u] = 1;
for (auto v : e[u]) if (v != fa) {
dfs(v, u), sz[u] += sz[v];
}
}
int main() {
scanf("%d", &n);
for (int i = 1, u, v; i < n; ++i) {
scanf("%d %d", &u, &v);
e[u].push_back(v), e[v].push_back(u);
}
dfs(1, 0);
int ans = 0;
for (int k = 1; k <= n; ++k) {
if (n % k == 0) {
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (sz[i] % k == 0) cnt ++;
}
if (cnt == n / k) ans ++;
}
}
printf("%d\n", ans);
return 0;
}
总结
好
- AB 切出来了
- C 暴力写出来了