「康复训练」6月12日联考

发表于

NOI2018 前的联考第一场。

奥义商店

Description

乐滋滋经常参加各种拍卖会，前不久，他收到了来自滋滋国最大的商店——奥义商店的拍卖会邀请函。

为了让拍卖会看起来更加奥妙重重，奥义商店设置了一个极为复杂的拍卖规则：一共 nn 个物品排成一排，第 ii 个物品价格是 viv_i 。对于一次拍卖，商店会指定 tt 种颜色，并对每种颜色指定一个数目 cjc_j 满足 ∑j=1tcj=n−1\sum_{j=1}^{t}c_j=n-1 ，另外还会指定一个下标 kk 和一个公差 dd 。

买家需要给第 kk 个物品染上一种颜色（在 tt 种颜色中选择一种）。接着，把剩下的 n−1n-1 个物品随机染成 tt 种颜色之一，并保证这 n−1n-1 个物品中第 jj 种颜色的恰好有 cjc_j 个。

买家需要购买的物品按这样的方式计算：找到 kk 所在的最长的以 dd 为公差的等差数列 ax=kx+d(x∈[L,R],L≤0≤R)a_x=kx+d(x\in [L,R],L\le 0 \le R) 满足其中所有物品都与第 kk 个物品同色。买家需要买下这个等差数列中的所有物品，显然花费就是 ∑x=LRvk+xd\sum_{x=L}^{R}v_{k+xd} 。

乐滋滋最近出现了点“经济危机”，希望你能帮他给第 kk 个物品选择合适的颜色，以此来最小化他花费的期望，你只需要输出这个期望即可。

当然商品的价格是可能出现变动的，你需要维护这些变化。

Constraints

1≤n,m≤1051 \leq n,m \leq 10^5

Solution

对于 t=1t=1 的部分，当 d≤100d \le 100 时通过预处理好的表 O(1)O(1) 查询结果，当 d>100d>100 时直接暴力计算即可。

对于 t>1t>1 的部分，贪心可得一定是选择 cc 最小的颜色。在 k+idk+id 的序列里，对于 i>0i>0 的部分， i=1i=1 时同颜色概率为 cn−1\frac{c}{n-1} ， i=2i=2 时概率为 cn−1⋅c−1n−2\frac{c}{n-1}\cdot \frac{c-1}{n-2} ，由此递推， i<0i<0 的部分同理。且由于 t!=1t!=1 且 cc 最小，所以当递推到后面的部分时，概率已经小到几乎可以忽略不计。为保证复杂度可以舍弃掉后面的部分，这里我选择了 500500 。

详见代码。

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
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=1e5+5;
int n,m,op,x,y,t,k,d;
int v[N],c[N];
double s[101][101];
int read()
{
	int x=0,f=1;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();}
	return x*f;
}
void work1()
{
	if(d<=100){printf("%.6lf\n",s[d][k%d]);return;}
	double ans=v[k];
	for(int i=k+d;i<=n;i+=d)ans+=v[i];
	for(int i=k-d;i>=1;i-=d)ans+=v[i];
	printf("%.6lf\n",ans);
}
void work2()
{
	int mn=c[1];
	for(int i=2;i<=t;i++)mn=min(mn,c[i]);
	double ans=v[k],base=1;
	for(int i=1;i<=500&&k+i*d<=n;i++)
	{
		base=1.0*base*(mn-i+1)/(n-i);
		ans+=1ll*v[k+i*d]*base;
	}
	base=1;
	for(int i=1;i<=500&&k-i*d>=1;i++)
	{
		base=1.0*base*(mn-i+1)/(n-i);
		ans+=1ll*v[k-i*d]*base;
	}
	printf("%.6lf\n",ans);
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)
	{
		v[i]=read();
		for(int j=1;j<=100;j++)
			s[j][i%j]+=v[i];
	}
	while(m--)
	{
		op=read();
		if(op==1)
		{
			x=read();y=read();
			for(int j=1;j<=100;j++)
				s[j][x%j]+=(y-v[x]);
			v[x]=y;
		}
		else
		{
			t=read();k=read();d=read();
			for(int i=1;i<=t;i++)c[i]=read();
			if(t==1)work1();
			else work2();
		}
	}
	return 0;
}

访问计划

Description

前不久，滋滋国来了一位白尛 FA 师，在滋滋国到处谈笑风生，滋滋国国王妹滋滋认为这个人姿势水平很高，便向他请教提高姿势水平的办法，白尛 FA 师说“滋滋国的哪一条路我没去过！”妹滋滋心想自己还没有好好考察过滋滋国的每一条道路呢，便计划进行一次访问来提高自己的姿势水平。

