T20201125

Posted on Edited on In Word count in article: 1.6k Reading time ≈ 6 mins.
NOI模拟题

T1

这个和 这道题 很像，其实本质就是一道题，所以可以就按照这道题的方法去写，完全没有问题。

但是进一步考虑，能发现还有一些性质：

  • 实际的路径长度和 \(m+n-1\) 的奇偶性相同

所以，可以考虑线性基，然后取二进制下第 \(30\) 位来控制奇偶性。

然后就可以线性基乱搞了。

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
#include <bits/stdc++.h>

using namespace std;

const int maxn = 30;
int p[maxn];

inline int read()
{
	int x(0);
	char o(getchar());
	while (o < '0' || o > '9') o = getchar();
	for (; o >= '0' && o <= '9'; o = getchar())
		x = (x << 1) + (x << 3) + (o ^ 48);
	return x;
}

inline void insert(int x)
{
	for (int i = maxn; ~i; --i) {
		if (!(x >> i)) continue;
		if (!p[i]) {
			p[i] = x;
			break;
		}
		x ^= p[i];
	}
}

inline int query(int x)
{
	for (int i = maxn; ~i; --i)
		if (~x & (1 << i)) x ^= p[i];
	return x & ((1 << maxn) - 1);
}

int main()
{
	freopen ("sign.in", "r", stdin);
	freopen ("sign.out", "w", stdout);
	int n = read(), m = read(), temp;
	for (int i = 1; i <= n * m; ++i) {
		temp = read();
		insert (temp | (1 << maxn));
	}
	temp = ((n + m) & 1) << maxn;
   cout << query (temp);	
}

T2

分块

就是可以按编号分块，然后预处理出所有点到每个块的最小值，然后块内的信息可以暴力跳。

然后就是可能有点小卡常。

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
const int size = 605;

int n, m, cur, cnt, id[maxn], dis[maxn][size];
int dep[maxn], len[maxn], f[maxn][20];
int head[maxn], edge[maxn << 1];
int cost[maxn << 1], nxt[maxn << 1];

inline int read()
{
    int x(0);
    char o(getchar());
    while (o < '0' || o > '9') o = getchar();
    for (; o >= '0' && o <= '9'; o = getchar())
        x = (x << 1) + (x << 3) + (o ^ 48);
    return x;
}

inline void addedge(int u, int v, int w)
{
    nxt[++cur] = head[u];
    head[u] = cur;
    edge[cur] = v;
    cost[cur] = w;
}

inline int get_lca(int u, int v)
{
    if (dep[u] < dep[v]) swap (u, v);
    for (int i = 17; ~i; --i)
        if (dep[f[u][i]] >= dep[v]) u = f[u][i];
    if (u == v) return u;
    for (int i = 17; ~i; --i)
        if (f[u][i] ^ f[v][i])
            u = f[u][i], v = f[v][i];
    return f[u][0];
}

void dfs(int u, int p)
{
    dep[u] = dep[p] + 1;
    f[u][0] = p, dis[u][id[u]] = 0;
    for (int i = 1; i < 18; ++i)
         f[u][i] = f[f[u][i - 1]][i - 1];
    for (int i = head[u]; i; i = nxt[i]) {
        if (edge[i] == p) continue;
        len[edge[i]] = len[u] + cost[i];
        dfs(edge[i], u);
        for (int j = 1; j <= cnt; ++j) {
            if (dis[edge[i]][j] == inf) continue;
            dis[u][j] = min(dis[edge[i]][j] + cost[i], dis[u][j]);
        }
    }
}

void dfs(int u)
{
    if (f[u][0]) {
        int tmp = len[u] - len[f[u][0]];
        for (int i = 1; i <= cnt; ++i) {
            if (dis[f[u][0]][i] == inf) continue;
            dis[u][i] = min(dis[u][i], dis[f[u][0]][i] + tmp);
        }
    }

    for (int i = head[u]; i; i = nxt[i]) {
        if (edge[i] == f[u][0]) continue;
        dfs(edge[i]);
    }
}

inline int realdis(int u, int v)
{
    if (u == v) return 0;
    return len[u] + len[v] - len[get_lca(u, v)] * 2;
}

int main()
{
    freopen ("tree.in", "r", stdin);
    freopen ("tree.out", "w", stdout);
    n = read(), m = pow(n, 0.4444) + 1;
    cnt = (n - 1) / m + 1;
    memset (dis, 0x3f, sizeof (dis));
    for (int i = 1; i <= n; ++i) id[i] = (i - 1) / m + 1;
    for (int i = 1, u, v, w; i < n; ++i) {
        u = read(), v = read(), w = read();
        addedge(u, v, w), addedge(v, u, w);
    }

    dfs(1, 0), dfs(1);
    m = read();
    int l, r, x, ans;
    while (m--) {
        l = read(), r = read(), x = read(), ans = inf;
        if (id[l] == id[r]) {
            for (int i = l; i <= r; ++i)
                ans = min(ans, realdis(x, i));
        } else {
            for (int i = id[l] + 1; i < id[r]; ++i) ans = min(ans, dis[x][i]);
            for (int i = l; id[i] == id[l]; ++i) ans = min(ans, realdis(x, i));
            for (int i = r; id[i] == id[r]; --i) ans = min(ans, realdis(x, i));
        }
        printf ("%d\n", ans);
    }
}

