首页 > 其他分享 >CSP2022

CSP2022

时间：2022-10-31 22:37:44浏览次数：48  
标签：int max CSP2022 负数 read while maxn

CSP 取消了，只能 vp 一下。

T1

先枚举每个点，bfs 出中转次数不超过 \(k\) 次的点，并标记 \(f[i][j]=f[j][i]=1\)。

发现 \(1\) 与 \(A,B,C,D\) 构成的环可以拆成 \(1,A,B\) 与 \(1,D,C\)，这里想了好一会枚举 \(A,D\) 怎么做，结果发现自己弱智了。已经确定 \(1\)，在 \(n=2500\) 的背景下选择了枚举 \(B\) 和 \(C\) ，然后预处理 \(A,D\)。

考虑到可能会重复，例如通过 \(B\) 选出的 \(A\) 可能与 \(C,D\) 相同，所以我们最多只需要记录前三大即可。

预处理出对于 \(i\) 满足满足 \(f[i][j]=1,f[j][1]=1\) 的分数前三大的点 \(j\)，记为 \(\max_1[i],\max_2[i],\max_3[i]\)。

我们钦定 \(B<C\)，枚举 \(B,C\)，判断然后取最大值即可。

复杂度 \(O(n^2)\)，常数 \(\frac{9}{2}\)。

#include<bits/stdc++.h>
using namespace std;

#define int long long

inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c<='9'&&c>='0'){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}

void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar(x%10^48);
}

const int N=2505,M=1e4+5,K=105;
int n,m,k,a[N],head[N],cnt;
struct node{
	int next,to;
}e[M<<1];

void add(int from,int to){
	e[++cnt]=(node){head[from],to};
	head[from]=cnt;
}

bool vis[N],f[N][N];
queue<int>q;
int dis[N];

void bfs(int x){
	while(!q.empty())q.pop();
	for(int i=1;i<=n;++i)vis[i]=0,dis[i]=1e18;
	q.push(x),dis[x]=-1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		if(dis[u]>=k)break;
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].to;
			f[x][v]=f[v][x]=1;
			dis[v]=min(dis[v],dis[u]+1);
			if(!vis[v])q.push(v);
		}
	}
}

int maxn[4][N];

signed main(){
	n=read(),m=read(),k=read();
	for(int i=2;i<=n;++i)a[i]=read();
	for(int i=1;i<=m;++i){
		int u=read(),v=read();
		add(u,v),add(v,u);
	}
	for(int i=1;i<=n;++i){
		bfs(i);
	}
	for(int i=2;i<=n;++i){
		for(int j=2;j<=n;++j){
			if(i==j)continue;
			if(f[i][j]&&f[j][1]){
				if(a[j]>a[maxn[1][i]]){
					maxn[3][i]=maxn[2][i];
					maxn[2][i]=maxn[1][i];
					maxn[1][i]=j;
				}else if(a[j]>a[maxn[2][i]]){
					maxn[3][i]=maxn[2][i];
					maxn[2][i]=j;
				}else if(a[j]>a[maxn[3][i]]){
					maxn[3][i]=j;
				}
			}
		}
	}
	int ans=0;
	for(int i=2;i<=n;++i){
		for(int j=i+1;j<=n;++j){
			if(!f[i][j])continue;
			for(int k1=1;k1<=3;++k1){
				if(maxn[k1][i]==j)continue;
				for(int k2=1;k2<=3;++k2){
					if(maxn[k1][i]!=maxn[k2][j]&&maxn[k2][j]!=i&&f[maxn[k1][i]][1]&&f[maxn[k2][j]][1]){
						ans=max(ans,a[i]+a[j]+a[maxn[k1][i]]+a[maxn[k2][j]]);
					}
				}
			}
		}
	}
	print(ans);
	return 0;
}

T2

考虑最优策略是什么，可以从暴力中发掘：

枚举小 L 选的每一个值，小 Q 选择乘积最小的值，而小 L 从这些值里面选取最大的。

根据暴力理解完题目之后，不能把目光只停留在列举每一个数中，要考虑数的形成过程，即两区间内选数相乘。

也就是说：对于小 L 的每种情况，小 Q 都有相应的对策，这个对策在形式上是固定的，而小 L 根据每一种情况反馈出的值选择对于他来说最优的。

先考虑 \(A_i,B_i>0\) 的情况，对于小 L 选的每一个正数 \(A_i\)，小 Q 形式上固定的对策是选择区间内最小的 \(B_i\) 与之相乘保证最小，对此，小 L 将会选区间内最大的 \(A_i\) 使乘积最大。

