首页 > 其他分享 >加塞

加塞

时间:2024-09-28 17:33:50浏览次数:6  
标签:删除 mathit buf obuf 虚点 加塞 dp

加塞

rnk7,\(100+30+10+15=155\)。

题目来源:2022 牛客 OI 赛前集训营-提高组(第三场)

T1 一般图最小匹配

说的很复杂,实际水题。就是从 \(n\) 个数中选 \(2m\) 个数,两个两个求差后,求这个差的和的最小值。

显然排序之后求差是最小的,但显然不能直接贪心,考虑 DP。

先排序,然后设 \(\mathit{dp}_{i,j}\) 表示前 \(i\) 个数选 \(j\) 的方案数,在以下两种情况中取 \(\min\):

  • 不选当前数,即 \(\mathit{dp}_{i-1,j}\);
  • 选当前数,即 \(\mathit{dp}_{i-2,j-1}+a_i-a_{i-1}\)。

初始化 \(\forall\mathit{dp}_{i,j}=\infty\) 且 \(\forall\mathit{dp}_{i,0}=0\),答案即为 \(\mathit{dp}_{n,m}\)。

#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
using namespace std;

char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
	int x=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
template<typename T>
void write(T x,char sf='\n'){
	if(x<0)putchar('-'),x=~x+1;
	int top=0;
	do str[top++]=x%10,x/=10;while(x);
	while(top)putchar(str[--top]+48);
	putchar(sf);
}
constexpr int MAXN=5005;
int n,m,a[MAXN];
long long dp[MAXN][MAXN];

int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;++i)a[i]=read();
	sort(a+1,a+n+1);
	memset(dp,0x3f,sizeof(dp));
	for(int i=0;i<=n;++i)dp[i][0]=0;
	for(int i=2;i<=n;++i)
		for(int j=1;j<=m;++j)
			dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+a[i]-a[i-1]);
	write(dp[n][m]);
	return fw,0;
}

T2 重定向

不难,没搞出来可惜了。

首先,50pts 的 \(O(Tn^2\log n)\) 暴力是好想的,暴力枚举要删除的位置,用 set 维护当前最小能填的数,在最终的序列中取字典序最小的即可。可以用 vector 自带重载小于运算符,直接比较字典序。实际上这个复杂度过不了,不知是否是出题人有意放过,但让我丢了 20pts。

考虑正解。发现复杂度瓶颈主要在求出最优的删除位置,那么我们就调用我们智慧的人类大脑得:

  • 若 \(a_i\ne0\land a_{i+1}\ne0\),那么将 \(i\) 删除最优当且仅当 \(a_i>a_{i+1}\);
  • 若 \(a_i\ne0\land a_{i+1}=0\),那么将 \(i\) 删除最优当且仅当 \(a_i>w\),其中 \(w\) 是当前序列能填的最小数;
  • 若 \(a_i=0\),则只有位置 \(i\) 的后缀最小值小于当前序列能填的最小数时,删除这个后缀最小值第一次出现的位置最优。换句话说,如果后面出现了一个更小的,把这个更小的数放到前面是更优的。

如果没找到,默认删除 \(n\) 即可。注意删除的这个点的值在最后是可以回填进序列中的。找到了最优删除位置,填数就很简单。复杂度 \(O(Tn\log n)\),2s 时限加上出题人的有意防水,能过。

#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
#define INF 0x3f3f3f3f
using namespace std;

char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
	int x=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
template<typename T>
void write(T x,char sf='\n'){
	if(x<0)putchar('-'),x=~x+1;
	int top=0;
	do str[top++]=x%10,x/=10;while(x);
	while(top)putchar(str[--top]+48);
	putchar(sf);
}
constexpr int MAXN=2e5+5;
int T,n,a[MAXN],tmp[MAXN];
int minn[MAXN],pos[MAXN];

int main(){
	freopen("repeat.in","r",stdin);
	freopen("repeat.out","w",stdout);
	T=read();
	while(T--){
		set<int>st;
		n=read();
		for(int i=1;i<=n;++i)pos[i]=0;
		for(int i=1;i<=n;++i)pos[a[i]=read()]=i;
		for(int i=1;i<=n;++i)if(!pos[i])st.emplace(i);
		minn[n+1]=INF;
		for(int i=n;i;--i)minn[i]=min(minn[i+1],a[i]?a[i]:INF);
		int del=n;
		for(int i=1;i<n;++i)
			if(a[i]&&a[i+1]&&a[i]>a[i+1]){
				del=i;st.emplace(a[i]);break;
			}else if(a[i]&&!a[i+1]&&a[i]>*st.begin()){
				del=i;st.emplace(a[i]);break;
			}else if(!a[i]){
				if(minn[i]<*st.begin()){
					a[i]=minn[i],del=pos[a[i]];break;
				}
				a[i]=*st.begin(),st.erase(a[i]);
			}
		for(int i=1;i<=n;++i){
			if(a[i]||del==i)continue;
			a[i]=*st.begin(),st.erase(a[i]);
		}
		for(int i=1;i<=n;++i)if(del^i)write(a[i],' ');
		putchar('\n');
	}
	return fw,0;
}

