nowcoder contest6

nowcoder contest6

测试比赛环境是否支持__int128;

树上任意两个节点之间的距离的求解

可以说是一个板子题了,只要统计每一条边对答案产生的贡献的次数

hdu2376

一遍dfs就可以了

ac code

时间复杂度为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4+10;
int n;
struct Edge{
int v, w;
};
vector<Edge> G[maxn];
int num[maxn];
ll dp[maxn];
void init(){
memset(num, 0, sizeof(num));
memset(dp, 0, sizeof(dp));
for(int i=0; i<maxn; i++)G[i].clear();
}
void dfs(int u, int fa){
num[u] = 1;
for(int i=0; i<G[u].size(); i++){
int v = G[u][i].v;
ll w = G[u][i].w;
if(v == fa) continue;
dfs(v, u);
num[u] += num[v];
dp[u] += dp[v]+1ll*(n-num[v])*num[v]*w;
}
}
int main()
{
ios::sync_with_stdio(false);
int _;
scanf("%d", &_);
while(_--){
init();
scanf("%d", &n);
int u, v, w;
for(int i=0; i<n-1; i++){
scanf("%d%d%d", &u, &v, &w);
G[u].push_back(Edge{v, w});
G[v].push_back(Edge{u, w});
}
dfs(0, -1);
printf("%.8lf\n", 1.0*dp[0]/(n*(n-1))*2);
}
return 0;
}

I team rocket

题目里面有一个很奇怪的运算,目的就是为了强制在线。

可以使用权值线段树(zkw)来维护
要维护删除区间的操作,操作简化为一个点
若使用树状数组来维护,就要对纵坐标排序,

树状数组

感觉有点骚,还是应该学习一下线段树的做法

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n , m , X[N] , Y[N];
int d[N] , D , o[N] , v[N];
vector<int> c[N];
int lowbit(int x){
return x&(-x);
}
struct Node{
int y;
int id;
}node[N];
bool cmp1(Node a, Node b){
return a.y<b.y;
}
void work() {
scanf("%d%d" , &n , &m);
D = 0;
//n个坐标
for (int i = 1 ; i <= n ; ++ i) {
scanf("%d%d" , X + i , Y + i);
d[D ++] = X[i];
}
//离散化
sort(d , d + D);
D = unique(d , d + D) - d;
for (int i = 1 ; i <= n ; ++ i) {
//o[i] = i;//什么意思?保存y的下标
X[i] = lower_bound(d , d + D , X[i]) - d + 1;
c[i].clear();
v[i] = 0;//vis?
}
//对Y排序,保存排好序后y的下标
for(int i=1; i<=n; i++){
node[i].y = Y[i];
node[i].id = i;
}
sort(node+1, node+n+1, cmp1);
// sort(o + 1 , o + n + 1 , [&](int x , int y) {
// return Y[x] < Y[y];
// });
for (int i = 1 ; i <= n ; ++ i) {
int j = node[i].id;
//lowbit
for (int k = X[j] ; k <= n ; k += lowbit(k)) {
c[k].push_back(j);
}
}
int res = 0;
for (int i = 1 ; i <= m ; ++ i) {
int x;
scanf("%d" , &x);
x ^= res;
int j = upper_bound(d , d + D , x) - d;
int cnt = 0;
res = 1;
for (int k = j ; k > 0 ; k -= lowbit(k)) {
while (!c[k].empty() && Y[c[k].back()] >= x) {
int w = c[k].back();
if (!v[w]) {
v[w] = i;//第几次被弹出来
++ cnt;
res = (long long)res * w % 998244353;//横坐标的乘积
}
c[k].pop_back();
}
}
printf("%d\n" , cnt);
if (cnt == 0) res = 0;
}
for (int i = 1 ; i <= n ; ++ i) {
printf("%d%c" , v[i] , " \n"[i == n]);
}
}
int main() {
int T;
scanf("%d" , &T);
while (T --) {
static int ca = 0;
printf("Case #%d:\n" , ++ ca);
work();
}
}

未解决的问题

文章目录
  1. 1. 树上任意两个节点之间的距离的求解
    1. 1.1. hdu2376
      1. 1.1.1. ac code
  2. 2. I team rocket
    1. 2.1. 树状数组
    2. 2.2. AC code
  3. 3. 未解决的问题
{{ live2d() }}