首页 > 其他分享 >[JOI 2015 Final]舞会 解题报告

[JOI 2015 Final]舞会 解题报告

时间:2022-09-01 20:34:43浏览次数:53  
标签:舞会 舞蹈 leq 贵族 2015 JOI Final 熟练度

[JOI 2015 Final]舞会

题目描述

IOI 王国为了庆祝 JOI 公主的生日,举行了舞会。 预定有 N 位贵族要参加舞会。 N 是奇数。将贵族们从 \(1\) 到 \(N\) 编号。每个贵族有一个由整数表示的舞蹈熟练度 。贵族 \(i\) (\(1 \leq i \leq N\)) 舞蹈熟练度为 \(D_i\)。 舞会中,含 JOI 公主在内的 \(N+1\) 人两两一组跳舞。 IOI 王国遵循老手帮新手的传统,按以下方法决定跳舞的分组。

  • 开始时, \(N\) 个贵族排成一列。
  • 直到队列中只剩下一个贵族为止,不断进行以下操作。
  • 调查最前面 \(3\) 个贵族的舞蹈熟练度。
  • 这 \(3\) 个人中舞蹈熟练度最大的贵族称为 \(A\) 。如果存在多个人,从中选出序号最小的称为 \(A\) 。
  • 这 \(3\) 个人中舞蹈熟练度最小的贵族称为 \(B\) 。如果存在多个人,从中选出序号最大的称为 \(B\) 。
  • \(A\) 和 \(B\) 离开队列并组成一组。
  • 这三人中没有被选择的一个人移动到队列最后。
  • 最后剩下的一个人和 JOI 公主一组。

从第 \(1\) 个贵族到第 \(M\)(\(1 \leq M \leq N-2\)) 个贵族的 \(M\) 个贵族已经决定了自己开始时排在队列的第几个。剩下的 \(N-M\) 个贵族的排列方式可以由国王自由决定。

因为 JOI 公主才刚开始学跳舞,国王想知道和 JOI 公主组队的贵族的舞蹈熟练度的最大值。

任务

给出每个贵族的舞蹈熟练度,和 \(M\) 个贵族开始时在队列中的位置。请编写程序求出和 JOI 公主一组的贵族的舞蹈熟练度的最大值。

输入格式

第一行为两个以空格分开的整数 \(N\),\(M\) 。分别表示舞会有 \(N\) 个贵族参加,已经决定排列位置的贵族有 \(M\) 人。
接下来 \(M\) 行中,第 \(i\) 行 (\(1\leq i \leq M\)) 为两个以空格分开的整数 \(D_i,P_i\) 。分别表示第 \(i\) 个贵族的舞蹈熟练度为 \(D_i\)。贵族 i 开始时排在队列的第 \(P_i\) 位。
接下来 N-M 行中,第 \(i\) 行 (\(1\leq i \leq N-M\)) 为一个整数 \(D_{i+M}\)。表示贵族 \((i+M)\) 的舞蹈的熟练度为 \(D_{i+M}\)。

输出格式

输出一行:表示和 JOI 公主组队的贵族的舞蹈熟练度的最大值。

solution

二分答案,但问题在于如何判断是否存在一种排列方式,使得我们能得到这个答案

我们可以发现这个淘汰的过程可以表示为一棵三叉树,那么树根的值就是答案

假设现在二分的答案为\(k\),设值大于等于\(k\)的点为黑点,小于\(k\)的点为白点

不难发现,当且仅当\(x\)的三个儿子中存在两个及以上黑点时,点\(x\)为黑点

所以我们考虑用树形DP,判断答案的合法性

设\(f_x\)表示要让\(x\)点为黑点,最少需要让多少个点为黑点(即最少放多少个\(≥k\)的点)

对于一个位置固定的点,其权值为\(a_i\),其确定的位置为\(b_i\),位置\(b_i\)对应的叶子节点为\(x\):

  • 若\(a_i ≥ k\),则\(f_x=0\)

  • 否则\(f_x=+∞\)

剩下的叶子节点dp值都为1

表示只需要将ta自己变为黑色即可

转移就是从儿子较小的两个转移即可

复杂度\(O(nlogn)\),足以通过此题

code

