运维开发网

[补档]noip2019集训测试赛(十一)

运维开发网 https://www.qedev.com 2020-07-17 14:00 出处:网络 作者:运维开发网整理
Problem A: 管道(pipe) Time Limit: 1000 ms Memory Limit: 512 MB Description 给你一个城市下水道网络图,你需要选出一些管道,使得在只使用这些管道的情况下,令整个网络联通,并且花费最小。 网络图可以看做是无向连通图,有n个节点和m条边,每条边连接ui和vi,选择的花费是wi。 不巧的是,由于某些原因,现在市政局要求选定某条特定的边管

Problem A: 管道(pipe)

Time Limit: 1000 ms Memory Limit: 512 MB

Description

给你一个城市下水道网络图,你需要选出一些管道,使得在只使用这些管道的情况下,令整个网络联通,并且花费最小。

网络图可以看做是无向连通图,有n个节点和m条边,每条边连接ui和vi,选择的花费是wi。

不巧的是,由于某些原因,现在市政局要求选定某条特定的边管道,你的任务是求出对于某一条边,在选择这条管道的前提下的最小花费。

Input

第1行包含两个整数n,m,表示点数和边数。

第2~m+1行每行三个整数ui,vi,wi,表示有一条管道连接ui和vi,费用为wi。

Output

输出m行,每行一个整数,表示选择第i条管道的前提下的最小花费。

管道按输入的顺序编号为1~m。

Sample Input

5 7
1 2 3
1 3 1
1 4 5
2 3 2
2 5 3
3 4 2
4 5 4 

Sample Output

9
8
11
8
8
8
9

HINT

对于20%的数据,n<=1000,m<=2000

对于另外20%的数据,m<=n+10

对于100%的数据,2<=n<=100000,1<=m<=200000

保证初始图连通

Solution

几天前的MST的弱化版本???

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct sb{
    int v;
    int w;
    int id;
    int nxt;
}edge[400001];
int cnt=-1;
int head[200001];
void add(int u,int v,int w,int id){
    edge[++cnt].nxt=head[u];
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].id=id;
    head[u]=cnt;
}
struct qwq{
    int u,v,w;
    int id;
}e[400001];
int fa[200001];
bool operator <(qwq a,qwq b){
    return a.w<b.w;
}
int findfa(int x){
    return x==fa[x]?x:fa[x]=findfa(fa[x]);
}
int n,m;
bool vis[200001];
int sum;
void kruskal(){
    for(int i=1;i<=n;++i){
        fa[i]=i;
    }
    sort(e+1,e+1+m);
    int tot=0;
    for(int i=1;i<=m;++i){
        int u=e[i].u,v=e[i].v;
        int x=findfa(u),y=findfa(v);
        if(x!=y){
            vis[i]=true;
            tot++;
            fa[x]=y;
            sum+=e[i].w;
        }
        if(tot==n-1){
            break;
        }
    }
    //cout<<sum<<endl;
    for(int i=1;i<=m;++i){
        if(vis[i]){
            //cout<<e[i].u<<" "<<e[i].v<<" "<<e[i].w<<endl;
            add(e[i].u,e[i].v,e[i].w,e[i].id);
            add(e[i].v,e[i].u,e[i].w,e[i].id);
        }
    }
}
int f[200001][21];
int maxn[200001][21];
int dep[200001];
void dfs(int u,int fa){
    for(int i=1;i<=20;++i){
        f[u][i]=f[f[u][i-1]][i-1];
        maxn[u][i]=max(maxn[u][i-1],maxn[f[u][i-1]][i-1]);
    }
    for(int i=head[u];~i;i=edge[i].nxt){
        int v=edge[i].v,w=edge[i].w,id=edge[i].id;
        if(v!=f[u][0]){
            maxn[v][0]=w;
            f[v][0]=u;
            dep[v]=dep[u]+1;
            dfs(v,u);
        }
    }
}
int LCA(int x,int y,int &lca){
    int ans=0;
    if(dep[x]<dep[y])swap(x,y);
    int depth=dep[x]-dep[y];
    for(int i=0;i<=20;++i){
        if(depth&(1<<i)){
            ans=max(ans,maxn[x][i]);
            x=f[x][i];
        }
    }
    if(x==y){
        lca=x;
        return ans;
    }
    for(int i=20;i>=0;--i){
        if(f[x][i]==f[y][i])continue;
        ans=max(ans,max(maxn[x][i],maxn[y][i]));
        x=f[x][i],y=f[y][i];
    }
    lca=f[x][0];
    ans=max(ans,max(maxn[x][0],maxn[y][0]));
    return ans;
}
int ans[200001];
signed main(){
    //freopen("pipe.in","r",stdin);
    //freopen("ans.out","w",stdout);
    memset(head,-1,sizeof(head));
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%lld%lld%lld",&e[i].u,&e[i].v,&e[i].w);
        e[i].id=i;
    }
    kruskal();
    dep[1]=1;
    dfs(1,-1);
    for(int i=1;i<=m;++i){
        if(vis[i]){
            ans[e[i].id]=sum;
            continue;
        }
        int u=e[i].u,v=e[i].v;
        int lca;
        int maxn=LCA(u,v,lca);
        //cout<<maxn<<endl;
        ans[e[i].id]=sum+e[i].w-maxn;
    }
    for(int i=1;i<=m;++i){
        printf("%lld\n",ans[i]);
    }
}

