洛谷刷题7.31

本文介绍了多个算法题目的解决思路和代码实现，主要包括： MooFestG加强版：使用离散化和树状数组计算位置绝对差之和，时间复杂度O(nlogn)。递增问题：通过二分查找优化最长上升子序列计算，复杂度O(nlogn)。逆序数问题：利用线段树统计逆序对数量。火柴排队：通过离散化和树状数组求逆序数实现最小移动代价。约瑟夫问题：使用vector模拟环形删除过程。 HH的项链：离线处理+树状数组维

圆头猫爹

873人浏览 · 2025-07-31 17:48:25

圆头猫爹 · 2025-07-31 17:48:25 发布

P2345 [USACO04OPEN] MooFest G - 洛谷

P5094 [USACO04OPEN] MooFest G 加强版 - 洛谷

这题用到树状数组，首先我们肯定要以v从小到大排序，这样我们从前向后遍历时max{vi,vj}=vi，j<i。vi确定了我们就要确定 $\sum_{1}^{i-1}\left | xi-xj \right |$ 。首先要将数据离散化，这里相同的数离散化为同一值和不同值都没有影响，因为相减会抵消。我们找到比他小的数的和sum,数的个数n，那么相减的绝对值之和就是n*xi-sum,同理，找到比他大的数的和sum,数的个数n，那么相减的绝对值之和就是 sum-n*xi

#include<bits/stdc++.h>
#define ll long long
#define samplepassediscorrect for(;;)
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define lowbit(x) (x&(-x))
#define N 20050
using namespace std;
struct point{
	ll v,x;
}arr[N];
int n,b[N],temp[N];
bool cmp(point &s1,point &s2){return s1.v<s2.v;}
struct Fenwick_Tree{
	ll tree[N]={0};
	void update(ll x,ll d){
		while(x<=n){
			tree[x]+=d;
			x+=lowbit(x);
		}
	}
	ll sum(ll x){
		ll ans=0;
		while(x>0){
			ans+=tree[x];
			x-=lowbit(x);
		}
		return ans;
	}
}r1,r2; 
int main(){
jiasu;
cin>>n;
for(int i=1;i<=n;i++)
	cin>>arr[i].v>>arr[i].x,temp[i]=arr[i].x;
sort(temp+1,temp+1+n);
int cnt=0;
for(int i=1;i<=n;i++){
	if(b[temp[i]]==0){
		b[temp[i]]=++cnt;//离散化 
	}
}
sort(arr+1,arr+1+n,cmp);
ll ans=0;
for(int i=1;i<=n;i++){
	r1.update(b[arr[i].x],arr[i].x);
	r2.update(b[arr[i].x],1);
	ans+=arr[i].v*(arr[i].x*r2.sum(b[arr[i].x]-1)-r1.sum(b[arr[i].x]-1)+r1.sum(n)-r1.sum(b[arr[i].x])-arr[i].x*(r2.sum(n)-r2.sum(b[arr[i].x])));
}
cout<<ans;	
	return 0;
}

P3902 递增 - 洛谷

很明显这题是让求最长上升子序列长度的，我们需要用二分优化。具体方法自行了解。

#include<bits/stdc++.h>
#define ll long long
#define samplepassediscorrect for(;;)
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define lowbit(x) (x&(-x))
#define N 50050
using namespace std;
int n,a,arr[100005],m=0;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
	cin>>a;
	if(a>arr[m]) arr[++m]=a;
	else arr[lower_bound(arr+1,arr+1+m,a)-arr]=a;
}
cout<<n-m;
	return 0;
}

P1774 最接近神的人 - 洛谷

其实就是逆序数

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
struct node{
	ll r,l,sum,lz;
}tree[3000005];
struct point{
	ll x,num;
}a[500005];
bool cmp(point &s1,point &s2){
	return s1.x<s2.x;
}
ll n,arr[500005];
void push_down(int i){//下传函数
	if(tree[i].lz!=0){
		tree[i*2].lz+=tree[i].lz;
		tree[i*2+1].lz+=tree[i].lz;
		tree[i*2].sum+=tree[i].lz*(tree[i*2].r-tree[i*2].l+1);
		tree[i*2+1].sum+=tree[i].lz*(tree[i*2+1].r-tree[i*2+1].l+1);
		tree[i].lz=0;
	}
	return;
}
void build(int i,int l,int r){//建树
	tree[i].l=l,tree[i].r=r;
	tree[i].lz=0;
	if(l==r) return; 
	int mid=(l+r)/2;
	build(2*i,l,mid);
	build(2*i+1,mid+1,r);
}
void add(int i,int l,int r,int k){//区间加减
	if(tree[i].l>=l&&tree[i].r<=r){	
		tree[i].sum+=k*(tree[i].r-tree[i].l+1);
		tree[i].lz+=k;
		return;
	}
	push_down(i);
	if(tree[i*2].r>=l) add(i*2,l,r,k);
	if(tree[i*2+1].l<=r) add(i*2+1,l,r,k);
	tree[i].sum=tree[2*i].sum+tree[2*i+1].sum;
	return;
}
ll search(int i,int l,int r){//查询
	if(tree[i].l>=l&&tree[i].r<=r) return tree[i].sum;
	if(tree[i].r<l||tree[i].l>r) return 0;
	push_down(i);
	ll ans=0;
	if(tree[i*2].r>=l) ans+=search(i*2,l,r);
	if(tree[i*2+1].l<=r) ans+=search(i*2+1,l,r);
	return ans;
}
int main()
{
jiasu;
cin>>n;
for(int i=1;i<=n;i++){
	cin>>a[i].x;
	a[i].num=i;
}
sort(a+1,a+1+n,cmp);
ll now=0,cnt=0;
for(int i=1;i<=n;i++){
	if(a[i].x!=now){
		now=a[i].x;
		arr[a[i].num]=++cnt;
	}
	else arr[a[i].num]=cnt;
}
build(1,1,n);
ll ans=0;
for(int i=n;i>=1;i--){
	ans+=search(1,1,arr[i]-1);
	add(1,arr[i],arr[i],1);
}
cout<<ans;
	return 0;
}

