差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:组队训练比赛记录:contest14 [2021/08/12 20:27]
jxm2001
+++ 2020-2021:teams:legal_string:组队训练比赛记录:contest14 [2021/08/13 19:13] (当前版本)
jxm2001
@@ 行 6: / 行 6: @@
 |  B  |  0  |  0  |  0  |
 |  C  |  0  |  0  |  0  |
-|  D  |  0  |  0  |  0  |
+|  D  |  2  |  0  |  0  |
 |  E  |  0  |  0  |  0  |
-|  G  |  0  |  0  |  0  |
+|  G  |  2  |  0  |  0  |
-|  J  |  0  |  0  |  0  |
+|  J  |  2  |  0  |  0  |
 |  K  |  0  |  0  |  0  |
 |  M  |  0  |  0  |  0  |
 ====== 题解 ======
+===== D. Dumae =====
+==== 题意 ====
+要求构造一个 $1\sim n$ 的排列，设元素 $i$ 的位置为 $p_i$，需要满足 $L_i\le p_i\le R_i$。同时有 $m$ 个额外约束，表示 $p_u\lt p_v$。
+==== 题解 ====
+首先如果 $p_u\lt p_v$，则连一条有向边 $u\to v$。然后进行拓扑，如果出现环显然无解。接下来考虑将从小到大考虑每个位置上的数。
+如果不存在所有形如 $u\to v$ 的约束，那么一种经典的做法为从所有未被选中且满足 $L_i$ 不小于当前位置的点中选中 $R_i$ 最小的点放入该位置。
+对于每个限制 $u\to v$，显然要先选 $u$ 再选 $v$，于是可以更新约束 $R_u=\min(R_u,R_v-1)$。
+然后选位置时从当前入度为 $0$ 且 $L_i$ 不小于当前位置的点中选择一个 $R_u$ 最小的点。时间复杂度 $O(n\log n+m)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=3e5+5,MAXM=1e6+5;
+struct Edge{
+	int to,next;
+}edge[MAXM];
+int head[MAXN],edge_cnt,deg[MAXN];
+void Insert(int u,int v){
+	edge[++edge_cnt]=Edge{v,head[u]};
+	head[u]=edge_cnt;
+	deg[v]++;
+}
+int L[MAXN],R[MAXN],ans[MAXN];
+vector<int> c[MAXN];
+struct cmp{
+	bool operator () (const int a,const int b){
+		return R[a]>R[b];
+	}
+};
+int temp[MAXN],tp[MAXN];
+bool topu(int n){
+	int tpn=0;
+	queue<int> q;
+	_rep(i,1,n){
+		temp[i]=deg[i];
+		if(deg[i]==0)
+		q.push(i);
+	}
+	while(!q.empty()){
+		int u=q.front();q.pop();
+		tp[++tpn]=u;
+		for(int i=head[u];i;i=edge[i].next){
+			int v=edge[i].to;
+			deg[v]--;
+			if(deg[v]==0)
+			q.push(v);
+		}
+	}
+	if(tpn!=n)
+	return false;
+	for(int j=n;j;j--){
+		int u=tp[j];
+		for(int i=head[u];i;i=edge[i].next){
+			int v=edge[i].to;
+			R[u]=min(R[u],R[v]-1);
+		}
+	}
+	_rep(i,1,n)
+	deg[i]=temp[i];
+	return true;
+}
+int main(){
+	int n=read_int(),m=read_int();
+	_rep(i,1,n){
+		L[i]=read_int();
+		R[i]=read_int();
+	}
+	while(m--){
+		int u=read_int(),v=read_int();
+		Insert(u,v);
+	}
+	if(!topu(n)){
+		puts("-1");
+		return 0;
+	}
+	_rep(i,1,n){
+		if(deg[i]==0)
+		c[L[i]].push_back(i);
+	}
+	priority_queue<int,vector<int>,cmp> q;
+	bool flag=true;
+	_rep(t,1,n){
+		for(int u:c[t])
+		q.push(u);
+		if(q.empty()){
+			flag=false;
+			break;
+		}
+		int u=q.top();q.pop();
+		if(R[u]<t){
+			flag=false;
+			break;
+		}
+		ans[t]=u;
+		for(int i=head[u];i;i=edge[i].next){
+			int v=edge[i].to;
+			deg[v]--;
+			if(deg[v]==0){
+				if(L[v]<=t)
+				q.push(v);
+				else
+				c[L[v]].push_back(v);
+			}
+		}
+	}
+	if(flag){
+		_rep(i,1,n)
+		enter(ans[i]);
+	}
+	else
+	puts("-1");
+	return 0;
+}
+</code>
+</hidden>
 ===== G. Fascination Street =====
