寒假集训DAY5考试D2

A. U.N.OWEN就是她吗?

考试时有个费用流的思路,但是爆0了,考后看到有人拿这个得了60分,应该是自己打错了,但看不出来.

题意:n堆石子,每堆石子有ai个,m次指令,每次指令要求把li,ri内的石子拿ki个,如果不够可以全拿,求拿的石子的最大字典序。保证区间互不包含。n=3e5 m=3e5 ai=500 ki=10000

题解:好神的霍尔定理用法啊,没想到它还能这样用...

把指令按照li排序,把每个指令拆成ki个,把每堆石头拆成ai个。设每个指令的答案为B[i],那么用霍尔定理检验的话就是检验是由有完美匹配。

由于题目保证互不包含,因此如果使用霍尔定理的话,原定理:“如果X存在完美匹配,那么对于任意子集|S|和对应的连边集合|T|都有|S|<=|T|。“

就可以将任意子集转化成连续的几个指令,原因:考虑不连续的若干个指令,这里只考虑两个的情况,大于两个的情况可以连续的指令两两间考虑来达到目的。

如果说这两个指令的区间相离,只需要检验分别这两个指令是否合法;

如果两个指令相交,那么由于互不包含的特殊性质,把这两个指令中间的指令加入|S|,|T|不变,这时的条件比原条件更为苛刻。

对于每次指令,是要求所有包含这个指令的区间都符合条件,即

$$\sum\limits_{l=1}^{p[i]}\sum\limits_{r=p[i]}^m sumB[r]-sumB[l-1]<=sumA[R[r]]-sumA[L[l]-1]$$

$$sumB[r]-sumA[R[r]]<=sumB[l-1]-sumA[L[l]-1]$$

线段树上维护每个点最大的sumB[i]-sumA[R[i]]与最小的sumB[i-1]-sumA[L[i]-1],查询时查询max p[i]~m sumB[i]-sumA[R[i]],min 1~p[i] sumB[i-1]-sumA[L[i]-1],再用min-max就是答案。

要和ki取min。

复杂度O(mlog)。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3e5+50;
inline int rd(register int x=0,register char ch=getchar(),register int f=0){
    while(!isdigit(ch)) f=ch==‘-‘,ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-48,ch=getchar();
    return f?-x:x;
}
int n,m;
int a[N],cf[N],ans[N],I[N];
ll sum[N],C[N<<2],D[N<<2],tagC[N<<2],tagD[N<<2],sc[N],sd[N];
struct O{int l,r,id;}dat[N];
bool cmp(O a,O b){return a.l<b.l;}
#define lch k<<1
#define rch k<<1|1
//C维护最小值,D维护最大值
void down(int k){
    if(tagC[k]) C[lch]+=tagC[k],C[rch]+=tagC[k],tagC[lch]+=tagC[k],tagC[rch]+=tagC[k],tagC[k]=0;
    if(tagD[k]) D[lch]+=tagD[k],D[rch]+=tagD[k],tagD[lch]+=tagD[k],tagD[rch]+=tagD[k],tagD[k]=0;
}
void add(int k,int l,int r,int L,int R,int opt,int e){//0是C,1是D 

    if(L>R) return;
    if(L<=l&&r<=R) return opt?(D[k]+=e,tagD[k]+=e):(C[k]+=e,tagC[k]+=e)/*,printf("!%d %d %d %d %d %d %lld %lld\n",l,r,L,R,opt,e,C[k],D[k])*/,void();
    int mid=(l+r)>>1;down(k);
    if(L<=mid) add(lch,l,mid,L,R,opt,e);
    if(R>mid) add(rch,mid+1,r,L,R,opt,e);
    C[k]=min(C[lch],C[rch]),D[k]=max(D[lch],D[rch]);

}
ll g(int opt,ll res,ll querY){return opt?max(res,querY):min(res,querY);}
ll query(int k,int l,int r,int L,int R,int opt){
    if(L<=l&&r<=R) return opt?D[k]:C[k];
    int mid=(l+r)>>1;down(k);
    ll res=opt?-0x3f3f3f3f3f3f3f3f:0x3f3f3f3f3f3f3f3f;
    if(L<=mid) res=g(opt,res,query(lch,l,mid,L,R,opt));
    if(R>mid) res=g(opt,res,query(rch,mid+1,r,L,R,opt));
    return res;
}
void build(int k,int l,int r){
    if(l==r) return C[k]=sc[dat[l].id],D[k]=sd[dat[l].id],void();
    int mid=(l+r)>>1;build(lch,l,mid),build(rch,mid+1,r);
    C[k]=min(C[lch],C[rch]),D[k]=max(D[lch],D[rch]);
}
#undef lch
#undef rch
int main(){
    n=rd();for(int i=1;i<=n;++i) a[i]=rd();m=rd();for(int i=1;i<=m;++i) dat[i].l=rd(),dat[i].r=rd(),ans[i]=rd(),dat[i].id=i,cf[dat[i].l]++,cf[dat[i].r+1]--;
    sort(dat+1,dat+m+1,cmp);for(int i=1;i<=m;++i) I[dat[i].id]=i;
    for(int i=1;i<=n;++i) cf[i]+=cf[i-1],sum[i]=sum[i-1]+(cf[i]>0?a[i]:0);
    for(int i=1;i<=m;++i) sd[i]=-sum[dat[I[i]].r],sc[i]=-sum[dat[I[i]].l-1];
    build(1,1,m);
    for(int i=1;i<=m;++i){
        ll rx=query(1,1,m,I[i],m,1),ln=query(1,1,m,1,I[i],0);
        printf("%d\n",ans[i]=min(0ll+ans[i],ln-rx));
        add(1,1,m,I[i],m,1,ans[i]);add(1,1,m,I[i]+1,m,0,ans[i]);
        //for(int j=1;j<=m;++j) printf("C[%d]=%lld D[%d]=%lld\n",j,query(1,1,m,j,j,0),j,query(1,1,m,j,j,1));puts("");
    }
    return 0;
}

