CF ROUND 847(Div3)

最新推荐文章于 2025-01-28 22:41:48 发布

一条大祥脚

最新推荐文章于 2025-01-28 22:41:48 发布

阅读量630

点赞数 12

文章标签：算法

本文链接：https://blog.csdn.net/Maxwell_Newton/article/details/145146464

版权

B

告诉你所有元素和，以及拿走一个最大值的剩余元素和，构造原序列。首先肯定有一个元素是最大值，剩下的就是构造一个最大值不超过某个值的，和为定值的序列。

最简单的构造方式就是元素和均分，这样可以让最大元素尽量小，肯定不会超过最大值的限制

void solve(){
	cin>>n>>m>>k;
	int mx=m-k;
	n--;
	cout<<mx<<' ';
	int a=k/n;
	int b=k%n;
	
	rep(i,1,n){
		if(i<=b){
			cout<<a+1<<' ';
		}
		else{
			cout<<a<<' ';
		}
	}
	cout<<'\n';
}

C

每次从一个排列里拿走一个元素，输出剩余的元素。共n个这样的输出。从这n个残缺的排列里还原原始排列。

如何确定一个元素在序列中的位置？一种方法是：一个元素后面有多少元素是固定的，统计每个数字后面出现过多少个不同元素，就能确定他在原始排列中是第几个

这可以对于每个元素都开一个set实现。遍历这n个残缺的排列，把每个元素后面的元素都加入这个元素的set。由于n=100，这样复杂度是n^3，是可行的

最后根据后面的元素个数降序排列，就是原始排列的顺序

void solve(){
	cin>>n;
	set<int>s[n+1];
	rep(i,1,n){
		vi a(n);
		rep(j,1,n-1){
			cin>>a[j];
		}
		rep(j,1,n-1){
			rep(k,j+1,n-1){
				s[a[j]].insert(a[k]);
			}
		}
	}
	vector<vector<int>>b;
	rep(i,1,n){
		b.pb({s[i].size(),i});
	}
	sort(b.begin(),b.end());
	reverse(b.begin(),b.end());
	rep(i,1,n){
		cout<<b[i-1][1]<<' ';
	}
	cout<<'\n';
}

D

一段连续的数字被称为一段，例如x+1,x+2……x+n，问共有多少段。

这其实和每一站都会上下人，问公交车上人数最大人数有点像，对于出现相同元素，都要分成多层，每一层一个元素只能出现一次。不同之处在于本题每一层，如果中间断开了，会被视为多个。

思路可以借鉴公交车那题，开个map记录每种元素的个数，从小到大遍历所有元素，每遍历到一次，就出现次数减一。遍历时如果断了，也就是不连续，就记录出现了新的一段。如果扫完一轮了，还有元素，就重复这个过程

void solve(){
	cin>>n;
	map<int,int>mp;
	rep(i,1,n){
		int t;
		cin>>t;
		mp[t]++;
	}
	int ans=0;
	while(mp.size()){
		int pre=-1;
		vi del;
		for(auto &[k,v]:mp){
			if(k!=pre+1){
				ans++;
				//cout<<k<<' '<<ans<<'\n';
			}
			pre=k;
			v--;
			if(v==0)del.pb(k);
		}
		for(int x:del)mp.erase(x);
	}
	cout<<ans<<'\n';
}

E

位运算构造。很妙，但仔细想其实也很典。

首先本题的条件是x^y=(x+y)/2，我们又知道x+y=x^y+2(x&y)，可以理解为加法对于01，加完是1，对于11，加完会在更高一位是1，所以要乘2。带入可以得到x^y=2(x&y)。题目给出x^y了，那么x&y我们也可以求出。

那么问题转化成：已知x^y，x&y，构造x,y？这显然可以按位构造，我们可以根据x^y x&y每一位的情况，来判断xy每一位的情况

具体来说，x&y在一位为1，xy在这一位都必须为1，如果x&y为0，去看x^y,如果为1，说明xy在这一位一个1一个0，1可以随便给xy其中一个。如果x^y这一位为0，xy这一位都为0

何时无解呢？x&y=(x^y)/2肯定是整数，所以x^y必须是偶数。并且x^y x&y显然不能在同一位上都为1。出现以上任意一种情况都无解

void solve(){
	int x;
	cin>>x;
	int y=x/2;
	if(x%2==1||(y&x)!=0){
		cout<<-1<<'\n';
		return;
	}
	int a=0,b=0;
	rep(i,0,30){
		if(y>>i&1){
			a|=1<<i;
			b|=1<<i;
		}
		else{
			if(x>>i&1){
				a|=1<<i;
			}
		}
	}
	cout<<a<<' '<<b<<'\n';
}

F

给一棵树上所有点按一个顺序依次染色，每次染色后求当前两个染色点间最小距离。

首先这个问题可以转化为，维护一个dis数组，存每个点到最近的染色点的距离，然后我们每染色一个点的时候，直接查这个点的dis，和之前的最小值取个min就行了

现在的问题就是染色一个点之后怎么更新dis数组。暴力的思想是，从这个新染色的点开始bfs，对搜到的点更新dis。这样太慢了，需要剪枝。一个显然的剪枝是，如果这次bfs到达x点的距离，比这个点到其他染色点的距离更远，就不用更新了，并且这个分支再往下搜索，到这次染色点的距离只会更大，肯定也不会更新了，剪枝这个分支。

另一个不那么显然的剪枝是，我们维护全局最短距离ans，如果当前搜索到的点x,dis[x]>=ans，由于ans是不增的，dis[x]肯定对ans没影响，直接停止搜索。

如果只用第一个剪枝,会tle22。

int c[N],dis[N],ans;
vi g[N];
void bfs(int s){
	dis[s]=0;
	queue<int>q;
	q.push(s);
	while(q.size()){
		int u=q.front();
		q.pop();if(dis[u]>=ans)break;
		for(int v:g[u]){
			if(dis[v]<=dis[u]+1)continue;
			dis[v]=dis[u]+1;
			q.push(v);
		}
	}
}
void solve(){
	int c0;
	cin>>n>>c[0];
	rep(i,1,n-1)cin>>c[i];
	rep(i,1,n){
		g[i].clear();
		dis[i]=n+1;
	}
	rep(i,1,n-1){
		int u,v;
		cin>>u>>v;
		g[u].pb(v);
		g[v].pb(u);
	}
	ans=n+1;
	bfs(c[0]);
	rep(i,1,n-1){
		ans=min(ans,dis[c[i]]);
		bfs(c[i]);
		cout<<ans<<' ';
	}
	cout<<'\n';
}