题目限制一览

题目 时间限制 内存限制
抓蛇 Snake $1000$ MS $256$ MB
分组行走 Walk $1000$ MS $512$ MB
谈笑风生 Talk $2000$ MS $512$ MB

Problem#1. 抓蛇 Snake

Description

传说，数千年前圣帕特里克消灭了哞尔兰所有的蛇。然而，蛇们现在卷土重来了！圣帕特里克节是在每年的3月17日，所以小明要用彻底清除哞尔兰所有的蛇来纪念圣帕特里克。小明装备了一个捕网，用来捕捉N组排成一行的蛇（1≤N≤400）。小明必须按照这些组在这一行中出现的顺序捕捉每一组的所有蛇。每当小明抓完一组蛇之后，她就会将蛇放在笼子里，然后带着空的捕网开始捕捉下一组。

一个大小为s的捕网意味着小明可以抓住任意包含g条的一组蛇，其中g≤s。然而，每当小明用大小为s的捕网抓住了一组g条蛇，就意味着浪费了s−g的空间。小明可以任意设定捕网的初始大小，并且她可以改变K次捕网大小（1≤K<N）。

请告诉小明她捕捉完所有组的蛇之后可以达到的总浪费空间的最小值。

Input

输入的第一行包含N和K。第二行包含N个整数a1,…,aN，其中ai（0≤ai≤10^6）为第i组蛇的数量。

Output

输出一个整数，为小明抓住所有蛇的总浪费空间的最小值。

Sample Input

1
2
6 2
7 9 8 2 3 2

Sample Output

1
3

Hint

小明可以设置她的捕网开始时大小为7。当她抓完第一组蛇之后，她将她的捕网的大小调整为9，保持这个大小直到抓完第4组蛇，再将捕网大小调整为3。总浪费空间为 (7−7)+(9−9)+(9−8)+(3−2)+(3−3)+(3−2)=3。

分析

做法一：DP，空间二维 + $O(n^3)$ 时间复杂度

设 $f[i][j]$ 表示抓到第 $i$ 组蛇，并且改变了 $j$ 次网的大小的最小的浪费空间，则转移方程为：

$f[i][j]=min(f[i][j],\;f[k][j-1]+r[k+1][i])$

其中 $k$ 是枚举的中转点，$r[k+1][j]$ 表示 $[k+1,\;j]$ 这段区间内剩余空间的最小值，$r[k+1][j]$ 可以用这段区间内的最大元素 $max[k+1][j]$ 减去每个元素累加得到，进一步化简就是：

$r[k+1][j]=max[k+1][j]\times(j-(k+1)+1)-sum[k+1][j]$ ，其中 $sum[k+1][j]$ 为区间和

由于 $max[i][j]$，$sum[i][j]$，$r[i][j]$ 都可以通过预处理得到，所以它们的时间复杂度可以忽略不计

做法二：DP，空间三维 + $O(n^3)$ 时间复杂度 + 滚动优化

设 $f[i][j][k]$ 表示表示抓到第 $i$ 组蛇，并且改变了 $j$ 次网的大小，现在的网的大小为 $a[k]$ 的最小浪费，则转移方程为：

$f[i][j][k]=min(f[i][j][k]，f[i-1][j-1][k’])+a[k]-a[i]\quad(k’\in[1，n]，a[k]\geq a[i])$

这种方法是考试的时候写的，很容易想到的一个思路，虽然小明每次改变网大小的时候可以任意，但是直接改变成某一组蛇的数量显然是最明智的选择

算法看上去像是 $O(n^4)$ 的时间复杂度，然而注意到 $f[i-1][j-1][k]$ 一遍for 循环算完之后不会再算了，于是我用了一个 $f[i][j][0]$ 存储 $min{f[i][j][k]，k\in[1，n]}$ 好像就能把时间提升到 $O(n^3)$ 的水平（相当于预处理吧）

最后加一个滚动优化就能 2MB 过了（原题的空间限制为 $128$ MB，不是 $256$ MB）

Codes

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
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define maxn 401
using namespace std;
template<typename t>inline void fcin(t &x){
	int sign=1; x=0; char op=getchar();
	while(op<'0'||op>'9'){if(op=='-') sign=-1;op=getchar();}
	while(op>='0'&&op<='9'){x=x*10+(op-48);op=getchar();}
	x*=sign;
}
int f[2][maxn][maxn];
int a[maxn],n,k;
int main(){
	#ifndef ONLINE_JUDGE
	freopen("snake.in","r",stdin);
	freopen("snake.out","w",stdout);
	#endif
	fcin(n);fcin(k);
	memset(f,127,sizeof(f));
	for(int i=1;i<=n;i++)
		fcin(a[i]);
	for(int i=1;i<=n;i++){
		if(a[i]>=a[1]) f[1][0][i]=a[i]-a[1];
		f[1][0][0]=min(f[1][0][0],f[1][0][i]);
	}
	for(int i=2;i<=n;i++){
		memset(f[i&1],127,sizeof(f[i&1]));
		for(int j=0;j<=k;j++)
		for(int p=1;p<=n;p++){
			if(a[p]<a[i]) continue;
			f[i&1][j][p]=min(f[i&1][j][p],f[(i-1)&1][j][p]+a[p]-a[i]);
			if(j>=1) f[i&1][j][p]=min(f[i&1][j][p],f[(i-1)&1][j-1][0]+a[p]-a[i]);
			f[i&1][j][0]=min(f[i&1][j][0],f[i&1][j][p]);
		}
	}
	printf("%d",f[n&1][k][0]);
	return 0;
}

