【题解】Educational Codeforces Round 146（CF1814）-526互联

而且怎么感觉 E,F 比 D 要简单很多，大概是因为比较套路吧[惊恐]

A.Coins

题目描述：

本题一共有 $t$ 组数据。

每组数据包含两个整数 $n$ 和 $k$，如果存在两个非负整数 $x,y$，满足 $2\times x+k\times y=n$，输出 YES，否则输出 NO（yes,Yes,NO,nO 均可）。

题目分析：

注意到 $y$ 可能的取值只有 $0,1$，因为如果 $y \ge 2$ 那么必然有 $y = (2p + y')$，所以可以直接用 $2x$ 表示出前面的贡献。

B.Long Legs

题目描述：

给你一个无限大小的棋盘，一个机器人初始位置为 $(0,0)$，初始每次可移动的长度为 $1$。

对于一个当前在 $(x,y)$ 的机器人，且它当前的可移动长度为 $m$（初始为 $1$)。则它可以耗费 $1$ 个时间进行如下操作之一：

移动到 $(x+m,y)$
移动到 $(x,y+m)$
使得 $m=m+1$

注意：在当前位置使得 $m=m+1$ 后会影响后面的操作。

现在给你两个正整数 $a,b(1 \leq a,b \leq 10^9)$，问机器人最少需要多少单位时间可以到达 $(a,b)$。

题目分析：

最优的方案肯定先用操作 $3$ 将 $m$ 变成某个数然后一直用操作 $1$ 和操作 $2$。

因为考虑如果我们在改变 $m$ 的过程中使用了操作 $1$ 和操作 $2$ 显然不如留到最后用产生的贡献多，而他们需要的时间是一样的。

当然如果 $m$ 最后大于我们要到达的位置肯定就是在中间用 $1$ 次操作过去然后就不管了，但是这其实没什么影响。

所以可以直接枚举 $m$ 变成多少，然后答案就是 $\lceil \frac{a}{m} \rceil + \lceil \frac{b}{m} \rceil$，因为 $m$ 特别大的时候答案一定不优，所以大概枚举到 $10^5 \sim 10^6$ 就差不多了。

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9+5;
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int T;scanf("%d",&T);
	while(T--){
		int x,y;scanf("%d%d",&x,&y);
		int ans = INF;
		for(int i=1; i<=1000000; i++){
			ans = min(ans,(x + i - 1) / i + (y + i - 1) / i + (i-1));
		}
		printf("%d\n",ans);
	}
	return 0;
}

C.Search in Parallel

题目描述：

要求构造两个序列 $a,b$ 使得两个序列的长度之和为 $n$。

对于查询 $i$ 所需要的时间定义为：

有两个机器人，同时从 $a,b$ 的第一个数开始取，每一次 $a$ 拿出的数会花费 $s_1$ 的时间扫描，$b$ 拿出的数会花费 $s_2$ 的时间扫描，两个机器人同时行动互相独立，不存在

等待另一个机器人一起拿下一个数的情况，当某一个机器人扫描完成之后发现这个数为 $i$ 则从这个时刻停止机器人的所有操作，并且将这段时间定义为需要的时间。

我们会对 $i\in [1,n]$ 查询 $a_i$ 次，要求构造的序列满足查询的总时间最小。

题目分析：

一个显然的想法就是查询次数越多的越放到前面，这样就只需要判断将当前数插入哪个序列造成的贡献更小就放入哪个序列就可以了。
设序列中有 $cnt$ 个数，则查询这个数的时间就是 $(cnt+1) \times s$。

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+5;
int cnt[N],p[N];
vector<int> v1,v2;
bool cmp(int a,int b){
	return cnt[a] > cnt[b];
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int T;scanf("%d",&T);
	while(T--){
		int n,s1,s2;scanf("%d%d%d",&n,&s1,&s2);
		for(int i=1; i<=n; i++){
			scanf("%d",&cnt[i]);
		}
		for(int i=1; i<=n; i++)	p[i] = i;
		sort(p+1,p+n+1,cmp);
		
		for(int i=1; i<=n; i++){
			if(s1 * (int)(v1.size() + 1) > s2 * ((int)v2.size() + 1))	
				v2.push_back(p[i]);
			else	v1.push_back(p[i]);
		}
		
		printf("%d ",(int)v1.size());
		for(auto x : v1)	printf("%d ",x);
		printf("\n");
		printf("%d ",(int)v2.size());
		for(auto x : v2)	printf("%d ",x);
		printf("\n");
		
		v1.clear(),v2.clear();
		for(int i=1; i<=n; i++)	cnt[i] = 0;
	}
	return 0;
}

D.Balancing Weapons

题目描述：

有 $n$ 把枪，第 $i$ 把枪的攻击力是 $p_i = f_i \cdot d_i$。你需要调整 $d_i$ 使得 $ \max\limits_{1 \le i \le n}{p_i} - \min\limits_{1 \le i \le n}{p_i} \le k $，要保证 $d_i > 0$，求最少调整几把枪的 $d_i$ 可以满足条件。
$n \le 3000，k \le 1500，1 \le f_i \le 2000，1 \le d_i \le 10^9$

题目分析：

