头像

whsstory


访客:32181

离线:5小时前


活动打卡代码 AcWing 233. 换教室

whsstory
5小时前
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
typedef long long ll;
typedef unsigned un;
typedef std::string str;
typedef std::pair<ll,ll> pll;
typedef std::pair<int,int> pii;
typedef std::pair<double,double> pd;
ll read(){ll x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return f*x;}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
void umax(int& a,int t){if(t>a)a=t;}
bool umin(ll& a,ll t){if(t<a)return a=t,1;return 0;}
#define MAXN 2011
#define MAXV 511
ll dis[MAXV][MAXV],a[MAXN],b[MAXN];
double f[MAXN][MAXN][2],p[MAXN];
void Floyd(int n)
{
    for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)umin(dis[i][j],dis[i][k]+dis[k][j]);
}
int main()
{
    memset(dis,0x3f,sizeof dis);
    int n=read(),m=read(),v=read(),e=read();
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=n;++i)b[i]=read();
    for(int i=1;i<=v;++i)dis[i][i]=0;
    for(int i=1;i<=n;++i)scanf("%lf",&p[i]);
    while(e--)
    {
        int u=read(),v=read();ll w=read();
        umin(dis[u][v],w),umin(dis[v][u],w);
    }
    Floyd(v);
    for(int i=1;i<=n;++i)
        for(int j=0;j<=m;++j)f[i][j][0]=f[i][j][1]=1e18;
    f[1][0][0]=0,f[1][1][1]=0;
    for(int i=2;i<=n;++i)
    {
        f[i][0][0]=f[i-1][0][0]+dis[a[i-1]][a[i]];
        for(int j=1;j<=min(i,m);++j)
        {
            f[i][j][0]=std::min(f[i-1][j][0]+dis[a[i-1]][a[i]],f[i-1][j][1]+p[i-1]*dis[b[i-1]][a[i]]+(1-p[i-1])*dis[a[i-1]][a[i]] );
            f[i][j][1]=std::min(
                f[i-1][j-1][0]+p[i]*dis[a[i-1]][b[i]]+(1-p[i])*dis[a[i-1]][a[i]],
                f[i-1][j-1][1]+p[i-1]*p[i]*dis[b[i-1]][b[i]]+p[i-1]*(1-p[i])*dis[b[i-1]][a[i]]+(1-p[i-1])*p[i]*dis[a[i-1]][b[i]]+(1-p[i-1])*(1-p[i])*dis[a[i-1]][a[i]]
            );
        }
    }
    double ans=1e28;
    for(int j=0;j<=m;++j)ans=std::min(ans,std::min(f[n][j][0],f[n][j][1]));
    printf("%.2lf",ans);
    return 0;
}


活动打卡代码 AcWing 2280. 最优标号

whsstory
12小时前
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
typedef long long ll;
typedef unsigned un;
//typedef std::string str;
typedef std::pair<ll,ll> pll;
typedef std::pair<int,int> pii;
typedef std::pair<double,double> pd;
ll read(){ll x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return f*x;}
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
void umax(ll& a,ll t){if(t>a)a=t;}
bool umin(ll& a,ll t){if(t<a)return a=t,1;return 0;}
const ll INF=1ll<<58;
#define MAXN 511
#define MAXM 200011
struct edge
{
    ll v,w,nxt;
}e[MAXM<<1|1];
ll cnt=1,last[MAXN],cur[MAXN],dep[MAXN];
void add_directed_edge(ll u,ll v,ll w){e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=last[u],last[u]=cnt;}
void adde(ll u,ll v,ll w){add_directed_edge(u,v,w),add_directed_edge(v,u,0);}
bool bfs(ll s,ll t,ll n)
{
    for(ll i=1;i<=n;++i)cur[i]=last[i],dep[i]=0;
    std::queue<ll>q;
    dep[s]=1,q.push(s);
    while(q.size())
    {
        ll u=q.front();q.pop();
        for(ll i=last[u];i;i=e[i].nxt)
        {
            ll v=e[i].v;
            if(e[i].w&&!dep[v])dep[v]=dep[u]+1,q.push(v);
        }
    }
    return dep[t]>0;
}
ll ex_flow(ll u,ll t,ll flow=INF)
{
    if(u==t)return flow;
    ll f=0;
    for(ll& i=cur[u];i;i=e[i].nxt)
    {
        ll v=e[i].v;
        if(dep[v]==dep[u]+1&&e[i].w)
        {
            ll tmp=ex_flow(v,t,min(e[i].w,flow-f));
            e[i].w-=tmp,e[i^1].w+=tmp;
            f+=tmp;
            if(f==flow)return f;
        }
    }
    return f;
}
ll Dinic(ll s,ll t,ll n)
{
    ll res=0;
    while(bfs(s,t,n))res+=ex_flow(s,t);
    return res;
}

