二分弄得很清楚，每次都是感性理解，拿直线切凸包的过程总是搞不清什么是常量，什么是变量。

整理出来，顺便再次理解

WQS

如果理解不了我在说什么，可以试着把凸包和直线画出来自己切一切，会清楚很多。

此类知识点大纲中并未涉及，所以【8】是我自己的估计，后带星号表示估计，仅供参考。

inline">\(f(\frac{x_1+x_2}{2})-f(x_1)\le

f(x_2)-f(\frac{x_1+x_2}{2})\)，则称函数

inline">\(f(\frac{x_1+x_2}{2})-f(x_1)\ge

f(x_2)-f(\frac{x_1+x_2}{2})\)，则称函数

即上凸函数满足斜率单调递增，下凸函数斜率单调递减。

经过移项，还可以得到另外一个更优雅的表达式：

class="math

inline">\(2f(\frac{x_1+x_2}{2})\le

为上凸函数，

inline">\(2f(\frac{x_1+x_2}{2})\ge

的值，但我们并不能快速求出这个位置的值。

此时，如果对于确定的常数

inline">\(\text{mid}\)，我们能快速求出

inline">\(f(x)-\text{mid}x\)

的最小值(或最大值)，我们就可以使用

WQS

inline">\(y=\text{mid}x+b\)

inline">\(f(x')=\text{mid}x'+b\)，整理得

inline">\(b=f(x')-\text{mid}x'\)。

又由于直线与

必然取能取到的最小值。

而我们对这条直线的

inline">\(f(x)-\text{mid}x\)

inline">\(f(x_{\min})-\text{mid}x_{\min}\)，由于

inline">\(f(x)-\text{mid}x\)

inline">\(x_{\min}\)，就可以直接通过最小值

inline">\(f(x_{\min})-\text{mid}x_{\min}\)

inline">\(\text{mid}x_{\min}\)

inline">\(\text{mid}\)，如果算出来的

这个问题的一个实例是每个对象都有若干种决策，每种决策有各自的贡献，求恰好

个的限制存在，我们求解时往往必须要升一维记录要求的决策已经选了多少个，这常常会使我们的复杂度难以接受。

而利用

WQS

inline">\(f(x)-\text{mid}x\)

class="math

inline">\(\text{mid}\)

求解无恰好

个限制的原问题，可以直接求最大/最小贡献，就避免了记录选的个数而升维。

因此通常恰好

inline">\(f(k)\)，check(mid,cnt)

inline">\(f(x)-\text{mid}x\)

mid=(l+r)>>1;check(mid,cnt);if(cnt>=k)ans=mid,l=mid+1;else

r=mid-1;}

printf("%d\n",check(ans,cnt)+k*ans);

理解为对选择这种决策的惩罚。

如果惩罚力度增大，则更有可能不选这个决策，于是

上存在多点共线，与凸包切于这些点的直线的

inline">\(\text{cnt}\)。

例如，如果二分条件写的是

更新答案，那我们就应该在满足取到最小值/最大值的情况下返回最大的

inline">\(\text{cnt}\)。

否则，如果

inline">\(\text{cnt}\)，而我们返回的不是最大的

inline">\(\text{cnt}\)，就不满足二分时

不是最大值依旧满足更新答案的条件，不会错误地跳过这一段。

同理，如果写的是

inline">\(\text{cnt}\)。

同样的，由于可能多点共线，在二分结束后计算时应当加上

inline">\(\text{mid}\times\text{cnt}\)，其中

inline">\(\text{cnt}\)。

首先是上下界，根据单调性，我们只需要在与

的最后一个点相切斜率之间二分即可。

假设是取最小值，如果

的最后一个点。

最大值反之。

可以利用这一点估算二分的上下界。

另外，取特殊点也可以用于确定上下界。

如果

的定义域是连续的整数，

class="math

inline">\(1\)，纵坐标之差为整数，则斜率必然为整数。

此时，我们可以只进行整数二分。

inline">\((x,f(x))\)，存在一个整数

inline">\(k_1\)，到后一个点的斜率为

inline">\(b=f(x)-k'x\)，可得

