soj2164Problem B:爱恨就在一瞬间

2024-06-12 17:48

本文主要是介绍soj2164Problem B:爱恨就在一瞬间,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

据说soj外网访问不了,那就贴题目吧



本来应该很简单的题,却让我花了很多时间。。。不过学到了更多

开始我的思路就不正确,想的是先枚举两点,再找与这两点共线的点累加,这样以来复杂度就是10e9,根本跑不了,于是比赛时我就没做出来。。。。

吴大大教给我们的思路是,从1到n,枚举这个点与之后的所有点的斜率,再统计数量最多的哪个斜率。这样做的正确性在于,如果在某个枚举点可以取到最大值,且与他相连得点存在至少一个在他前面的话,这个最大值一定会在枚举前面哪个点时得到,故只需要枚举从一点开始往后的点。

对于具体的实现,我就各种学习了,吴大大的代码写的确实好,我终于明白了自己的编程能力和大牛之间差距有多大。。几乎每个地方我都会犯错而大大则写的几乎完美。。

对于怎么判断斜率相等,这里不是用的斜率,三维坐标也没有斜率这个说法,而是由于各点坐标都是整数,就可以将每个点的坐标除以各坐标值的最大公约数,但是相互平行的向量还有可能反向,这里又是让我开眼界的技巧了,如果可以想办法尽量让所有的向量都指向第一卦限。具体操作就是,如果x小于0,各点坐标就反向,因为如果x小于0的话必然要将向量反向;如果x==0且y<0;或x==0且y==0且z<0,也要反向,原因类似。。。虽然这个看起来也没什么,但让我自己想的话可能怎么都想不出来。。。这样,判断各向量共线时就直接比较是否相等就行了。

对于怎么统计共线的点,方法就是先对各向量排序,这样相同的向量(即原本平行而不一定相同的向量)就挨在一起了。而具体的代码实现我出了错误找了半天才找到,而大大写的我第一眼看上去感觉累赘,再看才觉得写的精妙而“不刊一码”,等下看具体代码


一段一段贴大大的代码吧:(注释全是我加的,希望能尽量理解大大的精髓)