Problem#2. 分组行走 walk

Description

小明喜欢养宠物，想要将编号为1…N的N只宠物（N≤7500）分为非空的K组（2≤K≤N），使得任意两只来自不同组的宠物都需要走一定的距离才能相遇。宠物x和宠物y（其中1≤x<y≤N）愿意为了见面走 (2019201913x+2019201949y) mod 2019201997英里。给定一个将N只宠物分为K个非空小组的分组方案，令M为任意两头来自不同组的宠物愿意为了见面行走的英里数的最小值。为了测试宠物们相互之间的忠诚度，小明想要将N头宠物以最佳的方式分为K组，使得M尽可能大。

Input

输入仅有一行，包含N和K，用空格分隔。

Output

输出最优的M。

Sample Input

1
3 2

Sample Output

1
2019201769

Hint

在这个例子中，宠物1和宠物2愿意为了见面走2019201817英里。宠物2和宠物3愿意走2019201685英里。宠物1和宠物3愿意走2019201769英里。所以，将宠物1单独分为一组，宠物2和宠物3分为一组，M=min(2019201817,2019201769)=2019201769（这是我们在这个问题中能够达到的最佳结果）。

分析

常规思路 #1. 最小生成树

考虑将每一对宠物 $(x，y)(x<y)$ 的距离计算出来并算成一条无向边，那么划分出 K 个集合之后，原本连通的图会出现 K 个连通支，那么问题就转化为：找到一个最小的 $d{min}$，使得去掉权值大于$d{min}$ 的边之后，原图被分为 K 个连通支

那么此题的思路就和北极通讯网络 一模一样了，注意到 $N\leq7500$，意味着加入的边数为 $N\times (N-1)$ 会达到一个巨大的数量级，此时进行 Kruskal 的排序操作会消耗很多时间，所以求最小生成树的时候可以采用 Prim 算法

进阶思路 #2. 贪心（By LTX）

设 $f(x)=min{dist(i,x)，i\in [1，n]，i\neq x}$，即为 $x$ 与其他宠物之间的最短距离

同上述最小生成树的思想有着相似之处，答案为第 $n-k+1$ 大的 $f(x)$ 值

进阶思路 #3. 找规律

设 $P=2019201997$，则 $d(x,y)=((P-84)x+(P-48)y)\mod P$

化简：$((P-84)x+(P-48)y)\mod P \Leftrightarrow ((-84x-48y)\mod P+P)\mod P$

由于$x<y\leq7500$ ，所以认为 $(-84x-48y)\mod P=-84x-48y+P$

则原式：$D=-84x-48y+P$，可以发现，要使 $D$ 尽量大，就是让 $x$ 尽量小，由于选出了非空 $K$ 组，把 $1\to K-1$ 的每个元素独自成组，然后 $K\to N$ 的元素分成一组

那么答案就是 $D=-84x-48y+P$ ，时间复杂度仅仅 $O(1)$

Codes

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
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define maxn 7502
#define maxm maxn*(maxn-1)
using namespace std;
typedef long long ll;
template<typename t>inline void fcin(t &x){
	int sign=1; x=0; char op=getchar();
	while(op<'0'||op>'9'){if(op=='-') sign=-1;op=getchar();}
	while(op>='0'&&op<='9'){x=x*10+(op-48);op=getchar();}
	x*=sign;
}
int n,k;
inline ll pets(int x,int y){
	return ((ll)2019201913*x+(ll)2019201949*y)%2019201997;
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("walk.in","r",stdin);
	freopen("walk.out","w",stdout);
	#endif
	fcin(n);fcin(k);
	printf("%lld",pets(k-1,n));
	return 0;
}

Problem#3. 谈笑风生 talk

Description

设 T 为一棵有根树，我们做如下的定义：

• 设 a 和 b 为 T 中的两个不同节点。如果 a 是 b 的祖先，那么称“a 比 b 不知道高明到哪里去了”。

• 设 a 和 b 为 T 中的两个不同节点。如果 a 与 b 在树上的距离不超过某个给定常数 x，那么称“a 与 b 谈笑风生”。

