CF1463F Max Correct Set 做题记录

定义集合 SS 合法当且仅当满足以下条件:

  • S{1,2,...,n}S \subseteq \{1,2,...,n\}

  • aS,bS\forall a\in S,b\in Sab{x,y}|a-b|\not\in\{x,y\}

给定 n,x,yn,x,y,求最大的 S|S|

1n1091\le n\le 10^91x,y221\le x,y\le 22

阅读全文 »

CF1784F Minimums or Medians 做题记录

你有一个包含 12n1 \sim 2n2n2n 个整数的集合 SS。你必须执行恰好 kk1kn1061 \le k \le n \le 10^6)次操作,每个操作都是以下两种其中之一:

  • SS 中第 1,21, 2 个元素删去。

  • SS 中第 S2,S2+1\frac{|S|}2, \frac{|S|}2 + 1 个元素删去。(显然 S|S| 一直是偶数,所以 S2\frac{|S|}2 也一定是整数)

请你统计,通过这些操作可以获得多少个本质不同的最终集合 SS?答案对 998244353998244353 取模。

阅读全文 »

CF1648E Air Reform 做题记录

一张 nn 个点 mm 条边的无向带权简单连通图,其上一条路径的权值为其中所有边权的 max\max

考虑这张图的补图,补图中一条边的权值为原图中该边两端点间的最短路(路径长度的定义同上)。保证补图亦是连通图。

对于原图中每条边,求出其两端点在补图中的最短路(定义仍同上)。

1n,m2×1051\le n,m\le 2\times 10^5,边权范围 [0,109][0,10^9]

阅读全文 »

CF1172F Nauuo and Bug & P5609 做题记录

给定一个如图所示的计算方法:

现在给定长 nn 的数组 aapp,要求 qq 次询问 sum(a,li,ri,p)\text{sum}(a,l_i,r_i,p) 的值。

1n1061\le n\le 10^61m2×1051\le m\le 2\times 10^51p1091\le p\le 10^9ai109|a_i|\le 10^9

阅读全文 »

AGC040E Prefix Suffix Addition 做题记录

你有一个长为 nn 的序列 x1,x2,,xnx_1,x_2,\dots,x_n,一开始全部为 00,你现在可以以任意顺序进行任意次以下两种操作:

  1. 选定整数 1kn1\le k\le n 与不下降非负整数序列 c1,c2,,ckc_1,c_2,\dots,c_k,对所有 1ik1\le i \le k,令 xix_i 加上 cic_i
  2. 选定整数 1kn1\le k\le n 与不上升非负整数序列 c1,c2,,ckc_1,c_2,\dots,c_k,对所有 1ik1\le i \le k,令 xnk+ix_{n-k+i} 加上 cic_i

问最少进行多少次操作使得 xi=aix_i=a_i

1n2×1051\le n\le 2\times 10^51ai1091\le a_i\le 10^9

阅读全文 »

AGC024E Sequence Growing Hard 做题记录

给定 nn, kk, mm , 问有多少个序列组 (A0,A1,,An)(A_0,A_1,\dots,A_n) 满足:

  • 序列 AiA_i 的元素个数为 ii
  • 所有元素都在 [1,k][1,k] 内;
  • i[0,n1]\forall i\in[0,n-1]AiA_iAi+1A_{i+1} 的子序列且 AiA_i 的字典序小于 Ai+1A_{i+1}

答案对 mm 取模。

1n,k3001\le n,k\le 3002m1092\le m\le 10^9

阅读全文 »

CF1456E XOR-ranges 做题记录

给定 nnkk,有 nn<2k< 2^k 的非负整数变量 x1,x2,,xnx_1,x_2,\dots,x_n,其中 xix_i 的取值范围是 [li,ri][l_i,r_i]

给出数列 c0,c1,,cK1c_0,c_1,\dots,c_{K-1},并由此定义一个代价函数 f(x)f(x)

f(x)=i=0k1(x2imod2)cif(x)=\sum_{i=0}^{k-1}(\lfloor\tfrac x{2^i}\rfloor\bmod 2)\cdot c_i

确定每个变量的取值,使得 i=2nf(xixi1)\sum_{i=2}^nf(x_i\oplus x_{i-1}) 最小,输出该最小值。

2n502\le n\le501k501\le k\le500liri<2k0\le l_i\le r_i< 2^k0ci10120\le c_i\le10^{12}

阅读全文 »