CF1787E The Harmonization of XOR 做题记录
给定 n 个数 [1,2,3,…,n] 和两个正整数 k 和 x。
将这些数分成恰好 k 组使得每组的异或和都是 x。具体地,每个数都必须出现在恰好一组内。
1≤k≤n≤2⋅105,1≤x≤109。
CF354D Transferring Pyramid 做题记录
一个 n 层的金字塔,你能进行两种操作。
给某个点染色,代价是 3。给某一个底边是金字塔的底边的子三角形染色,,代价是 点数+2。
现在有 m 个黑点,求出把所有黑点染色所需的最小代价。
1≤n,m≤105。
P9003 [RC-07] Game Theory 做题记录
给出长度为 n 的
01
序列 a1∼n,序列中有偶数个1
。NIT 和 TIN 轮流做以下操作,NIT 先手:
- 选择位置 i (1≤i≤n),满足区间 [1,i] 中有奇数个
1
。再选择位置 j (i<j≤n)。将 ai,aj 都取反(即,0
变1
,1
变0
)当整个序列中的所有元素都变为
0
时,当前轮到的人就无法操作,他就输了。假设 NIT 和 TIN 都绝顶聪明,谁会赢?可以证明,游戏总会结束。n 可能很大,但序列中 1 的个数不超过 2×105。
01
序列的输入方式是 m 个递增的正整数,描述这些1
的下标,下标从 1 开始。1≤n≤1018,2≤m≤106。保证 m 是偶数,保证为
1
的下标是递增顺序给出的。
UniversalOJ 228 基础数据结构练习题 做题记录
题目链接:UniversalOJ 228 基础数据结构练习题
你需要维护一个数据结构,支持以下三种操作:
1 l r k
给 i∈[l,r] 的所有 ai 加上 k;2 l r
对于 i∈[l,r] 的所有 ai,令其变为 ⌊ai⌋;3 l r
查询 i=l∑rai;序列长度为 n,操作次数为 q,值域为 V。
1≤n,q≤105,1≤V≤109。
CF1498F Christmas Game 做题记录
Alice 和 Bob 在一棵 n 个点的树上玩游戏,第 i 个节点上有 ai 个石子,每轮可以选择一个深度至少为 k 的节点并移动任意多石子到其 k 级祖先处,对每个结点询问如果将其作为根谁会赢。
n≤105,k≤20,ai≤109。
CF1572C Paint 做题记录
给定长度为 n 的颜色序列 ai,每次你可以选择任意长度的连续且颜色相同的一段位置,将其全部变成任意同一种颜色,问你最少总共需要多少次操作才能使得整个序列颜色相同。
限制: 每一种颜色初始时在序列中最多只有20个位置(是该种颜色)。
n≤3000,ai≤n,∑n≤3000。
P3188 [HNOI2007]梦幻岛宝珠 做题记录
给你 n 颗宝石,每颗宝石都有重量和价值。要你从这些宝石中选取一些宝石,保证总重量不超过 W,且总价值最大,并输出最大的总价值。
1≤n≤100,1≤W,wi,vi≤230。
保证每个 wi 能写成 a×2b (a,b∈N) 的形式,a≤10 , b≤30,且答案不超过 230。
CF710F String Set Queries 做题记录
维护一个字符串集合,支持三种操作:
- 加字符串
- 删字符串
- 查询集合中的所有字符串在给出的模板串中出现的次数
操作数 m≤3×105,输入字符串总长度 ∑∣si∣≤3×105。
本题强制在线,应该在每次输出后调用
fflush(stdout)
。你只有在输出上一个询问的答案后才能读入下一组询问。