再考虑正负零的情况，稍微列举归纳可发现，我们将数分为非负数和负数：

对于小 L 选这两种情况，小 Q 也有固定的策略：

  • 小 L 选非负数，小 Q 有负数选负数，没有负数选最小的非负数，总结一下可以得到小 Q 的策略是：选最小的。
  • 小 L 选负数，小 Q 有非负数选最大的非负数，没有非负数选最大的负数，总结一下可以得到小 Q 的策略是：选最大的。

所以我们只需要预处理 \(6\) 组值：

  • \(A\) 序列非负数 \(\max_1,\min_1\)
  • \(A\) 序列负数 \(\max_2,\min_2\)
  • \(B\) 序列 \(\max_3,\min_3\)

用 ST 表实现即可，复杂度 \(O(n\log n)\)。

#include<bits/stdc++.h>
using namespace std;

#define int long long 

inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c<='9'&&c>='0'){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}

void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar(x%10^48);
}

const int N=1e5+5;
int n,m,q,a[N],b[N],num[N],lgn,lgm;
int maxn1[N][21],minn1[N][21];
int maxn2[N][21],minn2[N][21];
int maxn3[N][21],minn3[N][21];

void init_maxn1(){
	for(int i=1;i<=n;++i)maxn1[i][0]=a[i];
	for(int j=1;j<=lgn;++j){
		for(int i=1;i+(1<<j)-1<=n;++i){
			maxn1[i][j]=max(maxn1[i][j-1],maxn1[i+(1ll<<(j-1))][j-1]);
		}
	}
}

void init_minn1(){
	for(int i=1;i<=n;++i){
		if(a[i]>=0)minn1[i][0]=a[i];
		else minn1[i][0]=1e18;
	}
	for(int j=1;j<=lgn;++j){
		for(int i=1;i+(1<<j)-1<=n;++i){
			minn1[i][j]=min(minn1[i][j-1],minn1[i+(1ll<<(j-1))][j-1]);
		}
	}
}

void init_maxn2(){
	for(int i=1;i<=n;++i){
		if(a[i]<0)maxn2[i][0]=a[i];
		else maxn2[i][0]=-1e18;
	}
	for(int j=1;j<=lgn;++j){
		for(int i=1;i+(1<<j)-1<=n;++i){
			maxn2[i][j]=max(maxn2[i][j-1],maxn2[i+(1ll<<(j-1))][j-1]);
		}
	}
}

void init_minn2(){
	for(int i=1;i<=n;++i)minn2[i][0]=a[i];
	for(int j=1;j<=lgn;++j){
		for(int i=1;i+(1<<j)-1<=n;++i){
			minn2[i][j]=min(minn2[i][j-1],minn2[i+(1ll<<(j-1))][j-1]);
		}
	}
}

void init_maxn3(){
	for(int i=1;i<=m;++i)maxn3[i][0]=b[i];
	for(int j=1;j<=lgm;++j){
		for(int i=1;i+(1<<j)-1<=m;++i){
			maxn3[i][j]=max(maxn3[i][j-1],maxn3[i+(1ll<<(j-1))][j-1]);
		}
	}
}

void init_minn3(){
	for(int i=1;i<=m;++i)minn3[i][0]=b[i];
	for(int j=1;j<=lgm;++j){
		for(int i=1;i+(1<<j)-1<=m;++i){
			minn3[i][j]=min(minn3[i][j-1],minn3[i+(1ll<<(j-1))][j-1]);
		}
	}
}

signed main(){
	n=read(),m=read(),q=read();
	lgn=(int)log2(n),lgm=(int)log2(m);
	for(int i=1;i<=n;++i)a[i]=read();
	for(int i=1;i<=m;++i)b[i]=read();
	for(int i=1;i<=n;++i){
		if(a[i]>=0)num[i]=num[i-1]+1;
		else num[i]=num[i-1];
	}
	init_maxn1(),init_minn1();
	init_maxn2(),init_minn2();
	init_maxn3(),init_minn3();
	int l1,r1,l2,r2,ans,lga,lgb,tmpa,tmpb;
	while(q--){
		l1=read(),r1=read(),l2=read(),r2=read();
		ans=-1e18;
		lga=(int)log2(r1-l1+1);
		lgb=(int)log2(r2-l2+1);
		if(num[r1]-num[l1-1]>0){
			tmpb=min(minn3[l2][lgb],minn3[r2-(1<<lgb)+1][lgb]);
			if(tmpb>=0){
				tmpa=max(maxn1[l1][lga],maxn1[r1-(1<<lga)+1][lga]);
				ans=max(ans,tmpa*tmpb);
			}else{
				tmpa=min(minn1[l1][lga],minn1[r1-(1<<lga)+1][lga]);
				ans=max(ans,tmpa*tmpb);
			}
		}
		if(num[r1]-num[l1-1]<r1-l1+1){
			tmpb=max(maxn3[l2][lgb],maxn3[r2-(1<<lgb)+1][lgb]);
			if(tmpb>=0){
				tmpa=max(maxn2[l1][lga],maxn2[r1-(1<<lga)+1][lga]);
				ans=max(ans,tmpa*tmpb);
			}else{
				tmpa=min(minn2[l1][lga],minn2[r1-(1<<lga)+1][lga]);
				ans=max(ans,tmpa*tmpb);
			}
		}
		print(ans),puts("");
	}
	return 0;
}

