• 欢迎光临~

2022.10.13 CSP2022 模拟赛三

开发技术 开发技术 2022-10-13 次浏览

Source: JOI 2018 Final T2-T5

绝了会最后一题不会 T2,麻了。

美术展览

显然的事情:在规定 (A) 的值域 ([l,r]) 之后,对于所有 (A_iin[l,r]),都选进来一定最优。

(A_i) 从小到大排序后,问题变成了选定一个区间 ([l,r]),其答案为 (s_r-s_{l-1}-a_r+a_l),随便记个前缀 (max) 就行了。

当然我场上脑抽抽了,写了棵线段树。

Code
const int N=5e5+5;
struct node {ll a,b;} t[N];
bool cmp(node x,node y) {return x.a<y.a;}
ll ma[N*4],add[N*4];
void pushadd(int p,ll v) {ma[p]+=v,add[p]+=v;}
void pushdown(int p) {if(add[p]) pushadd(p*2,add[p]),pushadd(p*2+1,add[p]),add[p]=0;}
void pushup(int p) {ma[p]=max(ma[p*2],ma[p*2+1]);}
void build(int p,int l,int r) {
	if(l==r) return ma[p]=t[l].a,void();
	int mid=(l+r)>>1;
	build(p*2,l,mid),build(p*2+1,mid+1,r);
	pushup(p);
}
void update(int p,int l,int r,int x,int y,ll v) {
	if(x<=l&&r<=y) return pushadd(p,v);
	int mid=(l+r)>>1;pushdown(p);
	if(x<=mid) update(p*2,l,mid,x,y,v);
	if(y>mid) update(p*2+1,mid+1,r,x,y,v);
	pushup(p);
}
ll query(int p,int l,int r,int x,int y) {
	if(x<=l&&r<=y) return ma[p];
	int mid=(l+r)>>1;pushdown(p);
	ll ret=0;
	if(x<=mid) ret=max(ret,query(p*2,l,mid,x,y));
	if(y>mid) ret=max(ret,query(p*2+1,mid+1,r,x,y));
	return ret;
}
int main() {
 	int n=read();
 	FOR(i,1,n) t[i].a=read(),t[i].b=read();
 	sort(t+1,t+n+1,cmp);
 	build(1,1,n);
 	ll ans=0;
 	FOR(i,1,n) {
 		update(1,1,n,1,i,t[i].b);
 		ans=max(ans,query(1,1,n,1,i)-t[i].a);
 	}
 	printf("%lldn",ans);
}

团子制作

我,挺脑瘫的。

注意到互斥的团子串的中间 G 对应的位置一定是对角线:

  R    
  G
RGW

枚举每一条对角线,对对角线从上往下做 DP,具体地,设 (f_{i,0/1/2}) 表示第 (i) 行 不选/选横的/选竖的 的答案,注意这里的横竖以 G 为中心。

做到 (O(nm))

Code
const int N=3005;
char ch[N][N];
int f[N][3];
int main() {
    int n=read(),m=read();
    FOR(i,1,n) scanf("%s",ch[i]+1);
    int ans=0;
    FOR(s,2,n+m) {
        memset(f,0,sizeof f);
        int sum=0,i,j;
        for(i=max(1,s-m),j=s-i;i<=n&&j;i++,j--) {
            f[i][0]=max({f[i-1][0],f[i-1][1],f[i-1][2]});
            if(ch[i][j]=='G') {
                if(ch[i-1][j]=='R'&&ch[i+1][j]=='W') f[i][1]=max(f[i][1],max(f[i-1][0],f[i-1][1])+1);
                if(ch[i][j-1]=='R'&&ch[i][j+1]=='W') f[i][2]=max(f[i][2],max(f[i-1][0],f[i-1][2])+1);
            }
            sum=max({sum,f[i][0],f[i][1],f[i][2]});
        }
        ans+=sum;
    }
    printf("%dn",ans);
}

月票购买

求出 (Sto T) 的最短路 DAG,考虑 (U,V) 的最短路的变化:

  1. 不经过最短路 DAG,此时的答案可以直接预处理出来。
  2. 经过最短路 DAG,若最短路 DAG 上存在 (Sto ato bto T),则有一种路径就是 (Uto ato bto T),以及 (Tto ato bto U),拓扑排序 DP 即可。

总时间复杂度 (O(nlog n))

