超级码力在线编程大赛初赛 第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前端开发要学多久 如何系统学习 Web前端要学习哪些内容呢 前端工程师至少要满足四类客户的需求 前端学习计划思维导图 前端人如何选择自己的技术栈 前端人如何更快地成长 大数据的七大核心具体价值 核心价值究其用户到底是谁 大数据核心技术是什么 该怎么掌握Hadoop知识 未来大数据应用场景广阔 中国将成为全球最大的数据圈
您的位置:首页 >运维 >

超级码力在线编程大赛初赛 第2场 T1-T4题解

文章目录

T3.五字回文T2.区间异或T1.三角魔法T4.小栖的金字塔

T3.五字回文

class Solution {public:/** * @param s: The given string * @return: return the number of Five-character palindrome */int Fivecharacterpalindrome(string &s) {// write your code hereint sz=s.size();string t;int ans=0;for(int i=0;i<sz-4;i++){t=s.substr(i,5);if(t[0]==t[4]&&t[1]==t[3]&&t[0]!=t[1]&&t[0]!=t[2]&&t[1]!=t1[2])ans++;}return ans;}};

T2.区间异或

一开口就知道是老数据结构题了,经典的求区间最大值,数据结构用ST表或线段树均可。
(ST表的模板来自于这篇文章)

const int N=5e4+10;int x,y,k,a[N],lg[N],fmx[N][21],fmi[N][21];vector<int>t;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 n=num.size();lg[0]=-1;for(int i=1;i<=n;i++){a[i]=num[i-1]; // 先把给出的num数组存到a数组中,方便下标从1开始fmx[i][0]=a[i];//从i开始的连续2^0个数的最大值就等于a[i]本身fmi[i][0]=a[i];lg[i]=lg[i/2]+1;//预处理log2(i),因为cmath库中自带的函数log2(x)速度较慢}for(int j=1;j<=20;j++)//O(nlogn)的预处理for(int i=1;i+(1<<j)-1<=n;i++)//i+2^j-1不能超过边界n{fmx[i][j]=max(fmx[i][j-1],fmx[i+(1<<(j-1))][j-1]);//把[i,i+2^j-1]分成左区间[i,i+2^(j-1)-1]和右区间[i+2^(j-1),i+2^j-1],取较大值fmi[i][j]=min(fmi[i][j-1],fmi[i+(1<<(j-1))][j-1]);}int q=ask.size();int ans=0;for(int i=0;i<q;i++){x=ask[i][0];y=ask[i][1];k=lg[y-x+1];//k为方程2^k<=y-x+1的解的最大值,即log2(y-x+1)向下取整int mx=max(fmx[x][k],fmx[y-(1<<k)+1][k]);x=ask[i][2];y=ask[i][3];k=lg[y-x+1];int mi=min(fmi[x][k],fmi[y-(1<<k)+1][k]);ans=ans^(mx+mi);}return ans;}};

T1.三角魔法

计算几何的经典题,运用叉乘(向量积)来判断一个点P是否在三角形ABC内部。
在这里插入图片描述
(上图中i,j,k为x,y,z轴的单位向量)

简单介绍一下原理:叉乘a×b\vec{a}×\vec{b}a×b垂直于a\vec{a}a和b\vec{b}b组成的平面,根据a×b\vec{a}×\vec{b}a×b的正负,可得到a\vec{a}a与b\vec{b}b的相对位置关系。设三维空间中的平面向量a=(x1,y1,0),b=(x2,y2,0)\vec{a}=(x_1,y_1,0),\vec{b}=(x_2,y_2,0)a=(x1​,y1​,0),b=(x2​,y2​,0),那么a×b=(0,0,x1y2x2y1)\vec{a}×\vec{b}=(0,0,x_1y_2-x_2y_1)a×b=(0,0,x1​y2​−x2​y1​),可用右手定则判断a×b\vec{a}×\vec{b}a×b的方向。若x1y2x2y1>0x_1y_2-x_2y_1>0x1​y2​−x2​y1​>0,则b\vec{b}b在a\vec{a}a的左侧,从a\vec{a}a到b\vec{b}b是逆时针,如下图:
在这里插入图片描述
判断一个点P是否在三角形ABC内部,那么求t1=AB×AP,t2=AB×AC,若t1*t2>=0,说明P,C在AB的同一侧(t1*t2>0) 或者 P,C中至少有一个点在AB上(t1*t2=0);其他两种情况类似判断(P,A在BC的同一侧、P,B在CA的同一侧)。

注意还要判断三个点是否共线,共线就不能组成三角形了。

typedef long long ll;class Solution {public:/** * @param triangle: Coordinates of three points * @param point: Xiaoqi"s coordinates * @return: Judge whether you can cast magic */bool istr(int x1,int y1,int x2,int y2,int x3,int y3) // 判断三点是否共线{ll a=(x3-x1)*(y2-y1);ll b=(x2-x1)*(y3-y1);return a!=b; // 不共线,三点可组成三角形}bool judge(int x1,int y1,int x2,int y2,int x3,int y3,int x,int y)// A(x1,y1) B(x2,y2) C(x3,y3) P(x,y)// AB=(x2-x1,y2-y1)// AC=(x3-x1,y3-y1)// BC=(x3-x2,y3-y2)// AP=(x-x1,y-y1)// BP=(x-x2,y-y2)// CP=(x-x3,y-y3)// 判断(x,y)是否在其他三点的内部{ll d=(y-y1)*(x2-x1)-(y2-y1)*(x-x1); // AB×APll q=(y3-y1)*(x2-x1)-(y2-y1)*(x3-x1); // AB×ACif(d*q<0) return false; // 两个叉积异号,说明P,C不在AB的同一侧,那么P在外部d=(y-y2)*(x3-x2)-(y3-y2)*(x-x2);// BC×BPq=(y1-y2)*(x3-x2)-(y3-y2)*(x1-x2); // BC×BAif(d*q<0) return false; // 两个叉积异号,说明P,A不在BC的同一侧,那么P在外部d=(y-y3)*(x1-x3)-(y1-y3)*(x-x3); // CA×CPq=(y2-y3)*(x1-x3)-(y1-y3)*(x2-x3); // CA×CBif(d*q<0) return false; // 两个叉积异号,说明P,B不在CA的同一侧,那么P在外部return true;}string castMagic(vector<vector<int>> &triangle, vector<int> &point) {// write your code hereint ans1=istr(triangle[0][0],triangle[0][1],triangle[1][0],triangle[1][1],triangle[2][0],triangle[2][1]);int ans2=judge(triangle[0][0],triangle[0][1],triangle[1][0],triangle[1][1],triangle[2][0],triangle[2][1],point[0],point[1]);if(ans1&&ans2)return "Yes";else return "No";}};

T4.小栖的金字塔

首先说明一下,这题是个固定的数列,前人已经研究出公式了,我只是在OEIS上查找这个数列…

用f(i)表示从左上角(1,1)到右下角(i,i)的方案数。
先写个打表代码,打表前10项,看看有没有规律。

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N=10;ll dp[N+10][N+10];int main(){ios::sync_with_stdio(false);for(int i=1;i<=N;i++){dp[i][1]=1;for(int j=2;j<=i;j++){dp[i][j]=dp[i][j-1]+dp[i-1][j-1];if(j!=i)dp[i][j]+=dp[i-1][j];}printf("i=%d dp[i][i]=%lld\n",i,dp[i][i]);}return 0;}

得到前10项:
i=1 dp[i][i]=1
i=2 dp[i][i]=2
i=3 dp[i][i]=6
i=4 dp[i][i]=22
i=5 dp[i][i]=90
i=6 dp[i][i]=394
i=7 dp[i][i]=1806
i=8 dp[i][i]=8558
i=9 dp[i][i]=41586
i=10 dp[i][i]=206098

1, 2, 6, 22, 90, 394, 1806, 8558, 41586, 206098看起来确实没什么规律,去OEIS查一下,找到了题目要求的这个数列:http://oeis.org/A006318,Large Schröder numbers(大施罗德数)。

网页显示,Twice A001003 (except for the first term),也就是说,我们要求的大施罗德数是A001003这个数列中每个数的两倍(除了第一项)。

打开A001003这个数列:http://oeis.org/A001003,super-Catalan numbers or little Schroeder numbers(超级卡特兰数/小施罗德数)。找到求超级卡特兰数的公式:

D-finite with recurrence: (n+1) * a(n) = (6*n-3) * a(n-1) - (n-2) * a(n-2) if n>1. a(0) = a(1) = 1.

按上述公式O(n)递推求出超级卡特兰数,除了第一项(注意这里的第一项下标从0开始),大施罗德数 = 超级卡特兰数 * 2。

typedef long long ll;const int N=1e7,mod=1e9+7;ll f[N+10];ll qpow(ll a,ll b){ll s=1;while(b){if(b&1)s=s*a%mod;a=a*a%mod;b/=2;}return s;}ll inv(ll a){return qpow(a,mod-2);}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 */int pyramid(int n, vector<int> &k) {// write your code hereint sz=k.size();int ans=0;for(int i=0;i<=n;i++){if(i<=1)f[i]=1; // f[0]=f[1]=1;else f[i]=((6*i-3)*f[i-1]%mod-(i-2)*f[i-2]%mod+mod)%mod*inv(i+1)%mod;}for(int i=0;i<sz;i++){int pos=n-k[i];if(pos==0)ans=(ans+f[pos])%mod;else ans=(ans+f[pos]*2)%mod;}return ans;}};

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