void build(){//模拟题目中淘汰过程,建树
	queue<ll> q;
	for(ll i=1;i<=n;i++){
		q.push(i);
	}
	ll tot=n;//节点个数
	while(!q.empty()){
		ll x=++tot;//选出来的
		if(q.size()==3) rt=x;//只剩下3个节点了
		for(ll i=1;i<=3;i++){
			add(x,q.front());
			q.pop();
		}
		q.push(x);
		if(x==rt) return ;
	}
}
void dfs(ll k){
	if(k<=n) return ;//叶子节点
	ll mx=0;
	for(ll i=hd[k];i;i=a[i].nxt){
		ll y=a[i].to;
		dfs(y);
		dp[k]+=dp[y];
		mx=max(mx,dp[y]);
	}
	dp[k]-=mx;//选出较小的两个=总和-最大的
}
bool check(ll x){
	memset(dp,0,sizeof dp);
	for(ll i=1;i<=n;i++){
		dp[i]=1;
	}
	for(ll i=1;i<=m;i++){
		if(d[i]>=x) dp[p[i]]=0;
		else dp[p[i]]=INF;
	}
	ll sum=0;
	for(ll i=m+1;i<=n;i++){
		if(d[i]>=x) sum++;
	}
	dfs(rt);
	return dp[rt]<=sum;//判断最终选出来的点若要符合≥x需要放的自由黑点是否足够
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=m;i++){
		scanf("%lld%lld",&d[i],&p[i]);
	}
	for(ll i=m+1;i<=n;i++){
		scanf("%lld",&d[i]);
	}
	for(ll i=1;i<=n;i++){
		v[i]=d[i];
	}
	sort(v+1,v+1+n);//排序,便于二分答案
	//cout<<"---\n"; 
	ll sz=unique(v+1,v+1+n)-v-1;//去重
	build();
	ll l=1,r=sz,ans;
	while(l<=r){
		ll mid=(l+r)>>1;
		if(check(v[mid])){
			l=mid+1;
			ans=mid;
		}else{
			r=mid-1;
		}
	}
	printf("%lld",v[ans]);
	return 0;
}

完结撒花❀

★,°:.☆( ̄▽ ̄)/$:.°★

标签:舞会,舞蹈,leq,贵族,2015,JOI,Final,熟练度
From: https://www.cnblogs.com/Aurora1217/p/16647746.html

相关文章

  • 37. SQL--self join:自连接
    1.前言selfjoin用于将一个表和自身连接,就好像存在两个表一样。为了区分两个表,在sql语句中需要至少重命名一个表。自连接通常用于将表的某个字段与该表的同一字段的......
  • 【Java面试】面试如何让面试官面的很爽,看完这道面试题,finally块一定会执行吗?
    “finally块一定会执行吗?”这是最近一个工作3年的小伙伴去面试的时候遇到的问题。你遇到这个问题会怎么回答呢?大家好,我是Mic,一个工作了14年的Java程序员对于这个问题,......
  • 35. SQL--right join:右连接
    1.前言sqlrightjoin和leftjoin是相对的,rightjoin将返回右表(table2)中的所有记录,即使左表(table1)中没有匹配的记录也是如此。当左表中没有匹配的记录时,rightjoin仍......
  • 33. SQL--inner join:内连接
    1.前言innerjoin是sql中最重要、最常用的表连接形式,只有当连接的两个或者多个表中都存在满足条件的记录时,才返回行。sqlinnerjoin子句将table1和table2中的......
  • 32. SQL--join:联合表
    1.前言Join是“连接”的意思,顾名思义,SQLJOIN子句用于将两个或者多个表联合起来进行查询。联合表时需要在每个表中选择一个字段,并对这些字段的值进行比较,值相同的两条......
  • 板刷 JOISC
    这几年的虽然打过但忘的差不多了,所以也能弄JOISC2014Day1巴士走读随便做。有趣的家庭菜园sb题。历史研究板子题。JOISC2017Day1开荒者sb题。港口设施随便做......
  • 推荐一款国产网络管理工具-FinalShell
    FinalShell是一款免费的国产的集SSH工具、服务器管理、远程桌面加速的良心软件,同时支持Windows,macOS,Linux,它不单单是一个SSH工具,完整的说法应该叫一体化的的服务器,网络管......
  • CCF 201503-1 图像旋转(C++)
    好像旋转矩阵有更好的做法,但是我觉得这样也足够了,如果需要更好的做法,大家得自己在去找一下。我主要是找了下规律,然后做出来的#include<iostream>#include<bits/stdc+......
  • Update Join delete JOIN
    UPDATEINNERJOINUPDATEASETName='whq'FROMTableAASAINNERJOINTableBASBONA.ID=B.IDWHEREA.ID<1000ANDB.Type=2DELETEINNERJOINDELETEAFRO......
  • Joinery——Java的数据处理库
    资源https://joinery.sh/v1.10/api/reference/joinery/DataFrame.htmlhttps://github.com/cardillo/joinery使用maven集成到java项目中<dependency><groupId>sh.jo......