【突破训练】CF1519E Off by One

2021/5/2 10:27:13

本文主要是介绍【突破训练】CF1519E Off by One,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

我与这道题的故事还挺多的。
整场比赛中,只有前50多位做出了E,甚至有人前半个小时就做出了D剩下的时间依然却无法做出E。因此我觉得E是不属于前面题目难度的题目,也就是能让我突破的题目。
而我现在很想突破。前天和why大佬聊了几句,他和zxy是能“单人拿银”的人,组队后尚且需要运气和突破才能拿金。我只是一个水平一般的普通选手,所以一定要有突破。
因此我要开启突破训练,做以前没做过的难度和知识点。我要尝试突破。

题目解析

题意:在一个二维坐标系中,有n个点,坐标用分数表示,横坐标x=a/b,纵坐标y=c/d。每个点必须移动一次,移动是指由(x,y)移动到(x+1,y)或(x,y+1)。若存在两个点i和j移动后i,j,(0,0)在同一条直线上,那么我们的计数器+1并把i和j删掉。请问计数器最多可以是几,并给出每对选择的i,j分别是几。
1<=n<=2*105, 1<=a_i<=b_i<=c_i<=d_i<=109

这道题有很长的转化过程。

容易想到,两个点在同一条直线上即原点到两个点的斜率相同,对于每个斜率,我们要让它有唯一的表示方法。若点i坐标为(x=a/b,y=c/d),向右移动移动后则为(a/b+1,c/d),同分后为(d*(a+b),b*c),令g=gcd(d*(a+b),b*c),那么斜率表示成(d*(a+b)/g,b*c/g)。向上移动的同理,为(a*d/g,b*(c+d)/g)。

接下来似乎变成了一道匹配题。如果两个点i和j移动后斜率相同,我们将他们之间连一条边,这样就组成了一张图,我们要保证一个点最多连一条边,求选择的边数。然而这张图点数为105级别,边数可能达到1010级别,是不可能实现的。这就是我的思维所限。

恰当的做法是,把每个斜率看作一个点,如果一个点i能达到斜率k_1和k_2,那么就在k_1和k_2之间连一条边。这张无向图点的个数为4*105,边个数为2*105。我们要找到“两条边有一个公共点”这样的边对的最大数量,当然,每条边只能被选择一次。

我们考虑答案的上限。下面说的都是对新图的处理。我们考虑一个点,如果它连有m条边,那么它参与的边对数目最多为m/2。我们要尽可能达到这个上限。

现在考虑dfs树。我们从树的叶子出发,叶子结点为u,它的父亲为fa。如果不包括(u,fa)在内,u连有偶数条边,那么结果一定是把这些边都算到u点上是最优的;如果u连有奇数条边,那么我们把(u,fa)也算到u上去。这样这几条边的归属就决定好了,我们把这几条边删掉,现在fa成为了新的叶子节点,就这样递归考虑。

思路顺理成章,但是实现难度还是有的。这就考验代码能力了,也提醒着我们要熟练掌握STL。有思路却不会写就太憋屈了吧。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=2e5+10;

int n;
pair<pair<LL,LL>,pair<LL,LL>> p[N];
vector<pair<LL,LL>> all;
vector<pair<int,int>> gra[N<<1];
vector<int> can[N<<1];
vector<pair<int,int>> res;
bool vis[N<<1], used[N];

bool dfs(int u, int pre=-1){
	vis[u]=true;
	for(auto &e: gra[u]){
		int v=e.first, i=e.second;
		if(!vis[v]){
			used[i]=true;
			dfs(v,u);
			if(can[v].size()&1){
				can[v].push_back(i);
			}else{
				can[u].push_back(i);
			}
		}else if(v!=pre){
			if(used[i]) continue; 
			used[i]=true;
			can[u].push_back(i);
		}
		
	}
}

int main(){
	scanf("%d", &n);
	for(LL i=1, a, b, c, d, g, x, y; i<=n; ++i){
		scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
		x=d*(a+b); y=b*c;
		g=__gcd(x,y);
		p[i].first={x/g,y/g};
		x=a*d; y=b*(c+d);
		g=__gcd(x,y);
		p[i].second={x/g,y/g};
		all.push_back(p[i].first);
		all.push_back(p[i].second);
	}
	sort(all.begin(),all.end());//关于auto和unique的用法  
	auto pos=unique(all.begin(),all.end());
	all.erase(pos,all.end());
	for(int i=1, u, v; i<=n; ++i){//用下标代替map 
		u=lower_bound(all.begin(),all.end(),p[i].first)-all.begin();
		v=lower_bound(all.begin(),all.end(),p[i].second)-all.begin();
		gra[u].push_back({v,i});
		gra[v].push_back({u,i});
	}
	
	for(int i=all.size()-1; ~i; --i){
		if(!vis[i]) dfs(i);
	}
	
	for(int i=all.size()-1; ~i; --i){
		int sz=can[i].size();
		for(int j=0; j+1<sz; j+=2){
			res.push_back({can[i][j],can[i][j+1]});
		}
	}
	printf("%d\n", res.size());
	for(auto &i: res){
		printf("%d %d\n", i.first, i.second);
	}
	
}

补充

这份代码有很多值得学习的地方。

首先是STL的应用。我对vector、pair、set、map等的认知还停留在高中时期,比如上面的erase(pos1,pos2)我之前是不了解的。
然后是一些函数的应用。比如unique我一直不太会使,__gcd我也是刚知道,虽然手写也很简单。
接下来是c++11的特性,如auto,如{first,second}等,这些都是方便码题的重要工具。
再然后是一些技巧,如用下标代替map的技巧。

最后,我也应该了解一下hash_map(可能也叫unordered_map?),据说是查找会更快一些。

啊,还有好多事需要做啊。



这篇关于【突破训练】CF1519E Off by One的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程