B. 哈德曼的妖怪少女

不会枯了

C. 平安时代的外星人

题意:同圈地游戏。

题解:可以发现(?)最终路线一定不会穿过从起点到每个特殊点的左上端点的最短路,如果穿过就完全可以顺着最短路走。

所以需要找到一条包裹所有最短路的环,使得环长最小。

那么对每个点建出四个点

然后对应的向四周连边

假如说有某条边不能经过,那么它上下(左右)的两个点就不能连边(如上边的边lim=1,则0 3不能连边,表示不能这样走)

注意,特殊点由于不能经过,因此特殊点内部的四个点不能连边。

注意,(1,1)的(0,1),(0,3)不能连边,答案就是s=(1,1,3)t=(1,1,1)的最短路。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=405;
inline int rd(register int x=0,register char ch=getchar(),register int f=0){
    while(!isdigit(ch)) f=ch==‘-‘,ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-48,ch=getchar();
    return f?-x:x;
}
const int sx[4]={0,0,1,-1},sy[4]={1,-1,0,0};
int n,m,B,head[N*N*4],to[N*N*16],nxt[N*N*16],vis[N*N*4],nw[N*N][4],al[N*N][4];
ll s[N][N],dis[N*N],pre[N*N],w[N*N*16];
map<int,int>lim[N*N],a[N*N];
pair<int,int> rem(int x){return make_pair((x-1)/m+1,(x-1)%m+1);}
bool check(int x,int y){return (x<=0||x>n||y<=0||y>m)?0:1;}
int id(int x,int y){return check(x,y)?(x-1)*m+y:0;}
void lnk(int x,int y,int value){if(!x||!y) return ;
    to[++B]=y,nxt[B]=head[x],head[x]=B,w[B]=value;
}
int main(){
    n=rd();m=rd();n++;m++;//点的数量是块的数量+1
    for(int i=1;i<=n-1;++i) for(int j=1;j<=m-1;++j) s[i][j]=rd();
    for(int i=1;i<=n-1;++i) for(int j=1;j<=m;++j) a[id(i,j)][id(i+1,j)]=a[id(i+1,j)][id(i,j)]=rd();
    for(int i=1;i<=n;++i) for(int j=1;j<=m-1;++j) a[id(i,j)][id(i,j+1)]=a[id(i,j+1)][id(i,j)]=rd();
    for(int i=1;i<=n*m;++i) dis[i]=0x3f3f3f3f3f3f3f3f,vis[i]=0;
    priority_queue<pair<ll,int> >q;q.push(make_pair(dis[1]=0,1));
    while(!q.empty()){
        int u=q.top().second;q.pop();
        if(vis[u]) continue;vis[u]=1;
        pair<int,int>A=rem(u);
        for(int i=0,I;i<4;++i) if(check(A.first+sx[i],A.second+sy[i])&&dis[I=id(A.first+sx[i],A.second+sy[i])]>dis[u]+a[u][I]) pre[I]=u,q.push(make_pair(-(dis[I]=dis[u]+a[u][I]),I));
    }
    for(int i=1;i<=n-1;++i) for(int j=1;j<=m-1;++j) if(s[i][j]){
        int I=id(i,j),J;
        while(I!=1) J=pre[I],lim[I][J]=lim[J][I]=1,I=J;
    }
    int tot=0;for(int i=1;i<=n*m;++i) for(int j=0;j<4;++j) nw[i][j]=++tot;

    al[id(1,1)][0]=1;
    for(int i=1;i<=n-1;++i) for(int j=1;j<=m-1;++j) if(s[i][j]) al[id(i,j)][2]=al[id(i+1,j)][3]=al[id(i,j+1)][1]=al[id(i+1,j+1)][0]=1;

    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){
        int I=id(i,j),J;
        if(!al[I][0]&&!al[I][3]&&!lim[I][id(i-1,j)]) lnk(nw[I][0],nw[I][3],0),lnk(nw[I][3],nw[I][0],0);
        if(!al[I][0]&&!al[I][1]&&!lim[I][id(i,j-1)]) lnk(nw[I][0],nw[I][1],0),lnk(nw[I][1],nw[I][0],0);
        if(!al[I][1]&&!al[I][2]&&!lim[I][id(i+1,j)]) lnk(nw[I][1],nw[I][2],0),lnk(nw[I][2],nw[I][1],0);
        if(!al[I][2]&&!al[I][3]&&!lim[I][id(i,j+1)]) lnk(nw[I][2],nw[I][3],0),lnk(nw[I][3],nw[I][2],0);

        if(j-1>=1){J=id(i,j-1);
            if(!al[I][0]&&!al[J][3]) lnk(nw[I][0],nw[J][3],a[J][I]);
            if(!al[I][1]&&!al[J][2]) lnk(nw[I][1],nw[J][2],a[J][I]);
        }
        if(j+1<=m){J=id(i,j+1);
            if(!al[I][3]&&!al[J][0]) lnk(nw[I][3],nw[J][0],a[J][I]);
            if(!al[I][2]&&!al[J][1]) lnk(nw[I][2],nw[J][1],a[J][I]);
        }
        if(i-1>=1){J=id(i-1,j);
            if(!al[I][0]&&!al[J][1]) lnk(nw[I][0],nw[J][1],a[J][I]);
            if(!al[I][3]&&!al[J][2]) lnk(nw[I][3],nw[J][2],a[J][I]);
        }
        if(i+1<=n){J=id(i+1,j);
            if(!al[I][1]&&!al[J][0]) lnk(nw[I][1],nw[J][0],a[J][I]);
            if(!al[I][2]&&!al[J][3]) lnk(nw[I][2],nw[J][3],a[J][I]);
        }
    }

    for(int i=1;i<=tot;++i) dis[i]=0x3f3f3f3f3f3f3f3f,vis[i]=0;
    q.push(make_pair(dis[nw[1][3]]=0,nw[1][3]));
    while(!q.empty()){
        int u=q.top().second;q.pop();
        if(vis[u]) continue;vis[u]=1;
        for(int i=head[u];i;i=nxt[i]) if(dis[to[i]]>dis[u]+w[i]) q.push(make_pair(-(dis[to[i]]=dis[u]+w[i]),to[i]));
    }
    printf("%lld\n",dis[nw[1][1]]);
    return 0;
}

