首页 > 其他分享 >动态dp——P8820 [CSP-S 2022] 数据传输 题解

动态dp——P8820 [CSP-S 2022] 数据传输 题解

时间：2024-08-26 19:23:16浏览次数：14  
标签：10 P8820 minn val min int 题解 2022 operatorname

P8820 [CSP-S 2022] 数据传输

可怜的cnblog被（昨天DDos + 今天CC）攻击了(望周知！)，只好先发在 CSDN
题面：

题目描述

小 C 正在设计计算机网络中的路由系统。

测试用的网络总共有 n n n 台主机，依次编号为 1 ∼ n 1 \sim n 1∼n。这 n n n 台主机之间由 n − 1 n - 1 n−1 根网线连接，第 i i i 条网线连接个主机 a i a_i ai​ 和 b i b_i bi​。保证任意两台主机可以通过有限根网线直接或者间接地相连。受制于信息发送的功率，主机 a a a 能够直接将信息传输给主机 b b b 当且仅当两个主机在可以通过不超过 k k k 根网线直接或者间接的相连。

在计算机网络中，数据的传输往往需要通过若干次转发。假定小 C 需要将数据从主机 a a a 传输到主机 b b b（ a ≠ b a \neq b a=b），则其会选择出若干台用于传输的主机 c 1 = a , c 2 , … , c m − 1 , c m = b c_1 = a, c_2, \ldots, c_{m - 1}, c_m = b c1​=a,c2​,…,cm−1​,cm​=b，并按照如下规则转发：对于所有的 1 ≤ i < m 1 \le i < m 1≤i<m，主机 c i c_i ci​ 将信息直接发送给 c i + 1 c_{i + 1} ci+1​。

每台主机处理信息都需要一定的时间，第 i i i 台主机处理信息需要 v i v_i vi​ 单位的时间。数据在网络中的传输非常迅速，因此传输的时间可以忽略不计。据此，上述传输过程花费的时间为 ∑ i = 1 m v c i \sum_{i = 1}^{m} v_{c_i} ∑i=1m​vci​​。

现在总共有 q q q 次数据发送请求，第 i i i 次请求会从主机 s i s_i si​ 发送数据到主机 t i t_i ti​。小 C 想要知道，对于每一次请求至少需要花费多少单位时间才能完成传输。

输入格式

输入的第一行包含三个正整数 n , Q , k n, Q, k n,Q,k，分别表示网络主机个数，请求个数，传输参数。数据保证 1 ≤ n ≤ 2 × 10 5 1 \le n \le 2 \times {10}^5 1≤n≤2×105， 1 ≤ Q ≤ 2 × 10 5 1 \le Q \le 2 \times {10}^5 1≤Q≤2×105， 1 ≤ k ≤ 3 1 \le k \le 3 1≤k≤3。

输入的第二行包含 n n n 个正整数，第 i i i 个正整数表示 v i v_i vi​，保证 1 ≤ v i ≤ 10 9 1 \le v_i \le {10}^9 1≤vi​≤109。

接下来 n − 1 n - 1 n−1 行，第 i i i 行包含两个正整数 a i , b i a_i, b_i ai​,bi​，表示一条连接主机 a i , b i a_i, b_i ai​,bi​ 的网线。保证 1 ≤ a i , b i ≤ n 1 \le a_i, b_i \le n 1≤ai​,bi​≤n。

接下来 Q Q Q 行，第 i i i 行包含两个正整数 s i , t i s_i, t_i si​,ti​，表示一次从主机 s i s_i si​ 发送数据到主机 t i t_i ti​ 的请求。保证 1 ≤ s i , t i ≤ n 1 \le s_i, t_i \le n 1≤si​,ti​≤n， s i ≠ t i s_i \ne t_i si​=ti​。

输出格式

Q Q Q 行，每行一个正整数，表示第 i i i 次请求在传输的时候至少需要花费多少单位的时间。

样例 #1
样例输入 #1
7 3 3
1 2 3 4 5 6 7
1 2
1 3
2 4
2 5
3 6
3 7
4 7
5 6
1 2
样例输出 #1
12
12
3
提示

【样例解释 #1】

