专栏文章

CEXE的%你赛5-题解

___CrossBow_EXE__
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minranz0
此快照首次捕获于
2025/12/02 07:04
3 个月前
此快照最后确认于
2025/12/02 07:04
3 个月前
查看原文

T1

简单 dfs，记录数组 visvis 表示一个点有没有被搜索过，从小到大遍历 visvis，如果 visi=0vis_i=0 则从 ii 开始遍历图，遍历时记录答案即可。
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m;
long long a[30005];
vector<int> G[30005];
bool vis[30005];
long long ans=0,maxn=-1;
void dfs(int x){
	vis[x]=1;
	maxn=max(maxn,a[x]);
	for(auto to:G[x]){
		if(vis[to]) continue;
		dfs(to);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1,u,v;i<=m;i++){
		cin>>u>>v;
		G[u].push_back(v);
	}
	
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			maxn=-1;
			dfs(i);
			ans+=maxn;
		}
	}
//	cout<<"13"<<endl;
	cout<<ans<<endl;
	return 0;
}

T2

数学题，答案为 ⌊n+12⌋\left \lfloor \frac{n+1}{2} \right \rfloor。记得开 unsigned long long。
CPP
void Main(int cases){
	ull x;cin>>x;
	cout<<(x+1>>1)<<endl;
	return;
}

T3

数据结构板子题。可以用树状数组、线段树、分块。这里讲最简单的分块做法。
把序列分成 n\sqrt n 个长度均匀的块。对于每个位置，记录 idiid_i，表示 ii 这个位置属于哪个块。
对于每个块记录几个属性：
  • sumsum，表示这个块的和
  • addadd，懒标记
  • cntcnt，这个块内包含了多少元素（接近 n\sqrt n）
两种操作如下：
  • 对于区间加，把范围内的整块的懒标记增加，整块两边的碎块暴力增加
  • 对于查询，整块的和为 sum+add×cntsum+add\times cnt，碎块直接暴力统计