Code
const int N=1e5+5;
vector<pii> G[N];
vi G2[N];
int n,u[2*N],v[2*N],w[2*N],deg[N];
ll dS[N],dT[N],dU[N],dV[N],f1[N],f2[N];
void dijskra(int s,ll *dis) {
    FOR(i,1,n) dis[i]=1e18;
    priority_queue<pair<ll,int> > pq;
    pq.push({0,s}),dis[s]=0;
    while(sz(pq)) {
        int u=pq.top().se;
        ll d=pq.top().fi;
        pq.pop();
        if(-d!=dis[u]) continue;
        for(pii i:G[u]) {
            int v=i.fi,d=i.se;
            if(dis[u]+d<dis[v]) dis[v]=dis[u]+d,pq.push({-dis[v],v});
        }
    }
}
int main() {
    n=read();int m=read(),S=read(),T=read(),U=read(),V=read();
    FOR(i,1,m) {
        u[i]=read(),v[i]=read(),w[i]=read();
        G[u[i]].pb({v[i],w[i]}),G[v[i]].pb({u[i],w[i]});
    }
    dijskra(S,dS),dijskra(T,dT),dijskra(U,dU),dijskra(V,dV);
    ll ans=dU[V];
    FOR(i,1,m) {
        if(dS[u[i]]+w[i]+dT[v[i]]==dS[T]) G2[u[i]].pb(v[i]),deg[v[i]]++;
        if(dS[v[i]]+w[i]+dT[u[i]]==dS[T]) G2[v[i]].pb(u[i]),deg[u[i]]++;
    }
    queue<int> q;
    q.push(S);
    FOR(i,1,n) f1[i]=dU[i],f2[i]=dV[i];
    while(sz(q)) {
        int u=q.front();q.pop();
        ans=min({ans,f1[u]+dV[u],f2[u]+dU[u]});
        for(int v:G2[u]) {
            f1[v]=min(f1[v],f1[u]),f2[v]=min(f2[v],f2[u]);
            deg[v]--;
            if(deg[v]==0) q.push(v);
        }
    }
    printf("%lldn",ans);
}

毒蛇越狱

听说过套路 trick 就薄纱了。

首先看到这个题,有三个暴力:

  1. 暴力枚举每个 ?,然后累加贡献。
  2. 预处理 (f_S=sum_{S'subseteq S}c_S),将每个 ? 看成 1,然后对原本的 1 容斥成 1 或者 0
  3. 预处理 (f_S=sum_{Ssubseteq S'}c_S),将每个 ? 看成 0,然后对原本的 0 容斥成 1 或者 0

你发现三个暴力分别与 (c_q,c_1,c_2) 相关,所以取最小的一个即可做到 (O(q2^{n/3}))

Code
const int MS=1<<21;
int L,Q,f[MS],g[MS];
char c[MS],q[22];
int ans=0;
void dfs1(int dep,int v) {
    if(dep==L) return ans+=c[v]-'0',void();
    if(q[dep]!='?') {
        v|=((q[dep]-'0')<<dep);
        return dfs1(dep+1,v);
    }
    dfs1(dep+1,v);
    v|=(1<<dep);
    dfs1(dep+1,v);
}
void dfs2(int dep,int v,int z) {
    if(dep==L) return ans+=z*g[v],void();
    if(q[dep]!='0') {
        if(q[dep]=='1') v|=1<<dep;
        return dfs2(dep+1,v,z);
    }
    dfs2(dep+1,v,z);
    v|=1<<dep;
    dfs2(dep+1,v,-z);
}
void dfs3(int dep,int v,int z) {
    if(dep==L) return ans+=z*f[v],void();
    if(q[dep]!='1') {
        if(q[dep]=='?') v|=1<<dep;
        return dfs3(dep+1,v,z);
    }
    dfs3(dep+1,v,-z);
    v|=1<<dep;
    dfs3(dep+1,v,z);
}
int main() {
    scanf("%d %d",&L,&Q);
    scanf("%s",c);
    FOR(i,0,(1<<L)-1) f[i]=g[i]=c[i]-'0';
    FOR(i,0,L-1) FOR(j,0,(1<<L)-1) if(!(j&(1<<i))) f[j|(1<<i)]+=f[j];
    FOR(i,0,L-1) FOR(j,0,(1<<L)-1) if(j&(1<<i)) g[j^(1<<i)]+=g[j];
    FOR(i,1,Q) {
        int cq=0,c0=0,c1=0;
        scanf("%s",q);
        FOR(j,0,L-1) {
            if(q[j]=='?') cq++;
            if(q[j]=='0') c0++;
            if(q[j]=='1') c1++;
        }
        reverse(q,q+L);
        int mc=min(cq,min(c0,c1));
        ans=0;
        if(mc==cq) dfs1(0,0);
        else if(mc==c0) dfs2(0,0,1);
        else dfs3(0,0,1);
        printf("%dn",ans);
    }
}
程序员灯塔
转载请注明原文链接:2022.10.13 CSP2022 模拟赛三
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com