T3 斯坦纳树

需要用到虚树的思想,不过输出全 1 就有 10pts。

我们首先考虑什么情况下牛的做法会假,实际上就是这种情况:

正确的斯坦纳树边权和是 \(3\),但牛的做法边权和是 \(4\)。

进而我们想到,用询问的点集作为关键点构造虚树,那么一旦虚点(图中是 \(\boldsymbol2\))的度数 \(\boldsymbol{\ge3}\) 时,牛的做法一定会假。

否则,当虚点度数 \(<3\) 时,只有两种情况:

  • 若度数为 \(1\),直接删除虚点,此时必不会影响答案;
  • 若度数为 \(2\),将虚点的两端连起来即可。

但是,这样我们少考虑了一种情况:如果边权是 \(0\),那么即使边被多跑了,答案不会受到影响。

所以我们需要用并查集维护连通块,把边权为 \(0\) 的两端合并,连通块被删除当且仅当它里面的所有点被删除。至于维护,我们从后往前删点(注意这个 trick 已经很老了),按上述策略维护虚点,如果操作后无虚点,则牛的做法为真,否则为假。

#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
using namespace std;

char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
	int x=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
template<typename T>
void write(T x,char sf='\n'){
	if(x<0)putchar('-'),x=~x+1;
	int top=0;
	do str[top++]=x%10,x/=10;while(x);
	while(top)putchar(str[--top]+48);
	if(sf^'#')putchar(sf);
}
constexpr int MAXN=3e5+5;
int n,p[MAXN],cnt[MAXN],ans[MAXN],sum;
struct Edge{
	int u,v,w;
	bool operator<(const Edge&x)const{
		return w<x.w;
	}
}e[MAXN];
int f[MAXN],siz[MAXN];
int find(int x){
	if(f[x]^x)f[x]=find(f[x]);
	return f[x];
}
unordered_set<int>st[MAXN];

void del(int x){
	if(st[x].size()<=2&&!cnt[x]){
		--sum;
		int tmp[3],len=0;
		for(auto v:st[x]){
			tmp[++len]=v;
			st[v].erase(x);
		}
		st[x].clear();
		if(len==2){
			st[tmp[1]].emplace(tmp[2]);
			st[tmp[2]].emplace(tmp[1]);
		}
		for(int i=1;i<=len;++i)del(tmp[i]);
	}
}

int main(){
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	n=read();
	iota(f+1,f+n+1,1);
	for(int i=1,u,v,w;i<n;++i){
		u=read(),v=read(),w=read();
		e[i]={u,v,w};
		if(!w)f[find(u)]=find(v);
	}
	for(int i=1;i<n;++i){
		if(!e[i].w)continue;
		st[find(e[i].u)].emplace(find(e[i].v));
		st[find(e[i].v)].emplace(find(e[i].u));
	}
	for(int i=1;i<=n;++i)++cnt[find(p[i]=read())];
	for(int i=n;~i;--i){
		ans[i]=!sum;
		if(!--cnt[find(p[i])])++sum,del(find(p[i]));
	}
	for(int i=1;i<=n;++i)write(ans[i],'#');
	return putchar('\n'),fw,0;
}

标签:删除,mathit,buf,obuf,虚点,加塞,dp
From: https://www.cnblogs.com/laoshan-plus/p/18438201

相关文章

  • 奔驰加塞事件的启发:交替汇入的入口建议安装监控器 —— 从事后舆论角度出发不如从实际
    新闻:奔驰加塞事件缺失监控曝光疑似车上有人劝说“她后边有俩老人,你跟她嚷什么”这件事就是个没法公论的事情,小白车确实加塞了奔驰,奔驰也确实砸了小白车,而小白车那排之前的车辆也确实被奔驰那排之前的车加了塞,但是也不能说因此小白车加塞奔驰就有理,要我看这件事应该从更高的le......
  • 奔驰加塞事件让我开窍了!揭开汽车营销的“竞争性真相”
    文 |AUTO芯球作者|雷歌广东湛江奔驰车加塞事件突然来了180度反转,你是不是觉得自己稀里糊涂就成了加害者?前几天,某网红曝出河北农业大学某教师开着一辆奔驰车加塞自己的奇瑞车,这位50万粉丝的网红拍摄了视频发布到网上,视频呈现的影像是:网红自己的奇瑞车上坐着一家老小,奔驰车加塞,并......
  • 2022牛客暑假第五场加塞
    M-MaimaiDX2077_"蔚来杯"2022牛客暑期多校训练营(加赛)(nowcoder.com)阅读理解和膜你题。doublepts[5][5]={ {1,1,0.8,0.5,0}, {2,2,1.6,1.0,0}, {3,3,2.4,1.5,0},......