给定一棵 n 个节点的有根树 T，节点的编号为 1 ∼ n，根节点为 1 号节点。你需要回答 q 个询问，询问给定两个整数 p 和 k，问有多少个有序三元组 (a; b; c) 满足：

  1. a、 b 和 c 为 T 中三个不同的点，且 a 为 p 号节点；
  2. a 和 b 都比 c 不知道高明到哪里去了；
  3. a 和 b 谈笑风生。这里谈笑风生中的常数为给定的 k。

Input

输入文件的第一行含有两个正整数 n 和 q，分别代表有根树的点数与询问的个数。

接下来 n − 1 行，每行描述一条树上的边。每行含有两个整数 u 和 v，代表在节点 u 和 v 之间有一条边。

接下来 q 行，每行描述一个操作。第 i 行含有两个整数，分别表示第 i 个询问的 p 和 k。

Output

输出 q 行，每行对应一个询问，代表询问的答案。

Sample Input

1
2
3
4
5
6
7
8
5 3
1 2
1 3
2 4
4 5
2 2
4 1
2 3

Sample Output

1
2
3
3
1
3

Hint

样例中的树如下图所示：

pic

对于第一个和第三个询问，合法的三元组有 (2,1,4)、 (2,1,5) 和 (2,4,5)。

对于第二个询问，合法的三元组只有 (4,2,5)。

所有测试点的数据规模如下：

pic2

分析

显然如果b在a上面可以直接算

考虑在a子树中的情况

由于要求的答案是一个深度连续的区间,考虑以深度为下标建主席树

将每个点的贡献size[i]-1依次插入主席树

直接查一个点子树就可以了

Codes

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
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define maxn (300001*10)
#define maxm (maxn*2)
using namespace std;
typedef long long ll;
template<typename t>inline void fcin(t &x){
	int sign=1; x=0; char op=getchar();
	while(op<'0'||op>'9'){if(op=='-') sign=-1;op=getchar();}
	while(op>='0'&&op<='9'){x=x*10+(op-48);op=getchar();}
	x*=sign;
}
int newp,root[maxn];
struct TT{
	struct TTNode{
		int LC,RC; ll VAL;
		#define lc(x) T[x].LC
		#define rc(x) T[x].RC
		#define val(x) T[x].VAL
		#define mid ((L+R)>>1) 
	}T[maxn<<1];
	inline void init(int &x,int y,int L,int R,int pos,int d){
		x=++newp;val(x)=val(y)+d;
		if(L==R) return;
		lc(x)=lc(y);rc(x)=rc(y);
		if(pos<=mid) init(lc(x),lc(y),L,mid,pos,d);
		else init(rc(x),rc(y),mid+1,R,pos,d);
	}
	ll res(int k,int L,int R,int x,int y){
		if(!k) return 0; y=(y>R)?R:y;
		if(x==L && y==R) return val(k);
		if(y<=mid) return res(lc(k),L,mid,x,y);
		else if(x>mid) return res(rc(k),mid+1,R,x,y);
		else return res(lc(k),L,mid,x,mid)+res(rc(k),mid+1,R,mid+1,y);
	}
}st;int ref[maxn],dep[maxn],siz[maxn];
int to[maxm],nxt[maxm],head[maxn];
int tot,n,s,dfn,ld[maxn],rd[maxn];
inline void Eadd(int u,int v){
	to[++tot]=v;nxt[tot]=head[u];
	head[u]=tot;
}
void dfs(int u,int fu){
	ld[u]=++dfn;ref[dfn]=u;
	for(int i=head[u];i;i=nxt[i])
		if(to[i]!=fu){
			dep[to[i]]=dep[u]+1;
			dfs(to[i],u);siz[u]+=siz[to[i]]+1;
		}
	rd[u]=dfn;
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("talk.in","r",stdin);
	freopen("talk.out","w",stdout);
	#endif
	fcin(n);fcin(s);int x,y;
	for(int i=1;i<n;i++){
		fcin(x);fcin(y);
		Eadd(x,y);Eadd(y,x);
	} dfs(1,0); ll ans=0;
	for(int i=1;i<=n;i++) dep[0]=max(dep[0],dep[i]);
	for(int i=1;i<=n;i++)
		st.init(root[i],root[i-1],0,dep[0],dep[ref[i]],siz[ref[i]]);
	while(s--){
		fcin(x);fcin(y);ans=0;
		ans+=(ll)siz[x]*min(dep[x],y);
		ans+=st.res(root[rd[x]],0,dep[0],dep[x]+1,dep[x]+y);
		ans-=st.res(root[ld[x]-1],0,dep[0],dep[x]+1,dep[x]+y);
		printf("%lld\n",ans);
	}
	return 0;
}