我们肯定是让最大值变小或者让最小值变大，也就是会保留排序后的一个区间，使得不在区间内部的数尽可能通过调整靠近这个区间。

所以其实每个数通过调整能得到的有用的数只有 $O(n)$ 个，可以直接将这些数记下来然后双指针扫描区间（双指针是因为有极差不超过 $k$ 的限制），如果当前区间使得所有的数都有某个调整得到的数出现过那么就更新答案。

E.Chain Chips

题目描述：

在一条长度为 $n$ 的链上，有 $1\sim n$ 这 $n$ 个点，第 $i$ 条边连接着第 $i$ 个点到第 $i+1$ 个点，长度是 $w_i$ 。

在一开始，在第 $i$ 个点上都停着一辆车 $i$ 。现在，你需要通过这些道路，移动一些车辆，使得每一辆车都不停在它的初始位置上，同时每个位置最终也仅有一辆车，并且车的移动总距离尽可能小。

接下来会有 $m$ 组询问，每组询问会修改一条边的边权，你需要输出修改后的车的移动的最小距离。修改不独立，车并不会真的移动。

$n,m\leq 2\times 10^5$

题目分析：

看上去比较想贪心，也就是看看每一个边造成的贡献，但是好像不大可能贪。

虽然不能贪心但是我们也可以由此联想到 $dp$，考虑我们一条边肯定最多造成 $2$ 次贡献，也就是让左右的车交换，因为交换多次其实没意义，我们只需要错位即可。

而因为错位是一个必须要管的东西，所以考虑记 $f[i][0/1]$ 表示前 $i$ 个位置第 $i$ 个位置上是否为第 $i$ 辆车，且 $[1,i-1]$ 已经错位的最小移动距离。

转移就是枚举第 $i-1$ 个位置是什么状态然后判断是否交换 $i$ 和 $i-1$：

\[\begin{aligned} f[i][0] &= \min(f[i-1][0] + f[i-1][1]) + 2 \times w_i \\ f[i][1] &= f[i-1][0] \end{aligned} \]

发现这个东西就是一个 $\min+$ 矩乘的形式，因为带修所以直接线段树维护矩阵乘法去优化 $dp$ 就好了，或者叫做 $ddp$。

矩阵大概就是下面这个东西：

\[\begin{bmatrix} f_{i-1,0} & f_{i-1,1} \end{bmatrix} \times \begin{bmatrix} 2 \times w_i & 0 \\ 2 \times w_i & \infty \\ \end{bmatrix} = \begin{bmatrix} f_{i,0} & f_{i,1} \end{bmatrix} \]

自己根据矩阵乘法的定义就可以发现，这个就是将转移方程再写了一遍而已。
写的时候要注意 $dp$ 的初值啊。（我就因为这里写错了寄了十几分钟）

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5+5;
const int INF = 1e9+5;
int n,w[N],dp[N][2];
int get_ans(){   //那个暴力 dp 
	dp[1][1] = 0,dp[1][0] = INF;
	for(int i=2; i<=n; i++){
		dp[i][0] = min(dp[i-1][0],dp[i-1][1]) + w[i-1];
		dp[i][1] = dp[i-1][0];
	}
	return dp[n][0] * 2;
}
struct matrix{
	int n,m;
	int a[3][3];
	matrix(){
		memset(a,0x3f,sizeof(a));
	}
}M[4 * N];
matrix operator * (matrix A,matrix B){
	matrix C;
	C.n = A.n,C.m = B.m;
	for(int i=1; i<=C.n; i++){
		for(int j=1; j<=C.m; j++){
			for(int k=1; k<=A.m; k++){
				C.a[i][j] = min(C.a[i][j],A.a[i][k] + B.a[k][j]);
			}
		}
	}
	return C;
}
void build(int now,int now_l,int now_r){
	if(now_l == now_r){
		M[now].a[1][1] = M[now].a[2][1] = w[now_l];
		M[now].a[1][2] = 0;
		M[now].a[2][2] = INF;
		M[now].n = M[now].m = 2;
		return;
	}
	int mid = (now_l + now_r) >> 1;
	build(now<<1,now_l,mid);build(now<<1|1,mid+1,now_r);
	M[now] = M[now<<1] * M[now<<1|1];
}
void modify(int now,int now_l,int now_r,int pos,int val){
	if(now_l == now_r){
		M[now].a[1][1] = M[now].a[2][1] = val;
		return;
	}
	int mid = (now_l + now_r)>>1;
	if(pos <= mid)	modify(now<<1,now_l,mid,pos,val);
	if(pos > mid)	modify(now<<1|1,mid+1,now_r,pos,val);
	M[now] = M[now<<1] * M[now<<1|1];
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout); 
	scanf("%lld",&n);
	for(int i=1; i<n; i++)	scanf("%lld",&w[i]);
	build(1,1,n-1);
	int q;scanf("%lld",&q);
	while(q--){
		int k,a;scanf("%lld%lld",&k,&a);
		w[k] = a;
		modify(1,1,n-1,k,a);
		matrix tmp;
		tmp.a[1][1] = INF,tmp.a[1][2] = 0;
		tmp.n = 1,tmp.m = 2;
		tmp = tmp * M[1];
		printf("%lld\n",tmp.a[1][1] * 2);
	} 
	return 0;
}