const int maxN = 1000 + 10; // 常量声明用const 感觉应该会比我的define 要好一些,因为有了类型int gcd(int a, int b) {  //gcd我自以为没什么问题,写的时候才发现一些微妙之处,一是gcd调用时不用对ab进行排序,二是负数的gcd在这里依然可以直接调用if( b == 0 )  return a;  return gcd(b, a % b);  
}  struct point3 {  int x, y, z;  point3() {}  point3(int _x, int _y, int _z) : x(_x), y(_y), z(_z) {}  inline point3 operator-(const point3 &s) const {  return point3(x - s.x, y - s.y, z - s.z);  }  inline void unit() {  //大大思维的厉害之处,学习了int d = gcd(x, gcd(y, z));  if( d )  x /= d, y /= d, z /= d;  if( x < 0 )  x = -x, y = -y, z = -z;  if( x == 0 && y < 0 )  x = -x, y = -y, z = -z;  if( x == 0 && y == 0 && z < 0 )  x = -x, y = -y, z = -z;  }  inline bool operator<(const point3 &s) const {  //每个函数都加了inline可见大大的谨慎,是我这种粗狂不能比的,不过话说回来,感觉上面那个函数加inline可能不太好,毕竟有递归啊。。而且我测试了下,好像差别也不大。。。可能题目里的数据量还是不够大,还是看不出差别。。if( x == s.x && y == s.y )  return z < s.z;  if( x == s.x )  return y < s.y;  return x < s.x;  //这里也比我一般用的方式高明}  inline bool operator==(const point3 &s) const {  return x == s.x && y == s.y && z == s.z;  }  inline void in() {  scanf("%d %d %d", &x, &y, &z); }  
};<pre name="code" class="cpp">point3 p[maxN]; int n;  point3 q[maxN]; int nq;  
int gao(int idx) {  //不太明白大大的主处理函数为什么要叫gao查了下词典也没找到是什么单词,可能是大大喜欢的人的名字吧^_^nq = 0;  for(int i = idx + 1; i < n; i ++) //正如上面说的,只遍历之后的点 q[nq ++] = p[i] - p[idx];  for(int i = 0; i < nq; i ++)  q[i].unit();  sort(q, q + nq);  int res = 0;  for(int i = 0; i < nq; ) {  //看似平淡无奇,其实滴水不漏,我写的最初版本忽略了最后一个,就一直waint j = i;  while( j < nq && q[i] == q[j] ) j ++;  res = max(res, j - i); i = j;  }  return 1 + res;  
}  int main()  
{  //freopen("data.in", "r", stdin);  //freopen("data.out", "w", stdout);  while( scanf("%d", &n) == 1 ) {  for(int i = 0; i < n; i ++)  p[i].in();  int res = 0;  for(int i = 0; i < n; i ++)  if( n - i < res )  //剪枝break;  else  res = max(res, gao(i));  printf("%d\n", res);  }  return 0;  
}  

 
</pre><br /><p></p><p><br /></p><p>向大大学习,向大大看齐</p><p>最后,还是贴上我的代码吧,虽然丑了点,至少留在这,将来看看自己是不是进步了,还是依然放纵自己</p><p></p><pre name="code" class="cpp">#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX 1010
using namespace std;int gcd(int a,int b)
{if(b==0)return a;return gcd(b,a%b);
}int s[MAX][3];struct point3
{int x,y,z;point3(int _x,int _y,int _z):x(_x),y(_y),z(_z){}point3(){}inline void modify(){int a=gcd(x,gcd(y,z));//必须在前面,gcd 不分正负及大小if(a)x/=a,y/=a,z/=a;if(x<0)x=-x,y=-y,z=-z;else if(x==0&&y<0)x=-x,y=-y,z=-z;else if(x==0&&y==0&&z<0)x=-x,y=-y,z=-z;}bool operator<(point3 other)const{if(x==other.x&&y==other.y)return z<other.z;if(x==other.x)return y<other.y;return x<other.x;}bool operator==(point3 other){return x==other.x&&y==other.y&&z==other.z;}
}ss[MAX];int main()
{int n,i,j,t,p,maxx;while(scanf("%d",&n)==1){if(n<=2){for(i=0;i<n;i++)scanf("%d %d %d",&t,&t,&t);printf("%d\n",n);continue;}maxx=0;for(i=0;i<n;i++)scanf("%d %d %d",&s[i][0],&s[i][1],&s[i][2]);for(i=0;i<n;i++){t=0;//if(n-i+1<maxx)//这里没想清楚//    break;for(j=i+1;j<n;j++){ss[t++]=point3(s[i][0]-s[j][0],s[i][1]-s[j][1],s[i][2]-s[j][2]);}for(j=0;j<t;j++)ss[j].modify();sort(ss,ss+t);for(j=0,p=1;p<=t;p++){//if(t-j<maxx)//不加就会tle//   break;if(!(ss[j]==ss[p])){maxx=max(p-j-1,maxx);j=p;}}}printf("%d\n",maxx+2);}return 0;
}



这篇关于soj2164Problem B:爱恨就在一瞬间的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1054908

相关文章

2024-8月,有没有那一瞬间让你悟到了过去10多年没有想明白的事

今年,我踏上了海外之旅,经历了长达4-5个月的阵痛期,期间充满了迷茫与挑战。无论是语言障碍还是环境适应,都让我感到前所未有的压力,甚至一度想要放弃,卷铺盖走人。然而,在每次的无奈与迷茫中,我都坚持了下来。如今,我已经基本适应了新的环境,是时候开始真正做些事情了。 最近,我研究了2012实验室和ICT基础设施的组织结构,看到了许多高级别总裁的身影。我不禁思考,是什么驱使他们能够在如此巨大的压力下持续

vue项目按键回车页面刷新且路由带?一瞬间消失

vue项目按键回车页面刷新且路由带?一瞬间消失 这是因为页面中带elementui表单,且表单中只有一个输入框,在该输入框中按下回车是提交表单 阻止这一默认行为,可以在el-form标签中添加@submit.native.prevent <el-form @submit.native.prevent></el-form>

JAVA WEB里头有关url-pattern的爱恨情仇(搜集了部分人的介绍)

1、以”/’开头和以”/*”结尾的是用来做路径映射的 2、以前缀”*.”开头的是用来做扩展映射的 ① 完全匹配   <url-pattern>/test/list.do</url-pattern>   ② 路径匹配   <url-pattern>/*</url-pattern> struts2匹配根路径下的全部请求 ③ 扩展名匹配   <url-pattern>*.do</url-p

Android之打开APP部分页面(Activity)的一瞬间手机状态栏会变成蓝色解决办法

一、问题 我们在打开app部分页面的时候状态栏是蓝色的,一闪而过。    二、原因和解决办法 我们在AndroidManifest.xml给application配置主题,然后主题是这一样的 <style name="*****" parent="*****"><!-- Customize your theme here. --><item name="color

我与今目标的爱恨情仇

大家最近谈论的话题莫过于今目标了,其实不单单是今目标的问题,卫生,博客,纪律都有问题,单单是这几个方面,纠其根本还是我们的思想有问题,我们从根儿上还是没有管理好我们自己,虽不能说是鼠目寸光吧,但是眼光还是不够长远,没有从根本上把自己当做精英,当做贵人,当做一个能有所作为的人,所以造就了现在的我们,浑身还有这么多杂七杂八的坏毛病。          这次的导火索是今目标,那还是从今目

PID微分器与滤波器的爱恨情仇

文章目录 1 先说噪声2 噪声对于系统的影响3 对于PID控制器的影响4 加入滤波器4.1 传递函数4.2 串联微分的等效形式反馈积分 5 C语言实现6 参考 1 先说噪声 在电子设备等电路系统中,噪声是不被系统需要的电信号;电子设备产生的噪声会由于多种不同的影响而产生很大的差异。 在通信系统中,噪声是一个错误或不希望出现的随机干扰从而作用于有效的信号。 2 噪声对于系统

看马斯克与OpenAI的爱恨情仇,AGI之路会走向何方?

揭秘马斯克与OpenAI的决裂:AI的未来将何去何从? ©作者|Steven 来源|神州问学 引言 2024 年 3 月 1 日,时任OpenAI联合创始人的Elon Musk(下文简称:马斯克)将现任 CEO、创始人Sam Altman(下文简称:阿尔特曼)告上法庭。马斯克在详细的诉讼文件中指控阿尔特曼和公司其他初创人违反了 OpenAI 的创立协议,该协议旨在开发对全人

【C++进阶】红黑树的复仇(红与黑的爱恨厮杀)

🪐🪐🪐欢迎来到程序员餐厅💫💫💫           主厨:邪王真眼 主厨的主页:Chef‘s blog    所属专栏:c++大冒险    总有光环在陨落,总有新星在闪烁 引言: 之前我们学习了 AVL树,不得不惊叹于他那近乎绝对的平衡,然而也惋惜于插入删除效率的低下,今天要讲的红黑树则是以相对的平衡换来了插入删除效率的大幅提高,可谓是各有千秋 ps:建议

MySQL事务与储存引擎的爱恨情仇 (:=)

事务的概念 是一种机制、一个操作序列,包含了一组数据库操作命令,并且把所有的命令作为一个整体一起向系统提交或撤销操作请求,即这一组数据库命令要么都执行,要么都不执行是一个不可分割的工作逻辑单元,在数据库系统上执行并发操作时,事务是最小的控制单元适用于多用户同时操作的数据库系统的场景,如银行、保险公司及证券交易系统等等 心通过事务的整体性以保证数据的一致性 事务的ACID特点 隔离性(lsol

19.题目:编号3865 Alice与Bob的爱恨情仇

题目: ###该题主要考察思维、和博弈 (写起来容易,但是不太好想) #include<bits/stdc++.h>using namespace std;int main(){int n,k;cin>>n>>k;int ans=0,x;while(n--){cin>>x;ans+=x%2;}if(ans%2){cout<<"Alice"<<'\n';}else{cout<<"Bob"<<