AGC023F 01 on Tree 做题记录

给定一棵 nn 个点的有根树,每个节点上有一个 0/10/1 权值。

你需要以这样的方式生成一个序列:

  • 每次选择一个没有父节点(或者父节点已被删除)的点删除,将其上的权值放到序列的末尾;

请求出所有可能序列中逆序对数的最小值。

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

阅读全文 »

P6646 [CCO 2020] Shopping Plans 做题记录

nn 个商品和 mm 种颜色,第 ii 个物品颜色为 aia_i,价格为 cic_i

对于一个购买物品的方案 S{1,2,3,,n}S\subseteq\{1,2,3,\dots,n\},定义其价格为 iSai\sum\limits_{i\in S}a_i

一个方案合法当且仅当:

  • 对于第 jj 种颜色,购买的该种颜色的商品的个数必须要在区间 [lj,rj][l_j,r_j] 中;

对于所有合法的方案,将其按照价格升序排序后,对于 i[1,k]i\in [1,k],求出第 ii 种合法方案的价格(合法方案数不足 ii 则输出 1-1)。

1n,m,k2×1051\le n,m,k\le 2\times 10^51aim1\le a_i\le m1ci1091\le c_i\le 10^90lirin0\le l_i\le r_i\le n

阅读全文 »

ARC130E Increasing Minimum 做题记录

对于一个长 nn 的正整数序列 AA,定义一个长 mm 的,值域 [1,n][1,n] 的正整数序列 bb 关于 AA 是好的当且仅当:

  • 从前往后遍历 bb,遍历到 ii 时:
    1. 需要满足 Abi=minj=1n{Aj}A_{b_i}=\min\limits_{j=1}^n\{A_j\}
    2. AbiA_{b_i} 增加 11

现给定 n,mn,m 和序列 bb,你需要构造一个长 nn 的字典序最小的正整数序列 AA,使得 bb 关于 AA 是好的,或报告无解。

1n,m3×1051\le n,m\le 3\times 10^5

阅读全文 »

ARC199A Flip Row or Col 2 做题记录

给定一个 n×nn\times n 的 01 矩阵 AA,和两个长 nn 的非负整数数组 ca,cbca,cb。请构造两个长 nn 的 01 数组 fa,fbfa,fb,满足:

  • i[1,n]\forall i\in [1,n] 都有 cai=1jnAi,jfaifbjca_i=\sum\limits_{1\le j\le n} A_{i,j}\oplus fa_i\oplus fb_j
  • j[1,n]\forall j\in [1,n] 都有 cbj=1inAi,jfaifbjcb_j=\sum\limits_{1\le i\le n} A_{i,j}\oplus fa_i\oplus fb_j

1n10001\le n\le 10000cai,cbi<n40\le ca_i,cb_i<\frac{n}{4}

阅读全文 »

ARC143F Counting Subsets 做题记录

给定正整数 nn,求有多少个 {1,2,3,,n}\{1,2,3,\dots,n\} 的子集 SS,满足对于任意 [1,n][1,n] 中的正整数 xx,都存在一个或两个 SS 的子集 TT 满足 x=yTyx=\sum\limits_{y\in T}y。对 998244353998244353 取模。

1n15001\le n\le 1500

阅读全文 »

【第七届图灵杯高级组】A. 棋无常树 做题记录

给定一棵 nn 个点的以 11 为根的有根树,点 uu 有权值 aia_ibib_i。定义树合法当且仅当每个点 uu 都满足其子树内 aia_imex\text{mex}bib_i

有些 bu=1b_u=-1 表示点 uu 没有限制,还有些 au=1a_u=-1 表示 aua_u 可以在 [0,n][0,n] 中任选。求有多少种给所有 au=1a_u=-1aua_u 赋值的方案使得树是合法的,对 109+710^9+7 取模。

1n50001\le n\le 50001au,bun-1\le a_u,b_u\le n

阅读全文 »