7.17 模拟赛

, , ,

7.17 模拟赛

T1. Tree

Description

给你一棵 $n$ 个节点的树, 每次询问包含第 $i$ 条边的树上最长路径长度。

$n\le 10^6$

1s 512MB

Solution

对于每个点，求从自己出发子树内的最长路径和子树外的最长路径。就是这个点和这个点父亲相连的边最长路径。

换根 dp。复杂度 $O(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
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 1000005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int n;
struct ed{
	int x,y;
}e[maxn];
vector<int>to[maxn];
int f[maxn],g[maxn],ff[maxn];
inline void dfs1(int x,int pre) {
	f[x]=0;
	for (auto y:to[x]) if (y^pre) {
		dfs1(y,x);
		if (f[x]<=f[y]+1) ff[x]=f[x],f[x]=f[y]+1;
		else if (ff[x]<f[y]+1) ff[x]=f[y]+1;
	}
}
inline void dfs2(int x,int pre) {
	for (auto y:to[x]) if (y^pre) {
		if (f[y]==f[x]-1) g[y]=max(g[x]+1,ff[x]+1);
		else g[y]=max(g[x]+1,f[x]+1);
		dfs2(y,x);
	}
}
signed main(void){
  	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	int i;
	read(n);
	for (i=1;i<n;i++) read(e[i].x),read(e[i].y),to[e[i].x].push_back(e[i].y),to[e[i].y].push_back(e[i].x);
	dfs1(1,0);
	g[1]=0;
	dfs2(1,0);
	for (i=1;i<n;i++) {
		if (f[e[i].x]>f[e[i].y]) swap(e[i].x,e[i].y);
		printf("%d\n",f[e[i].x]+g[e[i].x]);
	}
	return 0;
}

T2. path

Description

给出一个 $n$ 个点，$m$ 条边的无向图。接下来 $Q$ 次询问，每次从图中删掉一个点 $A$ 后，请问此时点 $B$ 到点 $C$ 的最短路长度。每次询问独立。

$n\le 200,m\le n^2,q\le 10^5$

0.3s 512MB

Solution

首先，Floyd 最外层的 $k$ 只需要是 $n$ 的排列即可。Floyd 加入一个点的复杂度是 $O(n^2)$ 的。

考虑分治（类似于线段树分治）。复杂度 $O(n^3\log n)$ ，每层记录一个数组，空间复杂度 $O(n^2\log 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
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 205
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int a[maxn][maxn],n,m,q;
struct node{
	int id,x,y;
	node(int a=0,int b=0,int c=0) {id=a;x=b;y=c;}
};
vector<node>O[maxn];
int f[19][maxn][maxn],Ans[100005];
inline void solve(int L,int R,int deep) {
	int mid=L+R>>1,i,j,k;
	if (L==R) {
 		memcpy(f[deep],f[deep-1],sizeof(f[deep]));
		for (auto tmp:O[L]) {
			Ans[tmp.id]=f[deep][tmp.x][tmp.y];
		}
		return; 
	}
 	memcpy(f[deep],f[deep-1],sizeof(f[deep]));
	for (k=mid+1;k<=R;k++) {
		for (i=1;i<=n;i++)
			for (j=1;j<=n;j++)
				f[deep][i][j]=min(f[deep][i][j],f[deep][i][k]+f[deep][k][j]);
	}
	solve(L,mid,deep+1);
	
 	memcpy(f[deep],f[deep-1],sizeof(f[deep]));
	for (k=L;k<=mid;k++) {
		for (i=1;i<=n;i++)
			for (j=1;j<=n;j++)
				f[deep][i][j]=min(f[deep][i][j],f[deep][i][k]+f[deep][k][j]);
	}
	solve(mid+1,R,deep+1);
}
signed main(void){
	freopen("path.in","r",stdin);
	freopen("path.out","w",stdout);
	int i,j,k,x,y,z;
	memset(a,0x3f,sizeof(a));
	memset(f,0x3f,sizeof(f));
	read(n);read(m);read(q);
	for (i=1;i<=m;i++) {
		read(x);read(y);read(z); 
		a[x][y]=min(a[x][y],z);
		a[y][x]=min(a[y][x],z); 
	}
	for (i=1;i<=n;i++) a[i][i]=0;
	for (i=1;i<=q;i++) {
		read(x),read(y),read(z);
		O[x].push_back(node(i,y,z));
	}
	memcpy(f[0],a,sizeof(f[0]));
	solve(1,n,1);
	for (i=1;i<=q;i++) printf("%d\n",Ans[i]>=1e9?-1:Ans[i]);
	return 0;
}

T3. dove

Description

有 $n$ 个互不相同的位置 $p_i$，初始每个位置有值 $w_i$ ，有两个操作：

  • 给 $[l,r]$ 的每个位置加上 $c$
  • 给定 $l,r$ ，如果 $l<r$ ，则把 $l$ 移到 $r$ 的位置，$[l+1,r]$ 向前移一个位置。反之，把 $r$ 移到 $l$ 的位置，$[l,r-1]$ 向后移一个位置。

每次操作结束，求带权中位数的位置（权值是每个点的值）。

$n\le 10^5$

1s 512MB

Solution

平衡树维护即可。

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
//原题中毒瘤zj卡了一个爆long long的点。所以 sum 用 int128 存一下。
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 100005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
struct yyy{
    __int128 sum;
	int ls,rs,siz,rnd,lazy,val;
}a[maxn];
int root,cnt;
mt19937 rnd(time(0));
inline int clone(int val) {
	++cnt;
	a[cnt].ls=a[cnt].rs=0;a[cnt].rnd=rnd();
	a[cnt].siz=1;a[cnt].lazy=0;
	a[cnt].val=a[cnt].sum=val;
	return cnt;
} 
inline void pushup(int k) {
	a[k].sum=a[a[k].ls].sum+a[a[k].rs].sum+a[k].val;
	a[k].siz=a[a[k].ls].siz+a[a[k].rs].siz+1;
}
inline void cover(int x,int k) {
	a[x].lazy+=k;
	a[x].sum+=k*a[x].siz;
	a[x].val+=k; 
}
inline void pushdown(int k) {
	if (a[k].lazy) {
		if (a[k].ls) cover(a[k].ls,a[k].lazy);
		if (a[k].rs) cover(a[k].rs,a[k].lazy);
		a[k].lazy=0;
	}
}
inline void split(int k,int x,int &tmp1,int &tmp2) {
	if (!k) return tmp1=tmp2=0,void();
	pushdown(k);
	if (a[a[k].ls].siz+1<x) {
		split(a[k].rs,x-a[a[k].ls].siz-1,a[k].rs,tmp2);
		pushup(k);tmp1=k;
	}
	else {
		split(a[k].ls,x,tmp1,a[k].ls);
		pushup(k);tmp2=k;
	}
}
inline int merge(int x,int y) {
	if (!x||!y) return x+y;
	if (a[x].rnd<a[y].rnd) {
		pushdown(x);
		a[x].rs=merge(a[x].rs,y);
		pushup(x);return x;
	}
	else {
		pushdown(y);
		a[y].ls=merge(x,a[y].ls);
		pushup(y);return y;
	}
}
inline int query(int k) {
	int x=(a[k].sum+1)/2,sum=0;
	while (k) {
		pushdown(k);
		if (x<=a[a[k].ls].sum) k=a[k].ls;
		else if (x<=a[a[k].ls].sum+a[k].val) return sum+1+a[a[k].ls].siz;
		else x=x-a[a[k].ls].sum-a[k].val,sum+=a[a[k].ls].siz+1,k=a[k].rs; 
	}
	return 0;
}
int n,m;
int p[maxn],w[maxn];
inline void print(int k) {
	if (!k) return ;
	pushdown(k);
	assert(a[k].sum==a[a[k].ls].sum+a[a[k].rs].sum+a[k].val);
	print(a[k].ls);
	printf("%lld ",a[k].val);
	print(a[k].rs);
}
signed main(void){
	freopen("dove.in","r",stdin);
	freopen("dove.out","w",stdout);
	char ch;int l,r,s,i,sum=0;
	int tmp1,tmp2,tmp3,tmp4;
	read(n);read(m);
	for (i=1;i<=n;i++) read(w[i]),root=merge(root,clone(w[i])),sum+=w[i];
	for (i=1;i<=n;i++) read(p[i]);
	printf("%lld\n",p[query(root)]);
	while (m--) {
		ch=getchar();while (ch!='A'&&ch!='B') ch=getchar();
		if (ch=='A') {
			read(l);read(r);read(s);
			split(root,l,tmp1,tmp2);
			split(tmp2,r-l+2,tmp2,tmp3);
			cover(tmp2,s);
			root=merge(tmp1,merge(tmp2,tmp3));
		}
		else {
			read(l);read(r);
			if (l<r) {
				split(root,l,tmp1,tmp2);
				split(tmp2,2,tmp2,tmp3);
				split(tmp3,r-l+1,tmp3,tmp4);
				root=merge(merge(tmp1,tmp3),merge(tmp2,tmp4));
			}
			else {
				swap(l,r);
				split(root,l,tmp1,tmp2);
				split(tmp2,r-l+1,tmp2,tmp3);
				split(tmp3,2,tmp3,tmp4);
				root=merge(merge(tmp1,tmp3),merge(tmp2,tmp4));
			}
		}
		printf("%lld\n",p[query(root)]);
	}
	return 0;
}

T4. music

今天 T4 好像是错题，就不放了。