夢に僕らで帆を張って
来るべき日のために夜を超え

标签 二分 下的文章

November 6, 2019

洛谷P4318 完全平方数

题意求第$k$个不含完全平方数因子的数数据范围:$k \le 10^9$题解二分这个数,然后验证其排名是否$\ge k$对于计算$n$以内的无平方因子数的个数,可以用到容斥原理$$ans=含0个质数的平方因子的个数-含1个质数的平方因子的个数+含2个质数的平方因子的个数 \dots$$注意到每个数的容斥系数恰好为莫比乌斯函数$\mu(i)$,上式即为$$\sum_{i=1}^{\lfloor...
October 31, 2019

洛谷P1768 天路

题意最优比率环数据范围:$1 \le n \le 7000,1 \le m \le 20000$题解$0/1$分数规划要求$$ans=\frac{\sum_i^{i \in E} v_i}{\sum_i^{i \in E} p_i}$$二分这个答案$mid$,将每条边的边更改为$$mid \cdot p_i-v_i$$跑负环即可代码:#include<iostream> #in...
October 28, 2019

洛谷P1314 聪明的质监员

题意略数据范围:$1 \le n,m \le 200000,s \le 10^{12}$题解二分$W$,更新$|S-Y|$在每次验证的时候用前缀和维护$\ge W$的$w_i$的数量与总和代码:#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #i...