细节还行,打完后一遍过的。

原文地址:https://www.cnblogs.com/hzoi2018-xuefeng/p/12310577.html

时间: 02-15

寒假集训DAY5考试D2的相关文章

FJ省队集训DAY5 T1

思路:考试的时候打了LCT,自以为能过,没想到只能过80.. 考完一想:lct的做法点数是100W,就算是nlogn也会T. 讲一下lct的做法把:首先如果一条边连接的两个点都在同一个联通块内,那么这条边对答案没有影响,可以忽略,因此,问题变成了每次询问两个点中路径上权值最大的边(这里的权值我们令它为加入这条边的时间),边我们用一个点连接两个端点来表示. 正解:由于是无根树,因此我们用并查集按秩合并,每次把小的加到大的里面去,询问的时候暴力走lct查找最大即可. 1 #include<cstdi

寒假集训日志(二)——最小生成树,拓扑排序,欧拉回路,连通路

今天学的内容挺多的. (一)首先说最小生成树,两种算法: 1.Kruskal算法( 将边排序,然后再选,关键在于检查是否连通,使用并查集) 2.Prim算法(使用点集,有点类似与最短路的算法) 第一题是并查集算法的使用: A - The Suspects Time Limit:1000MS     Memory Limit:20000KB     64bit IO Format:%I64d & %I64u Submit Status Description 严重急性呼吸系统综合症( SARS),

