时间戳

首页 > 技术文章 > NOIP2021模拟17

NOIP2021模拟17

SYDevil 2021-10-28 09:30 原文

NOIP2021模拟17

宝藏

不难发现答案关于\(x_i\)单调(当一个数在\(x_i\)大时能作为中位数，那么\(x_i\)小时同样也能)

所以我们先对原序列按\(w_i\)排序

设\(f_i\)表示新序列第\(i\)个点作为中位数时\(x_i\)最大能为多少

我们考虑对于每个位置\(i\)求出\(g_i=\max_{j=i}^nf_j\)然后求答案时使用二分

从后往前计算\(g\),使用四个\(\tt multiset\)维护前\(i-1\)个数中前\(g_i\)小的数,后\(n-i\)个数中前\(g_i\)小的数

从\(g_i\)推往\(g_{i-1}\)时,直接从\(\tt multiset\)中删除/加入即可

由于\(g_i\)是单调的，所以使用类似于尺取的技巧即可

时间复杂度\(O(n\log n)\),当然，如果不嫌麻烦的话四个\(\tt multiset\)可以换成八个\(\tt priority\_queue\)

#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
	T t=0;
	char k;
	bool vis=0;
	do (k=getchar())=='-'&&(vis=-1);while('0'>k||k>'9');
	while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
	return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
int s,m,h[300005];
ll sumx,sumy,T;
pair<int,int>a[300005];
multiset<int>qx,qy,q1,q2;
int main(){fre("treasure");
	s=read;T=read;m=read;
	for(int i=1;i<=s;++i)a[i].first=read,a[i].second=read;
	sort(a+1,a+s+1);
	for(int i=1;i<=s;++i)q1.insert(a[i].second);
	for(int i=s,j=0;i;--i){
		auto w=q1.find(a[i].second);
		if(w!=q1.end())q1.erase(w);
		else{w=qx.find(a[i].second);
			sumx-=*w;
			qx.erase(w);
			if(q1.empty()){
				for(int k=i;k;--k)h[k]=h[k+1];
				break;
			}
			sumx+=*q1.begin();
			qx.insert(*q1.begin());
			q1.erase(q1.begin());
		}
		while(sumx+sumy+a[i].second<=T&&q1.size()&&q2.size()){
			sumx+=*q1.begin();sumy+=*q2.begin();
			qx.insert(*q1.begin());qy.insert(*q2.begin());
			q1.erase(q1.begin());q2.erase(q2.begin());
			++j;
		}
		if(sumx+sumy+a[i].second<=T)h[i]=j;
		else h[i]=j-1;
		q2.insert(a[i].second);
		if(qy.size()&&*qy.rbegin()>*q2.begin()){
			sumy-=*qy.rbegin();sumy+=*q2.begin();
			q2.insert(*qy.rbegin());
			qy.insert(*q2.begin());
			auto w=qy.end();--w;
			qy.erase(w);
			q2.erase(q2.begin());
		}
	}
	while(m--){
		int x=read,l=1,r=s,ans=-1,mid;
		while(l<=r)h[mid=l+r>>1]*2+1>=x?l=(ans=mid)+1:r=mid-1;
		printf("%d\n",~ans?a[ans].first:-1);
	}
	return 0;
}

寻找道路

先用一次\(BFS\)把只走\(0\)边能到的点存下来，再以它们为起点跑\(BFS\),后者的\(\tt BFS\)需要用\(\tt vector\)存下距离相同的点，同时转移

#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
	T t=0;
	char k;
	bool vis=0;
	do (k=getchar())=='-'&&(vis=-1);while('0'>k||k>'9');
	while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
	return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
# define mod 1000000007
int s,m,dis[1000005];
bool vis[1000005];
vector<int>G[1000005],G1[1000005];
queue<int>q1;
queue<vector<int> >q;
int main(){fre("path");
	s=read,m=read;
	for(int i=1;i<=m;++i){
		int u=read,v=read,w=read;
		if(w)G1[u].push_back(v);
		else G[u].push_back(v);
	}q1.push(1);vis[1]=1;
	vector<int>vec;
	while(q1.size()){
		int n=q1.front();q1.pop();
		vec.push_back(n);
		for(int i:G[n])
			if(!vis[i]){
				dis[i]=(dis[n]<<1)%mod;
				vis[i]=1;
				q1.push(i);
			}
	}q.push(vec);
	while(q.size()){
		vector<int>x=q.front();q.pop();
		vec.clear();
		for(int n:x)
			for(int i:G[n])
				if(!vis[i]){
					dis[i]=(dis[n]<<1)%mod;
					vis[i]=1;
					vec.push_back(i);
				}
		if(vec.size())q.push(vec);
		vec.clear();
		for(int n:x)
			for(int i:G1[n])
				if(!vis[i]){
					dis[i]=(dis[n]<<1|1)%mod;
					vis[i]=1;
					vec.push_back(i);
				}
		if(vec.size())q.push(vec);
	}
	for(int i=2;i<=s;++i)printf("%d ",vis[i]?dis[i]:-1);
	return 0;
}

猪国杀

设\(dp_{x,i,j}\)表示使用\(i\)张牌，和为\(j\),牌最大值\(\leq x\)的方案数

我们考虑牌从小往大转移

\(dp_{x-1,i,j}{i+v\choose i}\rightarrow dp_{x,i+v,j+v*x}\)

至于对答案的贡献则是\(dp_{x-1,i,j}{i+v\choose i}{n\choose i+v}(A-i)^{n-i-v}(i+\lfloor\frac{m-k}{x}\rfloor)\rightarrow ans\)

前一步时间复杂度为\(O(mAn\ln m)\)

后一步可以通过将\(\lfloor\frac{m-k}{x}\rfloor\)相等的\(k\)合在一起处理,时间复杂度位\(O(mn^2\ln m)\)

所以时间复杂度位\(O(nm\ln m(A+n))\)

打出来就过了。。。可能是因为常数小

推荐阅读