说好的22:35开始推迟到0:35......
共6题, 比赛时完成A-C. C题搞复杂啦, Editorial比较喵......
题解: 4/6. # A. Buying A House 数轴单位长度为10m. n个点ai, 有些可购买且有一个价格. 求可购买且价格不超过k的点离第m个点的最近距离. (2≤n≤100, 1≤m≤n, 1≤k≤100, 0≤ai≤100)
int main()
{
int n, m, k, d = 100000;
scanf("%d%d%d", &n, &m, &k);
rep (i, 1, n+1) {
int a;
scanf("%d", &a);
if (a && a <= k) d = min(d, abs(m-i));
}
printf("%d\n", d*10);
return 0;
}B. Find The Bone
n个位置, 其中某m个有洞, 位置上盖着杯子. 一开始1号位置有一块骨头. k个交换操作, 每次连着可能存在的骨头交换ui与vi位置的杯子, 一旦骨头处在某个有洞的位置, 它就不会再动了. (2≤n≤10^6, 1≤m≤n, 1≤k≤3*10^5)
注意特判1号位置有洞的情况.
const int N = 1e6 + 1;
bool h[N];
int main()
{
int bone = 1, n, m, k;
scanf("%d%d%d", &n, &m, &k);
rep (i, 0, m) {
int x;
scanf("%d", &x);
h[x] = true;
}
if (h[1]) {
puts("1");
return 0;
}
rep (i, 0, k) {
int u, v;
scanf("%d%d", &u, &v);
if (u == bone) bone = v;
else if (v == bone) bone = u;
if (h[bone]) break;
}
printf("%d\n", bone);
return 0;
}C. Bank Hacking
一棵n个结点的树, 每个结点有力量值ai, 一开始所有结点全部在线, 某点被hack之后变为离线, 并且和它相邻或半相邻的在线结点的力量+1. u和v半相邻, 当且仅当u,v均和某在线结点w相邻. 一个点x可被hack当且仅当以下条件同时满足: - x是在线的. - x和某个离线结点相邻 (如果x是第一个被hack的结点, 则无此限制). - x的力量不大于hacker的力量.
求hack所有点所需的最小力量. (1≤n≤3*10^5, -109≤ai≤109)
一开始感觉是贪心, 但是没有什么思路......观察到某种hack方案所需的最小力量完全取决于第1个结点, 并且可以这样计算:
设第1个结点为u, 则ans[u] = max { a[u], a[v] + 1 (v和u相邻), a[v] + 2 (v和u的距离大于1) }.
树上DP可以做. 先转有根树. 考虑求max { a[v] + 2 (v和u的距离大于1) }. 设h[u] = max { a[v] (v在以u为根的子树中) }, g[u] = max { h[v] (v是u的儿子) }, 这两个量可以一次DFS求出. 然后, 对所有边u->v, 求出f[u, v] = max { h[w] (w是u除v以外的儿子) }, 这个量可以记在边上, 通过记录所有儿子h值的最大值和次大值求出. 再求出up[u] = max { a[v] (v是u, u的祖先) }. 第二次DFS的时候把一路上的max {f}作为参数传下去即可.
我好像搞麻烦了...... 但是这种处理树上问题的方法 (子树->子树外面) 感觉不错.
Editorial是这样做的:
用map维护一下每种权值的出现次数, 做一下减法即可......可以优化至
记mx = max { a[i] }. 注意到答案属于{ mx, mx+1, mx+2 }. 考虑{ a[v] + 2 }这部分. 如果某个a[v] = mx, 则ans[u] = mx + 2. 否则, 如果{ a[v] + 1 }这部分的a[v]能取到mx, 则ans[u]和{ a[v] + 2 }无关; 如果{ a[v] }这部分能取到mx, a[v] + 2 > mx <=> a[v] >= mx-1. 综合以上, 只用维护mx和mx-1的出现次数.
const int inf = 1e9 + 10, N = 3e5;
struct Edge {
int v, f;
};
vector<Edge> adj[N+1];
int g[N+1], h[N+1], a[N+1], up[N+1], fa[N+1], ans[N+1];
int dfs1(int u, int p)
{
fa[u] = p;
g[u] = -inf;
rep (i, 0, adj[u].size()) {
int v = adj[u][i].v;
if (v != p)
g[u] = max(g[u], dfs1(v, u));
}
return h[u] = max(g[u], a[u]);
}
void dfs2(int u, int p, int f)
{
up[u] = max(up[p], a[u]);
ans[u] = max(f, up[fa[p]]);
rep (i, 0, adj[u].size()) {
int v = adj[u][i].v;
if (v != p) {
ans[u] = max(ans[u], g[v]);
dfs2(v, u, max(f, adj[u][i].f));
}
}
}
int main()
{
int n;
scanf("%d", &n);
rep (i, 1, n+1)
scanf("%d", &a[i]);
rep (i, 0, n-1) {
int u, v;
scanf("%d%d", &u, &v);
adj[u].push_back((Edge){v, -inf});
adj[v].push_back((Edge){u, -inf});
}
dfs1(1, 0);
rep (i, 1, n+1) {
int mx1 = -inf, mx2 = -inf;
rep (j, 0, adj[i].size()) {
int v = adj[i][j].v;
if (v == fa[i]) continue;
int t = h[v];
if (t >= mx1) {
mx2 = mx1;
mx1 = t;
} else if (t > mx2) {
mx2 = t;
}
}
rep (j, 0, adj[i].size())
adj[i][j].f = h[adj[i][j].v] == mx1 ? mx2 : mx1;
}
up[0] = -inf;
dfs2(1, 0, -inf);
rep (i, 1, n+1) {
ans[i] = max(ans[i] + 2, a[i]);
rep (j, 0, adj[i].size())
ans[i] = max(ans[i], a[adj[i][j].v] + 1);
}
printf("%d\n", *min_element(ans+1, ans+n+1));
}const int N = 3e5, inf = 1e9 + 10;
int a[N+1];
vector<int> adj[N+1];
int main()
{
int n, ans = inf, mx = -inf, c0 = 0, c1 = 0;
scanf("%d", &n);
rep (i, 1, n+1) {
scanf("%d", &a[i]);
mx = max(mx, a[i]);
}
rep (i, 1, n+1) {
c0 += a[i] == mx;
c1 += a[i] == mx-1;
}
rep (i, 0, n-1) {
int u, v;
scanf("%d%d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
rep (i, 1, n+1) {
int d0 = c0 - (a[i] == mx), d1 = c1 - (a[i] == mx-1), m = -inf;
rep (j, 0, adj[i].size()) {
int k = adj[i][j];
d0 -= a[k] == mx;
d1 -= a[k] == mx-1;
m = max(m, a[k]);
}
int d = d0 ? mx : (d1 ? mx-1 : -inf);
ans = min(ans, max(a[i], max(m+1, d+2)));
}
printf("%d\n", ans);
return 0;
}D. Police Stations
n个结点的树, 有k个特殊点, 要求在保证每个点离某特殊点距离不超过d的前提下砍掉尽量多的边. 输入保证不砍掉任何边时满足该条件. 一个特殊点可能在输入中出现多次. 求砍掉的最多边数, 并任意输出一组方案. (2≤n≤3*10^5, 1≤k≤3*10^5, 0≤d≤n-1)
不妨先考虑一下答案的上界. 设去重后有k'个点. 每个连通块必须含一个特殊点, 所以至多砍掉(k'-1)条边. 这个上界是可以达到的. 只需要把每个点划给离它最近的特殊点. 把所有起始点扔进队列, 做一遍BFS即可保证划出来的是一个连通块, 且每个点都能访问到.
const int N = 3e5;
vector<int> adj[N+1];
vector<pair<int, int> > edges;
int D, color[N+1], d[N+1];
bool f[N+1];
queue<int> Q;
void bfs()
{
while (!Q.empty()) {
int u = Q.front();
Q.pop();
if (d[u] == D) continue;
rep (i, 0, adj[u].size()) {
int v = adj[u][i];
if (!color[v]) {
d[v] = d[u] + 1;
color[v] = color[u];
Q.push(v);
}
}
}
}
int main()
{
int n, k;
scanf("%d%d%d", &n, &k, &D);
rep (i, 0, k) {
int p;
scanf("%d", &p);
f[p] = true;
}
rep (i, 0, n-1) {
int u, v;
scanf("%d%d", &u, &v);
edges.push_back(make_pair(u, v));
adj[u].push_back(v);
adj[v].push_back(u);
}
int cnt = 0;
rep (i, 1, n+1)
if (f[i]) {
Q.push(i);
color[i] = i;
++cnt;
}
bfs();
printf("%d\n", cnt-1);
int now = 0;
rep (i, 0, n-1) {
if (color[edges[i].first] != color[edges[i].second]) {
++now;
printf("%d%c", i+1, " \n"[now == cnt-1]);
}
}
return 0;
}