# 阿里云天池超级码力在线编程大赛初赛 第2场 ABCD（A.计算几何 判断点在三角形内 D.大施罗德数/超级卡特兰数）

### 思路来源

https://blog.csdn.net/PleasantlY1/article/details/84074637

### A.三角魔法

①PA在PB顺时针，PB在PC顺时针，PC在PA顺时针

②PA在PB逆时针，PB在PC逆时针，PC在PA逆时针

class Solution {
public:
/**
* @param triangle: Coordinates of three points
* @param point: Xiaoqi's coordinates
* @return: Judge whether you can cast magic
*/
typedef long long ll;
struct Point{
ll x,y;
Point(){}
Point(ll xx,ll yy):x(xx),y(yy){}
Point operator-(Point &a){
return Point(x-a.x,y-a.y);
}
};
ll det(Point a,Point b){
return a.x*b.y-a.y*b.x;
}
ll dot(Point a,Point b){
return a.x*b.x+a.y*b.y;
}
bool on(Point pi,Point pj,Point Q){
if(det(Q-pi,pj-pi)==0&&min(pi.x,pj.x)<=Q.x&&Q.x<=max(pi.x,pj.x)&&min(pi.y,pj.y)<=Q.y&&Q.y<=max(pi.y,pj.y)){
return true;
}
return false;
}
bool in(Point a,Point b,Point c,Point p){
Point pa(a-p),pb(b-p),pc(c-p);
ll t1=det(pa,pb),t2=det(pb,pc),t3=det(pc,pa);
__int128 x=t1,y=t2,z=t3;
return x*y>=0 && x*z>=0;
}
string castMagic(vector<vector<int>> &triangle, vector<int> &point) {
Point a(triangle[0][0],triangle[0][1]);
Point b(triangle[1][0],triangle[1][1]);
Point c(triangle[2][0],triangle[2][1]);
Point d(point[0],point[1]);
Point e(b-a),f(c-a);
if(det(e,f)==0){
if(on(a,b,d) || on(a,c,d) || on(b,c,d))return "Yes";
return "No";
}
else{
if(in(a,b,c,d))return "Yes";
return "No";
}
}
};

### B.区间异或

class Solution {
public:
/**
* @param num: array of num
* @return: return the sum of xor
*/
int mn[50005][16],mx[50005][16],lg[50005];
int amx(int l,int r){
int x=lg[r-l+1];
return max(mx[l][x],mx[r-(1<<x)+1][x]);
}
int amn(int l,int r){
int x=lg[r-l+1];
return min(mn[l][x],mn[r-(1<<x)+1][x]);
}
int Intervalxor(vector<int> &num, vector<vector<int>> &ask) {
int n=num.size();
for(int i=1;i<=n;++i)mn[i][0]=mx[i][0]=num[i-1];
lg[1]=0;for(int i=2;i<=n;++i)lg[i]=lg[i/2]+1;
for(int len=1;(1<<len)<=n;++len){
for(int l=1;l+(1<<len)-1<=n;++l){
int r=l+(1<<len)-1;
mx[l][len]=max(mx[l][len-1],mx[l+(1<<(len-1))][len-1]);
mn[l][len]=min(mn[l][len-1],mn[l+(1<<(len-1))][len-1]);
}
}
for(int i=0;i<sz;++i){
ans^=(amx(l1,r1)+amn(l2,r2));
}
return ans;
}
};

### C.五字回文

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

### D.小栖的金字塔

k由一个vector给出，需要对vector里的每个k都求方案数，

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
*/
typedef long long ll;
static const int mod=1e9+7;
static const int N=1e7+10;
int inv[N],ans[N];
void init(int n){
inv[0]=inv[1]=1;
for(int i=2;i<=n;++i)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
ans[0]=ans[1]=1;
for(int i=2;i<=n-1;++i)ans[i]=1ll*(1ll*(6*i-3)*ans[i-1]%mod-1ll*(i-2)*ans[i-2]%mod+mod)%mod*inv[i+1]%mod;
}
int cal(int k,int n){
if(n==k)return 1;
return 1ll*ans[n-k]*2%mod;
}
int pyramid(int n, vector<int> &k) {
init(N-5);
int sz=k.size(),ans=0;
for(int i=0;i<sz;++i){
int x=k[i];
ans=(ans+cal(x,n))%mod;
}
return ans;
}
};

原文作者：Code92007
原文地址: https://blog.csdn.net/Code92007/article/details/108305045
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。