原题解链接：https://ac.nowcoder.com/discuss/149978 考虑使用类似线性筛的方法，从小到大枚举每个a-贝利福斯数 iii ，然后从小到达枚举每个a-贝利福斯素数 xxx ，标记 i×xi \times xi×x ，如果 i mod x=0i \bmod x=0imodx=0 ，则结束枚举。 这个做法正确性是显然的，但是由于a-贝利福斯数并不满足唯一分解定理，可能存在多种分解成a-贝利福斯素数的 方式，所以一个数可能被标记多次。但是重复标记的次数不是很多，经检验，至少当 n=2×107,a≤10n=2 \times 10^{7}, a \leq 10n=2×10...

原题解链接：https://ac.nowcoder.com/discuss/149978 定义 sum⁡(a)=∑i=1nai\operatorname{sum}(a)=\sum_{i=1}^{n} a_{i}sum(a)=∑i=1n​ai​ ，考虑计算 sum⁡(a′)\operatorname{sum}\left(a^{\prime}\right)sum(a′) 。 sum⁡(a′)=∑i=1nai′=∑i=1n(sum⁡(a)−ai)=(∑i=1nsum⁡(a))−(∑i=1nai)=(n−1)sum⁡(a)\operatorname{sum}\left(a^{\prime}\right...

原题解链接：https://ac.nowcoder.com/discuss/149978 定义数组 b1..n−1b_{1 . . n-1}b1..n−1​ ，其中 bi=[ai<ai+1](i.eb_{i}=\left[a_{i}<a_{i+1}\right]\left(i . e\right.bi​=[ai​<ai+1​](i.e. 当 ai<ai+1a_{i}<a_{i+1}ai​<ai+1​ 时， bi=1b_{i}=1bi​=1 ；否则 bi=0)\left.b_{i}=0\right)bi​=0) 。 则所求 =b=b=b 中最长的连续的 1 的...

原题解链接：https://ac.nowcoder.com/discuss/149978 首先把因数个数和转化成倍数个数和，即 ∑i=1n⌊ni⌋\sum_{i=1}^{n}\left\lfloor\frac{n}{i}\right\rfloor∑i=1n​⌊in​⌋ 方法1: 利用 ⌊ni⌋\left\lfloor\frac{n}{i}\right\rfloor⌊in​⌋ 只有 O(n)O(\sqrt{n})O(n​) 种枚举计算。 方法2: 所求即 ∑x,y≥1[x×y≤n]\sum_{x, y \geq 1}[x \times y \leq n]∑x,y≥1​[x×y≤n] 考虑计算 ∑...

原题解链接：https://ac.nowcoder.com/discuss/149978 先考虑如何判断有xxx只青蛙要从起点跳到终点是否可行。 我们从左往右考虑每块石头, 1.可以强制使用这块石头,因为不用这块石头的方案可以转化成使用这块石头的方案; 2.可以强制让最左的青蛙跳到这块石头,因为让非最左的青蛙跳到这块石头的方案可以转化成让最左的青蛙跳到这块石头的方案。 可以发现青蛙一直是连续的一段,所以到第iii块石头的时候判断一下和第i−xi - xi−x块石头的距离就行了。 时间复杂度O(m)O(m) O(m)。 现在回到原问题。 直接二分就可以做到O(tmlogm)O(tmlogm)O(...

原题解链接：https://ac.nowcoder.com/discuss/149980 定理: nnn条直线最多能把空间划分为n∗(n+2)2+1\frac{n *(n+2)}{2}+12n∗(n+2)​+1 份 我们可以把XXX型看做两条不相交的直线，因此答案为2n∗(2n+1)2+1\frac{2 n *(2 n+1)}{2}+122n∗(2n+1)​+1 证明: 对于第nnn条直线，如果使得区域增加kkk个， 当且仅当它与k−1k- 1k−1条直线相交 而我们之前已经构造好了n−1n - 1n−1条两两相交的直线，且三三不相交的直线，因此第nnn条直线一定可以找到一种方法使得与n−1n...

原题解链接：https://ac.nowcoder.com/discuss/149980 第一问 由于每个烟花互不相同，因此每种颜色的个数都是1 根据期望的定义: ans =∑pi∗1=∑pi=\sum p_{i} * 1=\sum p_{i}=∑pi​∗1=∑pi​ 第二问 设f[i][j]f[i][j]f[i][j]表示前i个烟花，恰好有jjj个被点燃的概率 转移的时候枚举当前烟花是否被点燃 滚动数组优化 #include <iostream> using namespace std; const int maxn = 1e5+10, maxk = 105; double dp...

