去年、今年的这个日子心情都格外沮丧，

不是因为考的好不好，

而是因为你们要走了，

对于一位不是班主任的副科老师而言，

能和你们一起经历一年半的时间，这种经历尤为珍贵，

教育只是一种媒介，

成绩不是最终的目的，

最终影响我们一生的，是透过这种媒介，在追逐目的过程中所产生的思想、情感的共鸣，

今天目送你们退役，

希望你们能开开心心回到教室，

省一就算拿到了也无法让你们永远开心，

这只是当前阶段的最优子问题，

继续DP下去吧，

前方才是最精彩的，

欢迎你们经常回来！

Shaun Han

【5月27日—6月2日】

• 周三讲dp中的区间dp，提前看一看以下题目，本周要完成下列题目：

  • Zuma https://www.luogu.org/problemnew/show/CF607B
  • 石子合并 https://www.luogu.org/problemnew/show/P1880
  • 能量项链 https://www.luogu.org/problemnew/show/P1063
  • 凸多边形的划分 https://loj.ac/problem/10149
  • 祖玛 https://www.luogu.org/problemnew/show/P2145
  • 合唱队 https://www.luogu.org/problemnew/show/P3205
  • 字符串折叠 https://www.luogu.org/problemnew/show/P4302

• 每天坚持打1个模板
• 周六上午测试

下载链接

提取码：8ds3

OJ自测：380，381，382

p2678 rock 跳石头

#include<bits/stdc++.h>
using namespace std;
int L, N, M, a[50050], ans;
int s=1000000001, t;
int main()
{
    cin>>L>>N>>M;
    for(int i=1; i<=N; i++)
    {
        cin>>a[i];
        s=min(s, a[i]-a[i-1]);        //统计答案的下界 
    }
    t=L/(N-M+1);                    //计算答案的上界 
    while(s<=t)                        //在[s,t]范围内折半查找 
    {
        int m=(s+t)>>1;
        int cnt=M, pre=a[0];
        for(int i=1; i<=N; i++)
        {
            if((a[i]-pre)<m)        //跨度不够，移石头 
                cnt--;
            else
                pre=a[i];
        }
        if(cnt>=0)    s=m+1, ans=m;    //当前m可行，在右边查找 
        else        t=m-1;            //当前m不行，在左边查找 
    }
    if(!N)    cout<<L<<endl;            //一个坑，边界情况，N==0 
    else    cout<<ans<<endl;
    return 0;
}

p5021 road 赛道修建

#include<bits/stdc++.h>
using namespace std;
int n, m, s=0x7fffffff, t, head[50001], tot, ans, sum;
int fa[50001], c[50001];
struct edge
{
    int to, val, next;
}E[100001];
void add(int x, int y, int z)
{
    E[++tot].to=y;
    E[tot].val=z;
    E[tot].next=head[x];
    head[x]=tot;
}
void dfs(int x)
{
    for(int i=head[x]; i; i=E[i].next)
    {
        int y=E[i].to;
        if(y==fa[x]) continue;
        fa[y]=x;
        dfs(y);
    }
}
int dfs2(int x, int mid)
{

    int ans=0;
    multiset<int> tj;
    for(int i=head[x]; i; i=E[i].next)
    {
        int y=E[i].to;
        if(y==fa[x]) continue;
        ans+=dfs2(y, mid);
        if(c[y]+E[i].val>=mid)     ans++;
        else                    tj.insert(c[y]+E[i].val);
    }
    c[x]=0;
    while(!tj.empty())
    {
        int u=*tj.begin();
        tj.erase(tj.begin());
        multiset<int>::iterator p=tj.lower_bound(mid-u);
        if(p==tj.end())
        {
            c[x]=u;
        }
        else
        {
            tj.erase(p);
            ans++;
        }
    }
    tj.clear();
    return ans;
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<n; i++)
    {
        int a, b, l;
        scanf("%d%d%d", &a, &b, &l);
        add(a, b, l);
        add(b, a, l);
        s=min(s, l);
        sum+=l;
    }
    t=sum/m;
    fa[1]=1;
    dfs(1);
    while(s<=t)
    {
        memset(c, 0, sizeof(c));
        int mid=(s+t)>>1;
        if(dfs2(1, mid)>=m)
        {
            ans=mid;
            s=mid+1;
        }
        else t=mid-1;
    }
    printf("%d\n", ans);
    return 0;
}

