526互联

CSP-S 2022 题解（部分）

发布时间 2023-09-08 10:56:25作者: NBest

2023-09-07 16:21:33

2023.9.7 15:46

前言

算是旧事重提了吧，过去了快一年才想着来订正，不过不得不说我去年 -S 拿了挺多分的，虽然就想出了一道正解。

T1

这题我考场上暴力乱搞拿了 60。然后听说有什么 meet in the middle 的算法，愣是没想到这题怎么 meet in the middle，难道枚举中间的两个点就算是 meet in the middle 吗？

先想想怎么贪心吧？显然不能贪心的依次去 \(a,b,c,d\)，但是在确定了 \(a,b,c\) 之后，我们显然可以贪心的选取最大的能去的且可以到家的 \(d\)，通过这样的 \(O(n^3)\) 枚举，你应该可以拿到 70 分的好成绩。

都想到了枚举 \(a,b,c\) 的 \(O(n^3)\) 了，不妨想一想怎么可以只枚举两个点做到 \(O(n^2)\)，既然可以枚举 \(a,b,c\)，那枚举 \(b,c,d\) 是不是也行？那要不我们直接枚举 \(b,c\) 呢？枚举 \(b,c\) 然后看它们最大可到达的合法点？然后我们发现这个贪心是正确的。只不过要分类讨论，比如 \(b,c\) 最大的点是彼此，次大的点相同之类的，然后讨论完了之后发现我们只需要存前三个大的点即可，然后实现就行了。
不过要注意：跑广搜的时候 vis 数组放的位置很重要。

\(Code\)

int n,m,k;
ll a[2502],f[3][2502],ans;
bool to[2502][2502];//to[i][j] 表示 i->j 是否可达
vector<int>F[2502];
queue<pair<int,int> >Q;
void bfs(int st){
    Q.push({st,0});
    to[st][st]=1;
    while(!Q.empty()){
        int x=Q.front().first,t=Q.front().second;
        Q.pop();
        if(t<k)for(int y:F[x])
            if(!to[st][y])//在这里分类讨论比在上面重复加进队列要好的多，不然只能拿95
                Q.push({y,t+1}),to[st][y]=1;
        if(x==st||!to[1][x])continue;
        if(a[x]>a[f[0][st]]){//更新前三大的点
            f[2][st]=f[1][st];
            f[1][st]=f[0][st];
            f[0][st]=x;
        }else if(a[x]>a[f[1][st]]){
            f[2][st]=f[1][st];
            f[1][st]=x;
        }else if(a[x]>a[f[2][st]])
            f[2][st]=x;
    }
}
int main(){
    n=read(),m=read(),k=read()+1;
    for(int i=2;i<=n;i++)
        a[i]=read();
    for(int i=1,u,v;i<=m;i++)
        F[u=read()].push_back(v=read()),F[v].push_back(u);
    a[0]=a[1]=-3e18;//初始化一下
    for(int i=1;i<=n;i++)bfs(i);
    for(int i=2;i<n;i++){
        for(int j=i+1;j<=n;j++){//海量分类讨论
            if(!to[i][j])continue;
            if(f[0][i]!=j&&f[0][j]!=i){
                if(f[0][j]!=f[0][i])ans=max(ans,a[f[0][j]]+a[f[0][i]]+a[i]+a[j]);
                else{
                    if(f[1][i]!=j)ans=max(ans,a[f[1][i]]+a[f[0][j]]+a[i]+a[j]);
                    if(f[1][j]!=i)ans=max(ans,a[f[1][j]]+a[f[0][i]]+a[i]+a[j]);
                }
            }else if(f[0][i]!=j){
                if(f[0][i]!=f[1][j])ans=max(ans,a[f[0][i]]+a[f[1][j]]+a[i]+a[j]);
                else{
                    if(f[1][i]!=j)ans=max(ans,a[f[1][i]]+a[f[1][j]]+a[i]+a[j]);
                    ans=max(ans,a[f[0][i]]+a[f[2][j]]+a[i]+a[j]);
                }
            }else if(f[0][j]!=i){
                swap(i,j);
                if(f[0][i]!=f[1][j])ans=max(ans,a[f[0][i]]+a[f[1][j]]+a[i]+a[j]);
                else{
                    if(f[1][i]!=j)ans=max(ans,a[f[1][i]]+a[f[1][j]]+a[i]+a[j]);
                    ans=max(ans,a[f[0][i]]+a[f[2][j]]+a[i]+a[j]);
                }
                swap(i,j);
            }else{
                if(f[1][i]!=f[1][j])ans=max(ans,a[f[1][i]]+a[f[1][j]]+a[i]+a[j]);
                else{
                    ans=max(ans,a[f[1][i]]+max(a[f[2][i]],a[f[2][j]])+a[i]+a[j]);
                }
            }
        }
    }
    cout<<ans;
    return 0;
}

B

赛时唯一过的一题，当时码力不够，分类思想也不足，调个简简单单的分类讨论都调了很久。仔细思考一下几种情况就行了。

发现我这一年码风居然变化不大？？不过现在的我在非正式写题时更喜欢压行了哈哈。

赛时\(Code\)