总体复杂度 O(nn)O(n \sqrt n)。
分块写法：
CPP
ll n,m,len;
ll a[100005],id[100005],sum[100005],add[100005],cnt[100005];
ll op,x,y,k;
void op1(int l,int r,int x){
	if(id[l]==id[r]){
		for(int i=l;i<=r;i++){
			a[i]+=x;
			sum[id[i]]+=x;
		}
	}else{
		for(int i=l;id[i]==id[l];i++){
			a[i]+=x;
			sum[id[i]]+=x;
		}
		for(int i=r;id[i]==id[r];i--){
			a[i]+=x;
			sum[id[i]]+=x;
		}
		for(int i=id[l]+1;i<=id[r]-1;i++){
			add[i]+=x;
		}
	}
}
ll op2(int l,int r){
	ll ans=0;
	if(id[l]==id[r]){
		for(int i=l;i<=r;i++){
			ans+=a[i]+add[id[i]];
		}return ans;
	}else{
		for(int i=l;id[i]==id[l];i++){
			ans+=a[i]+add[id[i]];
		}
		for(int i=r;id[i]==id[r];i--){
			ans+=a[i]+add[id[i]];
		}
		for(int i=id[l]+1;i<=id[r]-1;i++){
			ans+=sum[i]+add[i]*cnt[i];
		}
		return ans;
	}
}
void Main(int cases){
	cin>>n;
	len=sqrt(n);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		id[i]=i/len;//i属于第几个块 
		sum[i/len]+=a[i];//第i个块的和 
		cnt[i/len]++;//第i个块有多少个数 
	}
	cin>>m;
	while(m--){
		cin>>op;
		if(op==1){
			cin>>x>>y>>k;
			op1(x,y,k);
		}
		if(op==2){
			cin>>x>>y;
			cout<<op2(x,y)<<endl;
		}
	}
	return;
}
线段树写法：
CPP
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define int long long
using namespace std;
const int N=100005;
int a[N];
int n,m,op,x,y,k;
struct node{
	int l,r,sum,lazy;
}tr[N<<2];
void pushup(int u){
	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void pushdown(int u){
	if(tr[u].lazy){//有懒标记才pushdown 
		tr[u<<1].sum+=(tr[u<<1].r-tr[u<<1].l+1)*tr[u].lazy;//区间和增加（区间元素个数）个懒标记 
		tr[u<<1|1].sum+=(tr[u<<1|1].r-tr[u<<1|1].l+1)*tr[u].lazy;
		tr[u<<1].lazy+=tr[u].lazy;//把懒标记传递给左右孩子 
		tr[u<<1|1].lazy+=tr[u].lazy;
		tr[u].lazy=0;//清空懒标记 
	}
}
void build(int u,int l,int r){
	tr[u].l=l,tr[u].r=r;
	if(l==r){
		tr[u].sum=a[l];
		tr[u].lazy=0;//懒标记初始化 
		return;
	}
	int mid=(l+r)>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	pushup(u);
}
void modify(int u,int l,int r,int val){
	if(tr[u].l>=l&&tr[u].r<=r){
		tr[u].sum+=val*(tr[u].r-tr[u].l+1);//需要加很多个val 
		tr[u].lazy+=val;//懒标记一下，标记加上过val
		return; 
	}
	pushdown(u);//懒标记下传
	int mid=(tr[u].l+tr[u].r)>>1;
	if(mid>=l) modify(u<<1,l,r,val);
	if(mid<r) modify(u<<1|1,l,r,val);
	pushup(u); 
}
int ask(int u,int l,int r){
	if(tr[u].l>=l&&tr[u].r<=r){
		return tr[u].sum;
	}
	pushdown(u);
	int mid=(tr[u].l+tr[u].r)>>1,sum=0;
	if(mid>=l) sum+=ask(u<<1,l,r);
	if(mid<r) sum+=ask(u<<1|1,l,r);
	return sum;
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
    cin>>m;
	build(1,1,n);
//	cout << tr[1].sum<<endl;
	while(m--){
		cin>>op;
		if(op==1){
			cin>>x>>y>>k;
			modify(1,x,y,k);
		}else{
			cin>>x>>y;
			cout<<ask(1,x,y)<<endl;
		}
	} 
	return 0;
}

T4

诈骗题。
注意到结尾的动图小标题为“小彩蛋”，而其他题目都为“小踩蛋”，显然答案与这个动图有关。
不难猜到题中所说的游戏是荒野乱斗（BrawlStars），查找荒野乱斗中的所有人物，可以发现动图中人物名为阿尔提，英文名为 R-T。小写的 rt 在锣鼓中恰好为“如题”的意思，所以答案为 rt。
下次模拟赛还有类似这样的题目！

T5

可爱动态规划。
第一问很好求，状态转移方程为 dpi=max⁡{dpj}+1dp_i=\max\{dp_j\}+1。
第二问，根据 Dilworth 定理，最小链覆盖等于最长反链长度（模拟即可理解），故答案与第一问答案完全相同。输出两次即可。
不知道 Dilworth 定理的去看 P1020 导弹拦截。
CPP
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
int n,a[5005],dp[5005],ans=-1e9;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		for(int j=0;j<i;j++){
			if(a[i]>a[j]) dp[i]=max(dp[i],dp[j]+1);
		}
	}
	for(int i=1;i<=n;i++) ans=max(dp[i],ans);
	cout<<ans<<' '<<ans<<endl;
	return 0;
}

T6

可爱动态规划。
第一问简单 dp，定义 dpi,jdp_{i,j} 表示从起点到 (i,j)(i,j) 的最大得分，显然有 dpi,j=max⁡(dpi−1,j,dpi,j−1)dp_{i,j}=\max(dp_{i-1,j},dp_{i,j-1})。
第二问需要在第一问转移时进行。定义 sumi,jsum_{i,j} 表示从起点走到 (i,j)(i,j) 能得到最大价值的方案数，转移方程为：
  • 如果 dpi−1,j>dpi,j−1dp_{i-1,j}>dp_{i,j-1}，则 sumi,j=sumi−1,jsum_{i,j}=sum_{i-1,j}；
  • 如果 dpi−1,j<dpi,j−1dp_{i-1,j}<dp_{i,j-1}，则 sumi,j=sumi,j−1sum_{i,j}=sum_{i,j-1}；
  • 如果 dpi−1,j=dpi,j−1dp_{i-1,j}=dp_{i,j-1}，则 sumi,j=sumi−1,j+sumi,j−1sum_{i,j}=sum_{i-1,j}+sum_{i,j-1}
