首页 > 其他分享 >P8099 [USACO22JAN] Minimizing Haybales P 题解

P8099 [USACO22JAN] Minimizing Haybales P 题解

时间:2024-11-14 20:10:54浏览次数:1  
标签:const val Haybales int 题解 tr 100005 Minimizing tag

好题
图论的难点在于建图~
首先我们关注到如果两个草堆之间的差大于K,那么他们的位置就是固定的,就相当于给了一些限制,这就是很经典的连边然后拓扑排序。其实你是不是可以直接从小的向大的连边(我没试)然后再做排序。
这一部分代码(粗略验证正确性,赶着写的,可能比较一言难尽)

#include<bits/stdc++.h>
using namespace std;
vector<int> tree[100005];
bool vis[100005];
int du[100005],ans[100005],h[100005],n,m;
void tuopu(){
	int done=0,now,mini;
	while(done<n){
		mini=1e9;
		for(int i=1;i<=n;++i){
			if(!du[i]&&!vis[i]){
				if(h[i]<mini) mini=h[i],now=i;
			}
		}
		vis[now]=1;ans[++done]=now;
		for(int j=0;j<tree[now].size();++j) --du[tree[now][j]];
	}
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",&h[i]);
	for(int i=1;i<n;++i){
		for(int j=i+1;j<=n;++j){
			if(abs(h[i]-h[j])>m) tree[i].push_back(j),++du[j];
		}
	}
	tuopu();
	for(int i=1;i<=n;++i) printf("%d\n",h[ans[i]]);
	return 0;
}

这样的时间和空间复杂度都是\(\Theta(nK)\)的,无法接受,注意到瓶颈在于K,所以我们对可能存在的边数进行一个优化,我们需要每次取出的信息是入度最小的可能点,然后每次还需要对这个点所可能指向的点的入度进行修改(注意我们是在值域上进行操作),可以发现这是一个区间操作,所以用线段树维护。由于值域是1e9的,所以要离散化。看注释。
代码

