T1 忘了叫什么名字
对于一个排列 \(p\),定义它的权值为其有多少个子串是一个值域从 \(1\) 开始的排列。给定排列 \(p\),对于 \(1\le i\le j\le n\),定义 \(f(i,j)\) 为交换 \(p_i,p_j\) 之后排列的权值。有 \(Q\) 次询问,每次询问所有 \(f(i,j)\) 中第 \(k\) 大的是多少。\(n,Q\le 5\times 10^5, k\le n(n+1)/2\)。
T2 Bulbel
checker 有一个用 bitset 表示的 \(w\times w\) 01 矩阵,你要将其转置。可用操作:赋值,AND,OR,XOR,左右移(多余补0),修改一个位置为常量。注意不能获取 bitset 中数的真实值,所有操作均可以指定操作完赋值给哪里。Sub1,2 15pts:\(w=2,128,m\le 10^5\)。Sub3 36pts:\(w=256,m\le 16384\),其中 \(m\le 65536\) 有 \(24\) 分。Sub4 49pts:\(w=1024,m\le 35436\),其中 \(m\le 40000\) 有忘了多少分。
T3 黄焖鸡
定义一个序列是坏的,当且仅当它的最大权独立集的两倍是所有数之和。定义一个序列是超级好的,当且仅当它的所有子串都不是坏的。给定 \(n\) 个集合 \(A_i\subseteq [1,m]\),求满足 \(a_i\in A_i\) 的超级好序列 \(a\) 有几个。\(n\le 200,m\le 19\)。
标签:CTT,排列,定义,Day3,le,序列 From: https://www.cnblogs.com/Charlie-Vinnie/p/17876274.html