Problem B: sequence

Time Limit: 2000 ms Memory Limit: 512 MB

Description

给定一个长度为n的由[‘0‘..‘9‘]组成的字符串s,v[i,j]表示由字符串s第i到第j位组成的十进制数字。

将它的某一个上升序列定义为:将这个字符串切割成m段不含前导‘0‘的串,切点分别为k1,k2...km-1,使得v[1,k1]<v[k1+1,k2]<...<v[km-2,km-1]。

请你求出该字符串s的上升序列个数,答案对 10^9+7 取模。

Input

第一行一个整数n,表示字符串长度;

第二行n个[‘0‘..‘9‘]内的字符,表示给出的字符串s。

Output

仅一行表示给出字符串s的上升序列个数对10^9+7取模的值。

Sample Input

6

123434 

Sample Output

8

HINT

对于30%的数据满足:n<=10;

对于100%的数据满足:n<=5000。

Solution

设s(i,j)代表从第i位到第j位的子串

设dp[i][j]代表第一段的开头是第i位,第一段的长度是j~n-i+1的数量

可以得到最后答案是dp[1][1]

状转方程:

$ dp[i][j]=dp[i+j][j] \times [s(i,i+j-1)<s(i+j,i+2 \times j-1)]+dp[i+j][j+1] \times [s(i,i+j-1)>=s(i+j,i+2 \times j+1)]+dp[i][j+1] $

那么考虑怎么\(O(1)\)判断两个子串的大小差别

设a[i][j]代表从第i位开始的子串与从第j位开始的子串的最长相同长度

显然有\(a[i][j]+=a[i+1][j+1] \times [s[i]==s[j]]\)