#include<bits/stdc++.h>
#define ll long long
#define lb lower_bound
#define ls p<<1
#define rs p<<1|1
using namespace std;
const int N=1e5+5;
unordered_map<int,int> mp;
int n,K,a[N],h[N],c[N],tree[N],deg[N];
struct Heap{ll d=N;int id;};//度和编号
struct Seg{
	int l,r;
	ll tag;
	Heap val;
}tr[N<<2];
inline Heap min(const Heap A,const Heap B){
	if(A.d==B.d)return A.id<B.id?A:B;
	else return A.d<B.d?A:B;
}
inline int read(){
	char ch;int x=0,f=1;
	while(!isdigit(ch=getchar())){if(ch=='-')f=-1;}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
inline int lowbit(int x){return x&(-x);} 
inline void add(int x,int k){
	while(x<=n){
		tree[x]+=k;
		x+=lowbit(x);
	}return;
}
inline ll qry(int x){
	ll res=0;while(x){
		res+=tree[x];
		x-=lowbit(x);
	}return res;
}
inline void Build(const int p,const int l,const int r){
	tr[p].l=l,tr[p].r=r;
	if(l==r){
		tr[p].val.d=deg[l],tr[p].val.id=l;
		return;
	}int mid=(l+r)>>1;
	Build(ls,l,mid),Build(rs,mid+1,r);
	tr[p].val=min(tr[ls].val,tr[rs].val);
}
inline void Change(const int p,const int val){tr[p].val.d+=val,tr[p].tag+=val;}//维护的是最小值所以只单点减 
inline void Pushdown(const int p){
	if(!tr[p].tag)return;
	Change(ls,tr[p].tag),Change(rs,tr[p].tag);
	tr[p].tag=0;
}
inline void Mdf(const int p,const int l,const int r,const int val){
    if(l>tr[p].r||r<tr[p].l)return;
	if(tr[p].l>=l&&tr[p].r<=r){
		Change(p,val);return;
	}Pushdown(p);
//	int mid=(tr[p].l+tr[p].r)>>1;
	/*if(l<=mid)*/Mdf(ls,l,r,val);
	/*if(mid<r)*/Mdf(rs,l,r,val);//离散化了,所以不能这样写 
	tr[p].val=min(tr[ls].val,tr[rs].val);
}
int main(){
	n=read(),K=read();
	for(int i=1;i<=n;++i)c[i]=h[i]=read();
	sort(c+1,c+n+1);
	for(int i=1;i<=n;++i){
		int x=lb(c+1,c+n+1,h[i])-c;
		mp[h[i]]++;h[i]=x+mp[h[i]]-1;
	}for(int i=1;i<=n;++i){
		int x=lb(c+1,c+n+1,c[h[i]]-K)-c-1,y=lb(c+1,c+n+1,c[h[i]]+K+1)-c-1;
		deg[h[i]]=i-1+qry(x)-qry(y),add(h[i],1);//x前面的和包含y的后面的都固定,也就是要连边 
	}Build(1,1,n);//for(int i=1;i<=n;++i)printf("%d ",c[i]);printf("\n");//for(int i=1;i<=n<<2;++i)printf("%d %d %d\n",tr[i].l,tr[i].r,tr[i].val.id);
	for(int i=1;i<=n;++i){//这个循环表示取出了几个队头,也就是更新了几个点 
		int u=tr[1].val.id;//每次取最小的可能为队头,和堆优化dij有相似之处 
		printf("%d\n",c[u]);
		int x=lb(c+1,c+n+1,c[u]-K)-c-1,y=lb(c+1,c+n+1,c[u]+K+1)-c-1;//和上面同理的区间
//		printf("%d %d\n%d %d\n%d %d\n%d %d\n%d\n",1,x,y+1,n,u,u,c[u]-K,c[u]+K+1,tr[1].val.d);
		Mdf(1,1,x,-1),Mdf(1,y+1,n,-1);//这些地方都有边,所以全部减 
		Mdf(1,u,u,n);//让这个地方不可能再成为最小 
	}return 0;
} //topo不局限于具体的图,而是维护deg 

标签:const,val,Haybales,int,题解,tr,100005,Minimizing,tag
From: https://www.cnblogs.com/mountzhu/p/18435523

相关文章

  • 【考试题解】NOIP2024(欢乐)加赛3
    目录A.SakurakoandWater题目内容思路代码B.BinomialCoefficients,KindOf题目内容思路代码C.QED'sFavoritePermutation题目内容思路代码D.CardGame题目内容思路代码E.LongWaytobeNon-decreasing题目内容思路代码F.ManyGames题目内容思路代码A.SakurakoandW......
  • COCI19-20#6 Trener题解
    COCI19-20#6Trenerlink一道水题(我真是太弱了啊啊啊啊。众所周知,看到这个题立刻知道他是要选名字长度为$1$到$N$的,而我们知道他每一个名字,所以可以直接用字符哈希去做,因为他每一个名字的字符数是上一层名字的字符数加一,所以对于哈希每个字符串只需要跑三次,分别是自己的这......
  • 【题解】洛谷P11186: 三目运算
    不好玩!!!这是个树形结构,直接暴力模拟,但过不去,但是需要发现答案是个区间,我们对字符串处理时记录最大值最小值,然后到叶子节点时我们将此时的区间存起来,查询时直接二分查询这个数对于的区间就可以了。总结:不好玩!!!#include<bits/stdc++.h>usingnamespacestd;#definelllonglon......
  • 【题解】洛谷P1712: [NOI2016] 区间
    P1712[NOI2016]区间我对尺取法并不敏感,所以感觉有点难度,我们想到按照区间长度排序加入使得满足单调性,直到有一个区间的覆盖次数达到了m就可以计算了,而这个就是尺取法,单调性使得我们答案总是最优的。覆盖次数就可以用线段树做,而且数据范围很大需要离散化,计算答案时注意把答案带......
  • 题解:P11251 [GESP202409 八级] 美丽路径
    题目传送门题目大意给你一颗树,每个结点为黑色或白色。求一条路径,使得路径上距离为奇数的点颜色不同,距离为偶数的点颜色相同,输出这条路径最多能包含多少结点。思路讲解容易想到用树形动态规划搭配dfs解决。将结点1......
  • 2021年6月上海月赛T5题解(做基础123题时遇到的)
    平衡点内存限制: 256 Mb时间限制: 1000 ms题目描述给定一个由 n 个整数组成的数列a1​,a2​,⋯,an​,请为这个数列找到一个平衡点,使得平衡点左侧与右侧的力矩尽量接近。若平衡点为 ak​,则左侧力矩定义为数列中下标小于 k 的各个元素到 ak​ 的距离乘以这些元素......
  • 「AT_diverta2019_2_e」Balanced Piles 题解
    题意描述有一个长度为\(N(2\leN\le10^6)\)的数组,一开始所有元素均为\(0\)。设\(M\)为当前数组中的最大元素,\(m\)是当前数组中的最小元素,你可以执行若干次以下操作:选择一个大小为\(m\)的元素,把他变为\(x\),其中\(M\lex\leM+D\)且\(m<x\)。求有多少种操作方法......
  • [ARC105C] Camels and Bridge 题解
    [ARC105C]CamelsandBridge题解https://www.luogu.com.cn/problem/AT_arc105_c记:这是24年夏天在北京梦熊写的(模拟赛撞原),希望这年夏天fowever。sol首先\(n\)很小,所以可以去暴力枚举顺序,也就是全排列。\(W_s\)表示排列为\(s\)时的间距。又令\(f_i\)为前\(i\)只......
  • [题解]P3119 [USACO15JAN] Grass Cownoisseur G
    P3119[USACO15JAN]GrassCownoisseurG显然我们可以先跑强连通分量,由\(x\)个点缩成的新点\(u\)权值为\(v[u]=x\)。下文中的节点\(1\)均表示缩点后节点\(1\)所在的节点。我们在缩点后的DAG上跑拓扑排序,预处理出\(fa[i]\)和\(fb[i]\),分别表示“\(1\)到\(i\)路径的点权和”,“\(i......
  • 洛谷P11228的C++题解
    题目分析题目题目让我们算出机器人走步后经过了多少个不重复的点这道题不是搜索!直接按照题意模拟就行了。遇到墙就向右转,不是就直行。特别注意:向右转也是一步!一个格子最多算一遍!我们可以用一个标记数组 st,走过的点就打上标记。判断走道的点有没有打上标记,有就不......