T3

题目比较难读，用了快半个小时才读懂题......

人话翻译：

\(n\) 个点，\(m\)​ 条边，要求支持：

  • 删边 \((u,v)\)
  • 删去所有以 \(u\) 为终点的点
  • 加边 \((u,v)\)
  • 加上所有以 \(u\) 为终点的点

在每一次操作之后判断：

  • 是否每个点的出度为 \(1\)
  • 是否每个点都能走到一个环

很显然第一个判断是包括了第二个的，所以我们只用判断：是否每个点的出度为 \(1\)。

赛时：\(O(mq)\) 模拟做法显然好做，然后没有 \(t=2\) 和 \(t=4\) 的情况只需要我们支持每次加删一条边和判断，用一个 multiset 维护出度判断首尾是否相同即可。对于有 \(t=2\) 的，我们用一个集合维护未被摧毁的边，由于每次加边只能加一条，复杂度是有保证的。这是 \(60\)，然后还写了一个用集合维护删边的，复杂度没有保证想骗点分，结果好像没骗到。码了整整两百行。

正解是 hash，看到判断每个点的出度全为 \(1\)，我们考虑给每个点随机赋一个权值 \(val_i\)，设出来一个与出度有关的 \(h(u)\)，用 \(\sum h(u)\) 来判断。

然后考虑如何应对上述操作。发现以 \(u\) 为终点很逆天，于是我们建反图把它干掉。

将图转化为反图，需要支持的操作变为：

  • 删边 \((u,v)\)
  • 删去所有以 \(u\) 为起点的点
  • 加边 \((u,v)\)
  • 加上所有以 \(u\) 为起点的点

此时我们需要判断：

  • 每个点的入度为 \(1\)

对于删去所有和恢复所有边，需要我们记录所有点的初始出度和当前出度。

但是判断的是入度，应该怎么办呢？

考虑把当前点的贡献转移到起点，即对于边 \(u\to v\)，我们不记录 \(v\) 的入度，而记录 \(u\) 的出度，把 \(val_v\) 记录到 \(h(u)\) 上，这样既不会改变最终答案，又能解决出入度冲突问题。

所以我们设 \(h(u)\) 为以 \(u\) 为起点的边的终点权值和，这满足对于每个点入度都为 \(1\) 的图他们的 \(\sum h(u)\) 相同，即一个点的权值只会被统计一次。

为了保证正确率，可以多随机几个点的权值。

#include<bits/stdc++.h>
using namespace std;

#define int long long

inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c<='9'&&c>='0'){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}

void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar(x%10^48);
}

const int N=5e5+5;
const int MAX=1e9+7;
int n,m,q;
int d[N],nd[N],val[N][5],ans[5];
int nsum[N][5],nSum[5],sum[N][5];

signed main(){
	n=read(),m=read();
	srand(time(0));
	for(int i=1;i<=n;++i){
		for(int j=0;j<5;++j){
			val[i][j]=rand()*rand()%MAX;
			ans[j]+=val[i][j];
		}
	}
	for(int i=1;i<=m;++i){
		int u=read(),v=read();
		d[v]++,nd[v]++;
		for(int j=0;j<5;++j){
			sum[v][j]+=val[u][j];
			nsum[v][j]+=val[u][j];
			nSum[j]+=val[u][j];
		}
	}
	q=read();
	int t,u,v;
	while(q--){
		t=read();
		if(t==1){
			u=read(),v=read();
			nd[u]--;
			for(int i=0;i<5;++i)nsum[v][i]-=val[u][i],nSum[i]-=val[u][i];
		}else if(t==2){
			u=read();
			nd[u]=0;
			for(int i=0;i<5;++i)nSum[i]-=nsum[u][i],nsum[u][i]=0;
		}else if(t==3){
			u=read(),v=read();
			nd[u]++;
			for(int i=0;i<5;++i)nsum[v][i]+=val[u][i],nSum[i]+=val[u][i];
		}else{
			u=read();
			nd[u]=d[u];
			for(int i=0;i<5;++i)nSum[i]+=(sum[u][i]-nsum[u][i]),nsum[u][i]=sum[u][i];
		}
		bool flag=1;
		for(int i=0;i<5;++i)if(ans[i]!=nSum[i])flag=0;
		if(flag)puts("YES");
		else puts("NO");
	} 
	return 0;
}

