专栏文章

题解：CF2053C Bewitching Stargazer

llgx57
CF2053C题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miqmmc81
此快照首次捕获于
2025/12/04 07:16
3 个月前
此快照最后确认于
2025/12/04 07:16
3 个月前
查看原文
赛时写了一个超级复杂的代码。
首先考虑直接暴力递归，但是这样的代码在最坏情况下是 O(n)O(n) 的，所以我们可以考虑一下优化。
当我们递归时，我们需要分别计算左区间和右区间，但是我们其实可以只算出来其中的一个区间，然后推出另外一个区间。
下面分 22 种情况考虑。
  1. 2∣len2 \mid len
设当前递归到的区间为 [l,r][l,r]。
我们记 cntcnt 为 [l,mid−1][l,mid-1] 的答案，通过找规律可以发现，如果左区间有 numnum 个数被统计了答案，那么右区间的答案为 cnt+num(mid−l+1)cnt+num(mid-l+1)。向上传回统计数时为 2num2num。
  1. 2∤len2 \nmid len
设当前递归到的区间为 [l,r][l,r]。
我们记 cntcnt 为 [l,mid−1][l,mid-1] 的答案，通过找规律可以发现，如果左区间有 numnum 个数被统计了答案，那么右区间的答案为 cnt+num(mid−l+1)cnt+num(mid-l+1)。向上传回统计数时为 2num+12num+1。请注意这里是 2num+12num+1，因为当前的 midmid 也被统计了。
CPP
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair<int,int>
#define endl '\n'
#define pb push_back
#define ls(p) ((p)<<1)
#define rs(p) ((p)<<1|1)
#define lowbit(x) ((x)&(-(x)))
#define abs(x) ((x)>0?(x):(-(x)))
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
using namespace std;
int n,k;
pii dfs(int l,int r){
	int len=r-l+1;
	int mid=(l+r)>>1;
	int ans=0;
	int tmp=0;
	if (len&1){
		ans+=mid;
		int nlen=mid-l;
		if (nlen<k) return {ans,1};
		pii cnt=dfs(l,mid-1);
		ans+=cnt.fi*2+(nlen+1)*cnt.se;
		tmp+=1+cnt.se*2;
	}
	else{
		int nlen=mid-l+1;
		if (nlen<k) return {0,0};
		pii cnt=dfs(l,mid);
		ans+=cnt.fi*2+nlen*cnt.se;
		tmp+=cnt.se*2;
	}
	return {ans,tmp};
}
void sol(){
	cin>>n>>k;
	cout<<dfs(1,n).fi<<endl;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t;
	cin>>t;
	while (t--) sol();
	return 0;
}

评论

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

正在加载评论...