对于第一组请求，由于主机 4 , 7 4, 7 4,7 之间需要至少 4 4 4 根网线才能连接，因此数据无法在两台主机之间直接传输，其至少需要一次转发；我们让其在主机 1 1 1 进行一次转发，不难发现主机 1 1 1 和主机 4 , 7 4, 7 4,7 之间都只需要两根网线即可连接，且主机 1 1 1 的数据处理时间仅为 1 1 1，为所有主机中最小，因此最少传输的时间为 4 + 1 + 7 = 12 4 + 1 + 7 = 12 4+1+7=12。

对于第三组请求，由于主机 1 , 2 1, 2 1,2 之间只需要 1 1 1 根网线就能连接，因此数据直接传输就是最优解，最少传输的时间为 1 + 2 = 3 1 + 2 = 3 1+2=3。

【样例 #2】

见附件中的 transmit/transmit2.in 与 transmit/transmit2.ans。

该样例满足测试点 2 2 2 的限制。

【样例 #3】

见附件中的 transmit/transmit3.in 与 transmit/transmit3.ans。

该样例满足测试点 3 3 3 的限制。

【样例 #4】

见附件中的 transmit/transmit4.in 与 transmit/transmit4.ans。

该样例满足测试点 20 20 20 的限制。

【数据范围】

对于所有的测试数据，满足 1 ≤ n ≤ 2 × 10 5 1 \le n \le 2 \times {10}^5 1≤n≤2×105， 1 ≤ Q ≤ 2 × 10 5 1 \le Q \le 2 \times {10}^5 1≤Q≤2×105， 1 ≤ k ≤ 3 1 \le k \le 3 1≤k≤3， 1 ≤ a i , b i ≤ n 1 \le a_i, b_i \le n 1≤ai​,bi​≤n， 1 ≤ s i , t i ≤ n 1 \le s_i, t_i \le n 1≤si​,ti​≤n， s i ≠ t i s_i \ne t_i si​=ti​。

测试点 n ≤ n \le n≤ Q ≤ Q \le Q≤ k = k = k=特殊性质
1 1 1 10 10 10 10 10 10 2 2 2是
2 2 2 10 10 10 10 10 10 3 3 3是
3 3 3 200 200 200 200 200 200 2 2 2是
4 ∼ 5 4 \sim 5 4∼5 200 200 200 200 200 200 3 3 3是
6 ∼ 7 6 \sim 7 6∼7 2000 2000 2000 2000 2000 2000 1 1 1否
8 ∼ 9 8 \sim 9 8∼9 2000 2000 2000 2000 2000 2000 2 2 2否
10 ∼ 11 10 \sim 11 10∼11 2000 2000 2000 2000 2000 2000 3 3 3否
12 ∼ 13 12 \sim 13 12∼13 2 × 10 5 2 \times {10}^5 2×105 2 × 10 5 2 \times {10}^5 2×105 1 1 1否
14 14 14 5 × 10 4 5 \times {10}^4 5×104 5 × 10 4 5 \times {10}^4 5×104 2 2 2是
15 ∼ 16 15 \sim 16 15∼16 10 5 {10}^5 105 10 5 {10}^5 105 2 2 2是
17 ∼ 19 17 \sim 19 17∼19 2 × 10 5 2 \times {10}^5 2×105 2 × 10 5 2 \times {10}^5 2×105 2 2 2否
20 20 20 5 × 10 4 5 \times {10}^4 5×104 5 × 10 4 5 \times {10}^4 5×104 3 3 3是
21 ∼ 22 21 \sim 22 21∼22 10 5 {10}^5 105 10 5 {10}^5 105 3 3 3是
23 ∼ 25 23 \sim 25 23∼25 2 × 10 5 2 \times {10}^5 2×105 2 × 10 5 2 \times {10}^5 2×105 3 3 3否

特殊性质：保证 a i = i + 1 a_i = i + 1 ai​=i+1，而 b i b_i bi​ 则从 1 , 2 , … , i 1, 2, \ldots, i 1,2,…,i 中等概率选取。

这道题的 k k k 很小，又是 多测 + dp

自然让我们想到动态dp！

考虑 k = 1 k = 1 k=1 的情况：

很简单，就是链上求和
f u = f v + val ⁡ u f_{u} = f_v + \operatorname{val}_u fu​=fv​+valu​

考虑 k = 2 k = 2 k=2 的情况：