T4

开 T4 的时候时间已经不多了，然后就写挂了 \(8\) 分。

看完这题我直接就写了个把 \(s\) 到 \(t\) 之间的链扯下来 dp，然后就挂在了样例 \(2\)。

可以发现当 \(k=3\) 时是能跳出链外的。

于是我在写的 dfs 上加了对于 \(x\) 向外枚举 \(3\) 层转移，然后加上 \(k=1\) 就交了......

赛后发现挂分了，写了个拍可以发现存在这样一种情况：\(x\) 是 \(s\) 到 \(t\) 最优的中转点，而如果只从 \(s\) 开始 dfs 可能先到 \(t\) 再到 \(x\)。

对于这种情况，我们只需要跑 \(n\) 遍 dfs 就写了（

这样就有 \(44\) 分。

正解是倍增维护矩阵，鉴定为是我考场上写不出来的。

先扔这了，有时间再补。

标签：int,max,CSP2022,负数,read,while,maxn
From： https://www.cnblogs.com/Daidly/p/16846087.html

相关文章

  • CSP2022游寄
    初赛好像要考初赛了，是不是得刷刷题啊。完了，刷一套不会一套，\(OIer\)是电脑白痴，\(linux\)的一车命令都是啥啊，这谁会啊。阅读程序又是啥啊，他在干啥，这谁看得懂啊。正式考......
  • CSP2022 S游记
    9.26：开坑。没报J组主要是因为J比较垃圾，去抢小朋友的一等没什么意思。初赛刚拿到试卷就直接懵了，这tm是给人做的题？宇宙射线是什么奇妙东西，还有基数排序我根本不会啊......
  • CSP2022 游记
    Day?初赛出来估分96，结果官方数据怎么只有90.5，感觉标准答案有很多错误！！出分的时候把准考证号记错了，于是当了半个上午的HN01。......
  • Solution Set - CSP2022
    妈的，我考的跟狗屎一样，按道理稳定发挥差不多有\(350\)，不济也是\(326\)，可惜没有如果。假期计划首先先预处理出两点之间是否可达，这个可以使用\(n\)次bfs在最多\(O(n(......
  • CSP2022-J组题解
    最后一次j组了，写篇题解纪念一下A假如\(a=1\)，\(a^b=1\)假如\(a>1\)，可以发现当\(b>30\)时\(a^b\)必然大于\(10^9\)于是我们可以暴力计算，如果计算的过程中大于\(1......
  • CSP2022 游记。
    作为第一次以高中生身份参加csp，虽然有了一定的经验，但还是有点小慌。14:20基本进完场了，考场内回忆了一下tarjan，然后眯眼休息。14:27开考，解压。T1一道图论题，找几个最......
  • CSP2022
    希望别伏笔小插曲：考前2天说取消了，但是过了1天又说恢复。Day0鉴于去年吃了不会网络流的亏，这次把各种算法都看了一遍，但是不想看LCT，如果考了我只能问候出题人的家人。......
  • CSP2022 游记
    Day0吃了个KFCJ组：赛前：J组总得AK掉吧？！赛时：T1，切了。T2，这不解方程吗，不过做得有些复杂，还手写了int128和sqrt，但还是很快切了。T3，大模拟先放一会儿。T4，好水，还不......
  • CSP2022 梦游记
    同步发表于luogu前情提要：csp前完全一天也没有停课，模拟赛自然更加不用说了，因此代码能力直线下降（大概是线段树2都打不出来233）。所以前面几天的也没啥好讲的了qwq。Day-1......
  • CSP2022 J2参考解析
    目录P8813[CSP-J2022]乘方P8814[CSP-J2022]解密P8815[CSP-J2022]逻辑表达式P8816[CSP-J2022]上升点列https://www.luogu.com.cn/contest/90215#problemsP8813[C......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99