inline">\(1\)：可以通过调整法利用凸性的定义直接说明凸性成立。

inline">\(2\)：归约为具有凸性的模型，最常见的有费用流模型：费用流每一次的流量是凸的。

inline">\(k\)，写出暴力动态规划，利用状态转移方程归纳地证明凸性成立。

需要用到一些凸函数的变换性质。

inline">\(4\)：对于区间分拆类型的问题，可以通过四边形不等式证明凸性。

但这些都比较困难，在赛场上更实用的方法是通过时间复杂度较劣的算法对

的每个点值进行打表，观察差分数组可以直接发现凸性。

考虑证明凸性。

本例题中，生成树与边的加法表示加入一条边，减法表示删除一条边。

数与边的加法表示加上这条边的边权，减法表示减去这条边的边权。

不妨设边权均不相同。

对于存在边权相同的情况，我们可以对每条边加上一个互不相同的值，且这些值远小于

inline">\(\frac{1}{n}\)。

回答原问题时我们只取整数部分，这些值不会影响整数部分，但每条边的权值就互不相同了。

我们首先证明一个引理（为了方便记忆，我将其称作生成树交换引理）：设

inline">\(e=(u,v)\)，

class="math

inline">\(V_1,V_2\)，因此存在

inline">\(T'=T_{m+1}-e+f\)

inline">\(T''=T_{m-1}+e-f\)

inline">\(v(T_{m+1})-e+f=v(T')\ge

v(T_m),v(T_{m-1})+e-f=v(T'')\ge

inline">\(v(T_{m+1})+v(T_{m-1})\ge2v(T_m)\)。

满足上凸函数的定义。

若

inline">\(v(T_{m+1})-e+f=v(T')\ge

v(T_{m+1}),v(T_{m-1})+e-f=v(T'')\ge

inline">\(e=f\)，与边权均不相同矛盾，故不存在这种情况。

我们便证明了凸性。

使用

inline">\(\text{mid}\)，把所有白边边权减

算法，这样我们可以把黑白边内部先排好序，再直接归并，一次判定的复杂度就做到了

inline">\(O(m\alpha(m))\)。

Kruskal

细节的话多点共线返回最有可能满足二分条件的白边数量；值域的话直接设成边权最大值的正负，因为调整一条边只会使至多一条边只能在此次调整中变化，所以全设成最大边权一定会尽量不选，因为全设成最大边权的负数一定会尽量选，恰好切在第一个点和最后一个点。

n,m,k,u,v,d,c,f[200000],cw=0,cb=0,sum=0;
bool
p=getf(x),q=getf(y);if(p!=q)f[q]=p;
}long
i=1;i<=cw;i++)ew[i].d-=mid;long
long
i=1;i<=m;i++){while(getf(ew[nw].u)==getf(ew[nw].v)&&nw<=cw)nw++;while(getf(eb[nb].u)==getf(eb[nb].v)&&nb<=cb)nb++;if(nw<=cw&&(ew[nw].d<=eb[nb].d||nb>cb))sum+=ew[nw].d,merge(ew[nw].u,ew[nw].v),cnt++,nw++;else
sum+=eb[nb].d,merge(eb[nb].u,eb[nb].v),nb++;}for(int
i=1;i<=cw;i++)ew[i].d+=mid;return
cnt;
{scanf("%lld%lld%lld",&n,&m,&k);for(int
i=1;i<=m;i++){scanf("%lld%lld%lld%lld",&u,&v,&d,&c);u++,v++;if(c==0)ew[++cw].u=u,ew[cw].v=v,ew[cw].d=d;else
if(c==1)eb[++cb].u=u,eb[cb].v=v,eb[cb].d=d;}sort(ew+1,ew+cw+1,cmp),sort(eb+1,eb+cb+1,cmp);long
long
l=-100,r=100,ans=0;while(l<=r){long
long
mid=(l+r)>>1,now=check(mid);if(now>=k)ans=mid,r=mid-1;else
l=mid+1;}check(ans);printf("%lld\n",sum+ans*k);return

由于选择的多少条白边是我们二分过程算出来的，不是我们直接二分的东西，因此不可以通过二分有没有找到答案或找到的答案等不等于

首先原图不连通一定无解。

我们值域取边权最大值的正负可以切到第一个点和最后一个点，因此我们先直接通过

}e[600000],e1[600000],e2[600000],e3[600000];

