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

心得

打了一下被群友吐槽的比赛,阅读体验极差

阴间题面,读题1小时,AC5min,原题警告

思路来源

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

题目

A.三角魔法

给定三个点ABC,再给一个点P,

问P是否在ABC构成的三角形上,在某一条边上也算

 

抄了个计算几何的板子,

判断一个点P是否在三角形ABC内,大致思路,

考虑P向ABC三点连线,形成三个向量PA,PB,PC

那么P如果在ABC内部,下述两种情况必成立之一,

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

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

叉积判断一下向量的顺逆关系,等于0是出现在某一条边上的情形

注意判断ABC三点共线的情况

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) {
        // write your code here
        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.区间异或

给一个5e4长的数组a[],

若干个询问,由一个vector给出,每个询问包括四个数[l1,r1,l2,r2],

这次询问对答案的贡献,是[l1,r1]区间的最大值+[l2,r2]区间的最小值

最终的答案,是每次询问的贡献的异或和,输出最终答案

 

区间RMQ,ST表裸题,线段树也能做

class Solution {
public:
    /**
     * @param num: array of num
     * @param ask: Interval pairs
     * @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) {
        // write your code here
        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]);
            }
        }
        int ans=0,sz=ask.size();
        for(int i=0;i<sz;++i){
            int l1=ask[i][0],r1=ask[i][1],l2=ask[i][2],r2=ask[i][3];
            ans^=(amx(l1,r1)+amn(l2,r2));
        }
        return ans;
    }
};

C.五字回文

签到题,注意abc是三种不同的字母

class Solution {
public:
    /**
     * @param s: The given string
     * @return: return the number of Five-character palindrome
     */
    int Fivecharacterpalindrome(string &s) {
        // write your code here
        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,k)只能向右或向上走,不能越过y=x这条对角线,走到(n,n)的方案数

比如,(k,k)只能走到(k+1,k),而(k+1,k)可以走到(k+1,k+1)或(k+2,k)

数据保证1<=k<=n<=1e7,

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

最后对所有方案数求总和,答案模1e9+7

 

如果听说过大施罗德数或超级卡特兰数,那么这就是个原题

如果手推出前几项然后OEIS一下找到数列,那么这就是个原题

大施罗德数(OEIS A006318),即本题所求,前几项为1, 2, 6, 22, 90, 394, 1806, 8558, 41586, 206098,…

超级卡特兰数前几项为1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049,…

可以发现除了第一项外,其余项大施罗德数=超级卡特兰数*2

而超级卡特兰数递推公式:《阿里云天池超级码力在线编程大赛初赛 第2场 ABCD(A.计算几何 判断点在三角形内 D.大施罗德数/超级卡特兰数)》

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) {
        // write your code here
        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
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