3.18 完美世界c++后端暑期实习笔试 2道编程题

选择题都是经典八股，啥也不会

代码题第一次写核心代码模式，有点不太习惯，而且没给数据范围属实恶心

1、用树状数组处理出每一位前面严格比它小的数的个数和后面严格比它大的数的个数，然后把乘积加起来，注意要离散化

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param damages int整型vector 技能伤害数组
     * @return int整型
     */
    int pre[20005],suf[20005];
    int tr[20005];
    
    int lowbit(int x)
    {
        return x&-x;
    }
    void add(int x)
    {
        while(x<=20000)
        {
            tr[x]++;
            x+=lowbit(x);
        }
    }
    int query(int x)
    {
        int ret=0;
        while(x)
        {
            ret+=tr[x];
            x-=lowbit(x);
        }
        return ret;
    }
    int FindSkillGroup(vector<int>& damages) {
        // write code here
        vector<int> nums;
        for(int i:damages)
        {
            nums.push_back(i);
        }
        sort(nums.begin(),nums.end());
        nums.erase(unique(nums.begin(),nums.end()),nums.end());
        for(int &i:damages)
        {
            i=lower_bound(nums.begin(), nums.end(), i)-nums.begin()+1;
        }
        for(int i=0;i<damages.size();i++)
        {
            pre[i]=query(damages[i]-1);
            add(damages[i]);
        }
        memset(tr, 0, sizeof(tr));
        for(int i=damages.size()-1;i>=0;i--)
        {
            suf[i]=damages.size()-1-i-query(damages[i]);
            add(damages[i]);
        }
        long long ans=0;
        for(int i=0;i<damages.size();i++)
            ans+=(long long)pre[i]*suf[i];
        return ans;
    }
};

2、dp，我用的记忆化搜索，f[i]表示所有在第i天才获得法力的人数，注意取模

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 拥有法力的玩家数量
     * @param n int整型 天数
     * @param delay int整型 
     * @param forget int整型 
     * @return int整型
     */
    int mod=1e9+7;
    vector<int> f;
    int dfs(int x,int delay,int forget)
    {
        if(x<=0)
            return 0;
        if(f[x])
            return f[x];
        for(int i=0;i<forget-delay;i++)
        {
            f[x]=(f[x]+dfs(x-delay-i,delay,forget))%mod;
        }
        return f[x];
    }
    int PlayerOfMana(int n, int delay, int forget) {
        // write code here
        f.resize(n+5,0);
        f[1]=1;
        long long ans=0;
        for(int i=0;i<forget;i++)
            ans=(ans+dfs(n-i,delay,forget))%mod;
        return ans;
    }
};