struct tree{
	int minn,maxx,zmin,fmin;
}tra[400005],trb[400005];
int n,m,q;
inline void pushup(int root,tree tr[]){
	tr[root].maxx=max(tr[root<<1].maxx,tr[root<<1|1].maxx);
	tr[root].minn=min(tr[root<<1].minn,tr[root<<1|1].minn);
	tr[root].fmin=max(tr[root<<1].fmin,tr[root<<1|1].fmin);
	tr[root].zmin=min(tr[root<<1].zmin,tr[root<<1|1].zmin);
	return;
}
inline void build(int root,int l,int r,int a[],tree tr[]){
	if(l==r){
		tr[root].maxx=tr[root].minn=a[l];
		if(a[l]<0)tr[root].fmin=a[l],tr[root].zmin=1000000001;
		else if(a[l]==0)tr[root].fmin=tr[root].zmin=0;
		else tr[root].zmin=a[l],tr[root].fmin=-1000000001;
		return;
	}
	int mid=(l+r)>>1;
	build(root<<1,l,mid,a,tr),build(root<<1|1,mid+1,r,a,tr);
	pushup(root,tr);
	return;
}
inline tree query(int root,int l,int r,int x,int y,tree tr[]){
	if(l>=x&&r<=y){
		return tr[root];
	}
	int mid=(l+r)>>1;
	tree T=(tree){1000000001,-1000000001,1000000001,-1000000001},k;
	if(mid>=x){
		k=query(root<<1,l,mid,x,y,tr);
		T.maxx=max(T.maxx,k.maxx);
		T.minn=min(T.minn,k.minn);
		T.fmin=max(T.fmin,k.fmin);
		T.zmin=min(T.zmin,k.zmin);
	}
	if(mid<y){
		k=query(root<<1|1,mid+1,r,x,y,tr);
		T.maxx=max(T.maxx,k.maxx);
		T.minn=min(T.minn,k.minn);
		T.fmin=max(T.fmin,k.fmin);
		T.zmin=min(T.zmin,k.zmin);
	}
	return T;
}
int a[100005],b[100005];
int main(){
	n=read(),m=read(),q=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	for(int i=1;i<=m;i++){
		b[i]=read();
	}
	build(1,1,n,a,tra);
	build(1,1,m,b,trb);
	while(q--){
		int la=read(),ra=read(),lb=read(),rb=read();
		tree A=query(1,1,n,la,ra,tra),B=query(1,1,m,lb,rb,trb);
		ll ans=0;
		if(A.minn>=0&&B.minn>=0){
			ans=(ll)A.maxx*B.minn;
		}
		else if(A.minn>=0&&B.maxx<=0){
			ans=(ll)A.minn*B.minn;
		}
		else if(A.maxx<=0&&B.minn>=0){
			ans=(ll)A.maxx*B.maxx;
		}
		else if(A.maxx<=0&&B.maxx<=0){
			ans=(ll)A.minn*B.maxx;
		}
		else if((A.maxx>=0&&A.minn<=0)&&B.minn>=0){
			ans=(ll)A.maxx*B.minn;
		}
		else if((A.maxx>=0&&A.minn<=0)&&B.maxx<=0){
			ans=(ll)A.minn*B.maxx;
		}
		else if((B.maxx>=0&&B.minn<=0)&&A.minn>=0){
			ans=(ll)A.minn*B.minn;
		}
		else if((B.maxx>=0&&B.minn<=0)&&A.maxx<=0){
			ans=(ll)A.maxx*B.maxx;
		}
		else if((B.maxx>=0&&B.minn<=0)&&(A.maxx>=0&&A.minn<=0)){
			ans=max((ll)A.zmin*B.minn,(ll)A.fmin*B.maxx);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

C

这题正解真的好简单好妙啊！不过我更喜欢“不可以，总司令”，然后拿 45 分跑路呢。

我们不妨翻译一下题意：
每个时间有四种操作：

  • 禁用某条边
  • 禁用一个点的所有入边
  • 启用某条边
  • 启用某个点所有入边

当某一时间的边的条件，满足下列情况时，输出 YES：

  • 任意点都可以到达一个环
  • 所有点的出度均为 \(1\)

我们发现，只要满足了出度都为 \(1\)，好像就一定能满足到达环。因为任意点出度为 \(1\)，说明我们在任何位置都能向前走，这样一定可以一直走下去即到达环。

然后我们发现因为每次都是禁用或者启用一个点入边，这意味着如果我们维护出边的话，每次 \(2,4\) 操作的复杂度就是 \(O(n^2)\) 了，而如果我们维护入边，那每次可以直接 \(O(1)\) 修改入度。

那我们是不是可以把维护出度为改为维护入度呢？我们发现，当出度全为 \(1\) 的时候，即入度等于总点数，但是反过来不一定成立。那我们是不是只要把不成立的概率减小，就可以使我们正确的概率大大增加呢？

这时我们考虑到随机化权值，我们给每个点赋一个随机的点权，最终出度全为 \(1\) 时，显然是入度的权值之和为点权之和，每次修改我们直接改每个点的入度权值即可。

\(Code\)

typedef unsigned long long ll;
mt19937_64 rnd(time(0));
int n,m,q;
ll ori[500005],in[500005],a[500005],sum,ans;
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        a[i]=rnd();//随机点权
        ans+=a[i];
    }
    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        in[v]+=a[u];//入度权值就是进入这个点的权值和
    }
    for(int i=1;i<=n;i++)sum+=(ori[i]=in[i]);//记录一开始所有边都在的时候每个点的点权和，用于操作 4 更新答案。并且计算总的入度权值和
    q=read();
    while(q--){
        int opt=read(),u=read();
        if(opt&1){//单边修改
            int v=read();
            if(opt==1){//保证有这条边了，所以我们直接入点的入度权值减点权即可
                in[v]-=a[u];
                sum-=a[u];
            }else{//同理
                in[v]+=a[u];
                sum+=a[u];
            }
        }else{//点所有边的修改
            if(opt==2){
                sum-=in[u];
                in[u]=0;//入度权值直接清空
            }else{
                sum+=ori[u]-in[u];
                in[u]=ori[u];//入度权值恢复以前的值
            }
        }
        if(sum==ans)puts("YES");//如果入度权值和等于权值和，则极大概率满足条件
        else puts("NO");
    }
    return 0;
}

D

暂时还没看懂，以后再补吧。