这个也不难想到，直接在链上跳，因为跳出链需要 2 2 2，跳进链也需要 2 2 2，然后的目的地和出发点也只有 2 2 2，非常的不值啊！
故有转移：（我们定义 f x , i f_{x,i} fx,i​ 表示到达离 x x x 距离为 i i i 的点的代价）
f u , 0 = min ⁡ ( f v , 0 , f v , 1 ) + val ⁡ u f u , 1 = f v , 0 \begin{align*} f_{u,0} &= \min(f_{v,0},f_{v,1}) + \operatorname{val}_u \\ f_{u,1} &= f_{v,0} \end{align*} fu,0​fu,1​​=min(fv,0​,fv,1​)+valu​=fv,0​​

img

考虑 k = 3 k = 3 k=3 的情况：

这时情况略有不同，跳出链是否可行呢？

img

我们发现，跳出链可能更优秀！
有转移：
f u , 0 = min ⁡ ( f v , 0 , f v , 1 , f v , 2 ) + val ⁡ u f u , 1 = min ⁡ { f u , 0 + minn ⁡ u min ⁡ ( f v , 0 , f v , 1 ) + minn ⁡ u f v , 0 f u , 2 = f v , 1 \begin{align*} f_{u,0} &= \min(f_{v,0},f_{v,1},f_{v,2}) + \operatorname{val}_u \\ f_{u,1} &= \min\begin{cases} f_{u,0} + \operatorname{minn}_u \\ \min(f_{v,0},f_{v,1}) + \operatorname{minn}_u \\ f_{v,0} \\ \end{cases} \\ f_{u,2} &= f_{v,1} \end{align*} fu,0​fu,1​fu,2​​=min(fv,0​,fv,1​,fv,2​)+valu​=min⎩ ⎨ ⎧​fu,0​+minnu​min(fv,0​,fv,1​)+minnu​fv,0​​=fv,1​​

这个 min ⁡ \min min 里面套 min ⁡ \min min 很烦人！

我们发现 f v , 0 + minn ⁡ u > f v , 0 f_{v,0} + \operatorname{minn}_u > f_{v,0} fv,0​+minnu​>fv,0​ ！

而且， f u , 0 = min ⁡ ( f v , 0 , f v , 1 , f v , 2 ) + val ⁡ u f_{u,0} = \min(f_{v,0},f_{v,1},f_{v,2}) + \operatorname{val}_u fu,0​=min(fv,0​,fv,1​,fv,2​)+valu​

所以， f u , 1 = min ⁡ ( f v , 1 + minn ⁡ u , f v , 0 , f v , 2 + val ⁡ u + minn ⁡ u ) f_{u,1} = \min(f_{v,1} + \operatorname{minn}_u,f_{v,0},f_{v,2} + \operatorname{val}_u +\operatorname{minn}_u) fu,1​=min(fv,1​+minnu​,fv,0​,fv,2​+valu​+minnu​)

构造出矩阵：

k = 1 k = 1 k=1 时，

[ f v 0 0 ] × [ val ⁡ u ∞ ∞ ∞ 0 ∞ ∞ ∞ 0 ] = [ f u 0 0 ] \begin{bmatrix} f_{v} & 0 & 0 \\ \end{bmatrix} \times\begin{bmatrix} \operatorname{val}_u & \infty & \infty \\ \infty & 0 & \infty \\ \infty & \infty & 0 \\ \end{bmatrix}=\begin{bmatrix} f_u & 0 & 0 \end{bmatrix} [fv​​0​0​]× ​valu​∞∞​∞0∞​∞∞0​ ​=[fu​​0​0​]

 

k = 2 k = 2 k=2 时，
[ f v , 0 f v , 1 0 ] × [ val ⁡ u 0 val ⁡ u ∞ ] = [ f u , 0 f u , 1 ] \begin{bmatrix} f_{v,0} & f_{v,1} & 0 \end{bmatrix} \times \begin{bmatrix} \operatorname{val}_u & 0 \\ \operatorname{val}_u & \infty \\ \end{bmatrix} = \begin{bmatrix} f_{u,0} & f_{u,1} \end{bmatrix} [fv,0​​fv,1​​0​]×[valu​valu​​0∞​]=[fu,0​​fu,1​​]

 

k = 3 k = 3 k=3 时，
[ f v , 0 f v , 1 f v , 2 ] × [ val ⁡ u 0 ∞ val ⁡ u minn ⁡ u ∞ val ⁡ u minn ⁡ u + val ⁡ u 0 ] = [ f u , 0 f u , 1 f u , 2 ] \begin{bmatrix} f_{v,0} & f_{v,1} & f_{v,2} \end{bmatrix} \times \begin{bmatrix} \operatorname{val}_u & 0 & \infty \\ \operatorname{val}_u & \operatorname{minn}_u & \infty \\ \operatorname{val}_u & \operatorname{minn}_u + \operatorname{val}_u & 0 \\ \end{bmatrix} = \begin{bmatrix} f_{u,0} & f_{u,1} & f_{u,2} \end{bmatrix} [fv,0​​fv,1​​fv,2​​]× ​valu​valu​valu​​0minnu​minnu​+valu​​∞∞0​ ​=[fu,0​​fu,1​​fu,2​​]

然后用树上倍增跑动态dp!

Tips : 本人对动态dp计算的误区——矩阵没有交换律！！！

为什么这个很重要呢？

看这段代码：

matrix<1,3> query(int x,int y) {
	matrix<3,3> c;
	for(int i = 0;i<3;i++) c[i][i] = 0;
	while(top[x] ^ top[y]) {
		if(dep[top[x]] < dep[top[y]]) swap(x,y);
		c = c * sgt::query(1,1,n,id[top[x]],id[x]);
		x = fa[top[x]];
	} 
	if(dep[x] > dep[y]) swap(x,y);
	c = c * sgt::query(1,1,n,id[x],id[y]);
	matrix<1,3> ans;
	ans = ans * c;
	return ans;
}

这个喜提 0 0 0 分，
因为他跳链计算的方式完全是乱的，但是这个广义矩阵乘法又没有交换律，故得出的答案也是完全错误！

而 P4719 这道题用树剖 + 线段树为什么是对的呢？

因为ta要求的答案是全局答案！并且修改的时候会对链头的父亲进行修改，而不是对整条链的修改！

而本题是一种类似于爬山的方式进行的矩阵乘法，如图：

img

这个时候，我们考虑用树上倍增模拟这个爬山过程：

  1. 求出 lca ⁡ ( s , t ) \operatorname{lca}(s,t) lca(s,t)

 

  1. 以上升的方式倍增求 mat ⁡ 1 = ∏ i : [ s ∼ l c a ] [ val ⁡ 0 ∞ val ⁡ minn ⁡ ∞ val ⁡ minn ⁡ + val ⁡ 0 ] \operatorname{mat}_1 = \prod\limits_{i:[s \sim lca]} \begin{bmatrix} \operatorname{val} & 0 & \infty \\ \operatorname{val} & \operatorname{minn} & \infty \\ \operatorname{val} & \operatorname{minn} + \operatorname{val} & 0 \\ \end{bmatrix} mat1​=i:[s∼lca]∏​ ​valvalval​0minnminn+val​∞∞0​ ​

 

  1. 以下降的方式倍增求 mat ⁡ 2 = ∏ i : [ l c a ∼ t ] [ val ⁡ 0 ∞ val ⁡ minn ⁡ ∞ val ⁡ minn ⁡ + val ⁡ 0 ] \operatorname{mat}_2 = \prod\limits_{i:[lca \sim t]} \begin{bmatrix} \operatorname{val} & 0 & \infty \\ \operatorname{val} & \operatorname{minn} & \infty \\ \operatorname{val} & \operatorname{minn} + \operatorname{val} & 0 \\ \end{bmatrix} mat2​=i:[lca∼t]∏​ ​valvalval​0minnminn+val​∞∞0​ ​

  2. 最后将答案 re ⁡ = mat ⁡ 1 × m a t [min{fa,minn}] ⁡ × mat ⁡ 2 \operatorname{re} = \operatorname{mat}_1 \times mat_{\operatorname{[min\{fa,minn\}]}} \times \operatorname{mat}_2 re=mat1​×mat[min{fa,minn}]​×mat2​

答案就是 : r e 0 , 0 re_{0,0} re0,0​

AC-code:

#include<bits/stdc++.h>
using namespace std;
#define int long long		
#define log2(x) __lg((x))
template<int N,int M,class T = long long>
struct matrix {
	T m[N][M];
	matrix(){memset(m,0x3f,sizeof(m));}
	T* operator [] (const int pos) {return m[pos];}
};
template<int N,int M,int R,class T = long long>
matrix<N,R,T> operator * (matrix<N,M,T> a,matrix<M,R,T> b) {
	matrix<N,R,T> c;
	for(int i = 0;i<N;i++)
		for(int j = 0;j<M;j++)
			for(int k = 0;k<R;k++)
				c[i][k] = min(c[i][k],a[i][j] + b[j][k]);
	return c;
}
int rd() {
	int x = 0, w = 1;
	char ch = 0;
	while (ch < '0' || ch > '9') {
		if (ch == '-') w = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + (ch - '0');
		ch = getchar();
	}
	return x * w;
}
const int N = 2e5+5,inf = 0x3f3f3f3f3f3f3f3fLL;
void wt(int x) {
	static int sta[35];
	int f = 1;
	if(x < 0) f = -1,x *= f;
	int top = 0;
	do {
		sta[top++] = x % 10, x /= 10;
	} while (x);
	if(f == -1) putchar('-');
	while (top) putchar(sta[--top] + 48);
}
int n,q,k,v[N],minn[N];
int head[N],nxt[N<<1],to[N<<1],cnt;
void init() {
	memset(head,-1,sizeof(head));
	cnt = 0;
}
void add(int u,int v) {
	nxt[cnt] = head[u];
	to[cnt] = v;
	head[u] = cnt++;
} 
int fa[19][N],dep[N];
matrix<3,3> down[19][N],up[19][N];
matrix<3,3> get(int id,int fav = inf) {
	matrix<3,3> c;
	switch(k) {
		case 1:
			c[0][0] = v[id];
			break;
		case 2:
			c[0][1] = 0;
			c[0][0] = c[1][0] = v[id];
			break;
		case 3:
			c[0][0] = c[1][0] = c[2][0] = v[id];
			c[1][1] = min(minn[id],fav);
			c[2][1] = min(minn[id],fav) + v[id];
			c[0][1] = c[1][2] = 0;
			break;
	}
	return c;
}

void dfs(int x,int f){
	fa[0][x] = f;
	dep[x] = dep[f] + 1;
	minn[x] = inf;
	for(int i = head[x];~i;i = nxt[i]) {
		int y = to[i];
		if(y ^ f) {
			dfs(y,x);
			minn[x] = min(minn[x],v[y]);
		}
	}
	down[0][x] = up[0][x] = get(x);
}

matrix<1,3> f;

int lca(int x,int y) {
	if(dep[x] < dep[y]) swap(x,y);
	int d = dep[x] - dep[y];
	for(int j = 18;j >= 0;j--) if(d >> j & 1) x = fa[j][x];
	if(x == y) return x;
	for(int j = 18;j >=0;j--) if(fa[j][x] ^ fa[j][y]) x = fa[j][x],y = fa[j][y];
	return fa[0][x];
}

matrix<3,3> getDown(int u,int k) {
	matrix<3,3> re;
	for(int i = 0;i<3;i++) re[i][i] = 0;
	for(int j = 18;j >= 0;j--) if(k >> j & 1) re = down[j][u] * re,u = fa[j][u];
	return re;
}

matrix<3,3> getUp(int u,int k) {
	matrix<3,3> re;
	for(int i = 0;i<3;i++) re[i][i] = 0;
	for(int j = 18;j >= 0;j--) if(k >> j & 1) re = re * up[j][u],u = fa[j][u];
	return re;
}

int query(int s,int t) {
	int LCA = lca(s,t);
	matrix<1,3> re = f * getUp(s,dep[s] - dep[LCA]) * get(LCA,v[fa[0][LCA]]) * getDown(t,dep[t] - dep[LCA]);
	return min({re[0][0] - v[t],re[0][1],re[0][2]}) + v[t]; 
}

signed main() {
	init();
	n = rd(),q = rd(),k = rd();
	f[0][k - 1] = 0;
	v[0] = inf;
	for(int i = 1;i<=n;i++) v[i] = rd();
	for(int i = 1;i<n;i++) {
		int u = rd(),v = rd();
		add(u,v);add(v,u);
	}
	dfs(1,0);
	for(int j = 1;j<=18;j++) {
		for(int i = 1;i<=n;i++) fa[j][i] = fa[j - 1][fa[j - 1][i]];
		for(int i = 1;i<=n;i++) down[j][i] = down[j - 1][fa[j - 1][i]] * down[j - 1][i];
		for(int i = 1;i<=n;i++) up[j][i] = up[j - 1][i] * up[j - 1][fa[j - 1][i]];
	}
	while(q--) {
		int s = rd(),t = rd();
		wt(query(s,t));
		putchar('\n');
	}
	
	return 0;
}

标签：10,P8820,minn,val,min,int,题解,2022,operatorname
From： https://blog.csdn.net/qq_49785217/article/details/141571399

相关文章

  • 【跨域问题解决】Access to XMLHttpRequest at xxx from origin xxx has been blocked
    这个错误是由于浏览器的同源策略（CORS,Cross-OriginResourceSharing）导致的。当从一个源（origin）向另一个源请求资源时，如果这两个源的协议、域名或端口号不同，就会触发CORS策略。解决方法要解决这个问题，你需要在你的后端服务中添加CORS支持，以便它允许来自你的请求。这通常......
  • [ARC182C] Sum of Number of Divisors of Product 题解
    题目链接点击打开链接题目解法我怎么不会分治/fn首先把\(x\)分解成\(\prodp_i^{x_i}(0\lei\le5)\)的形式，正因数个数为\(\prod(x_i+1)\)有一个很牛的想法是：合并两个\(x_i\)序列（假设一个叫\(x_0,...,x_5\)，另一个叫\(y_0,...,y_5\)）先不考虑后面的\(+1\)（可以最后......
  • 题解：AT_arc183_b [ARC183B] Near Assignment
    题意：给你长度为\(N\)的整数序列\(A,B\)以及整数\(K\)。你可以执行下列操作零次或多次。选择整数\(i\)和\(j\)(\(1\leqi,j\leqN\))。这里，\(|i-j|\leqK\)必须保持不变。然后，将\(A_{i}\)的值改为\(A_{j}\)。判断是否有可能使\(A\)与\(B\)相同。分......
  • 常见问题解决 --- 如何给一个不支持配置代理的程序抓取https流量数据
    比如我有一个C#编写票务系统，它内嵌浏览器功能，我想抓取它的流量，但是这个客户端不支持配置代理设置解决办法：1.安装配置proxifier开启全局代理服务。安装好后网上有激活码激活一下，点击profile-proxyserver，添加一个代理服务器127.0.0.1，端口8080，协议https。点击profile-prox......
  • Java | Leetcode Java题解之第374题猜数字大小
    题目：题解：publicclassSolutionextendsGuessGame{publicintguessNumber(intn){intleft=1,right=n;while(left<right){//循环直至区间左右端点相同intmid=left+(right-left)/2;//防止计算时溢出......
  • Hitachi Vantara Programming Contest 2024（AtCoder Beginner Contest 368）题解A~D
    A-Cut题意：将数组的后k个字符移到前面思路：可以用rotate（）函数让数组中的元素滚动旋转rotate(v.begin(),v.begin()+n-k,v.end());直接输出后k个元素，再输出前n-k个元素for(inti=n-k;i<n;i++)write(v[i]);for(inti=0;i<n-k;i++)write(v[i]);B-Decrease2......
  • 题解：AT_joisc2017_f 鉄道旅行 (Railway Trip)
    题意鉄道旅行(RailwayTrip)分析非常神仙的倍增做法。我们设\(l_{i,j}\)表示从\(i\)点出发，停靠\(2^j\)站后能抵达的最左位置。同理设\(r_{i,j}\)表示从\(i\)点出发，停靠\(2^j\)站后能抵达的最右位置。考虑如何更新这两个状态。因为可以走回头路，所以简单的\(l......
  • 题解：SP3109 STRLCP - Longest Common Prefix
    三倍经验：UVA11996JewelMagicP4036[JSOI2008]火星人题意维护一个字符串\(S\)，支持以下操作：\(Q\i\j\)：输出\(\operatorname{LCP}(S[i\dotsl],S[j\dotsl])\)\(R\i\char\)：用\(char\)替换\(S\)的第\(i\)个字符\(I\i\char\)：在\(S\)的第\(i\)......
  • 题解：CF590E Birthday
    题目分析题意给定\(n\)个字符串，要求从中选出若干个组成一个集合，且集合中每个字符串都互不包含。求集合最大包含几个字符串。分析本题弱化版：[ABC354G]SelectStrings就是求一个最长反链，并求构造方案。求构造方案还是比较有意思的。建议先做P4298[CTSC2008]祭祀。一......
  • 题解：P5217 贫穷
    题意维护一个字符串，支持以下操作：\(\texttt{Ixc}\)，在第\(x\)个字母后面插入一个\(c\)。\(\texttt{Dx}\)，删除第\(x\)个字母。\(\texttt{Rxy}\)，反转当前文本中的区间\([x,y]\)。\(\texttt{Px}\)，输出初始文本中第\(x\)个字母在当前文本中的位置。特别地，若不存在，......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99