int

n,m,s,k,cnt=0,cl=0,cr=0,fa[60000];

bool

{if(a.d==b.d){if(a.u==s||a.v==s)return

0;return

p=getf(x),q=getf(y);if(p!=q)fa[q]=p;

}long

i=1;i<=n;i++)fa[i]=i;for(int

i=1;i<=m;i++)if(e[i].u==s||e[i].v==s)e1[++cnt1]=e[i],e1[cnt1].d-=mid;else

e2[++cnt2]=e[i];merge(e1+1,e1+cnt1+1,e2+1,e2+cnt2+1,e3+1,cmp);long

long

i=1;i<=m;i++)if(getf(e3[i].u)!=getf(e3[i].v)){merge(e3[i].u,e3[i].v),ans+=e3[i].d;if(e3[i].u==s||e3[i].v==s)cnt++;}k=cnt;return

ans;

{scanf("%d%d%d%d",&n,&m,&s,&k);for(int

i=1;i<=n;i++)fa[i]=i;for(int

i=1;i<=m;i++){scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].d);merge(e[i].u,e[i].v);}for(int

i=2;i<=n;i++)if(getf(i)!=getf(i-1)){printf("Impossible\n");return

0;}sort(e+1,e+m+1,cmp),check(1e9,cr),check(-1e9,cl);if(k<cl||k>cr)printf("Impossible\n");else{int

l=-5e4,r=5e4,ans=0;while(l<=r){int

mid=(l+r)>>1;check(mid,cnt);if(cnt<=k)ans=mid,l=mid+1;else

r=mid-1;}printf("%lld\n",check(ans,cnt)+k*ans);}return

display">\[f_{i,j}=\min_{k=0}^{i-1}\{f_{k,j-1}+w(k+1,i)\}

class="math

【9】决策单调性学习笔记。

这种情况下，有一个通用的方法可以证明

inline">\(g(k)=f_{n,k}\)

---

inline">\([a_1,b_1],[a_2,b_2]\dots[a_{k-1},b_{k-1}]\)，

class="math

inline">\([c_1,d_1],[c_2,d_2]\dots[c_{k+1},d_{k+1}]\)。

显然

inline">\(g(k-1)=\sum_{i=1}^{k-1}w(a_i,b_i),g(k+1)=\sum_{i=1}^{k+1}w(c_i,d_i)\)。

由于

inline">\(a_j=b_{j-1}+1,c_{j+1}=d_j+1\)，且由最小性有

inline">\([a_1,b_1]\dots[a_{j-1},b_{j-1}],[a_{j},d_{j+1}],[c_{j+2},d_{j+2}]\dots[c_{k+1},d_{k+1}]\)

inline">\([c_1,d_1]\dots[c_j,d_j],[c_{j+1},b_j],[a_{j+1},b_{j+1}]\dots[a_{k-1},b_{k-1}]\)，注意到这是两个长度为

的划分方案。

将两种方案加起来，利用最小性可以得到如下式子。

display">\[2g(k)\le(\sum_{i=1}^{j-1}w(a_i,b_i))+(\sum_{i=j+2}^{k+1}w(c_i,d_i))+(\sum_{i=1}^{j}w(c_i,d_i))+(\sum_{i=j+1}^{k-1}w(a_i,b_i))+w(a_j,d_{j+1})+w(c_{j+1},b_{j})

inline">\(w(a_j,d_{j+1})+w(c_{j+1},b_{j})\le

w(a_j,b_{j})+w(c_{j+1},d_{j+1})\)。

放缩并整理，满足上凸函数的定义，结论得证。

display">\[2g(k)\le(\sum_{i=1}^{k-1}w(a_i,b_i))+(\sum_{i=1}^{k+1}w(c_i,d_i))=g(k-1)+g(k+1)

\]