1023考试总结
T1
题目大意:
有(n)个队伍,每个队伍有(v)个气球,每个队伍最多有(w)个气球,只要手中的气球大于这个数,那么所有气球都会爆掉.现在你在第1个队里,你可以把自己手里的气球给别人,也就是说你可以让别人的气球爆掉.最后谁气球多谁排名就靠前,求你所在的队伍的最好(最小)排名是多少? (n <= 3e5)
优先队列 + 贪心.
首先我们要确定怎么给气球是优的.给v比自己小的队伍肯定不优,因为他排名比你靠后,你还让自己的气球减少,显然不优.所以我们每次选一个v比自己大并且最容易爆掉的队伍,也就是(w - v)最小的那一个.
我们搞一个大根堆一个小根堆,大根堆存的是v比自己小的队伍,小根堆存的v是比自己大的队伍.我们每次从小根堆里取出一个(w - v)最小的让它爆掉,然后自己的v就会减去(w - v + 1),然后我们把大根堆里现在v比自己大的放到小根堆.然后一直按照这个过程模拟就好了.
复杂度(O(n log n)).
#include <bits/stdc++.h>
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N = 3e5 + 5;
int n, ans;
struct {
long long v, w, p;
} a[N];
priority_queue <pair<long long, int> > q1;
priority_queue <pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > q2;
int main() {
n = read();
for(int i = 1;i <= n; i++) {
a[i].v = read(), a[i].w = read(), a[i].p = a[i].w - a[i].v;
if(i != 1) {
if(a[i].v > a[1].v) q2.push(make_pair(a[i].p, i));
else q1.push(make_pair(a[i].v, i));
}
}
ans = (int) q2.size() + 1;
for(int i = 1;i <= n; i++) {
if(a[1].v < q2.top().first) break;
if(!q2.size()) break;
a[1].v -= (q2.top().first + 1);
q2.pop();
while(q1.size() && q1.top().first > a[1].v) {
int tmp = q1.top().second; q1.pop();
q2.push(make_pair(a[tmp].p, tmp));
}
ans = min(ans, (int) q2.size() + 1);
}
printf("%d", ans);
fclose(stdin); fclose(stdout);
return 0;
}
T2
题目大意:
给定一颗(n)个节点的树,有一些单向边具有边权.现在给你一个走点的顺序,每次经过一条有边权的边时要统计权值总和,第一次经过这条边边权为1,第二次为2,第三次为4,以此类推,问最后的权值总和是多少? (n <= 1e5)
树上差分.
我们把1作为根节点,把从儿子到父亲的边称为上行边,从父亲到儿子的边称为下行边.假设当前要从(s)走到(t),那么(s)到(lca)应该走的是上行边,(lca)到(t)应该走的是下行边.然后我们统计两个差分数组,分别统计上行边和下行边经过的次数,最后把有边权的统计到答案里就好了.
#include <bits/stdc++.h>
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N = 1e5 + 5, mod = 1e9 + 7;
int n, k, cnt, ans;
int up[N], down[N], id_up[N], id_down[N], f[N][21], dep[N], sum[N * 10], head[N];
struct task {
int s, t;
} b[N * 10];
struct edge {
int f, to, nxt, ans, from;
} e[N << 1];
void add(int x, int y, int z) {
e[++ cnt].nxt = head[x]; head[x] = cnt; e[cnt].to = y; e[cnt].f = z; e[cnt].from = x;
}
void get_tree(int x, int fa) {
dep[x] = dep[fa] + 1; f[x][0] = fa;
for(int i = head[x]; i ; i = e[i].nxt) {
int y = e[i].to; if(y == fa) continue;
get_tree(y, x);
}
}
void make_f_sum() {
for(int i = 1;i <= 20; i++)
for(int j = 1;j <= n; j++) f[j][i] = f[f[j][i - 1]][i - 1];
int tmp = 1; sum[1] = 1;
for(int i = 2;i <= k; i++) sum[i] = (sum[i - 1] + 1ll * tmp * 2 % mod) % mod, (tmp *= 2) %= mod;
}
int LCA(int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
for(int i = 20;i >= 0; i--) if(dep[x] - dep[y] >= (1 << i)) x = f[x][i];
if(x == y) return x;
for(int i = 20;i >= 0; i--) if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
return f[x][0];
}
void get_id(int x, int fa) {
for(int i = head[x]; i ; i = e[i].nxt) {
int y = e[i].to; if(y == fa) continue;
get_id(y, x); id_up[y] = i ^ 1; id_down[y] = i;
}
}
void get_ans(int x, int fa) {
for(int i = head[x]; i ; i = e[i].nxt) {
int y = e[i].to; if(y == fa) continue;
get_ans(y, x); up[x] += up[y]; down[x] += down[y];
e[id_up[y]].ans += up[y]; e[id_down[y]].ans += down[y];
}
}
int main() {
n = read(); cnt = 1;
for(int i = 1, x, y, opt;i <= n - 1; i++) {
x = read(); y = read(); opt = read();
add(x, y, 0); add(y, x, opt);
}
k = read();
get_tree(1, 0); make_f_sum();
int last = 1;
for(int i = 1, x, lca;i <= k; i++) {
x = read(); lca = LCA(last, x);
up[last] ++; up[lca] --;
down[x] ++; down[lca] --;
last = x;
}
get_id(1, 0); get_ans(1, 0);
for(int i = 1;i <= cnt; i++) {
if(!e[i].f) continue;
ans = (ans + sum[e[i].ans]) % mod;
}
printf("%d", ans);
fclose(stdin); fclose(stdout);
return 0;
}
T3
题目大意:
给定一颗(n)个节点的树,每次断开一条边,把两个子树内较大的那个直径统计到答案里,输出最后的总和.(n <= 1e5)
树的直径.
我们首先找到整颗树的直径,然后遍历每一条边,如果这条边不在直径上,那么两个子树内较大的那个直径就是整棵树的直径.如果这条边在直径上,那么我们就要找到这两棵子树内不在直径上的最长的一条路径.然后与部分直径合并,得到这颗子树内的直径.我们知道合并两颗树的直径时新的直径的端点一定是两条小直径的其中两个端点,反过来也是这样.
为什么复杂度是正确的,具体我也不会算复杂度,但是树的直径上的点应该很少,所以找新的小直径应该也不多.
#include <bits/stdc++.h>
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N = 1e5 + 5;
int n, s, t, dia, cnt;
long long ans, tmp1, tmp2, res;
int f[N], g[N], h[N], vis[N], fa[N], dia_node[N], head[N];
struct edge {
int to, nxt, val;
} e[N << 1];
void add(int x, int y, int z) {
e[++ cnt].nxt = head[x]; head[x] = cnt; e[cnt].to = y; e[cnt].val = z;
}
void get_node_1(int x, int fa, int sum) {
if(dia < sum) { dia = sum; s = x; }
for(int i = head[x]; i ; i = e[i].nxt) {
int y = e[i].to; if(y == fa) continue;
get_node_1(y, x, sum + e[i].val);
}
}
void get_node_2(int x, int Fa) {
if(dia_node[x] > dia) { dia = dia_node[x]; t = x; }
for(int i = head[x]; i ; i = e[i].nxt) {
int y = e[i].to; if(y == Fa) continue;
dia_node[y] = dia_node[x] + e[i].val; fa[y] = x;
get_node_2(y, x);
}
}
void get_f(int x, int fa, int &s) {
for(int i = head[x]; i ; i = e[i].nxt) {
int y = e[i].to; if(y == fa || vis[y]) continue;
g[y] = g[x] + e[i].val; get_f(y, x, s);
}
s = max(s, g[x]);
}
void get_g(int x, int fa) {
g[x] = f[x] + dia - dia_node[x];
for(int i = head[x]; i ; i = e[i].nxt) {
int y = e[i].to; if(!vis[y] || y == fa) continue;
get_g(y, x); g[x] = max(g[x], g[y]);
}
}
void get_ans(int x, int fa) {
for(int i = head[x]; i ; i = e[i].nxt) {
int y = e[i].to; if(y == fa) continue;
if(vis[y]) {
ans += max(h[x], g[y]);
h[y] = max(h[x], dia_node[y] + f[y]);
}
else ans += dia;
get_ans(y, x);
}
}
int main() {
n = read();
for(int i = 1, x, y, z;i <= n - 1; i++) {
x = read(); y = read(); z = read();
add(x, y, z); add(y, x, z);
}
get_node_1(1, 0, 0);
get_node_2(s, 0);
int tmp = t;
while(tmp != 0) { vis[tmp] = 1; tmp = fa[tmp]; }
for(int i = 1;i <= n; i++) if(vis[i]) get_f(i, 0, f[i]);
for(int i = 1;i <= n; i++) g[i] = 0; get_g(s, 0);
h[s] = f[s]; get_ans(s, 0);
printf("%lld", ans);
fclose(stdin); fclose(stdout);
return 0;
}