Forgive_jkxjkx1031

Forgive_jkxjkx1031 : #3393 巨(mu)型(ban)线段树
2 年,3 月前

线段树最基本的两种操作——段增加和段覆盖,放在一起之后,就如同干柴遇到烈火(?)一般,令人欲仙欲死......谁做谁知道...... 段增加和段覆盖结合之后,有以下几点需要注意: 1. 决定一个区间上同时存在 add 标记和 set 标记时,是 set 覆盖 add,还是在 set 基础上再 add?(我选择了后者,以避免 add 标记无处可 “pushdown” 的情况) 2. 更新时,add 标记和 set 标记都需要 pushdown。因为 set 标记以下的 add 标记是无效的(所以要 p ...查看全文
Forgive_jkxjkx1031 : #3334 题解(据说改版之后发博客能上首页?)
2 年,4 月前

枚举还剩2个数时的各种情况,可以发现还剩2个数的状态是必胜态。 由于每次操作必定会减少一个数,因此对于 n>1 的输入判断奇偶, n=1 的情况特判即可。 ...查看全文
Forgive_jkxjkx1031 : #3272 简易版题解
2 年,8 月前

可以用位运算实现。 先考虑第一个方案。用一个数组 b[] 表示集合,即当且仅当集合中存在 x 时 b[x]=1 。于是可以枚举 a[i] 和 b[j] ,判断 b[j+a[i]] 是否为 0 。 存在的问题:复杂度是 n*\max{a[i]} ,必定会超时。 第二个方案。将 01 数组 b[] 用二进制数 B 表示,于是可以直接判断 B \& (B \ll a[i]) 是否为零来获得答案。 存在的问题: B 的值最大可能为 2^{200000} ,C++ 不 ...查看全文