牛客编程巅峰赛S2第3场

-> 青铜&白银&黄金
https://ac.nowcoder.com/acm/contest/9246
钻石&王者
https://ac.nowcoder.com/acm/contest/9247
2020-11-24 20:00:00 至 2020-11-24 21:00:00
时长: 1小时
AC 2/3
Rank 195/696
罚时 01:44:59
A (555/1916) 00:20:15 (-1)
B (205/1349) 00:59:44 (-4)
C (56/187)

A 牛牛打怪

牛牛在各个平台被各种传奇游戏的广告轰炸，所以他决定去玩一玩这类的游戏。这类游戏挂机就可以升级，所以牛牛每天都能变强。在第i天里，牛牛能杀死防御力小于等于i的怪物。但由于牛牛还要刷题，所以牛牛每天最多杀一只怪物。这个游戏共有n只怪物，每只怪物的防御力为DEF[i]，牛牛想知道最少要到第几天才能把这n只怪物都杀死。

A.1 比赛时AC

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 
     * @param DEF int整型vector 
     * @return int整型
     */
    int Minimumdays(int n, vector<int>& DEF) {
        // write code here
        sort(DEF.begin(),DEF.end());
        for(int i=1;i<n;i++){
            if(DEF[i]<=DEF[i-1]){
                DEF[i]=DEF[i-1]+1;
            }
        }
        return max(n,DEF[n-1]);
    }
};

思路这样解释比较形象：
从小到大排列后，如果有相同数值的会形成一个平台。
而一天内最多只能打一个，
所以平台内的第二天需要增高一个台阶，
后面类似，小于等于前一个的数值将被更改为前一个的数值加一。
if(DEF[i]<=DEF[i-1]) DEF[i]=DEF[i-1]+1;

A.2 讲解

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 
     * @param DEF int整型vector 
     * @return int整型
     */
    int Minimumdays(int n, vector<int>& DEF) {
        // write code here
        sort(DEF.begin(),DEF.end());
        int cnt=DEF[0],i;
        for(i=1;i<DEF.size();i++){
            cnt=max(DEF[i],cnt+1);
        }
        return cnt;
    }
};

B 简单的公式

现在有3个数组a，b，c
a[1]=2,a[2]=6,对所有的n>=3, $a[n] = 2*a[n-1] + 3*a[n-2]$ 。
b[1]=7,b[2]=35,对所有的n>=3, $b[n] = 3*b[n-1] + 10*b[n-2]$ 。
对所有的n>=1,有c[n] = a[n]*b[n]。
现在给你一个正整数n,返回c[n]%1000000007的值。

B.1 比赛时AC

class Solution {
public:
    /**
     * 返回c[n]%1000000007的值
     * @param n long长整型 即题目中的n
     * @return int整型
     */
    int Answerforcn(long long n) {
        // write code here
        long long a=15,b=n-1,c=1000000007;
        long long ans = 14,base=a;
        base = base % c;

        if(b==0){
        return 14%c;
        } 
        while(b){   
            if(b & 1)
            ans = (ans*base) % c; 
            b = b >> 1;
            base = (base * base) % c; 
         } 
        return ans%c;
    }
};

其实这道题算作弊了。。
一开始没想到怎么算通项公式，
直接用特征方程来解的。

$x_n=p\cdot x_{n-1}+q\cdot x_{n-2}\rightarrow x^2-px-q=0$
解得 $x=a,b$
通项公式为 $x_n=\alpha\cdot a^{n-1}+\beta\cdot b^{n-1}$
其中 $\alpha,\beta$ 由初始条件 $x_1,x_2$ 求得。 $\alpha=\frac{x_2-bx_1}{a-b},\beta=\frac{x_2-ax_1}{b-a}$

后面算出 $c_n=14\cdot 15^{n-1}$ 之后超时了一次。
然后莫名其妙觉得余数会循环(并不会循环)。浪费了很多时间
搜了下“幂取模”，搜到了模板 | 整数快速幂 & 快速幂取模,。

// time：O(logN)
// 这里不考虑指数为负数的情况
int pow_mod(int a,int b,int  c)  
{
    int ans = 1,base=a;// ans：结果；base：底数
    base = base % c;
    //【考虑0次方的情况】
    if(b==0)
    {
        return 1%c;// 任意a的0次幂都是1,故直接用1%c即可 
    } 
    while(b)
    {   
        if(b & 1) // 与运算，判断奇偶性
        ans = (ans*base) % c; 
        b = b >> 1;// 右移一位，相当于除2
        base = (base * base) % c; 
    } 
    return ans;
}

就直接套进来了，一开始还忘记改b=0的情况了，后来改成14，终于AC了，2020-11-24 20:59:44，还差16秒结束，终于赶上了一道。

B.2 讲解

class Solution {
public:
    /**
     * 返回c[n]%1000000007的值
     * @param n long长整型 即题目中的n
     * @return int整型
     */
    typedef long long ll;
    int mod=1e9+7;
    ll power(ll a,ll b){
        ll res=1;
        while(b){
            if(b%2==1)res=res*a%mod;
            b/=2;
            a=a*a%mod;
        }
        return res;
    }
    int Answerforcn(long long n) {
        // write code here
        return 14*power(15,n-1)%mod;
    }
};

C Tree VI

系统中有一棵n个点的完全k叉树，现给出它的DFS先序遍历序列 $a_i$ ，请你还原这棵树，并返回加密后的答案。
答案加密方法：所有边两个端点异或的和，即 $\sum\limits_{i=1}^{n-1}u_i\ xor\ v_i$ ，其中 $(u_i, v_i)$ 为一条树上的边。

下面给出完全二叉树的定义：若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k层所有的结点都连续集中在最左边。
请你根据这个定义进行适度推广，得到完全k叉树的含义。

C.1 比赛时

又没做到这一题，太惨了。

C.2 讲解

class Solution {
public:
    /**
     * 
     * @param k int整型 表示完全k叉树的叉数k
     * @param a int整型vector 表示这棵完全k叉树的Dfs遍历序列的结点编号
     * @return long长整型
     */
    typedef long long ll;
    ll kk,nn,temp=1,res=0;
    vector<int> aa;
    void dfs(int x,int cnt){
        int i;
        for(i=1;i<=kk;i++){
            if(kk*x+i<nn){
                temp++;
                res+=aa[temp-1]^aa[cnt-1];
                dfs(kk*x+i,temp);
            }
            else return;
        }
    }
    long long tree6(int k, vector<int>& a) {
        // write code here
        kk=k ,nn=a.size(),aa=a;
        dfs(0,1);
        return res;
    }
};

引入BFS 辅助思考

D 整除问题

给定 $a, b, c, d$ ，求所有 $x\times y$ 被 2021 整除的 $(x, y)$ 数对个数，其中 $a\le x\le b, c\le y\le d$ 。

D.1 讲解

class Solution {
public:
    /**
     * 寻找所有能整除 2021 的数对个数
     * @param a long长整型 
     * @param b long长整型 
     * @param c long长整型 
     * @param d long长整型 
     * @return long长整型
     */
    long long f(long long a, long long b){
        return a/2021*b+b/2021*a-a/2021*(b/2021)+(a/43-a/2021)*(b/47-b/2021)+(a/47-a/2021)*(b/43-b/2021);
    }
    long long findPairs(long long a, long long b, long long c, long long d) {
        // write code here
        return f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1);
    }
};

容斥原理

牛客编程巅峰赛S2第3场 记录&总结