学习笔记

摘要： 题意 给定 \(n\) 及常数 \(A,B,t\)，数组 \(p_i\)。随机变量 \(S_i\in\{0,1\}\) 为 \(1\) 的概率为 \(p_i\)。定义 \(f_0=0\)，对 \(i=1..n\)： \[f_i = \begin{cases} f_{i-1}+1, & S_i=1,\ 阅读全文

摘要： 题意 https://codeforces.com/gym/102512/problem/G 给定长度为 \(N\) 的数组 \(a\)，进行 \(Q\) 次询问 \((l,r)\)。 对任意区间 \([l,r]\)，记长度 \(m=r-l+1\)。 定义前缀数组 \(\begin{cases} A 阅读全文

摘要： 题意 \(N\) 个正整数按顺序依次加入到数列里，可以决定将这个数写在当前数列的最左边或最右边。写下的数列的可能的最长严格上升子序列的长度是多少，搞出这样的子序列有多少种。加入数列的方法或子序列下标不同则认为两子序列不同。 此题还出现在：「雅礼集训 2017 Day10」数列。 思路 我们考虑取出 阅读全文

摘要： 题意 给定 \(n\) 个节点的树，每个点有权值 \(a_i\)。另外给定 \(k\) 个互不相同的非负整数 \(b_1, \ldots, b_k\)。求满足下面条件的边集的数量： 把这些边从树中移除后，树的每个连通块内所有节点的异或和都属于集合 \(b\)。 多测，\(\sum n \le 10^ 阅读全文

摘要： 题意 给定位数为 \(n-1\) 的两个正整数 \(A,B\)，需要动态维护两数之和 \(C=A+B\)。有 \(q\) 次操作，每次操作可能为修改 \(A\) 或 \(B\) 的某一位，或者求此时 \(C\) 的某一位。 \(n,q \le 10^5\)。 思路 考虑分块的做法，按位数分成 \(\ 阅读全文

摘要： 题意 给定正整数 \(n(n\leq 10^5)\)，求出 \(1,2,\dots,n\) 的满足下面条件的子集的个数： 若 \(x\) 在该子集中，则 \(2x\) 和 \(3x\) 不能在该子集中。 思路 我们简化问题，如果不考虑 \(3x\) 的出现，只考虑 \(2x\)。那么我们发现对于序列 阅读全文

摘要： 题意 \(x_1, x_2, \ldots, x_n\) 为在 \([0,1]\) 之间均匀分布的随机实数变量。有 \(m\) 个条件，每个条件的形式为 \(x_i + x_j \le 1\) 或 \(x_i + x_j \ge 1\)。 求所有条件都被满足的概率，结果对 \(998\,244\,3 阅读全文

摘要： 题意 给定长度为 \(n\) 的序列 \(A\)，求最大半公约数，其定义为最大正整数 \(g\)，使序列中至少一半的数都能被 \(g\) 整除。 思路 根据经验，遇到这种过半数的题可以考虑随机化。由于序列中有至少一半的数是 \(g\) 的倍数，故当我们从序列中随机选取一个数时，其所有因子中存在答案的 阅读全文

摘要： 题意 给出一个长度为 \(n\) 的数组 \(a\) 和以下两种操作： \(1\ i\ x\)：将 \(a_i\) 修改为 \(x\)。 \(2\ l\ r\ k\)：询问在数组区间 \([l, r]\) 内是否每个出现过的正整数的出现次数都是 \(k\) 的倍数。 思路 我们考虑询问内容的必要条件 阅读全文