CF1667C Half Queen Cover 做题记录

有一个 n×nn\times n 的棋盘,你要在上面放最少数量的”半皇后“,使得每个格子都能被攻击到。

一个位于 (x,y)(x,y) 的 ”半皇后“ 能攻击到 (a,b)(a,b) 当且仅当满足以下条件中至少一个:

  • a=xa=x
  • b=yb=y
  • ab=xya-b=x-y

输出方案。

1n1051\le n\le 10^5

阅读全文 »

ARC146C Even XOR 做题记录

给定 nn,求满足以下条件的集合 S{0,1,2,,2n1}S\in\{0,1,2,\dots,2^n-1\} 的个数:

对于所有 SS 的非空子集 TST\in STT 均满足以下条件中的至少一个:

  • T|T| 是奇数;
  • TT 中元素的异或和非零;

998244353998244353 取模。

1n2×1051\le n\le 2\times 10^5

阅读全文 »

CF891E Lust 做题记录

你有 nn 个数 a1,a2,,ana_1,a_2,\dots,a_n 要进行 kk 次操作,每次随机选择一个数 x[1,n]x \in [1,n],把 axa_x 减一,并将答案增加除 axa_x 外所有数的乘积。

求最终答案的期望,答案对 109+710^9 + 7 取模。

1n50001\le n\le 5000

阅读全文 »

CF1672F2 Checker for Array Shuffling 做题记录

给定一个长 nn,值域 [1,n][1,n] 的数组 aa,定义 aa 的排列(任意打乱元素顺序后的数组)bb 的价值为最小的操作次数使得 b=ab=a,一次操作可以:

  • 选定两个 1i<jn1\le i<j\le n,交换 bib_ibjb_j

F1:给定 aa,构造价值最大的 bb

F2:给定 aabb,判断 bb 的价值是否最大;

1n2×1051\le n\le 2\times 10^5

阅读全文 »

CF1685D1 Permutation Weight (Easy Version) 做题记录

给定一个 1n1\sim n 的排列 pp

对于一个 1n1\sim n 的排列 qq,定义其权值为:

q1pq2+q2pq3+q3pq4++qn1pqn+qnpq1|q_1-p_{q_2}|+|q_2-p_{q_3}|+|q_3-p_{q_4}|+\cdots+|q_{n-1}-p_{q_n}|+|q_n-p_{q_1}|

找出 任意一个 权值最小化的 1n1\sim n 的排列 qq

2n2002\le n\le 200

阅读全文 »