0302Week01自测T1

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
long long a[1000010], n, K, ans1, ans2;
priority_queue<long long, vector<long long>, less<long long> > Q;
int main()
{
    freopen("jkl.in", "r", stdin);
    freopen("jkl.out", "w", stdout);
    scanf("%lld%lld", &n, &K);
    for(int i=0; i<n; i++)    scanf("%lld", &a[i]), Q.push(a[i]);
    sort(a, a+n);

    for(int i=0, k2=K; k2; i++)
    {
        if(a[i])
        {
            if(k2<=a[i])    ans1+=((a[i]+a[i]-k2+1)*k2/2), k2=0;
            else            ans1+=((a[i]+1)*a[i]/2), k2-=a[i];
        }
    }
    for(int i=1, t; i<=K; i++)
    {
        t=Q.top();
        ans2+=t;
        Q.pop();
        Q.push(t-1);
    }
    printf("%lld %lld\n", ans2, ans1);
    return 0;
}

0302Week01自测T2

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll n, m, st[100005][65];

int main()
{
    freopen("walk.in", "r", stdin);
    freopen("walk.out", "w", stdout);
    scanf("%lld%lld", &n, &m);
    for(ll i=1; i<=n; i++)    scanf("%lld", &st[i][0]);
    for(ll k=1; k<=60; k++)
        for(ll i=1; i<=n; i++)
            st[i][k]=st[st[i][k-1]][k-1];
    for(ll i=1; i<=m; i++)
    {
        ll a, b;
        scanf("%lld%lld", &a, &b);
        for(int i=0; i<63; i++)
        {
            if(b&1) a=st[a][i];
            b>>=1;
        }
        printf("%lld\n", a);
    }
    return 0;
}

