• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

【总结】联合省选题目选做

开发技术 开发技术 3小时前 2次浏览

省选联考 (2021)

P7514 [省选联考 2021 A/B 卷] 卡牌游戏

题目描述

Alice 有 (n) 张卡牌,第 (i)(1 le i le n))张卡牌的正面有数字 (a_i),背面有数字 (b_i),初始时所有卡牌正面朝上。

现在 Alice 可以将不超过 (m) 张卡牌翻面,即由正面朝上改为背面朝上。Alice 的目标是让最终朝上的 (n) 个数字的极差(最大值与最小值的差)尽量小。请你帮 Alice 算一算极差的最小值是多少。

数据范围

(3le nle 10^6,1le m<n,1le a_i,b_i,le 10^9)

key idea : 极差的本质是限定值域大小,(forall a_iin [l,r],r-l+1le len)

题解 1 (二分 + 双指针):

首先,在最优解中我们只会翻一个前缀 / 后缀,若我们翻了位置 (1<i<n) 且没有翻 (i-1),(i+1) 那么对其造成的影响要么是最大的变大,要么就是最小的变小。

考虑二分答案,每次 check 是否存在一种合法的翻牌方案使得极差小于等于 (val)

直接枚举翻牌方案,很难确定合法的翻牌的后缀。

问题的本质是,我们要找到一种翻牌方案,使得朝上的数字均在值域 ([l,r],r-l+1le val) 内。

对于固定的值域,在值域内的 (a) 我们是不需要翻的,剩下的我们只需要看要翻的位置的 (b) 是否在值域内。

因此,我们的值域越大越好,因此枚举值域左端点一定可以唯一确定值域最大的右端点。

将所有的 (a)(b) 排序之后,对于每次 check 枚举值域即可。

复杂度 (O(nlog n))

题解 2 (排序 + 双指针):

我们考虑将所有的 (a)(b) 排序后,预处理 (b) 的前后缀 (min,max) ,每次在值域上双指针。

双指针正确的前提:

  • 如果值域 ([l_1,r_1]) 是合法的值域,那么值域 ([l_2,r_2] ,l_2le l_1 le r_1le r_2) 一定也是合法的值域。

双指针求最优解:

  • 初始化 (l,r) 为包含 (a,b) 的极大值域。

  • 枚举值域左端点,因为要求最优解所以右指针不应当向右移动,(r) 移动到最左的满足 (l,r) 是合法值域的位置。

复杂度 (O(nlog n))

P7515 [省选联考 2021 A 卷] 矩阵游戏

题目描述

Alice 有一个 (n times m) 的矩阵 (a_{i, j})(1 le i le n)(1 le j le m)),其每个元素为大小不超过 ({10}^6) 的非负整数。

Bob 根据该矩阵生成了一个 ((n – 1) times (m – 1)) 的矩阵 (b_{i, j})(1 le i le n – 1)(1 le j le m – 1)),每个元素的生成公式为

[b_{i, j} = a_{i, j} + a_{i, j + 1} + a_{i + 1, j} + a_{i + 1, j + 1}
]

现在 Alice 忘记了矩阵 (a_{i, j}),请你根据 Bob 给出的矩阵 (b_{i, j}) 还原出 (a_{i, j})

数据范围

(1le T le 10,2le n,mle 300,0le b_{i,j}le 4times 10^6)

题解(差分约束):

key idea : 对于这种 (2times 2) 的子矩阵的限制可以考虑确定第一行与第一列的状态,从而(唯一)确定整个矩阵。

不考虑 (a_{i,j}) 元素大小的限制,我们考虑直接确定 (a) 的第一行元素和第一列元素。

这样,我们就可以唯一确定 所有的 (a_{i,j})

我们发现确定第一行元素和第一列元素和满足 (b_{i, j} = a_{i, j} + a_{i, j + 1} + a_{i + 1, j} + a_{i + 1, j + 1}) 的矩阵 (a) 是双射关系。

我们发现,如果我们要给第一行或第一列的某一个位置 (+1)(-1) 对整个矩阵的影响为:

  • 选一行或者一列 (+1 – 1 + 1 – 1 …) 或者 (-1 +1 -1 +1 ….)

令目标方案为 (c_{1,1},c_{1,2}…c_{1,m})(c_{1,1},c_{2,1},…,c_{n,1}) ,当前方案为 (a_{1,1},a_{1,2}…a_{1,m})(a_{1,1},a_{2,1},…,a_{n,1})

我们可以通过如下步骤将任意一个确定第一行与第一列的方案,“调整” 成目标方案:

  • 先通过将第一行与第一列进行 (+1 – 1 + 1 – 1 …)(-1 +1 -1 +1 ….)
  • 接下来对其余行与列对应的行 / 列进行 (+1 – 1 + 1 – 1 …)(-1 +1 -1 +1 ….)

可以发现在第二步中,不同的行列相互不影响。

注意到,对于任意一个位置 ((i,j)) 只会被 “调整” 两次。