P1966 [NOIP 2013 提高组] 火柴排队 - 洛谷

严谨的证明这里不讲，凭感觉我们让 $\sum (a_i - b_i)^2$ 最小，我们应该让他们从小到大排序，这样一一对应得到的应该时最小值，但是都让他们从小到大排序的移动代价太高。我们让第一个序列作为基准，将第二个序列移动为第一个序列。首先我们要将两个序列都离散化。

例如离散化后：

a: 2 6 5 1 3 4

b: 3 2 5 4 6 1

a是基准排序,我们得到inva（a的反函数）

inva[1] = 4

inva[2] = 1

inva[3] = 5

inva[4] = 6

inva[5] = 3

inva[6] = 2

再得到b相对于a的位置序列

5 1 3 6 2 4

之后我们求这个序列逆序数就好了

#include<bits/stdc++.h>
#define ll long long
#define samplepassediscorrect for(;;)
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define lowbit(x) (x&(-x))
#define N 100050
using namespace std;
struct point{
	ll x,num;
}a[N],b[N];
const ll mod=1e8-3;
ll n,inva[N],invb[N],temp[N],ans=0;
bool cmp(point &s1,point &s2){return s1.x<s2.x;}
struct Fenwick_Tree{
	ll tree[N]={0};
	void update(ll x,ll d){
		while(x<=n){
			tree[x]+=d;
			x+=lowbit(x);
		}
	}
	ll sum(ll x){
		ll ans=0;
		while(x>0){
			ans+=tree[x];
			x-=lowbit(x);
		}
		return ans;
	}
}r; 
int main(){
cin>>n;
for(int i=1;i<=n;i++){
	cin>>a[i].x;
	a[i].num=i;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
	inva[i]=a[i].num;
}
for(int i=1;i<=n;i++){
	cin>>b[i].x;
	b[i].num=i;
}
sort(b+1,b+1+n,cmp);
for(int i=1;i<=n;i++){
	invb[b[i].num]=inva[i];
}
for(int i=n;i>=1;i--){
	r.update(invb[i],1);
	ans=(r.sum(invb[i]-1)+ans)%mod;
}
cout<<ans%mod;
	return 0;
}

P1996 约瑟夫问题 - 洛谷

本人懒省事，直接用vector硬模拟了

#include<bits/stdc++.h>
#define ll long long
#define samplepassediscorrect for(;;)
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define N 200005
using namespace std;
vector<int>arr;
int n,m,now=0;
int main()
{
jiasu;
cin>>n>>m;
m--;
for(int i=1;i<=n;i++) arr.push_back(i);
while(arr.size()){
	n=arr.size();
	now=(now+m)%n;
	cout<<arr[now]<<" ";
	arr.erase(arr.begin()+now);
}
	return 0;
}

P1972 [SDOI2009] HH的项链 - 洛谷

先将所有区间以r从小到大排序，对于一个区间，我们只关心最靠右的数，比如1，2，3，1

我们只在意第四个1，第一个1是可以忽略的，这里有点像是优先队列。所以我们从前向后遍历访问区间，不断添加新数，将老数归零。求前缀和就行。

#include<bits/stdc++.h>
#define ll long long
#define samplepassediscorrect for(;;)
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define lowbit(x) (x&(-x))
#define N 1000050
using namespace std;
struct ask{
	int l,r,num;
}a[N];
ll n,arr[N],m,last[N],ans[N];
bool cmp(ask &s1,ask &s2){return s1.r<s2.r;}
struct Fenwick_Tree{
	ll tree[N]={0};
	void update(ll x,ll d){
		while(x<=n){
			tree[x]+=d;
			x+=lowbit(x);
		}
	}
	ll sum(ll x){
		ll ans=0;
		while(x>0){
			ans+=tree[x];
			x-=lowbit(x);
		}
		return ans;
	}
}r; 
int main(){
jiasu;
cin>>n;
for(int i=1;i<=n;i++)
	cin>>arr[i];
cin>>m;
for(int i=1;i<=m;i++){
	cin>>a[i].l>>a[i].r;
	a[i].num=i;
}
sort(a+1,a+1+m,cmp);
int now=1;
for(int i=1;i<=m;i++){
	while(now<=a[i].r){
		r.update(now,1);
		if(last[arr[now]]!=0){
			r.update(last[arr[now]],-1);
		}
		last[arr[now]]=now;
		now++;
	}
	ans[a[i].num]=r.sum(a[i].r)-r.sum(a[i].l-1);
}
for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
	return 0;
}

