【突破训练】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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01UniApp 中组件的生命周期是多少-icode9专业技术文章分享
- 2024-11-01如何使用Svg Sprite Icon简化网页图标管理
- 2024-10-31Excel数据导出课程:新手从入门到精通的实用教程
- 2024-10-31Excel数据导入课程:新手入门指南
- 2024-10-31RBAC的权限课程:新手入门教程
- 2024-10-31Svg Sprite Icon课程:新手入门必备指南
- 2024-10-31怎么配置 L2TP 允许多用户连接-icode9专业技术文章分享
- 2024-10-31怎么在FreeBSD上 安装 OpenResty-icode9专业技术文章分享
- 2024-10-31运行 modprobe l2tp_ppp 时收到“module not found”消息提醒是什么-icode9专业技术文章分享
- 2024-10-31FreeBSD的下载命令有哪些-icode9专业技术文章分享