超级码力在线编程大赛初赛 第二场 UML类图的依赖和关联详解(含代码) 【C语言】新手实现简单的石头剪刀布人机对战 Codeforces Round #666 (Div. 2)题解ABC Codeforces Round #666 (Div. 2)E Monster Invaders 华为今年不会推出运行鸿蒙OS的手机;Deno 1.3.2发布|极客头条 异或在笔试题中的超神表现 超级码力在线编程大赛初赛 第2场 T1-T4题解 1397D. Stoned Game(博弈) Codeforces Round #666(Div.2)A~D题题解 高性能微服务架构技术选型 阿里饿了么Java4面:(数据结构+框架源码+JVM+分布式) 2020java面试总结 使用ffmpeg提取mp4内部日期重命名文件(需lua) 【剑指Offer】56.2 数组中只出现一次的数字,其他出现3次 JAVA二三事-使用IO+Properties实现动态读取文本信息 排序算法的C语言实现C代码(未更完) RT-Thread 内核学习--信号量的初步使用 【剑指Offer】57.2 和为S的连续正数序列 Qt三方库开发技术:QXlsx介绍、编译和使用 4G DTU模块的作用和功能说明 【Tips】- Wifi模块和4G无线通信 【5G核心网】 Identifiers 身份标识 DPDK支持的硬件:CPU、网卡NIC、加密引擎、基带加速器 如何根据普通ip地址获取当前地理位置 人工智能能力提升指导总结 520了,用32做个简单的小程序 程序员的数学--用贝叶斯定理来推断一个案子 文旅部新规:在线旅游网站不得擅自屏蔽删除评价 不得大数据杀熟 苏宁易购开学季消费大数据:手机以旧换新销量增长299% 做实供电服务“133” 助大数据直上“云”端 思科前程序员离职 5 月后“删虚拟机跑路”,240 万美元打水漂,网友:够狠! 抗疫代码成国博最新藏品 阿里程序员“写代码写进国博挺酷” 国博史上首次收藏代码!它们是阿里程序员写下的抗疫代码 威胜信息发布2020年上半年业绩:物联网产业进入爆发期 营收净利双增长 下月发布会不止有新品折叠屏手机 酷开的物联网家居生态野心初现 史上最全的数据库面试题 数据库面试必看 一个数据库SQL查询的数次轮回 百度智能云正式对外发布百度智能云数据库品牌GaiaDB 数据库三大泛式是什么 电力行业网管需求 IT运维管理解决方案 citrix桌面虚拟化中的运维工具Director SRE运维体系的构建和工作职责划分 运维的核心价值是什么 手游开发定制的全过程详解 开发人员透露:《赛博朋克2077》枪支泛滥 成熟的产品经理如何应对“这个需求不合理” CI/CD管道对开发和运维的重要性 APP开发的流程是怎样的 如何开发一个APP 零基础学web前端开发要学多久 如何系统学习
您的位置:首页 >前端 >

超级码力在线编程大赛初赛 第二场

文章目录

1.三角魔法2.区间异或3.五字回文4.小栖的金字塔

1.三角魔法

判断一个点在不在三角形内,有多种方法,这里采用面积法,即整个三角形的面积=3个小三角形面积之和。采用海伦公式计算面积。

class Solution {public:/** * @param triangle: Coordinates of three points * @param point: Xiaoqi"s coordinates * @return: Judge whether you can cast magic */ struct node{double x;double y;};float TriangleArea(node a,node b,node c){double AB,BC,AC,P;AB=sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));AC=sqrt((c.x-a.x)*(c.x-a.x)+(c.y-a.y)*(c.y-a.y));BC=sqrt((c.x-b.x)*(c.x-b.x)+(c.y-b.y)*(c.y-b.y));P=(AB+AC+BC)/2;return sqrt(P*(P-AB)*(P-AC)*(P-BC));}bool IsinTrangle(node a,node b,node c,node d){float s1,s2,s3,sum;s1=TriangleArea(a,b,d);s2=TriangleArea(a,c,d);s3=TriangleArea(b,c,d);sum=TriangleArea(a,b,c);if(0.0000001>fabs(sum-s1-s2-s3))return true;elsereturn false;}string castMagic(vector<vector<int>> &triangle, vector<int> &point) {// write your code herenode a,b,c,d;a.x=triangle[0][0];a.y=triangle[0][1];b.x=triangle[1][0];b.y=triangle[1][1];c.x=triangle[2][0];c.y=triangle[2][1];d.x=point[0];d.y=point[1];if(IsinTrangle(a,b,c,d))return "Yes";elsereturn "No";}};

2.区间异或

求区间最大值最小值,可以用ST算法,然后异或一下即可。刚开始用线段树TLE了QAQ

class Solution {public:/** * @param num: array of num * @param ask: Interval pairs * @return: return the sum of xor */int Intervalxor(vector<int> &num, vector<vector<int>> &ask) {// write your code hereint log[50005];int f1[50005][25];int f2[50005][25];int n=num.size();log[0]=-1;for(int i=1;i<=n;++i){f1[i][0]=num[i-1];f2[i][0]=num[i-1];log[i]=log[i>>1]+1;}for(int j=1;j<=20;++j)for(int i=1;i+(1<<j)-1<=n;++i){f1[i][j]=max(f1[i][j-1],f1[i+(1<<j-1)][j-1]);f2[i][j]=min(f2[i][j-1],f2[i+(1<<j-1)][j-1]);}int ans=0;for(int i=0;i<ask.size();++i){vector<int>cur=ask[i];int l1=cur[0],r1=cur[1];int l2=cur[2],r2=cur[3];int s1=log[r1-l1+1];int s2=log[r2-l2+1];ans^=(max(f1[l1][s1],f1[r1-(1<<s1)+1][s1])+min(f2[l2][s2],f2[r2-(1<<s2)+1][s2]));}return ans;}};

3.五字回文

枚举中间的数,向外扩,判断是否是abcba即可。

class Solution {public:/** * @param s: The given string * @return: return the number of Five-character palindrome */int Fivecharacterpalindrome(string &s) {// write your code hereint len=s.size();int ans=0;for(int i=2;i<len-2;++i){int a=i-2;int b=i-1;int c=i+1;int d=i+2;if(s[a]==s[d]&&s[b]==s[c]&&s[i]!=s[a]&&s[i]!=s[b]&&s[a]!=s[b])ans++;}return ans;}};

4.小栖的金字塔

我们发现从(k,k)到(n,n)的方案数可以转化为(1,1)到(n-k+1,n-k+1)的方案数。然后就是玄学的超级卡特兰数了。我们发现。
Fn*(n+1)=(6*n-3)*Fn-1-(n-2)*Fn-2
方案数就是超级卡特兰数X2。因为左边乘了n+1,要除下去,所以要用到除法取模。

class Solution {public:/** * @param n: The number of pyramid levels n * @param k: Possible coordinates k * @return: Find the sum of the number of plans */long long mod=1e9+7;long long f[10000007];long long quickpow(long long a,long long b){long long res=1;while(b){if(b&1)res=res*a%mod;b>>=1;a=a*a%mod;}return res;}long long cal(int a,int n){if(a==n)return 1;return f[n-a]*2%mod;}int pyramid(int n, vector<int> &k) {// write your code heref[0]=1;f[1]=1;for(int i=2;i<=n;++i)f[i]=((6*i-3)*f[i-1]%mod-(i-2)*f[i-2]%mod+mod)%mod*quickpow(i+1,mod-2)%mod;int x;long long ans=0;for(int i=0;i<k.size();++i){x=k[i];ans=(ans+cal(x,n))%mod;}return ans;}};

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。