test20191102

发表于

闲扯

考试想到了分段写，但是懒。。。

$T1$

Solution

显然，我们可以观察出这样一个性质：每次充电一定充满。

由这一点，我们可以得出每条路的停止次数为 $\lceil\frac{dis}{w}\rceil$ 。

我们观察到，对于电量为 $w$ 的车，我们走 $dis\in[k\cdot w+1,(k+1)\cdot w]$ 的路，答案都是 $k+1$ 。

所以我们可以枚举这一个 $k$ ，然后计算在 $[k\cdot w+1,(k+1)\cdot w]$ 这个范围内的路径的个数，就可以得到最终的答案。

对于每一个 $w$ ，我们的时间复杂度是 $O(\log^2n\cdot \lceil\frac{L}{w}\rceil)$ ，其中 $L$ 表示路径长度的最大值。

对于 $w$ 较大时，我们这个方法的复杂度是比较优秀的，但是 $w$ 较小的时候，就变得十分的弱智，甚至不如直接暴力。

所以我们对 $w$ 较小的用线段树维护一下，较大的再用这种方法查询即可。

其中这个界限大概设到 $\sqrt{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
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define re register
#define ri re int
#define rl re ll
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define mid ((l+r)>>1)
#define INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
using namespace std;
template<class T>il read(T &x){
	x=0;int f=1;char k=getchar();
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=x*10+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x>9) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
const int MAXN = 1e5+5;
int n,m,u,v,d,val[MAXN],head[MAXN],num_edge,mx;
it min(int x,int y){return x<y?x:y;}
it max(int x,int y){return x>y?x:y;}
struct Edge{
	int next,to,dis;
	Edge(){}
	Edge(int next,int to,int dis):next(next),to(to),dis(dis){}
}edge[MAXN<<1];
il add_edge(int u,int v,int dis){
	edge[++num_edge]=Edge(head[u],v,dis),head[u]=num_edge;
	edge[++num_edge]=Edge(head[v],u,dis),head[v]=num_edge;
}
int f[MAXN],sz[MAXN],son[MAXN],dep[MAXN],top[MAXN],id[MAXN],rk[MAXN],cnt;
il DFS1(int u,int fa){
	f[u]=fa,dep[u]=dep[fa]+1,sz[u]=1;
	for(ri i=head[u];i;i=edge[i].next){
		if(edge[i].to==fa) continue;
		DFS1(edge[i].to,u),sz[u]+=sz[edge[i].to],val[edge[i].to]=edge[i].dis;
		if(sz[edge[i].to]>sz[son[u]]) son[u]=edge[i].to;
	}
}
il DFS2(int u,int t){
	top[u]=t,id[u]=++cnt,rk[cnt]=u;
	if(!son[u]) return ;
	DFS2(son[u],t);
	for(ri i=head[u];i;i=edge[i].next){
		if(edge[i].to==f[u]||edge[i].to==son[u]) continue;
		DFS2(edge[i].to,edge[i].to);
	}
}
int rt[MAXN],lc[MAXN*20],rc[MAXN*20],siz[MAXN*20],tot;
il build(int &cur,int l,int r){
	cur=++tot;
	if(l==r) return ;
	build(lc[cur],l,mid);
	build(rc[cur],mid+1,r);
}
il insert(int &cur,int cmp,int l,int r,int k){
	cur=++tot,lc[cur]=lc[cmp],rc[cur]=rc[cmp],siz[cur]=siz[cmp]+1;
	if(l==r) return ;
	if(mid>=k) insert(lc[cur],lc[cmp],l,mid,k);
	else insert(rc[cur],rc[cmp],mid+1,r,k);
}
it query_num(int l,int r,int L,int R,int k){
	if(r<=k) return siz[R]-siz[L];
	ri res=0;
	res+=query_num(l,mid,lc[L],lc[R],k);
	if(k>mid) res+=query_num(mid+1,r,rc[L],rc[R],k);
	return res;
}
ill query(int l,int r,int dis){
	if(dis>mx) return query_num(0,mx,l,r,mx);
	rl res=0;
	for(ri i=dis,pre=0;;i+=dis){
		if(i<=mx){
			ri tmp=query_num(0,mx,l,r,i);
			res+=1ll*(tmp-pre)*(i/dis);
			pre=tmp;
		}
		else{
			res+=1ll*(query_num(0,mx,l,r,mx)-pre)*(i/dis);
			break;
		}
	}
	return res;
}
ill query_path(int u,int v,int dis){
	rl res=0;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		res+=query(rt[id[top[u]]-1],rt[id[u]],dis);
		u=f[top[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	res+=query(rt[id[u]],rt[id[v]],dis);
	return res;
}
struct Seg_Tree{
	ll sum[105][MAXN<<2];
	#define lc (cur<<1)
	#define rc (cur<<1|1)
	il pushup(int cur){for(ri i=1;i<=100;++i) sum[i][cur]=sum[i][lc]+sum[i][rc];}
	il build_tree(int cur,int l,int r){
		if(l==r){
			for(ri i=1;i<=100;++i) sum[i][cur]=(val[rk[l]]+i-1)/i;
			return ;
		}
		build_tree(lc,l,mid),build_tree(rc,mid+1,r);
		pushup(cur);
	}
	ill query(int cur,int l,int r,int L,int R,int k){
		if(l>=L&&r<=R) return sum[k][cur];
		rl res=0;
		if(mid>=L) res+=query(lc,l,mid,L,R,k);
		if(R>mid) res+=query(rc,mid+1,r,L,R,k);
		return res;
	}
	il solve(int u,int v,int dis){
		rl res=0;
		while(top[u]!=top[v]){
			if(dep[top[u]]<dep[top[v]]) swap(u,v);
			res+=query(1,1,n,id[top[u]],id[u],dis);
			u=f[top[u]];
		}
		if(dep[u]>dep[v]) swap(u,v);
		res+=query(1,1,n,id[u]+1,id[v],dis);
		print(1+res),puts("");
	}
}T;
int main(){
	freopen("delivery.in","r",stdin);
	freopen("delivery.out","w",stdout);
	read(n),read(m);
	for(ri i=1;i<n;++i) read(u),read(v),read(d),add_edge(u,v,d),mx=max(mx,d);
	DFS1(1,0),DFS2(1,0),build(rt[0],0,mx),T.build_tree(1,1,n);
	for(ri i=1;i<=n;++i) insert(rt[i],rt[i-1],0,mx,val[rk[i]]);
	for(ri i=1;i<=m;++i){
		read(u),read(v),read(d);
		if(d<=100) T.solve(u,v,d);
		else print(1+query_path(u,v,d)),puts("");
	}
	return 0;
}

其实可以不用树剖，改成查询两个点到根结点，再减去 $lca$ 到根结点的，这样就只有一个 $\log$ ，但是没必要。

$T3$

Solution

这道题需要知道一个结论：在一个有序的数列中任选两个数异或起来，最小值一定在相邻两个数的异或中取到。

然后我们就可以像把数组排个序，然后设 $dp_i$ 表示以第 $i$ 个元素作为数列的结尾，合法的子序列的个数。

那么我们有 $dp_{i}=1+\sum_{j=1}^{i-1}dp_j$ ，其中 $j$ 满足 $val_i\ xor\ val_j\geq x$ 。

这样我们就得到了一个 $O(n^2)$ 的转移方程。

考虑优化。

我们只需要将 $dp$ 放在 $Trie$ 树上，然后维护一下子树和即可。

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
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define re register
#define ri re int
#define rl re ll
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define mid ((l+r)>>1)
#define INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
using namespace std;
template<class T>il read(T &x){
	x=0;int f=1;char k=getchar();
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=x*10+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x>9) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
const int MAXN = 3e5+5,mod = 998244353;
it add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
it mul(int x,int y){return 1ll*x*y%mod;}
int n,Trie[MAXN*61][2],f[MAXN*61],ans,cnt=1;
ll val[MAXN],x;
il insert(ll a,ll k){
	ri now=1;
	for(ri i=59;i>=0;--i){
		ri s=(a&(1ll<<i))?1:0;
		if(!Trie[now][s]) Trie[now][s]=++cnt;
		now=Trie[now][s];
		f[now]=add(f[now],k);
	}
}
it query(ll a,ll k){
	ri now=1,res=0;
	for(ri i=59;i>=0;--i){
		ri s=(k&(1ll<<i))?1:0;
		ri p=(a&(1ll<<i))?1:0;
		if(s==1) now=Trie[now][p^1];
		else{//这一位是0，说明我们可以让它为1，使得异或大于x
			res=add(res,f[Trie[now][p^1]]);
			now=Trie[now][p];
		}
		if(!now) return res;
	}
	return add(res,f[now]);
}
int main(){
	freopen("xor.in","r",stdin);
	freopen("xor.out","w",stdout);
	read(n),read(x);
	for(ri i=1;i<=n;++i) read(val[i]);
	sort(val+1,val+1+n);
	for(ri i=1;i<=n;++i){
		ri res=add(query(val[i],x),1);
		insert(val[i],res);
		ans=add(ans,res);
	}
	print(ans);
	return 0;
}