0302Week01自测T3

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=4e4+5, maxm=2e5+5;
int N, M, mst[maxn], f[maxn], ans;
double tot, avg, min_ans=1e30, dis[maxn], sum[maxn];
struct item
{
    int u, v;
    double d;
    item(int x, int y, double z){u=x, v=y, d=z;}
    friend bool operator<(const item &A, const item &R){ return A.d>R.d; }
};
struct edge
{
    int t; double w; edge * nxt;
    edge(int to, double len, edge * next)
    {
        t=to, w=len, nxt=next;
    }
};
edge *h1[maxn], *h2[maxn];
void add1(int u, int v, double len)
{
    h1[u]=new edge(v, len, h1[u]);
}
void add2(int u, int v, double len)
{
    h2[u]=new edge(v, len, h2[u]);
}
double prim(int x)
{
    memset(dis, 0x7f, sizeof(dis));
    priority_queue<item, vector<item>, less<item> > Q;
    double ret=0;
    int    num=1;
    mst[x]=1;
    for(edge * p=h1[x]; p; p=p->nxt)
        if(p->t!=x) Q.push(item(x, p->t, p->w)), dis[p->t]=min(dis[p->t], p->w);
    while(!Q.empty() && num!=N)
    {
        while(!Q.empty() && mst[Q.top().v])    Q.pop();
        if(Q.empty()) break;
        int t=Q.top().v;
        mst[t]=true, ret+=Q.top().d, num++;
        add2(Q.top().u, Q.top().v, Q.top().d);
        add2(Q.top().v, Q.top().u, Q.top().d);
        Q.pop();
        for(edge *p=h1[t]; p; p=p->nxt)
            if(!mst[p->t] && dis[p->t]>p->w)    Q.push(item(t, p->t, p->w));
    }
    return ret;
}
void dfs(int x)
{
    sum[x]=0;
    for(edge *p=h2[x]; p; p=p->nxt)
    {
        if(p->t==f[x]) continue;
        f[p->t]=x;
        dfs(p->t);
        sum[x]=sum[x]+p->w+sum[p->t]; 
    }
}
int main()
{
    freopen("mokou.in", "r", stdin);
    freopen("mokou.out", "w", stdout); 
    scanf("%d%d", &N, &M);
    for(int i=1, u, v; i<=M; i++)
    {
        double len;
        scanf("%d%d%lf", &u, &v, &len);
        add1(u, v, len), add1(v, u, len);
    }
    tot=prim(1);                            //求MST 
    dfs(1);                                 //dfs求子树路径和 
    for(int i=1; i<=N; i++)                    //枚举每一个路口求权值 
    {
        double e=0, t_sum=0;
        vector<double> t;
        for(edge *p=h2[i]; p; p=p->nxt)
        {
            if(p->t==f[i]) continue;
            t.push_back(sum[p->t]+p->w);
            t_sum+=sum[p->t]+p->w;
        }
        if(tot-t_sum>0)    t.push_back(tot-t_sum);
        avg=tot/(t.size()+1);                //求平均值和方差 
        for(int j=0; j<t.size(); j++)    e+=((t[j]-avg)*(t[j]-avg));
        if(e<min_ans) min_ans=e, ans=i;
    }
    printf("%d\n", ans);
    return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MS=500050;
struct edge { int t; edge * nxt; edge(int to, edge * next){ t=to, nxt=next; } };
edge * h[MS];
int n, m, f[MS], q[MS], cnt, sp, spi, inc[MS], pmax[MS], tmax[MS];
void add(int u, int v) { h[u]=new edge(v, h[u]); }
void dfs1(int x)
{
    q[++cnt]=x;
    inc[x]=1;
    for(edge * p=h[x]; p && !sp; p=p->nxt)
    {
        if(p->t==f[x])     continue;
        if(inc[p->t])    sp=p->t;
        else            f[p->t]=x, dfs1(p->t);
    }
    if(!sp)    inc[x]=0, cnt--;
}
int clearINC(){ int i=1; while(q[i]!=sp) inc[q[i++]]=0; return i; }
void cut(int u, int v)
{
    edge * p=h[u];
    if(h[u]->t==v) h[u]=h[u]->nxt; else { while(p->nxt->t!=v) p=p->nxt; p->nxt=p->nxt->nxt; } 
}
void dfs3(int x)
{
    //cout<<"here: "<<x<<endl;
    int nextx;
    tmax[x]=inc[x]?0:x;
    for(edge *p=h[x]; p; p=p->nxt)
    {
        if(p->t==f[x])     continue;
        if(inc[p->t])    { nextx=p->t; continue; }
        f[p->t]=x;
        dfs3(p->t);
        tmax[x]=max(tmax[x], tmax[p->t]);
    }
    if(inc[x])
    {
        pmax[x]=tmax[f[x]];
        if(pmax[x]<x) pmax[x]=pmax[f[x]];
        //cout<<"Pmax:"<<pmax[x]<<"  nextx:"<<nextx<<"   tmax:"<<" "<<tmax[x]<<endl;
        if((nextx<x || nextx<tmax[x] || (nextx>tmax[x] && nextx<pmax[x]))&&nextx!=sp) f[nextx]=x, dfs3(nextx);
        else cut(x, nextx), cut(nextx, x);
    }
}
void findAndCut(int x)
{
    memset(f, 0, sizeof(f));
    if(q[spi+1]<q[cnt]) f[q[spi+1]]=sp, tmax[sp]=q[cnt], dfs3(q[spi+1]);    else f[q[cnt]]=sp, tmax[sp]=q[spi+1], dfs3(q[cnt]);
}
void dfs2(int x)
{
    printf("%d ", x);
    int c=0, temp[MS];
    for(edge * p=h[x]; p; p=p->nxt) if(p->t!=f[x]) temp[c++]=p->t;
    sort(temp, temp+c);
    for(int i=0; i<c; i++)    f[temp[i]]=x, dfs2(temp[i]);
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++){ int u, v; scanf("%d%d", &u, &v); add(u, v); add(v, u); }
    if(n==m){ f[1]=1; dfs1(1); spi=clearINC(); findAndCut(1); }
    memset(f, 0, sizeof(f));
    f[1]=1;
    dfs2(1);
    return 0;
}