CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
^  A  ^  B  ^  C  ^  D  ^  E  ^  F  ^
|  +  |  +  |  +  |  O  |  O  |  O  |
rank:197
 
=====A=====
  * 题意:有点复杂的签到题。

  * 题解:有程设那味儿了。

=====B=====
  * 题意:给定$n,m$，问是否存在$n > 0, l \leq a, b, c \leq r$，使得$n \cdot a + b - c = m$。$(1 \leq l \leq r \leq 500\,000, 1 \leq m \leq 10^{10})$

  * 题解:$b-c \in [-r+l,r-l]$，直接枚举$a$，进行取余看能是否存在$n \cdot a$在这个范围且满足条件即可。

=====C=====
  * 题意:有$m$种花，每种第一次买获得$a_i$权值，第二次及更多次买获得$b_i$权值，求买$n$次的最大权值。$(1 \le n \le 10^9, 1 \le m \le 100\,000)$

  * 题解:显然最优答案是把所有$\ge$某一个$b_i$的$a_i$全部买掉然后剩下全部买$b_i$，枚举每一种可能算一下即可。

=====D=====
  * 题意:$10^9$的区间覆盖求覆盖区域最少的点。

  * 题解:离散化差分即可。比赛的时候判区间重叠锅了，导致最后没过去。

=====E=====
  * 题意:构造一棵$n$个点的二叉树，要求每个点不能只有一个儿子，且有$k$个点的两颗子树大小相差两倍；或判断无解。$(1 \leq n \leq 100\,000)$

  * 题解:如果$k=0$，那么必是满二叉树；如果$k \ne 0$，那么$n$不能是$2^x-1$；如果$n=9,k=2$，无解（可以枚举所有情况发现无解）。其它情况只要$k \le \dfrac{n-3}{2}$就有解，上界是毛毛虫。构造时dfs划分左右子树即可，令左子树始终是一棵满二叉树，大小按$1,3,7,15 \cdots$的顺序枚举，时间复杂度$O(n\log n)$。

=====F=====
  * 题意:$2n \times 2m$的黑白棋盘，$i+j$为偶数则$(i,j)$为白否则为黑；$q$次操作，每次禁用或解禁一个白格，问每次操作后能否放置$n \times m$个国王使得他们互不相邻，两个国王所在格子有边相同或角相同则认为是相邻的。$(1 \leq n, m, q \leq 200\,000)$

  * 题解:考虑每四个格子为一个大矩阵，整个棋盘恰有$n \times m$个大矩阵，每个大矩阵里放且只能放一个国王。因此如果必须要求两两大矩阵的不冲突才能全部放满。一个大矩阵里面有$2$个白格，左上和右下，结论是如果有一个左上被禁的白格子完全位于另一个右下被禁的白格子的左上方，那么一定无解，因为假设其中一个放国王，那么他们路径上所有国王位置就被确定了，最后一定会冲突；否则一定有解。因此线段树维护$[1,x]$左上格子的最小行和$[x,m]$右下格子的最大行即可，修改则对每一列开一个set维护最大值和最小值即可。
CVBB ACM Team

用户工具

站点工具

页面工具