ll n,m,p[MAXN],S,T;
pll a[MAXM];
ll calc(ll x)
{
    cnt=1;for(int i=1;i<=T;++i)last[i]=0;
    for(int i=1;i<=m;++i)adde(a[i].first,a[i].second,1),adde(a[i].second,a[i].first,1);
    for(int i=1;i<=n;++i)
        if(p[i]>=0)
        {
            if(p[i]&(1ll<<x))adde(i,T,INF);
            else adde(S,i,INF);
        }
    return Dinic(S,T,T);
}
int main()
{
    n=read(),m=read();S=n+1,T=S+1;
    memset(p,-1,sizeof p);
    for(int i=1;i<=m;++i)a[i].first=read(),a[i].second=read();
    ll k=read(),ans=0;
    while(k--){ll x=read(),val=read();p[x]=val;}
    for(int i=0;i<31;++i)ans+=calc(i)*(1ll<<i);
    printf("%lld\n",ans);
    return 0;
}



whsstory
13小时前

网络战争

注:如果Latex挂掉了请告知我,或者用typora/vscode打开

求一个平均权值最小的割集。

考虑分数规划。存在一个平均值不大于$x$的割集等价于:
$$
\exists C,\dfrac{\sum_{e\in C}w(e)}{|C|}\le x
$$

$$
\Rightarrow \exists C,\sum_{e\in C}(w(e)-x)\le 0
$$

故 存在一个平均值不大于$x$的割集$\Leftrightarrow$将边权全部减少$x$后,最小割权值不超过0.二分答案+最大流 即可。

注意图中会出现负权边,没法直接最大流,但最小割中必然包含所有负权边,提前选上即可。

浮点数最大流真毒瘤啊

struct one{int u,v,w;}e2[MAXM];
int n,m,S,T;
bool check(double k)
{
    cnt=1;
    for(int i=1;i<=n;++i)last[i]=0;
    double sum=0;
    for(int i=1;i<=m;++i)
        if(e2[i].w<=k)sum+=e2[i].w-k;
        else adde(e2[i].u,e2[i].v,e2[i].w-k),adde(e2[i].v,e2[i].u,e2[i].w-k);
    return Dinic(S,T,n)+sum<=0;
}
int main()
{
    n=read(),m=read(),S=read(),T=read();
    for(int i=1;i<=m;++i)e2[i].u=read(),e2[i].v=read(),e2[i].w=read();
    double l=0,r=1e7;
    while(r-l>2e-3)
    {
        double mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid;
    }
    printf("%.2lf",l);
    return 0;
}


活动打卡代码 AcWing 2279. 网络战争

whsstory
13小时前
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
typedef long long ll;
typedef unsigned un;
//typedef std::string str;
typedef std::pair<ll,ll> pll;
typedef std::pair<int,int> pii;
typedef std::pair<double,double> pd;
ll read(){ll x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return f*x;}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
void umax(ll& a,ll t){if(t>a)a=t;}
bool umin(ll& a,ll t){if(t<a)return a=t,1;return 0;}
const double INF=1e18;
#define MAXN 100011
#define MAXM 200011
struct edge{int v,nxt;double w;}e[MAXM<<1|1];
int cnt=1,last[MAXN];
void adde(int u,int v,double w)
{
    e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=last[u],last[u]=cnt;
    e[++cnt].v=u,e[cnt].w=0,e[cnt].nxt=last[v],last[v]=cnt;
}