滋滋国有 NN 个城市，编号从 00 到 N−1N-1 ，其中 00 号城市是首都，这些城市被 N−1N-1 条道路连成一棵树，每个道路都有一个通过的花费，这个花费是每次通过时都需要付出的。

现在妹滋滋想要从首都出发，沿着道路行走，经过每条道路至少一次，并最终返回首都，除了沿着道路行走之外，妹滋滋还可以花费 CC 元乘坐跳蚤巴士从一个城市直接跳到任意一个城市，然而因为各种奥妙重重的原因，妹滋滋最多只能搭乘 KK 次跳蚤巴士。

现在妹滋滋找到了你，希望你为他安排一个最优的访问路径使得总花费最少，你只需要输出最小总花费即可。

Constraints

$ 1 \leq N,K \leq 2000$

Solution

由题意易得，若不使用跳跃，则每条边需要经过两次。若使用跳跃从 uu 跳跃到 vv ，则 uu 到 vv 路径上的边都可以少走一次。但由于每条边至少经过一次，所以问题可以转化为：求不超过 kk 条边不相交的链的最大权值和。

令 f(x,k,0/1)f(x,k,0/1) 表示点 xx 的子树里，已使用了 kk 条链， xx 在/不在链上的最小代价。分类讨论一下做树上背包即可。注意 kk 只需枚举到子树大小，维持复杂度为 O(n2)O(n^2) 。

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
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=2e3+5;
const int inf=0x3f3f3f3f;
int n,K,C,cnt,u,v,w,base,border;
int sz[N],first[N],f[N][N][2],g[N][2];
struct edge{int to,next,w;}e[N*2];
int read()
{
	int x=0,f=1;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();}
	return x*f;
}
void ins(int u,int v,int w){e[++cnt]=(edge){v,first[u],w};first[u]=cnt;}
void init()
{
	cnt=0;
	memset(f,0x3f,sizeof(f));
	memset(first,0,sizeof(first));
}
void Min(int& a,int b){if(b<a)a=b;}
void dfs(int x,int fa,int edg)
{
	bool isleaf=true;sz[x]=1;
	for(int i=first[x];i;i=e[i].next)
	{
		int to=e[i].to;
		if(to==fa)continue;
		dfs(to,x,e[i].w);
		sz[x]+=sz[to];
		if(isleaf)
			for(int k=0;k<=sz[to];k++)
			{
				Min(f[x][k][0],f[to][k][0]);
				Min(f[x][k][1],f[to][k][1]);
				if(k+1<=K)Min(f[x][k+1][0],f[to][k][1]);
			}
		else
		{
			memset(g,0x3f,sizeof(g));
			for(int xk=0;xk<=sz[x];xk++)
			{
				if(f[x][xk][0]!=inf)
				{
					base=f[x][xk][0];
					border=min(K-xk,sz[to]);
					for(int tk=0;tk<=border;tk++)
					{
						Min(g[xk+tk][0],base+f[to][tk][0]);
						Min(g[xk+tk][1],base+f[to][tk][1]);
						if(xk+tk+1<=K)Min(g[xk+tk+1][0],base+f[to][tk][1]);
					}
				}
				if(f[x][xk][1]!=inf)
				{
					base=f[x][xk][1];
					border=min(K-xk,sz[to]);
					for(int tk=0;tk<=border;tk++)
					{
						Min(g[xk+tk][1],base+f[to][tk][0]);
						if(xk+tk+1<=K)Min(g[xk+tk+1][0],base+f[to][tk][1]-C);
						if(xk+tk+1<=K)Min(g[xk+tk+1][1],base+f[to][tk][1]);
					}
				}
			}
			for(int k=0;k<=K;k++)
				for(int j=0;j<=1;j++)
					f[x][k][j]=g[k][j];
		}
		isleaf=false;
	}
	if(isleaf)
	{
		f[x][0][0]=2*edg;
		f[x][0][1]=C+edg;
	}
	else
	{
		for(int k=0;k<=K;k++)
			Min(f[x][k][1],f[x][k][0]+C);
		for(int k=0;k<=K;k++)
			for(int j=0;j<=1;j++)
				f[x][k][j]+=(2-j)*edg,Min(f[x][k][j],inf);
	}
}
int main()
{
	while(scanf("%d",&n)==1)
	{
		K=read();C=read();init();
		for(int i=1;i<n;i++)
		{
			u=read()+1;v=read()+1;w=read();
			ins(u,v,w);ins(v,u,w);
		}
		dfs(1,-1,0);
		int ans=inf;
		for(int k=0;k<=K;k++)
			Min(ans,f[1][k][0]);
		printf("%d\n",ans);
	}
	return 0;
}