有 个数组,每个数组里有 个 、 个 和 个 ,保证 。
对于每一个 ,求有多少种从 个数组中分别选一个数的方式,使得这些数异或起来等于 ,对 取模。
,。
CF573E Bear and Bowling 做题记录
给定一个长 n 的序列 a,从 a 中选择一个子序列 b,使得 ∑ibi 最大,输出这个最大值。
1≤n≤105,0≤∣ai∣≤107。
CF1720E Misha and Paintings 做题记录
给你一个 n×n 的矩阵 a 和一个正整数 k,你可以对 a 进行任意次操作(可以不操作),操作的具体步骤如下:
- 选择矩阵 a 的一个正方形子矩阵;
- 选择一个正整数数 x,其中 1≤x≤n2;
- 将子矩阵内的所有元素修改为 x。
你需要求出使矩阵 a 恰好包含 k 个不同元素所需的最小操作次数。
1≤n≤500,1≤k≤n2。
CF417E Square Table 做题记录
给你一个 N×M 的矩阵,要求在每一个格子内填一个不超过 108 的正整数,使得每一行和每一列的数的平方和仍然是一个平方数。
1≤n,m≤100。
[ABC304Ex] Constrained Topological Sort 做题记录
有 n 个点,每个点有 li,ri 两个值,有 m 条有向边 (si,ti),你要给每个点确定一个权值 ai,满足以下条件:
- ai 是 n 的排列;
- 对于所有 1≤i≤m 均有 asi<ati;
- 对于所有 1≤i≤n 均有 li≤ai≤ri;
判断无解。
2≤n≤2×105,0≤m≤min(n(n−1),4×105),i=j⇒si=sj。
CF1526E Oolimry and Suffix Array 做题记录
给定 n 和字符集大小 k 以及一个 0∼n−1 的排列 sa,求有多少个长 n,字符集大小 k ,从 0 开始标号的字符串 s 满足把 a={0,1,2,…,n−1} 按照 s[i,n−1] 字典序排序后满足 a=sa。
即生成的后缀数组是 sa。
1≤n,k≤2×105。
CF1427E Xum 做题记录
一开始黑板上有一个正奇数 x (3≤x<106),每次你可以选定黑板上已有的正整数 a,b(可以相等),将 a+b 或 a⊕b 写在黑板上,其中 ⊕ 表示异或运算,最终目标是将 1 写在黑板上。要求写数字不超过 105 次且写上的数字不超过 5∗1018 。
GYM103371B Cilantro 做题记录
给定 n 和两个长 n 的 01 串 S 与 T。
设入栈序列为 S,出栈序列为 T 的所有栈操作序列中,T1 可能对应的 S 中的下标集合为 A。
求 x∈A∑x。
例如 S=100,T=001 时答案为 5,因为共有 2 种栈操作序列满足入栈序列为 S,出栈序列为 T:
- 进,进,进,出,出,出,此时 T1 来自 S3;
- 进,进,出,进,出,出,此时 T1 来自 S2;
所以答案为 3+2=5。
1≤n≤5×106。