int cur[MAXN],dep[MAXN];
bool bfs(int s,int t,int n)
{
    for(int i=1;i<=n;++i)cur[i]=last[i],dep[i]=0;
    std::queue<int>q;
    q.push(s);dep[s]=1;
    while(q.size())
    {
        int u=q.front();q.pop();
        for(int i=last[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(!dep[v]&&e[i].w>0)dep[v]=dep[u]+1,q.push(v);
        }
    }
    return dep[t]>0;
}
double ex_flow(int u,int t,double flow=INF)
{
    if(u==t)return flow;
    double f=0;
    for(int& i=cur[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(dep[v]==dep[u]+1&&e[i].w>0)
        {
            double tmp=ex_flow(v,t,std::min(e[i].w,flow-f));
            f+=tmp,e[i].w-=tmp,e[i^1].w+=tmp;
            if(f==flow)return f;
        }
    }
    return f;
}
double Dinic(int s,int t,int n)
{
    double res=0;
    while(bfs(s,t,n))res+=ex_flow(s,t);
    return res;
}
struct one{int u,v,w;}e2[MAXM];
int n,m,S,T;
bool check(double k)
{
    cnt=1;
    for(int i=1;i<=n;++i)last[i]=0;
    double sum=0;
    for(int i=1;i<=m;++i)
        if(e2[i].w<=k)sum+=e2[i].w-k;
        else adde(e2[i].u,e2[i].v,e2[i].w-k),adde(e2[i].v,e2[i].u,e2[i].w-k);
    return Dinic(S,T,n)+sum<=0;
}
int main()
{
    n=read(),m=read(),S=read(),T=read();
    for(int i=1;i<=m;++i)e2[i].u=read(),e2[i].v=read(),e2[i].w=read();
    double l=0,r=1e7;
    while(r-l>2e-3)
    {
        double mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid;
    }
    printf("%.2lf",l);
    return 0;
}



whsstory
13小时前
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
typedef long long ll;
typedef unsigned un;
//typedef std::string str;
typedef std::pair<ll,ll> pll;
typedef std::pair<int,int> pii;
typedef std::pair<double,double> pd;
ll read(){ll x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return f*x;}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
void umax(ll& a,ll t){if(t>a)a=t;}
bool umin(ll& a,ll t){if(t<a)return a=t,1;return 0;}
const int INF=1<<29;
#define MAXN 100011
#define MAXM 200011
struct edge
{
    int v,w,nxt;
}e[MAXM<<1|1];
int cnt=1,last[MAXN],cur[MAXN],dep[MAXN];
void add_directed_edge(int u,int v,int w){e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=last[u],last[u]=cnt;}
void adde(int u,int v,int w){add_directed_edge(u,v,w),add_directed_edge(v,u,0);}
bool bfs(int s,int t,int n)
{
    for(int i=1;i<=n;++i)cur[i]=last[i],dep[i]=0;
    std::queue<int>q;
    dep[s]=1,q.push(s);
    while(q.size())
    {
        int u=q.front();q.pop();
        for(int i=last[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(e[i].w&&!dep[v])dep[v]=dep[u]+1,q.push(v);
        }
    }
    return dep[t]>0;
}
int ex_flow(int u,int t,int flow=INF)
{
    if(u==t)return flow;
    int f=0;
    for(int& i=cur[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(dep[v]==dep[u]+1&&e[i].w)
        {
            int tmp=ex_flow(v,t,min(e[i].w,flow-f));
            e[i].w-=tmp,e[i^1].w+=tmp;
            f+=tmp;
            if(f==flow)return f;
        }
    }
    return f;
}
int Dinic(int s,int t,int n)
{
    int res=0;
    while(bfs(s,t,n))res+=ex_flow(s,t);
    return res;
}

int main()
{
    int n=read(),m=read(),S=read(),T=read();
    for(int i=1;i<=m;++i)
    {
        int u=read(),v=read(),w=read();
        adde(u,v,w);
    }
    printf("%d",Dinic(S,T,n));
    return 0;
}


活动打卡代码 AcWing 2278. 企鹅游行

whsstory
13小时前
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
typedef long long ll;
typedef unsigned un;
//typedef std::string str;
typedef std::pair<ll,ll> pll;
typedef std::pair<int,int> pii;
typedef std::pair<double,double> pd;
ll read(){ll x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return f*x;}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
void umax(ll& a,ll t){if(t>a)a=t;}
bool umin(ll& a,ll t){if(t<a)return a=t,1;return 0;}
const int INF=1<<29;
#define MAXN 511
#define MAXM 200011
struct edge
{
    int v,w,nxt;
}e[MAXM<<1|1],e2[MAXM<<1|1];
int cnt=1,last[MAXN],cur[MAXN],dep[MAXN];
void add_directed_edge(int u,int v,int w){e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=last[u],last[u]=cnt;}
void adde(int u,int v,int w){add_directed_edge(u,v,w),add_directed_edge(v,u,0);}
bool bfs(int s,int t,int n)
{
    for(int i=1;i<=n;++i)cur[i]=last[i],dep[i]=0;
    std::queue<int>q;
    dep[s]=1,q.push(s);
    while(q.size())
    {
        int u=q.front();q.pop();
        for(int i=last[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(e[i].w&&!dep[v])dep[v]=dep[u]+1,q.push(v);
        }
    }
    return dep[t]>0;
}
int ex_flow(int u,int t,int flow=INF)
{
    if(u==t)return flow;
    int f=0;
    for(int& i=cur[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(dep[v]==dep[u]+1&&e[i].w)
        {
            int tmp=ex_flow(v,t,min(e[i].w,flow-f));
            e[i].w-=tmp,e[i^1].w+=tmp;
            f+=tmp;
            if(f==flow)return f;
        }
    }
    return f;
}
int Dinic(int s,int t,int n)
{
    int res=0;
    while(bfs(s,t,n))res+=ex_flow(s,t);
    return res;
}
pii a[MAXN];
double dist(pii a,pii b)
{
    return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}
int main()
{
    int task=read();
    while(task--)
    {
        cnt=1;
        int n=read(),S=n+n+1,T=S+1,sum=0;double d;scanf("%lf",&d);
        for(int i=1;i<=T;++i)last[i]=0;
        for(int i=1;i<=n;++i)
        {
            a[i].first=read(),a[i].second=read();
            int x=read();sum+=x,adde(S,i,x);
            adde(i,n+i,read());
        }
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                if(i!=j&&dist(a[i],a[j])<=d)adde(n+i,j,INF);
        for(int i=2;i<=cnt;++i)e2[i]=e[i];
        bool flag=0;
        for(T=1;T<=n;++T)
        {
            for(int i=2;i<=cnt;++i)e[i]=e2[i];
            if(Dinic(S,T,n+n+2)==sum)flag=1,printf("%d ",T-1);
        }
        if(!flag)puts("-1");
        else puts("");
    }
    return 0;
}



#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
typedef long long ll;
typedef unsigned un;
//typedef std::string str;
typedef std::pair<ll,ll> pll;
typedef std::pair<int,int> pii;
typedef std::pair<double,double> pd;
ll read(){ll x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return f*x;}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
void umax(ll& a,ll t){if(t>a)a=t;}
bool umin(ll& a,ll t){if(t<a)return a=t,1;return 0;}
const int INF=1<<29;
#define MAXN 50011
#define MAXM 200011
struct edge
{
    int v,w,nxt;
}e[MAXM<<1|1];
int cnt=1,last[MAXN],cur[MAXN],dep[MAXN];
void add_directed_edge(int u,int v,int w){e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=last[u],last[u]=cnt;}
void adde(int u,int v,int w){add_directed_edge(u,v,w),add_directed_edge(v,u,0);}
bool bfs(int s,int t,int n)
{
    for(int i=1;i<=n;++i)cur[i]=last[i],dep[i]=0;
    std::queue<int>q;
    dep[s]=1,q.push(s);
    while(q.size())
    {
        int u=q.front();q.pop();
        for(int i=last[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(e[i].w&&!dep[v])dep[v]=dep[u]+1,q.push(v);
        }
    }
    return dep[t]>0;
}
int ex_flow(int u,int t,int flow=INF)
{
    if(u==t)return flow;
    int f=0;
    for(int& i=cur[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(dep[v]==dep[u]+1&&e[i].w)
        {
            int tmp=ex_flow(v,t,min(e[i].w,flow-f));
            e[i].w-=tmp,e[i^1].w+=tmp;
            f+=tmp;
            if(f==flow)return f;
        }
    }
    return f;
}
int Dinic(int s,int t,int n)
{
    int res=0;
    while(bfs(s,t,n))res+=ex_flow(s,t);
    return res;
}
ll a[MAXN],f[MAXN];
ll dp(int n)
{
    ll res=0;
    for(int i=1;i<=n;++i)
    {
        f[i]=1;
        for(int j=1;j<i;++j)
            if(a[j]<=a[i])umax(f[i],f[j]+1);
        umax(res,f[i]);
    }
    return res;
}
int main()
{
    ll n=read(),S=n+n+1,T=S+1;
    for(int i=1;i<=n;++i)a[i]=read(),adde(i,n+i,1);
    ll s=dp(n);
    printf("%lld\n",s);
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
            if(a[i]<=a[j]&&f[i]+1==f[j])adde(n+i,j,1);
    for(int i=1;i<=n;++i)
    {
        if(f[i]==1)adde(S,i,1);
        if(f[i]==s)adde(n+i,T,1);
    }
    int pre=Dinic(S,T,T);
    printf("%d\n",pre);
    if(n==1){printf("%d\n",pre);return 0;}
    adde(1,n+1,INF),adde(n,n+n,INF),adde(S,1,INF);
    if(f[n]==s)adde(n+n,T,INF);
    printf("%d\n",pre+Dinic(S,T,T));
    return 0;
}


活动打卡代码 AcWing 2277. 秘密挤奶机

二分答案,检查最大流是否不小于$T$

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
typedef long long ll;
typedef unsigned un;
//typedef std::string str;
typedef std::pair<ll,ll> pll;
typedef std::pair<int,int> pii;
typedef std::pair<double,double> pd;
ll read(){ll x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return f*x;}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
void umax(ll& a,ll t){if(t>a)a=t;}
bool umin(ll& a,ll t){if(t<a)return a=t,1;return 0;}
const int INF=1<<29;
#define MAXN 50011
#define MAXM 200011
struct edge
{
    int v,w,nxt;
}e[MAXM<<1|1];
int cnt=1,last[MAXN],cur[MAXN],dep[MAXN];
void add_directed_edge(int u,int v,int w){e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=last[u],last[u]=cnt;}
void adde(int u,int v,int w){add_directed_edge(u,v,w),add_directed_edge(v,u,0);}
bool bfs(int s,int t,int n)
{
    for(int i=1;i<=n;++i)cur[i]=last[i],dep[i]=0;
    std::queue<int>q;
    dep[s]=1,q.push(s);
    while(q.size())
    {
        int u=q.front();q.pop();
        for(int i=last[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(e[i].w&&!dep[v])dep[v]=dep[u]+1,q.push(v);
        }
    }
    return dep[t]>0;
}
int ex_flow(int u,int t,int flow=INF)
{
    if(u==t)return flow;
    int f=0;
    for(int& i=cur[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(dep[v]==dep[u]+1&&e[i].w)
        {
            int tmp=ex_flow(v,t,min(e[i].w,flow-f));
            e[i].w-=tmp,e[i^1].w+=tmp;
            f+=tmp;
            if(f==flow)return f;
        }
    }
    return f;
}
int Dinic(int s,int t,int n)
{
    int res=0;
    while(bfs(s,t,n))res+=ex_flow(s,t);
    return res;
}
struct one{int u,v,k;}a[MAXM];
int n,m,t;
bool check(int k)
{
    for(int i=1;i<=n;++i)last[i]=0;
    cnt=1;
    for(int i=1;i<=m;++i)
        if(a[i].k<=k)adde(a[i].u,a[i].v,1),adde(a[i].v,a[i].u,1);
    return Dinic(1,n,n)>=t;
}
int main()
{
    n=read(),m=read(),t=read();
    for(int i=1;i<=m;++i)a[i].u=read(),a[i].v=read(),a[i].k=read();
    int l=1,r=int(1e6);
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    printf("%d",l);
    return 0;
}



看到有人在写这个题,来凑热闹(这题做法很多,只介绍我自己想出的比较套路的做法,那种ST表+二分的做法不好想到)

对于每个询问$[l,r],$以$s(l\le s\le r)$为起点的极长段$[s,s+len_s-1]$的贡献是

  1. $r-s+1(\text{if }s+len-1\ge r)$
  2. $len_s(\text{otherwise})$

又因为$s+len_s-1$单调递增,故考虑将询问离线,按$r$排序降维。维护指针$it$表示最小的$s$满足$s+len_s-1\ge r(r$即为情况1的最优决策),此时$[l,it-1]$中$len$的最大值即为情况2的最优值。

$len_s$可以双指针预处理,$[l,it-1]$中$len$的最大值用线段树维护即可。

时间复杂度$\mathcal O(n+m(\log m+\log n))$,空间线性。

最后有个小疑问,将原数组离散化后慢了近一倍,不知什么原理

#define MAXN 200011
int c[2000011];
int a[MAXN], n;
struct Segment_Tree
{
    int t[MAXN<<2|1];
    #define rt t[num]
    void build(int* arr,un l=1,un r=n,un num=1)
    {
        if(l==r)rt=arr[l];
        else
        {
            un mid=(l+r)>>1;
            build(arr,l,mid,num<<1),build(arr,mid+1,r,num<<1|1);
            rt=max(t[num<<1],t[num<<1|1]);
        }
    }
    int Qmax(un ql,un qr,un l=1,un r=n,un num=1)
    {
        if(ql<=l&&r<=qr)return rt;
        un mid=(l+r)>>1;
        if(qr<=mid)return Qmax(ql,qr,l,mid,num<<1);
        if(ql>mid)return Qmax(ql,qr,mid+1,r,num<<1|1);
        return max(Qmax(ql,qr,l,mid,num<<1),Qmax(ql,qr,mid+1,r,num<<1|1) );
    }
}sgt;
int len[MAXN],ans[MAXN];
struct one
{
    int l,r,dex;
    bool operator <(const one& you)const{return r<you.r;}
}q[MAXN];
int main()
{
    n=read();
    int m=read();
    for(int i=1;i<=n;++i)a[i]=1000000+read();
    int l=1,r=1;
    while(l<=n)
    {
        while(r<=n&&!c[a[r]])c[a[r++]]=1;
        len[l]=r-l;
        c[a[l++]]=0;
    }
    sgt.build(len);
    for(int i=1;i<=m;++i)q[i].l=read()+1,q[i].r=read()+1,q[i].dex=i;
    std::sort(q+1,q+m+1);
    int it=1;
    for(int i=1;i<=m;++i)
    {
        while(it+len[it]-1<q[i].r)++it;
        if(it<=q[i].l)ans[q[i].dex]=q[i].r-q[i].l+1;
        else ans[q[i].dex]=max(sgt.Qmax(q[i].l,it-1),q[i].r-it+1);
    }
    for(int i=1;i<=m;++i)printf("%d\n",ans[i]);
    return 0;
}


活动打卡代码 AcWing 2240. 餐饮

将牛拆点即可。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
typedef long long ll;
typedef unsigned un;
//typedef std::string str;
typedef std::pair<ll,ll> pll;
typedef std::pair<int,int> pii;
typedef std::pair<double,double> pd;
ll read(){ll x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return f*x;}
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
void umax(ll& a,ll t){if(t>a)a=t;}
bool umin(ll& a,ll t){if(t<a)return a=t,1;return 0;}
const ll INF=1ll<<30;
#define MAXN 200011
struct edge
{
    int v,w,nxt;
}e[MAXN<<1|1];
int cnt=1,last[MAXN];
void add_directed_edge(int u,int v,int w)
{
    e[++cnt].v=v,e[cnt].w=w;
    e[cnt].nxt=last[u],last[u]=cnt;
}
void adde(int u,int v,int w){ add_directed_edge(u,v,w),add_directed_edge(v,u,0);}

int cur[MAXN],dep[MAXN];
bool bfs(int s,int t,int n)
{
    for(int i=1;i<=n;++i)cur[i]=last[i],dep[i]=0;
    std::queue<int>q;
    q.push(s),dep[s]=1;
    while(q.size())
    {
        int u=q.front();q.pop();
        for(int i=last[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(e[i].w&&!dep[v])dep[v]=dep[u]+1,q.push(v);
        }
    }
    return dep[t]>0;
}
int ex_flow(int u,int t,int flow=INF)
{
    if(u==t)return flow;
    int f=0;
    for(int &i=cur[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(e[i].w&&dep[v]==dep[u]+1)
        {
            int tmp=ex_flow(v,t,min(e[i].w,flow-f));
            e[i].w-=tmp,e[i^1].w+=tmp;
            f+=tmp;
            if(f==flow)return f;
        }
    }
    return f;
}
int Dinic(int s,int t,int n)
{
    int res=0;
    while(bfs(s,t,n))res+=ex_flow(s,t);
    return res;
}
int main()
{
    int n=read(),F=read(),D=read(),S=n+n+F+D+1,T=S+1;
    for(int i=1;i<=n;++i)
    {
        adde(i,n+i,1);
        int LF=read(),LD=read();
        while(LF--)adde(n+n+read(),i,1);
        while(LD--)adde(n+i,n+n+F+read(),1);
    }
    for(int i=1;i<=F;++i)adde(S,n+n+i,1);
    for(int i=1;i<=D;++i)adde(n+n+F+i,T,1);
    printf("%d",Dinic(S,T,T));
    return 0;
}