STD

考虑分治，按线段树的方式把询问区间拆成 \(O(\log⁡n)\) 段，插到线段树上

  • 对线段树上每个节点把对应区间内所有节点和插到节点上的所有询问点拿出来建虚树处理答案

  • 虚树总节点数 \(O((n+m)\log⁡n)\)

  • 实现精细一点可以做到 \(O((n+m) \log⁡n)\) 的时间复杂度

  • 当然 \(O((n+m)\log^2⁡n)\)也能过

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

#define INF 1<<29

#define N 100010
int n,bel[17][N],Root[17][N];
int head[N],next[N<<1],end[N<<1],len[N<<1];
inline void addedge(int a,int b,int l){
	static int q=1;
	end[q]=b;
	next[q]=head[a];
	head[a]=q;
	len[q++]=l;
}
inline void make(int a,int b,int l){
	addedge(a,b,l);
	addedge(b,a,l);
}

#define l(x) S[x].l
#define r(x) S[x].r
struct Node{
	int l,r,re;
}S[15000010];
int cnt;

inline void Insert(int&q,int tl,int tr,int ins,int d){
	if(!q){
		q=++cnt;
		S[q].re=d;
	}
	S[q].re=min(S[q].re,d);
	if(tl==tr)
		return;
	int mid=(tl+tr)>>1;
	if(ins<=mid)
		Insert(S[q].l,tl,mid,ins,d);
	else
		Insert(S[q].r,mid+1,tr,ins,d);
}
inline int Query(int q,int tl,int tr,int dl,int dr){
	if(!q)
		return INF;
	if(dl<=tl&&tr<=dr)
		return S[q].re;
	int mid=(tl+tr)>>1;
	if(dr<=mid)
		return Query(S[q].l,tl,mid,dl,dr);
	else if(dl>mid)
		return Query(S[q].r,mid+1,tr,dl,dr);
	else
		return min(Query(S[q].l,tl,mid,dl,mid),Query(S[q].r,mid+1,tr,mid+1,dr));
}

int q[N],fr,ta;
struct Array{
	int re[N],t[N],tclock,init;
	Array():tclock(0),init(0){}
	inline int operator[](const int&x){
		if(t[x]!=tclock)
			t[x]=tclock,re[x]=init;
		return re[x];
	}
	inline void modify(int x,int c){
		t[x]=tclock;
		re[x]=c;
	}
}pa;
int seq[N],id;
int size[N],dis[17][N];
bool ban[N];

inline void solve(int x,int dep){
	int i,j;
	fr=ta=0;
	q[ta++]=x;
	id=0,seq[++id]=x;
	++pa.tclock;
	while(fr^ta){
		i=q[fr++];
		for(j=head[i];j;j=next[j]){
			if(pa[i]!=end[j]&&!ban[end[j]]){
				pa.modify(end[j],i);
				q[ta++]=seq[++id]=end[j];
			}
		}
	}
	int Maxsize,real_Root;
	for(i=id;i>=1;--i){
		size[seq[i]]=1;
		for(j=head[seq[i]];j;j=next[j]){
			if(end[j]!=pa[seq[i]]&&!ban[end[j]])
				size[seq[i]]+=size[end[j]];
		}
	}
	
	if(size[x]==1){
		bel[dep][x]=x;
		Insert(Root[dep][x],1,n,x,0);
		return;
	}
	
	for(i=1;i<=id;++i){
		Maxsize=size[x]-size[seq[i]];
		for(j=head[seq[i]];j;j=next[j]){
			if(end[j]!=pa[seq[i]]&&!ban[end[j]])
				Maxsize=max(Maxsize,size[end[j]]);
		}
		if(Maxsize<=size[x]/2)
			real_Root=seq[i];
	}
	
	fr=ta=0;
	q[ta++]=real_Root;
	++pa.tclock;
	dis[dep][real_Root]=0;
	bel[dep][real_Root]=real_Root;
	Insert(Root[dep][real_Root],1,n,real_Root,0);
	while(fr^ta){
		i=q[fr++];
		for(j=head[i];j;j=next[j]){
			if(end[j]!=pa[i]&&!ban[end[j]]){
				pa.modify(end[j],i);
				dis[dep][end[j]]=dis[dep][i]+len[j];
				bel[dep][end[j]]=real_Root;
				Insert(Root[dep][real_Root],1,n,end[j],dis[dep][end[j]]);
				q[ta++]=end[j];
			}
		}
	}
	
	ban[real_Root]=1;
	for(j=head[real_Root];j;j=next[j])
		if(!ban[end[j]])
			solve(end[j],dep+1);
}

int main(){
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	
	scanf("%d",&n);
	register int i;
	int a,b,c;
	for(i=1;i<n;++i)
		scanf("%d%d%d",&a,&b,&c),make(a,b,c);
	
	solve(1,0);
	
	int q;
	scanf("%d",&q);
	int l,r,x,re;
	while(q--){
		scanf("%d%d%d",&l,&r,&x);
		re=INF;
		for(i=0;i<17;++i){
			if(bel[i][x])
				re=min(re,dis[i][x]+Query(Root[i][bel[i][x]],1,n,l,r));
		}
		printf("%d\n",re);
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}