牛客编程巅峰赛S2第4场 - 青铜&白银&黄金

A 牛牛掷硬币
解题思路：硬币全部向上或向下，概率即为1/2^(n-1),保留到小数位最后两位并四舍五入，可以发现1/2^7约为0.007，四舍五入为0.01，1/2^8约为0.039，四舍五入为0.00，故在n>=9时答案全为0.00，n<9时可以直接求，然后转换为string类型返回。

class Solution {
public:
    /**
     * 返回一个严格四舍五入保留两位小数的字符串
     * @param n int整型 n
     * @return string字符串
     */
    string Probability(int n) {
        string str[]={"1.00","0.50","0.25","0.13","0.06","0.03","0.02","0.01"};
        if(n>=9)return "0.00";
        else return str[n-1];
    }
};

B 牛牛摆玩偶
解题思路：区间内才能放玩偶且要放完，最小间隔若更小依然能将所有玩偶放完，但若更大则不能全部放完，满足二分的条件，故使用二分法来找最小间隔的最大值。

/**
 * struct Interval {
 *    int start;
 *    int end;
 *    Interval(int s, int e) : start(start), end(e) {}
 * };
 */

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 玩偶数
     * @param m int整型 区间数
     * @param intervals Interval类vector 表示区间
     * @return int整型
     */
    typedef long long ll;
    int doll(int n, int m, vector<Interval>& intervals) {
        // write code here
        sort(intervals.begin(),intervals.end(),[&](Interval &a,Interval &b)->bool{return a.start<b.start;} );
        ll l=0,r=INT_MAX,ans=0;
        while(l<=r)
        {
            ll mid=(l+r)/2;
            if(check(intervals,mid,n))
            {
                ans=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        return ans;
    }
    bool check(vector<Interval>& intervals,ll mid,int n)
    {
        ll now=intervals[0].start+mid;
        int num=1;
        for(int i=0;i<(int)intervals.size();++i)
        {
            if(now>intervals[i].end)continue;
            now=max(now,(ll)intervals[i].start);//第i个区间里符合间隔mid的第一个位置
            int x=(intervals[i].end-now)/mid+1;
            num+=x;
            now+=mid*x;
        }
        return num>=n;
    }
};

C 交叉乘
解题思路：做题的时候没思路，听了讲解就两个字，妙啊！(还是我太菜了~)
1✖1.........1✖n
. .
. .
n✖1.........n✖n
题目求的就是主对角线下面的等式之和，矩阵里对角线上面的元素和下面的元素和相同，故可以总体来求，答案如下图：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 多次求交叉乘
     * @param a int整型vector a1,a2,...,an
     * @param query int整型vector l1,r1,l2,r2,...,lq,rq
     * @return int整型vector
     */
    typedef long long ll;
    vector<int> getSum(vector<int>& a, vector<int>& query) {
        // write code here
        int n=a.size(),m=query.size();
        vector<__int128>sum(n+1,0);
        vector<__int128>sumsq(n+1,0);
        for(int i=0;i<n;++i)
        {
            sum[i+1]=sum[i]+a[i];//a前缀和
            sumsq[i+1]=sumsq[i]+1LL*a[i]*a[i];//平方和前缀和
        }
        vector<int>ans(m/2,0);
        for(int i=0;i<m;i+=2)
        {
            int l=query[i],r=query[i+1];
            __int128 tmp=sum[r]-sum[l-1];
            tmp=tmp*tmp-(sumsq[r]-sumsq[l-1]);
            tmp=(tmp/2)%1000000007;
            ans[i/2]=tmp;
        }
        return ans;
    }
};