CF1787E The Harmonization of XOR 做题记录

给定 nn 个数 [1,2,3,,n][1,2,3,\ldots,n] 和两个正整数 kkxx

将这些数分成恰好 kk 组使得每组的异或和都是 xx。具体地,每个数都必须出现在恰好一组内。

1kn21051\le k\le n\le 2\cdot 10^51x1091\le x\le 10^9

阅读全文 »

CF354D Transferring Pyramid 做题记录

一个 nn 层的金字塔,你能进行两种操作。

给某个点染色,代价是 33。给某一个底边是金字塔的底边的子三角形染色,,代价是 点数+2\text{点数}+2

现在有 mm 个黑点,求出把所有黑点染色所需的最小代价。

1n,m1051\le n,m\le 10^5

阅读全文 »

P9003 [RC-07] Game Theory 做题记录

给出长度为 nn01 序列 a1na_{1\sim n}序列中有偶数个 1。NIT 和 TIN 轮流做以下操作,NIT 先手:

  • 选择位置 i (1in)i\ (1\le i\le n),满足区间 [1,i][1,i] 中有奇数个 1。再选择位置 j (i<jn)j\ (i<j\le n)。将 ai,aja_i,a_j 都取反(即,0110

当整个序列中的所有元素都变为 0 时,当前轮到的人就无法操作,他就输了。假设 NIT 和 TIN 都绝顶聪明,谁会赢?可以证明,游戏总会结束。

nn 可能很大,但序列中 11 的个数不超过 2×1052\times 10^5

01 序列的输入方式是 mm递增的正整数,描述这些 1 的下标,下标从 11 开始。

1n10181\le n\le 10^{18}2m1062 \le m\le 10^6。保证 mm 是偶数,保证为 1 的下标是递增顺序给出的。

阅读全文 »

UniversalOJ 228 基础数据结构练习题 做题记录

题目链接:UniversalOJ 228 基础数据结构练习题

你需要维护一个数据结构,支持以下三种操作:

  • 1 l r ki[l,r]i\in[l,r] 的所有 aia_i 加上 kk
  • 2 l r 对于 i[l,r]i\in[l,r] 的所有 aia_i,令其变为 ai\lfloor\sqrt a_i\rfloor
  • 3 l r 查询 i=lrai\sum\limits_{i=l}^r a_i

序列长度为 nn,操作次数为 qq,值域为 VV

1n,q1051\le n,q\le 10^51V1091\le V\le 10^9

阅读全文 »

CF1498F Christmas Game 做题记录

Alice 和 Bob 在一棵 nn 个点的树上玩游戏,第 ii 个节点上有 aia_i 个石子,每轮可以选择一个深度至少为 kk 的节点并移动任意多石子到其 kk 级祖先处,对每个结点询问如果将其作为根谁会赢。

n105,k20,ai109n\le 10^5 , k\le 20 , a_i\le 10^9

阅读全文 »

CF1572C Paint 做题记录

给定长度为 nn 的颜色序列 aia_i,每次你可以选择任意长度的连续且颜色相同的一段位置,将其全部变成任意同一种颜色,问你最少总共需要多少次操作才能使得整个序列颜色相同。

限制: 每一种颜色初始时在序列中最多只有20个位置(是该种颜色)。

n3000n\le 3000aina_i \le nn3000\sum n \le 3000

阅读全文 »

P3188 [HNOI2007]梦幻岛宝珠 做题记录

给你 nn 颗宝石,每颗宝石都有重量和价值。要你从这些宝石中选取一些宝石,保证总重量不超过 WW,且总价值最大,并输出最大的总价值。

1n1001\le n \le 1001W,wi,vi2301\le W,w_i,v_i \le 2^{30}

保证每个 wiw_i 能写成 a×2b (a,bN)a \times 2^b\space (a,b \in \mathbb N) 的形式,a10a \leq 10 , b30b \leq 30,且答案不超过 2302^{30}

阅读全文 »

CF710F String Set Queries 做题记录

维护一个字符串集合,支持三种操作:

  1. 加字符串
  2. 删字符串
  3. 查询集合中的所有字符串在给出的模板串中出现的次数

操作数 m3×105m \leq 3 \times 10^5,输入字符串总长度 si3×105\sum |s_i| \leq 3\times 10^5

本题强制在线,应该在每次输出后调用fflush(stdout)。你只有在输出上一个询问的答案后才能读入下一组询问。

阅读全文 »