给定一个序列 ,长度为 的序列 符合以下条件
- 为不下降序列, 为不上升序列,即
有 个操作,每次操作把 的数增加 。求每次操作后最小的
CF1110E Magic Stones 做题记录
一次操作选择1<i<n,使ci变为ci′,ci′=ci+1+ci−1−ci
是否能做若干次操作,使每个ci和ti相等?
2≤n≤105,0≤ci≤2∗109,0≤ti≤2∗109。
CF1485D Multiples and Power Differences 做题记录
有一个 n×m 的矩阵 a ,请你构造一个矩阵 b ,使得:
- 0<bi,j≤106
- bi,j 是 ai,j 的倍数
- b 中相邻的两个数的差的绝对值可以写成 k4(k∈N+)
1≤n,m≤500,1≤ai,j≤16。
ARC147D Sets Scores 做题记录
构造 N 个集合,S1 到 SN 。
每个集合满足以下条件:
- 每个元素是不大于 M 的正整数;
- 对于两个相邻的集合 Si 和 Si+1,有且仅有一个数恰好在这两个集合中的一个里出现。
定义这 N 个集合的分数为 i=1∏mcnt(i) ,其中 cnt(i) 为 i 在所有 N 个集合中出现的次数。
求所有满足条件的集合簇的分数之和,答案对 998244353 取模。
1≤N,M≤2×105 。
P6892 [ICPC2014 WF]Baggage 做题记录
有一无穷长的流水线 a,初始时 ∀i≤0 和 i>2n,ai=0。否则,若 i 为奇数,则 ai=2;若 i 为偶数,则 ai=1。也就是说,ai=2 和 ai=1 是交替出现的。
现需要进行若干次 如下 操作,使得 a 中的所有 非零元素 为 连续 的一段且所有的 1 均在 2 前面。
选择两个位置 p 和 q,满足 ap=0,ap+1=0 且 aq=aq+1=0,将 aq 设为 ap,aq+1 设为 ap+1,并且将 ap 和 ap+1 均设为 0。输出时将此操作表示为
p to q
(p 和 q 是具体的值)。最小化操作步数,并输出操作序列,出题人将用 Special Judge 来评判您的答案的正确性。
3≤n≤100。
Mine Sweeper II 做题记录
扫雷地图是一张 n 行 m 列的网格,其中每个格子是地雷或空地。每个空地会显示一个数字代表与它相邻的雷的数量(两个格子相邻当且仅当它们共用一个顶点或一条边,不在边界上的格子与恰好 8 个格子相邻)。 在一次操作中,你可以将一个地雷改成空地,或将空地改成地雷。 给定两张扫雷地图 A 和 B,你需要对 A 进行不超过 ⌊2nm⌋ 次操作,使得 A 所有空地上的数字之和等于 B 所有空地上的数字之和。
CF1450C2 Errich-Tac-Toe (Hard Version) 做题记录
给定一张 n 行 n 列的棋盘,每个格子可能是空的或包含一个标志,标志有 X 和 O 两种。
如果有三个相同的标志排列在一行或一列上的三个连续的位置,则称这个棋盘是一个 胜局,
否则称其为 平局。例如,上图第一行的局面都是胜局,而第二行的局面都是平局。
在一次操作中,你可以将一个 X 改成 O,或将一个 O 改成 X。
设棋盘中标志的总数为 k,你需要用不超过 ⌊3k⌋
次操作把给定的局面变成平局。1≤n≤300。
CF1495C Garden of the Sun 做题记录
风见幽香的太阳花田是一个 n×m 的矩阵。
X
的位置是空地,.
的位置是向日葵,Imakf 保证给出的矩阵满足所有X
两两之间的切比雪夫距离大于 1(没有公共点)。请把一些
.
换成X
,使得所有的X
四连通且不存在简单环(形成一棵树)。1≤n,m≤500。
CF1552E Colors and Intervals 做题记录
n×k 个格子,编号从 1 到 n×k,染成 n 种颜色,每种颜色恰好 k 个。
构造 n 个区间,第 i 个区间 [ai,bi] 满足
- 1≤ai<bi≤n×k
- 第 ai 个和第 bi 个格子的颜色都是 i。
- 每个格子被包含不超过 ⌈k−1n⌉ 次。
1≤n≤100,2≤k≤100。
CF1628C Grid Xor 做题记录
给定 n×n 的矩阵 a,求满足 a 中任意一个元素等于 b 中与其相邻元素的异或和的矩阵 b 的异或和。
2≤n≤1000,n 是偶数。