当然你也可以写后缀数组或哈希表(雾(况且哈希表还是logn的判断)

于是代码如下:

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int dp[5001][5001];
int a[5001][5001];
char s[200001];
bool cmp(int x,int y){
    int l=min(y-x-1,a[x][y]);
    return s[x+l]<s[y+l];
}
int main(){
    int n;
    scanf("%d%s",&n,s+1);
    for(int i=n;i;--i){
        for(int j=i+1;j<=n;++j){
            if(s[i]==s[j])a[i][j]=a[i+1][j+1]+1;
        }
    }
    for(int i=n;i;--i){
        if(s[i]=='0')continue;
        dp[i][n-i+1]=1;
        for(int j=1;j<=n-i;++j){
            if(cmp(i,i+j))dp[i][j]=dp[i+j][j];
            else dp[i][j]=dp[i+j][j+1];
        }
        for(int j=n-i;j;--j){
            dp[i][j]=(dp[i][j]+dp[i][j+1])%mod;
        }
    }
    printf("%d\n",dp[1][1]);
}

Problem C: 颜色(color)

Time Limit: 5000 ms Memory Limit: 512 MB

Description

世界上有n种颜色,每种颜色有着一个美丽度。

现在你有一根分成n段的木棒,分别被涂上了颜色,可以将木棒看做长度为n的颜色序列。一段木棒的美丽度定义为出现的颜色的美丽度之和,如果一种颜色出现了多次,也只被计算一次。

现在你需要回答一些询问,每个询问形如(li,ri),意思是询问木棒上[li,ri]这一段的美丽度。由于世界线收束,有时候某段的颜色会被修改。

注意,由于某些原因,数据被加密了。

Input

第1行包含两个整数n和m,表示木棒的长度和操作个数。

第2行包含n个整数,表示每一段的初始颜色ci。

第3行包含n个整树,表示每种颜色的美丽度wi。

第4~m+3行,每行第1个整数kind。

若kind=1,后面跟两个整数p和c,表示将第p段的颜色改成c。

若kind=2,后面跟两个整数l和r,表示询问[li,ri]的美丽度。

除了kind以外的数均需要异或上一次询问的结果(一开始为0)。

Output

对于每个kind=2的操作,输出一行一个整数,表示[li,ri]的美丽度。

Sample Input

3 3

1 2 3

1 2 3

2 1 3

1 7 4

2 7 5 

Sample Output

6

5

HINT

对于10%的数据,n,m<=1000

对于另外10%的数据,保证所有2操作在1操作之后

对于另外20%的数据,保证wi=1

对于另外10%的数据,n,m<=30000

对于另外10%的数据,n,m<=50000

对于另外10%的数据,n,m<=70000

对于另外10%的数据,n,m<=80000

对于另外10%的数据,n,m<=90000

对于100%的数据,n,m<=100000

Solution

设a[i]为第i位置上的颜色,last(a[i],i)为i的上一个同样颜色为a[i]的位置

我们把每个点的每种颜色抽象成二维坐标系中的一个点,其坐标为\((last(a[x],x)+1,a[x])\)

然后每次查询时,我们查\((1,l)\)到\((l,r)\)矩阵的总和。

于是只有当上一位在l~r前且自己在l~r内我们才会统计

这样就可以避免重复了

树套树维护一下,代码实现不难

#include<bits/stdc++.h>
using namespace std;
set<int> S[200001];
void insert(int x,int v){
    S[x].insert(v);
}
void erase(int x,int v){
    S[x].erase(v);
}
int lst(int x,int v){
    set<int>::iterator i=S[x].lower_bound(v);
    i--;
    return *i;
}
int nxt(int x,int v){
    set<int>::iterator i=S[x].upper_bound(v);
    return i==S[x].end()?-1:*i;
}
struct node{
    int l,r;
    int val;
}t[30000001];
int cnt;
int rt[200001];
void update(int &o,int l,int r,int pos,int val){
    if(!o)o=++cnt;
    if(l==r){
        t[o].val+=val;
        return;
    }
    int mid=(l+r)/2;
    if(pos<=mid)update(t[o].l,l,mid,pos,val);
    else update(t[o].r,mid+1,r,pos,val);
    t[o].val=t[t[o].l].val+t[t[o].r].val;
}
int query(int o,int l,int r,int L,int R){
    if(!o)return 0;
    if(L<=l&&r<=R){
        return t[o].val;
    }
    int mid=(l+r)/2;
    int ret=0;
    if(L<=mid)ret+=query(t[o].l,l,mid,L,R);
    if(mid<R)ret+=query(t[o].r,mid+1,r,L,R);
    return ret;
}
int n,m;
#define lowbit(x) x&-x
void upd(int x,int y,int v){
    while(x<=n){
        update(rt[x],1,n,y,v);
        x+=lowbit(x);
    }
}
int query(int x,int l,int r){
    int ret=0;
    while(x){
        ret+=query(rt[x],1,n,l,r);
        x-=lowbit(x);
    }
    return ret;
}
int a[200001];
int w[200001];
void change(int x,int y){
    int l=lst(a[x],x);
    //cout<<"OK"<<endl;
    upd(l+1,x,-w[a[x]]);
    int n=nxt(a[x],x);
    if(~n){
        upd(x+1,n,-w[a[x]]);
        upd(l+1,n,w[a[x]]);
    }
    erase(a[x],x);
    a[x]=y;
    insert(a[x],x);
    l=lst(a[x],x);
    upd(l+1,x,w[a[x]]);
    n=nxt(a[x],x);
    if(~n){
        upd(l+1,n,-w[a[x]]);
        upd(x+1,n,w[a[x]]);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]),insert(i,0),insert(a[i],i);
    for(int i=1;i<=n;++i)scanf("%d",&w[i]);
    for(int i=1;i<=n;++i)upd(lst(a[i],i)+1,i,w[a[i]]);
    int anss=0;
    for(int i=1;i<=m;++i){
        int opt;
        scanf("%d",&opt);
        if(opt==1){
            int x,y;
            scanf("%d%d",&x,&y);
            x^=anss,y^=anss;
            //cout<<"OK"<<endl;
            change(x,y);
        }
        else {
            int x,y;
            scanf("%d%d",&x,&y);
            x^=anss,y^=anss;
            printf("%d\n",anss=query(x,x,y));
        }
    }
}
0

精彩评论

暂无评论...
验证码 换一张
取 消