P4939 Agent2 - 洛谷

依旧用树状数组维护差分数组，这适用于区间修改单点查询。

#include<bits/stdc++.h>
#define ll long long
#define samplepassediscorrect for(;;)
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define lowbit(x) (x&(-x))
#define N 10000050
using namespace std;
ll n,m,f,a,b;
struct Fenwick_Tree{
	ll tree[N]={0};
	void update(ll x,ll d){
		while(x<=n){
			tree[x]+=d;
			x+=lowbit(x);
		}
	}
	ll sum(ll x){
		ll ans=0;
		while(x>0){
			ans+=tree[x];
			x-=lowbit(x);
		}
		return ans;
	}
}r; 
int main(){
jiasu;
cin>>n>>m;
while(m--){
	cin>>f;
	if(f){
		cin>>a;
		cout<<r.sum(a)<<endl;
	}
	else{
		cin>>a>>b;
		r.update(a,1);
		r.update(b+1,-1);
	}
}
	return 0;
}

P1438 无聊的数列 - 洛谷

这里是区间修改区间查询，所以我用线段树，我们要维护一个差分数组，第一个修改的要+k，后面的l+1——r加上d，在r+1减去k+(r-l)*d复原，求某个值就是求前缀和。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define samplepassediscorrect for(;;)
#define lowbit(x) (x&(-x))
#define N 5000005
using namespace std;
ll n,a[N],m,input[N],f,l,r,k,d;
struct node{long long r,l,sum,lz;};
struct Segment_Tree{
	node tree[N];
	void push_down(int i){//下传函数	
		if(tree[i].lz!=0){		
			tree[i*2].lz+=tree[i].lz;
			tree[i*2+1].lz+=tree[i].lz;
			tree[i*2].sum+=tree[i].lz*(tree[i*2].r-tree[i*2].l+1);
			tree[i*2+1].sum+=tree[i].lz*(tree[i*2+1].r-tree[i*2+1].l+1);
			tree[i].lz=0;
		}
		return;
	}
	void build(int i,int l,int r){//建树
		tree[i].l=l,tree[i].r=r;
		tree[i].lz=0;
		if(l==r){	
			tree[i].sum=input[l];
			return;
		}
		int mid=(l+r)/2;
		build(2*i,l,mid);
		build(2*i+1,mid+1,r);
		tree[i].sum=tree[2*i].sum+tree[2*i+1].sum;
	}
	void add(int i,int l,int r,int k){//区间加减
		if(tree[i].l>=l&&tree[i].r<=r){	
			tree[i].sum+=k*(tree[i].r-tree[i].l+1);
			tree[i].lz+=k;
			return;
		}
		push_down(i);
		if(tree[i*2].r>=l) add(i*2,l,r,k);
		if(tree[i*2+1].l<=r) add(i*2+1,l,r,k);
		tree[i].sum=tree[2*i].sum+tree[2*i+1].sum;
		return;
	}
	ll search(int i,int l,int r){//查询
		if(tree[i].l>=l&&tree[i].r<=r) return tree[i].sum;
		if(tree[i].r<l||tree[i].l>r) return 0;
		push_down(i);
		long long ans=0;
		if(tree[i*2].r>=l) ans+=search(i*2,l,r);
		if(tree[i*2+1].l<=r) ans+=search(i*2+1,l,r);
		return ans;
	}
}q;
int main(){
jiasu;
cin>>n>>m;
for(int i=1;i<=n;i++){
	cin>>a[i];
	input[i]=a[i]-a[i-1];
}
q.build(1,1,n+1);
while(m--){
	cin>>f;
	if(f==1){
		cin>>l>>r>>k>>d;
		q.add(1,l,l,k);
		q.add(1,l+1,r,d);
		q.add(1,r+1,r+1,-(k+(r-l)*d));
	}
	else{
		cin>>r;
		cout<<q.search(1,1,r)<<endl;
	}
}
	return 0;
}

2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

SSH 命令从新手入门到安全运维

2048 AI社区

CAD-Assistant 闭环逻辑详解：无训练也能精准建模的核心密码

CAD-Assistant 的闭环逻辑，本质是用 “大模型的推理能力 + 工具的精确性 + 环境的反馈机制”，重构了 CAD 设计的自动化流程。其核心价值在于：零训练成本：无需标注 CAD 数据集，仅通过工具调用和反馈就能适配多样场景；高精度落地：闭环迭代确保结果与需求一致，解决了 VLLM “光说不练” 的痛点；低使用门槛：设计师无需编写代码，仅通过草图、文本就能生成专业 CAD 模型。