A. 三级包##
比赛时没什么想法，五分钟写了个暴搜 + 最优化剪枝竟然就可以过 90 分。比赛结束后试了发卡时，竟然就过了 OrzOrzOrz 。还是积累下经验吧，比赛的时候就算觉得暴力完全不可能过，也应该顺手卡一下时的。毕竟有时候人品攒够指不定就 A 了呢……
可以 A 的暴搜 + 剪枝 + 卡时
#include <cstdio>
#include <algorithm>
#include <ctype.h>
char buf[1 << 20], *p1, *p2, sss[30], top;
inline gc() { return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?EOF:*p1++; }
template<typename T>
void rd(T &num)
{
char tt;
bool flag = 0;
while (!isdigit(tt = gc()) && tt != '-');
if (tt == '-') num = 0, flag = 1;
else num = tt - '0';
while (isdigit(tt = gc()))
num = num * 10 + tt - '0';
if (flag) num = -num;
return;
}
template<typename T>
void pt(T num)
{
if (num < 0) putchar('-'), num = -num;
top = 0;
do sss[++top] = num % 10 + '0';
while (num /= 10);
while (top) putchar(sss[top--]);
putchar('
');
return;
}
typedef long long ll;
using namespace std;
const int _N = 100;
ll A[_N], B[_N], ans;
int K, N, M, Time;
void dfs(int p, int res, ll w)
{
ans = max(ans, w);
if (p == K + 1)
return;
if (w + B[min(K, p + res - 1)] - B[p - 1] <= ans)
return;
if (++Time > 100000000) return;
dfs(p + 1, res, w);
if (w + A[p] <= M && res - 1 >= 0)
dfs(p + 1, res - 1, w + A[p]);
return;
}
bool cmp(const ll &a, const ll &b) { return a > b; }
int main()
{
rd(N), rd(M), rd(K);
for (int i = 1; i <= K; ++i)
rd(A[i]), B[i] = A[i];
sort(B + 1, B + 1 + K, cmp);
for (int i = 1; i <= K; ++i)
A[i] = B[i], B[i] += B[i - 1];
dfs(1, N, 0);
printf("%lld
", ans);
return 0;
}
B. 三级甲##
C. 三级头##
这个换根操作写在 其他-Little Tricks 里了。
树上换根对子树影响##
假设原树的根是 (x) ，新根是 (y) 。讨论 (t) 在新树中的子树。
- 如果 (y) 就是 (t)， (t) 在新树中的子树就是整棵树。
- 如果 (y) 在原树中 (t) 的子树外，那么新树中 (t) 的子树仍然是原树中它的子树。
- 如果 (y) 在原树中 (t) 的子树内，设 (t) 在 (y) 到 (x) 的路径上的儿子是 (g) ，而原树中 (g) 的子树是 (s) ，那么新树中 (t) 的子树是整棵树除去 (s) 这部分。
这样问题就转化成了求区间严格大于 (k) 的数的个数。写一发分块，然后二分查找就可以了。也可以用平衡树维护，不过树套树代码略难写，况且 NOIP 考不到，所以只写了分块（其实是太懒）。
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>
const int _N = 110000;
using namespace std;
vector<int> G[_N];
int dad[_N][20], siz[_N], dep[_N], dfn[_N], W[_N], A[_N], B[_N];
int Time, L, N, M, Rt, mxdep, LG;
void build(int p)
{
dfn[p] = ++Time, siz[p] = 1;
for (int i = G[p].size() - 1; i >= 0; --i) {
int v = G[p][i];
if (v != dad[p][0]) {
dad[v][0] = p;
mxdep = max(mxdep, dep[v] = dep[p] + 1);
build(v);
siz[p] += siz[v];
}
}
return;
}
inline int gl(int v) { return (v - 1) / L * L + 1; }
inline int gr(int v) { return min(N, (v - 1) / L * L + L); }
int getgrt(int l, int r, int k)
{
if (l > r) return 0;
int cnt = 0;
if (gl(l) == gl(r)) {
for (int i = l; i <= r; ++i)
if (A[i] > k) ++cnt;
return cnt;
}
for (int i = l; i <= gr(l); ++i)
if (A[i] > k) ++cnt;
for (int i = r; i >= gl(r); --i)
if (A[i] > k) ++cnt;
for (int i = gr(l) + 1; i != gl(r); i += L) {
int t = upper_bound(W + i, W + i + L, k) - W;
cnt += gr(i) - t + 1;
}
return cnt;
}
void modify(int p, int k)
{
int t = lower_bound(W + gl(p), W + gr(p) + 1, A[p]) - W;
W[t] = k, A[p] = k;
for (int i = t - 1; i >= gl(t) && W[i] > W[i + 1]; --i)
swap(W[i], W[i + 1]);
for (int i = t + 1; i <= gr(t) && W[i - 1] > W[i]; ++i)
swap(W[i - 1], W[i]);
return;
}
int moveup(int p, int k)
{
for (int i = 0; i <= LG; ++i)
if (k >> i & 1)
p = dad[p][i];
return p;
}
int query(int p, int k)
{
if (Rt == p)
return getgrt(1, N, k);
if (dfn[Rt] < dfn[p] || dfn[Rt] >= dfn[p] + siz[p])
return getgrt(dfn[p], dfn[p] + siz[p] - 1, k);
int tmp = moveup(Rt, dep[Rt] - dep[p] - 1);
return getgrt(1, dfn[tmp] - 1, k) + getgrt(dfn[tmp] + siz[tmp], N, k);
}
int main()
{
scanf("%d%d", &N, &M);
L = sqrt(N + 0.5);
for (int i = 1; i <= N; ++i)
scanf("%d", &B[i]);
for (int a, b, i = 1; i < N; ++i) {
scanf("%d%d", &a, &b);
G[a].push_back(b), G[b].push_back(a);
}
Rt = 1;
build(1);
LG = log2(mxdep + 0.5);
for (int i = 1; i <= LG; ++i)
for (int j = 1; j <= N; ++j)
dad[j][i] = dad[dad[j][i - 1]][i - 1];
for (int i = 1; i <= N; ++i)
W[dfn[i]] = A[dfn[i]] = B[i];
for (int i = L; i <= N; i += L)
sort(W + i - L + 1, W + i + 1);
sort(W + gl(N), W + gr(N) + 1);
for (int i = 1; i <= M; ++i) {
int ins, x, y;
scanf("%d%d", &ins, &x);
if (ins == 1) {
scanf("%d", &y);
printf("%d
", query(x, y));
} else if (ins == 2) {
Rt = x;
} else if (ins == 3) {
scanf("%d", &y);
modify(dfn[x], y);
}
}
return 0;
}