别忘了取模。
第三问直接再次 dp，从 (x,y)(x,y) 点开始递推直到 (n,m)(n,m) 即可。
CPP
int n,m,x,y;
ll a[N][N];
ll dp1[N][N],dp2[N][N];
ll sum[N][N];

void Main(int cases){
	n=read(),m=read(),x=read(),y=read();
	up(i,1,n){
		up(j,1,m){
			a[i][j]=read();
		}
	}
	sum[1][1]=1;
	up(i,1,n) dp1[i][1]=dp1[i-1][1]+a[i][1],sum[i][1]=1;
	up(j,1,m) dp1[1][j]=dp1[1][j-1]+a[1][j],sum[1][j]=1;
	up(i,2,n){
		up(j,2,m){
			if(dp1[i-1][j]>dp1[i][j-1]) dp1[i][j]=dp1[i-1][j]+a[i][j],sum[i][j]=sum[i-1][j]%1000000000;
			if(dp1[i-1][j]<dp1[i][j-1]) dp1[i][j]=dp1[i][j-1]+a[i][j],sum[i][j]=sum[i][j-1]%1000000000;
			if(dp1[i-1][j]==dp1[i][j-1]) dp1[i][j]=dp1[i][j-1]+a[i][j],sum[i][j]=(sum[i][j-1]+sum[i-1][j])%1000000000;
		}
	}
//	up(i,1,n){
//		up(j,1,m){
//			cout<<sum[i][j]<<' ';
//		}cout<<endl;
//	}
	cout<<dp1[n][m]<<' '<<sum[n][m]<<' ';
	up(i,x,n) dp2[i][y]=dp2[i-1][y]+a[i][y];
	up(j,y,m) dp2[x][j]=dp2[x][j-1]+a[x][j];
	up(i,x+1,n){
		up(j,y+1,m){
			if(i==x&&y==j) continue;
			dp2[i][j]=max(dp2[i-1][j],dp2[i][j-1])+a[i][j];
		}
	}
	cout<<dp1[x][y]+dp2[n][m]-a[x][y]<<endl;
	return;
}

T7

双指针。为了快速求出区间和，先预处理前缀和。
维护两个指针 p1,p2p_1,p_2，从一开始往后扫。
注意到正整数序列，所以对于一个区间 [l,r][l,r] 的和 suml,rsum_{l,r}，一定有 suml+1,r<suml,r<suml,r+1sum_{l+1,r} < sum_{l,r} < sum_{l,r+1}。即区间和是递增的。
接着，我们会发现，对于一个给定的区间右端点 rr，满足条件的左端点 ll 的取值一定是连续的。我们只需要找出这个连续区间的长度，那么这个 rr 对答案的贡献就是这个区间的长度。
所以，我们用开头提到的两个指针从 11 开始，枚举区间右端点 rightright，对于每个右端点分别找到第一个满足和小于等于 rr 的地方 p1p_1，以及第一个满足和小于 ll 的地方 p2p_2，则这个右端点对答案的贡献为 max⁡{0,p1−p2}\max\{0,p_1-p_2\}。
答案很大，记得开 long long。
CPP
int a[3000005],sum[3000005];
int p1=1,p2=1;
ll ans=0;
void Main(int cases){
	n=read(),l=read(),r=read();
	up(i,1,n){
		a[i]=read();
		sum[i]=sum[i-1]+a[i];
	}
	up(right,1,n){
		int p=sum[right];
		while(p1<=right&&p-sum[p1-1]>r) p1++;
		while(p2<=right&&p-sum[p2-1]>=l) p2++;
		ans+=max(0,p2-p1);
	}
	cout<<ans<<endl;
	return;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...