那么 (a_{i,j}) 调整后的取值 (c_{i,j}=a_{i,j} pm P_i pm Q_j)

那么有不等式组:(0le a_{i,j} pm P_i pm Q_j le 10^6)

然而这并不仅有我们熟知的 差分约束 ,还有 “和分约束”,并且符号我们是确定不了的,怎么办呢?

一种理想的确定符号的方式是棋盘黑白染色:

[text{行}
begin{bmatrix}
+ & – & + & -\
– & + & – & +\
+ & – & + & -\
– & + & – & +\
end{bmatrix}
]

[text{列}
begin{bmatrix}
– & + & – & +\
+ & – & + & -\
– & + & – & +\
+ & – & + & -\
end{bmatrix}
]

但是这样是否能够达到任意状态呢?

如果没有差分约束 (forall xge 0) 或者 (forall xle 0) 的限制,其是很好证明的(因为不同的行和列是独立的)。

引理:对于一组形如 (x_i-x_jle a_k) 的不等式组存在一组解,那么一定可以用差分约束求解出一组 (forall x ge 0)(forall x le 0) 的一组解。

黑白染色后,可以保证其符号是不同的。

复杂度 (O(nm(n+m)))

P7516 [省选联考 2021 A/B 卷] 图函数

题目描述

对于一张 (n) 个点 (m) 条边的有向图 (G)(顶点从 (1 sim n) 编号),定义函数 (f(u, G))

  1. 初始化返回值 (cnt = 0),图 (G’ = G)
  2. (1)(n) 按顺序枚举顶点 (v),如果当前的图 (G’) 中,从 (u)(v) 与从 (v)(u) 的路径都存在,则将 (cnt + 1),并在图 (G’) 中删去顶点 (v) 以及与它相关的边。
  3. (2) 步结束后,返回值 (cnt) 即为函数值。

现在给定一张有向图 (G),请你求出 (h(G) = f(1, G) + f(2, G) + cdots + f(n, G)) 的值。

更进一步地,记删除(按输入顺序给出的)第 (1)(i) 条边后的图为 (G_i)(1 le i le m)),请你求出所有 (h(G_i)) 的值。

数据范围

(1le nle 10^3,1le mle 2times 10^5)

题解 ( (O(n^3)) 动态加边传递闭包 )

我们将计算 (f(u,G)) 的过程重新描述一下:

  • 初始化返回值 (cnt = 0),图 (G’ = G) ,集合 (S_{u,G} = emptyset)
  • (1)(n) 按顺序枚举顶点 (v),如果当前的图 (G’) 中,从 (u)(v) 与从 (v)(u) 的路径都存在,则将 (cnt + 1)(S_{u,G} gets S_{u,G} cup <u,v>) , 其中 (<u,v>) 是有序点对,并在图 (G’) 中删去顶点 (v) 以及与它相关的边。
  • 对于任一有序点对 (<u,v>in S_{u,G}) ,一定有 (vle u)
  • (f(u,G)=cnt=|S_u,G|)
  • 因为任意两个不同的 (u) ,(S_{u,G}) 不交,所以有 (h(G)=|bigcup_{1le ule n} S_{u,G}|)
  • 定义集合 (H(G)=bigcup_{1le ule n} S_{u,G})

考虑点对 (<u,v> in H(G)) 的条件:

  • 当且仅当图 (G) 中存在路径 (uto v) 满足路径上编号最小的点的编号为 (v) ,且存在路径 (vto u) 满足路径上编号最小的点的编号为 (v)

动态删边不是一个好做的条件,我们将其转化为倒着加边。

(f[x][y]) 为点 (x) 到点 (y) 路径上编号最小的点的编号最大是多少。

动态加边更新这个数组即可。 复杂度 (O(n^2m)) 可以拿到 (44) 分。

但是这个做法接着往下想是很没用前途的。

令图 (G_i’gets G_{m-i+1})

我们考虑一个点对 (<u,v>) 哪些集合 (H(G_i’)) 中。

我们考虑固定 (G) 去求 (H(G)) 的暴力做法:

  • 从后往前枚举 (v) 每次枚举一个 (u) 查询 (v) 是否可以到达 (u) , (u) 是否可以到达 (v)

而对于 “只有加边的动态传递闭包问题” 中,我们有一个建图技巧:

对于第 (i) 条插入的边 ((u_i,v_i)) ,建边 ((u_i,v_i,i))

那么每次相当于 (u)(v) 路径上最大的边权最小是多少。

对于该问题,我们采用类似地建边方法,即将边 ((u_i,v_i)) 建成 ((u_i,v_i,i))

那么跑动态加点的 (text{floyd}) 即可(复杂度 (O(n^3)) ),卡卡常可以过。

卡常小技巧(可以节约近一半的常数):

for (int x = n; x >= 1; x--) {
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= (i>x?x:n); j++)
			f[i][j] = std::max(f[i][j],std::min(f[i][x],f[x][j]));
}

程序员灯塔
转载请注明原文链接:【总结】联合省选题目选做
喜欢 (0)