CF1406D Three Sequences 做题记录

给定一个序列 a1,a2,,ana_1,a_2,\ldots ,a_n,长度为 nn 的序列 b,cb,c 符合以下条件

  1. ai=bi+cia_i=b_i+c_i
  2. bb 为不下降序列,cc 为不上升序列,即 bibi1,cici1b_i\geq b_{i-1}, c_i\leq c_{i-1}

qq 个操作,每次操作把 [l,r][l,r] 的数增加 xx。求每次操作后最小的 max(bi,ci)\max(b_i,c_i)

阅读全文 »

CF1110E Magic Stones 做题记录

一次操作选择1<i<n1<i<n,使cic_i变为cic_i'ci=ci+1+ci1cic_i'=c_{i+1}+c_{i-1}-c_i

是否能做若干次操作,使每个cic_itit_i相等?

2n105,0ci2109,0ti21092\le n\le 10^5, 0\le c_i\le 2*10^9, 0\le t_i\le 2*10^9

阅读全文 »

CF1485D Multiples and Power Differences 做题记录

有一个 n×mn\times m 的矩阵 aa ,请你构造一个矩阵 bb ,使得:

  • 0<bi,j1060<b_{i,j}\le 10^6
  • bi,jb_{i,j}ai,ja_{i,j} 的倍数
  • bb 中相邻的两个数的差的绝对值可以写成 k4(kN+)k^4(k\in\mathbb{N}^+)

1n,m5001\le n,m\le 5001ai,j161\le a_{i,j}\le 16

阅读全文 »

ARC147D Sets Scores 做题记录

构造 NN 个集合,S1S_1SNS_N

每个集合满足以下条件:

  • 每个元素是不大于 MM 的正整数;
  • 对于两个相邻的集合 SiS_iSi+1S_{i+1},有且仅有一个数恰好在这两个集合中的一个里出现。

定义这 NN 个集合的分数为 i=1mcnt(i)\prod\limits_{i=1}^m cnt(i) ,其中 cnt(i)cnt(i)ii 在所有 NN 个集合中出现的次数。

求所有满足条件的集合簇的分数之和,答案对 998244353998244353 取模。

1N,M2×1051\le N,M\le 2\times 10^5

阅读全文 »

P6892 [ICPC2014 WF]Baggage 做题记录

有一无穷长的流水线 aa,初始时 i0 和 i>2n,ai=0\forall i\le0\text{ 和 } i>2n ,a_i=0否则,若 ii 为奇数,则 ai=2a_i=2;若 ii 为偶数,则 ai=1a_i=1也就是说,ai=2a_i=2ai=1a_i=1 是交替出现的。

现需要进行若干次 如下 操作,使得 aa 中的所有 非零元素连续 的一段且所有的 11 均在 22 前面

选择两个位置 ppqq,满足 ap0,ap+10a_p\ne0,a_{p+1}\ne0aq=aq+1=0a_q=a_{q+1}=0,将 aqa_q 设为 apa_paq+1a_{q+1} 设为 ap+1a_{p+1},并且将 apa_pap+1a_{p+1} 均设为 00输出时将此操作表示为 p to qppqq 是具体的值)

最小化操作步数,并输出操作序列,出题人将用 Special Judge\text{Special Judge} 来评判您的答案的正确性。

3n1003\le n\le 100

阅读全文 »

Mine Sweeper II 做题记录

扫雷地图是一张 nnmm 列的网格,其中每个格子是地雷或空地。每个空地会显示一个数字代表与它相邻的雷的数量(两个格子相邻当且仅当它们共用一个顶点或一条边,不在边界上的格子与恰好 88 个格子相邻)。 在一次操作中,你可以将一个地雷改成空地,或将空地改成地雷。 给定两张扫雷地图 AABB,你需要对 AA 进行不超过 nm2\lfloor\frac{nm}{2}\rfloor 次操作,使得 AA 所有空地上的数字之和等于 BB 所有空地上的数字之和。

阅读全文 »

CF1450C2 Errich-Tac-Toe (Hard Version) 做题记录

给定一张 nnnn 列的棋盘,每个格子可能是空的或包含一个标志,标志有 X\text{X}O\text{O} 两种。

如果有三个相同的标志排列在一行或一列上的三个连续的位置,则称这个棋盘是一个 胜局
否则称其为 平局

例如,上图第一行的局面都是胜局,而第二行的局面都是平局。

在一次操作中,你可以将一个 X\text X 改成 O\text O,或将一个 O\text O 改成 X\text X

设棋盘中标志的总数为 kk,你需要用不超过 k3\lfloor \frac{k}{3}\rfloor
次操作把给定的局面变成平局。

1n3001\leq n\leq 300

阅读全文 »

CF1495C Garden of the Sun 做题记录

风见幽香的太阳花田是一个 n×mn\times m 的矩阵。

X 的位置是空地,. 的位置是向日葵,Imakf 保证给出的矩阵满足所有 X 两两之间的切比雪夫距离大于 11(没有公共点)

请把一些 . 换成 X,使得所有的 X 四连通且不存在简单环(形成一棵树)。

1n,m5001\le n,m\le 500

阅读全文 »

CF1552E Colors and Intervals 做题记录

n×kn \times k 个格子,编号从 11n×kn \times k,染成 nn 种颜色,每种颜色恰好 kk 个。
构造 nn 个区间,第 ii 个区间 [ai,bi][a_i, b_i] 满足

  • 1ai<bin×k1 \le a_i < b_i \le n \times k
  • aia_i 个和第 bib_i 个格子的颜色都是 ii
  • 每个格子被包含不超过 nk1\lceil \frac{n}{k-1} \rceil 次。

1n1001\le n\le 1002k1002\le k\le 100

阅读全文 »