施工中。。。

d1t1 字符串

题面

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

题解

考虑两个字符串 \(s_i,s_j(i<j)\) ，实质是 \(s[i+1,\dots j]\) 和 \(s[i,\dots ,j-1]\) 的字符串字典序比较。我们可以对于每个 \(i\) 从后往前线性维护出 \(j>i,s_j\neq s_{j+1}\) 的最小的 \(j\) 和 \(s_j,s_{j+1}\) 大小关系。这样比较两个字符串大小我们就能很容易的判两段字符串是否相等和它们的大小关系。排序即可。复杂度 \(O(n\log n)\) 。

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e6+5;
char s[N];
int comp[N],fst[N],id[N];
bool cmp(int x, int y)
{
    if(x<y)
    {
        if(fst[x]>=y) return true;
        else return comp[x];
    }
    else
    {
        if(fst[y]>=x) return false;
        else return !comp[y];
    }
}
int main()
{
    int n;
    scanf("%d%s",&n,s+1);
    fst[n]=n;
    for(int i=n-1;i;--i)
        if(s[i]!=s[i+1]) fst[i]=i,comp[i]=(s[i+1]<s[i]);
        else fst[i]=fst[i+1],comp[i]=comp[i+1];
    for(int i=1;i<=n;++i) id[i]=i;
    sort(id+1,id+1+n,cmp);
    for(int i=1;i<=n;++i) printf("%d ",id[i]);
}

d1t2 数论

咕咕咕。

d1t3 通信

题意

题解

一眼网络流。暴力建图相信都会。

注意到权值和位置有关，考虑用分治优化建图。对于区间 \([l,r]\) ，我们考虑 \([mid+1,r]\) 内的点向 \([l,mid]\) 内的点连接。我们将 \([l,r]\) 内的点复制一份，按照位置排序后串成一条链。然后 \([mid+1,r]\) 的点由原图上的点连入， \([l,mid]\) 的点连出即可。这样点数和边数都是 \(O(n\log n)\) 级别的。

code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=200005,inf=1<<30;
int a[N],head[N],nxt[N],to[N],wei[N],cost[N],tot=1,n,w,s,t,now,q[N*3];
bool vis[N];
ll dis[N],ans;
void addedge(int u, int v, int w, int c)
{
    nxt[++tot]=head[u], head[u]=tot, to[tot]=v, wei[tot]=w, cost[tot]=c;
    nxt[++tot]=head[v], head[v]=tot, to[tot]=u, wei[tot]=0, cost[tot]=-c;
}
bool spfa()
{
    memset(vis,false,sizeof(int)*(now+1));
    memset(dis,0x3f,sizeof(ll)*(now+1));
    int l=0,r=0;
    q[0]=t,dis[t]=0;
    while(l<=r)
    {
        int u=q[l++]; vis[u]=false;
        for(int e=head[u];e;e=nxt[e])
            if(wei[e^1]&&dis[to[e]]>dis[u]-cost[e])
            {
                dis[to[e]]=dis[u]-cost[e];
                if(!vis[to[e]]) vis[to[e]]=true,q[++r]=to[e];
            }
    }
    return dis[s]!=dis[0];
}
int dfs(int u, int mx)
{
    vis[u]=true;
    if(u==t) return mx;
    int l=mx;
    for(int e=head[u];l&&e;e=nxt[e])
        if(!vis[to[e]]&&wei[e]>0&&dis[to[e]]==dis[u]-cost[e])
        {
            int f=dfs(to[e],min(l,wei[e]));
            ans+=1ll*f*cost[e];
            l-=f,wei[e]-=f,wei[e^1]+=f;
        }
    return mx-l;
}
int tmp[N];
void solve(int l, int r)
{
    if(l==r) return ;
    int mid=l+r>>1;
    solve(l,mid),solve(mid+1,r);
    int t=0;
    for(int i=l;i<=r;++i) tmp[++t]=a[i];
    sort(tmp+1,tmp+1+t);
    for(int i=2;i<=t;++i)
    {
        addedge(now+i,now+i-1,inf,tmp[i]-tmp[i-1]);
        addedge(now+i-1,now+i,inf,tmp[i]-tmp[i-1]);
    }
    for(int i=l;i<=mid;++i)
    {
        int x=lower_bound(tmp+1,tmp+t+1,a[i])-tmp;
        addedge(now+x,i+n,1,0);
    }
    for(int i=mid+1;i<=r;++i)
    {
        int x=lower_bound(tmp+1,tmp+t+1,a[i])-tmp;
        addedge(i,now+x,1,0);
    }
    now+=t;
}
int main()
{
    scanf("%d%d",&n,&w);
    s=2*n+1,t=now=s+1;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        addedge(s,i,1,0);
        addedge(i,t,1,w);
        addedge(i+n,t,1,0);
    }
    solve(1,n);
    while(spfa())
        do {
            memset(vis,false,sizeof(vis));
            dfs(s,inf);
        } while(vis[t]);
    printf("%lld",ans);
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