@@ 行 70: / 行 192: @@
 	}
 	enter(ans);
+	return 0;
+}
+</code>
+</hidden>
+===== J. Histogram Sequence =====
+==== 题意 ====
+给定一个序列 $h$，其中二元组 $(a,b)(a\le b)$ 的权重为 $(b-a+1)\min (h[a\sim b])$。
+将所有 $\frac {n(n-1)}2$ 个二元组按权重从小到大排序，求第 $L\sim R$ 个二元组。
+==== 题解 ====
+考虑构造 $n$ 个集合，第 $i$ 个集合维护所有 $\min (h[a\sim b])=h_i$ 的 $(a,b)$ 二元组。
+另外为了保证每个二元组恰属于一个集合，强制规定偏序：当 $h_i=h_j$ 时如果 $i\lt j$ 则 $\min(h_i,h_j)=h_i$。
+单调栈求出每个集合对应的左边界 $L_i$ 和右边界 $R_i$。对每个集合和给定 $S$，显然可以 $O(1)$ 计算出所有满足 $w(a,b)\lt S$ 的二元组个数。
+于是二分答案求出第 $L$ 个二元组的取值 $S$，然后将每个集合转化为类似迭代器的形式丢入优先队列，求出第 $L\sim R$ 个二元组。
+时间复杂度 $O(n\log V+(R-L)\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=3e5+5;
+int h[MAXN],st[MAXN],vl[MAXN],vr[MAXN];
+LL cal(LL n,LL len){
+	len=min(n,len);
+	return len*(n+n+1-len)/2;
+}
+LL check(int n,LL s){
+	LL ans=0;
+	_rep(i,1,n){
+		LL len=(s-1)/h[i];
+		ans+=cal(vr[i]-vl[i]+1,len)-cal(vr[i]-i,len)-cal(i-vl[i],len);
+	}
+	return ans;
+}
+int cal2(int n,int len){
+	return max(n-len+1,0);
+}
+struct Node{
+	int i,curlen;
+	LL getS()const{
+		return 1LL*curlen*h[i];
+	}
+	int count(){
+		return cal2(vr[i]-vl[i]+1,curlen)-cal2(vr[i]-i,curlen)-cal2(i-vl[i],curlen);
+	}
+	bool has_next(){
+		return curlen<vr[i]-vl[i]+1;
+	}
+	bool operator < (const Node &b)const {
+		return getS()>b.getS();
+	}
+};
+int main(){
+	int n=read_int();
+	_rep(i,1,n)h[i]=read_int();
+	LL ql=read_int(),qr=read_int();
+	int tp=0;
+	_rep(i,1,n){
+		while(tp&&h[st[tp]]>h[i])tp--;
+		vl[i]=st[tp]+1;
+		st[++tp]=i;
+	}
+	tp=0;
+	for(int i=n;i;i--){
+		while(tp&&h[st[tp]]>=h[i])tp--;
+		if(!tp)vr[i]=n;
+		else
+		vr[i]=st[tp]-1;
+		st[++tp]=i;
+	}
+	LL lef=1,rig=MAXN*1e9,ans;
+	while(lef<=rig){
+		LL mid=lef+rig>>1;
+		if(check(n,mid)<ql){
+			ans=mid;
+			lef=mid+1;
+		}
+		else
+		rig=mid-1;
+	}
+	priority_queue<Node> q;
+	_rep(i,1,n){
+		if(1LL*(vr[i]-vl[i]+1)*h[i]>=ans){
+			Node t=Node{i,(int)(ans/h[i])};
+			if(t.has_next()){
+				t.curlen++;
+				q.push(t);
+			}
+		}
+	}
+	LL pos=check(n,ans+1);
+	for(LL i=ql;i<=qr;i++){
+		if(i>pos){
+			Node t=q.top();q.pop();
+			ans=t.getS();
+			pos+=t.count();
+			if(t.has_next()){
+				t.curlen++;
+				q.push(t);
+			}
+		}
+		space(ans);
+	}
 	return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具