(寒假集训)Roadblock(最短路)

Roadblock 时间限制: 1 Sec  内存限制: 64 MB提交: 9  解决: 5[提交][状态][讨论版] 题目描述 Every morning, FJ wakes up and walks across the farm from his house to the barn.  The farm is a collection of N fields (1 <= N <= 250) connected by M bidirectional pathways (1 <= M

(寒假集训)Mooo Moo (完全背包)

Mooo Moo 时间限制: 1 Sec  内存限制: 64 MB提交: 5  解决: 4[提交][状态][讨论版] 题目描述 Farmer John has completely forgotten how many cows he owns!  He is too embarrassed to go to his fields to count the cows, since he doesn't want the cows to realize his mental lapse.  Ins

(寒假集训)Watering the Fields (最小生成树)

Watering the Fields 时间限制: 1 Sec  内存限制: 64 MB提交: 26  解决: 10[提交][状态][讨论版] 题目描述 Due to a lack of rain, Farmer John wants to build an irrigation system to send water between his N fields (1 <= N <= 2000). Each field i is described by a distinct point (x

(寒假集训) 卡片(离散化)

卡片 时间限制: 1 Sec  内存限制: 128 MB提交: 22  解决: 13[提交][状态][讨论版] 题目描述 每个卡片的开头和结尾都有标记,把每张卡片看成数轴上的一条线段,开头和结尾的标记A,B为数轴上的两个点.每张卡片的颜色都不同.将卡片按照标记贴到数轴上,请问贴完卡片以后的数轴上一共有多少种不同的颜色. 输入 第1行:一个整数N,表示卡片的数量. 第2行至第N+1行:第i+1行给出了第i张卡片的头尾两个标记Ai,Bi,贴卡片的顺序与输入文件中出现的先后顺序一致. 输出 一个整数,

寒假集训.Skew Binary

Skew Binary Time Limit:3000MS     Memory Limit:0KB     64bit IO Format:%lld & %llu Submit Status Practice UVA 575 Description When a number is expressed in decimal, the k-th digit represents a multiple of 10k. (Digits are numbered from right to left,

暑假集训day5

今天的主要内容为最小生成树.判负环和差分约束系统 苗条的最小生成树 poj3522 本题排序完枚举最小边,Kruskal跑n遍即可. #include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int INF=0x7fffffff; inline int read(){ int num=0,t=1;char c=getchar(); while(c>'9'||

(寒假集训) 调查

调查 时间限制: 1 Sec  内存限制: 128 MB提交: 30  解决: 10[提交][状态][讨论版] 题目描述 Ezio作为一名刺客,调查情报是必不可少的环节,比如目标最近的活动安排之类的情报还是很有用的. Ezio现在有一份调查列表,上面有n个人,每个人有一个编号,编号在1到m之间,编号记录的是这个人与哪一条情报有关,Ezio现在要调查1到m所有的情报,每条情报只需要调查与该条情报有关的一个人即可,由于时间关系,Ezio想要调查连续的一段人,并且调查的人数尽量少. 输入 共两行,第一

(寒假集训) Piggyback(最短路)

Piggyback 时间限制: 1 Sec  内存限制: 64 MB提交: 3  解决: 3[提交][状态][讨论版] 题目描述 Bessie and her sister Elsie graze in different fields during the day,and in the evening they both want to walk back to the barn to rest.Being clever bovines, they come up with a plan to