2024.10.24 题目

题解：2024.10.24 模拟赛

长方体

容斥 数学 几何

有 $n$ 个长方体，第 $i$ 个对角线的两个顶点为 $(x_0,y_0,z_0)$ 和 $(x_1,y_1,z_1)$。求至少被 $n-1$ 个长方体所覆盖的整点数量。

三角形

斐波那契数列 找规律

给定长度为 $n$ 的序列 $a$，第 $i$ 个数为 $a_i$。进行 $q$ 次询问，每次询问的格式为 $[l,r]$，求区间内是否能够选出三个不同的下标 $(i,j,k)$ 使得三条 $(a_i,a_j,a_k)$ 的线段可以组成三角形。

区间

平衡树 模拟

给定长度为 $n$ 的序列 $a$，第 $i$ 个数为 $a_i$，并给定 $m$ 和 $q$ 次操作，每次操作给出 $(o,l)$。若 $o=1$，则翻转区间 $[l,l+m-1]$ 内的元素；如果 $o=2$，则获取 $a_l$。对于所有的操作 $2$，求出答案的异或和。

图

生成树

有 $n$ 个结点，第 $i$ 个结点的点权为 $a_i$。若 $a_i\mathrm{and}{a}_j=0$（$\mathrm{and}$ 是按位与），则 $i$ 与 $j$ 有一条边。初始时集合 $S=\varnothing$，进行 $n$ 次操作，每次加入一个结点到 $S$。加入结点 $v$ 有两种方式：

• 直接加入结点 $v$，代价为 $0$；
• 选择另一个结点 $u\in S$ 且 $u$ 与 $v$ 之间有一条边，代价为 $a_u$。

求能够获得的最大代价。