AGC023F 01 on Tree 做题记录
给定一棵 n 个点的有根树,每个节点上有一个 0/1 权值。
你需要以这样的方式生成一个序列:
- 每次选择一个没有父节点(或者父节点已被删除)的点删除,将其上的权值放到序列的末尾;
请求出所有可能序列中逆序对数的最小值。
1≤n≤2×105。
P6646 [CCO 2020] Shopping Plans 做题记录
有 n 个商品和 m 种颜色,第 i 个物品颜色为 ai,价格为 ci。
对于一个购买物品的方案 S⊆{1,2,3,…,n},定义其价格为 i∈S∑ai。
一个方案合法当且仅当:
- 对于第 j 种颜色,购买的该种颜色的商品的个数必须要在区间 [lj,rj] 中;
对于所有合法的方案,将其按照价格升序排序后,对于 i∈[1,k],求出第 i 种合法方案的价格(合法方案数不足 i 则输出 −1)。
1≤n,m,k≤2×105,1≤ai≤m,1≤ci≤109,0≤li≤ri≤n。
ARC130E Increasing Minimum 做题记录
对于一个长 n 的正整数序列 A,定义一个长 m 的,值域 [1,n] 的正整数序列 b 关于 A 是好的当且仅当:
- 从前往后遍历 b,遍历到 i 时:
- 需要满足 Abi=j=1minn{Aj};
- 将 Abi 增加 1;
现给定 n,m 和序列 b,你需要构造一个长 n 的字典序最小的正整数序列 A,使得 b 关于 A 是好的,或报告无解。
1≤n,m≤3×105。
ARC199A Flip Row or Col 2 做题记录
给定一个 n×n 的 01 矩阵 A,和两个长 n 的非负整数数组 ca,cb。请构造两个长 n 的 01 数组 fa,fb,满足:
- ∀i∈[1,n] 都有 cai=1≤j≤n∑Ai,j⊕fai⊕fbj;
- ∀j∈[1,n] 都有 cbj=1≤i≤n∑Ai,j⊕fai⊕fbj;
1≤n≤1000,0≤cai,cbi<4n。
【第七届图灵杯高级组】A. 棋无常树 做题记录
给定一棵 n 个点的以 1 为根的有根树,点 u 有权值 ai 和 bi。定义树合法当且仅当每个点 u 都满足其子树内 ai 的 mex 为 bi。
有些 bu=−1 表示点 u 没有限制,还有些 au=−1 表示 au 可以在 [0,n] 中任选。求有多少种给所有 au=−1 的 au 赋值的方案使得树是合法的,对 109+7 取模。
1≤n≤5000,−1≤au,bu≤n。
0%