其他不大正统的学习笔记

# 整除分块 ## Part 1 ### 简介 在$O(\sqrt{n})$复杂度内乱搞出所有$[\frac{k}{i}](1<=i<=n)$ ## Part 2 ### 模板 # 0/1分数规划 ## Part 1 ### 简介 是二分中的一种，主要用来求平均数的最大值等，常见的形式是 $$ans=max (\frac{\sum\limits_{i=l}^r a_i}{\sum\limits_{i=l}^r b_i}) (0<l<=r<=n)$$ ## Part 2 ### 例题 这种题目有明显的特征，就是所求可以改写成上面的式子，然后二分这个值判定，可以和很多算法搭配，可考性很强 #### 最佳牛围栏 [题目](https://www.acwing.com/problem/content/104/) 这种情况其实是上面公式的一个特殊情况，即所有的$b_i$都为零，在这种情况下，我们可以直接减去这个二分的值，然后再用$O(n)$的复杂度递推判定即可 ```cpp #include<bits/stdc++.h> using namespace std; const int eps=1e-5; int n,m,i; double l,r,mid,ans,a[200000]; double f[200000]; bool check(double x) { int i; double min_v,ans; for (i=0;i<=n;i++) f[i]=0; for (i=1;i<=n;i++) f[i]=a[i]-x+f[i-1]; ans=-1e8; min_v=1e8; for (i=m;i<=n;i++) { min_v=min(min_v,f[i-m]); ans=max(ans,f[i]-min_v); } return ans>=0; } int main() { cin>>n>>m; for (i=1;i<=n;i++) cin>>a[i]; l=-1e8; r=1e8; i=0; while (r-l>eps) { i++; mid=(l+r)/2; if (check(mid)) { ans=mid; l=mid; } else r=mid; if (l>=r) break; if (i>100) break; } cout<<(int)((ans+0.0001)*1000)<<endl; } ``` #### KC喝咖啡 [题目](https://www.luogu.org/problem/P1570) 这道题是之前公式的最直接的应用，二分$mid$之后采用贪心判定即可，代码略 #### [HNOI2009]最小圈 [题目](https://www.luogu.org/problem/P3199) 这道题和第一道例题相似，也是直接要求平均值最小值，所以二分答案，然后把所有权值减去二分值，然后再跑一下负环，如果出现负环，说明二分值偏大，否则二分值偏小，最后输出 ```cpp #include<bits/stdc++.h> using namespace std; const int N=100005; const int eps=1e-9; #define db double int a[N],nxt[N],las[N],ru[N],x[N],q[10000000]; int t,n,m,len,i,w,k; db b[N],dis[N],y[N],z[N]; db l,r,bo,mid; void add(int xx,db yy,db zz) { len++; a[len]=yy; b[len]=zz; nxt[len]=las[xx]; las[xx]=len; } bool spfa() { int i,l,r,x; l=1; r=1; q[1]=1; dis[1]=0; while (l<=r) { if (r>2*(n+m)) return true; x=q[l]; for (i=las[x];i;i=nxt[i]) if (dis[x]+b[i]<dis[a[i]]) { dis[a[i]]=dis[x]+b[i]; ru[a[i]]++; if (ru[a[i]]>=n) { return true; } r++; q[r]=a[i]; } l++; } return false; } int main() { scanf("%d%d",&n,&m); for (i=1;i<=m;i++) cin>>x[i]>>y[i]>>z[i]; l=-1e5; r=1e5; while (r-l>eps) { k++; if (k>65)break; mid=(l+r)/2; len=0; memset(las,0,sizeof(las)); memset(nxt,0,sizeof(nxt)); memset(dis,0x7f,sizeof(dis)); memset(ru,0,sizeof(ru)); ru[1]=1; for (i=1;i<=m;i++) add(x[i],y[i],z[i]-mid); if (spfa()) { bo=mid; r=mid; } else l=mid; } printf("%0.8lf",bo); } ```