原题解链接：https://ac.nowcoder.com/discuss/149980 考虑一个很显然的O(mlogm)O(m log m)O(mlogm)的做法 首先对所有线段按照右端点排序，然后每次在右端点处切 但是mmm达到了10710^7107级别，所以不能通过此题 由于题目保证所有线段的值域为1−n1-n1−n，我们可以对所有左端点，直接记录出右端点最靠左的位置 同样每次切右端点，扫一遍即可 时间复杂度:O(m)O(m)O(m) #include<cstdio> const int MAXN = 1e6 + 10; #define getchar() (p1 == p2...

原题解链接：https://ac.nowcoder.com/discuss/149980 性质: 若 x⊕z=y,x \oplus z=y, \quadx⊕z=y, 则 x⊕y=zx \oplus y=zx⊕y=z 考虑答案一定是 x⊕{x \oplus\{x⊕{ 坨东西 }=y\}=y}=y 那么 x⊕y={x \oplus y=\{x⊕y={ 一坨东西 }\}} 因此问题变为询问序列中是否有 x⊕yx \oplus yx⊕y ->线性基经典操作 时间复杂度: O(nlog⁡n)O(n \log n)O(nlogn) #include<cstdio> #include&l...

原题解链接： ∑1⩽i,j⩽Nai∗aj=(∑ai)2−∑ai2\sum_{1 \leqslant i, j \leqslant N} a_{i} * a_{j}=\left(\sum a_{i}\right)^{2}-\sum a_{i}^{2}∑1⩽i,j⩽N​ai​∗aj​=(∑ai​)2−∑ai2​ 证明可以暴力展开 后面的两项都可以通过树剖打标记维护 第一个直接维护和，询问的时候乘起来即可 第二个可以展开 ∑(ai+b)2=∑ai2+∑2aib+siz∗b2\sum\left(a_{i}+b\right)^{2}=\sum a_{i}^{2}+\sum 2 a_{i} b+s i z...

原题解链接：https://ac.nowcoder.com/discuss/149980 把每个植物成熟的时间投射到位置1上，将 p[i]p[i]p[i] 减去 ∑j=2id[i]\sum_{j=2}^{i} d[i]∑j=2i​d[i] ， 排序后形成了一个序列。 可以证明，每个药农只会采集一段区间。 题目转化成一个序列分成kkk个区间求最小花费。 花费的计算可以用前缀和来表示，SiS_iSi​表示成熟时间前缀和，那么转移方程。 f[[i]表示前i个采集完毕，出动了j个药农。 那么 f[i][j]=min⁡(f[i][j−1]+(i−k)∗p[i]−(s[i]−s[k]))f[i][j]=\...

原题解链接：https://ac.nowcoder.com/discuss/149984 最优解先手一定变为了000 定有一或者两次先手共减少了nnn,设先手减少的为XXX 设k为中间后手减少的那次，kkk要满足k≤n−x,n−x≤n−kk≤n-x,n-x≤n-kk≤n−x,n−x≤n−k 此时k≤xk≤xk≤x且k≤n−xk≤n-xk≤n−x #include<cstdio> using namespace std; int main() { int n; scanf("%d",&n) ; printf("%d\n",n - n / 2)...

原题解链接：https://ac.nowcoder.com/discuss/149990 我们发现，这些位运算都是按位独立的,也就是说,我们可以将每一位分别维护, 而不是维护整个数字。 那我们可以先拆位，然后依次考虑如何实现这几个操作。 首先先看区间与，假设我们现在要与上xxx,操作的区间是[l,r][l,r][l,r],我们要考虑它对第www位的影响。 那么很显然，如果xxx的第www位是111,那么这个操作对这一位没有影响。否则，就是将[l,r][l, r][l,r]的这一位赋值为000。 我们再来考虑区间或，假设我们现在要或上x,操作的区间是[1,r][1, r][1,r],我们要考虑它...

原题解链接：https://ac.nowcoder.com/discuss/149990 首先，裴蜀定理告诉我们，对于如下关于xix_ixi​的整数方程: ∑i=1naixi=k\sum_{i=1}^{n} a_{i} x_{i}=ki=1∑n​ai​xi​=k 有解的条件是 gcd⁡(a1,a2,a3,…,an)∣k\operatorname{gcd}\left(a_{1}, a_{2}, a_{3}, \ldots, a_{n}\right) \mid kgcd(a1​,a2​,a3​,…,an​)∣k 在这道题中， 是求 gcd⁡(x1,x2,x3,…,xn)∣1\operatornam...