网易互娱4.11笔试题

第一题ac，第二题ac，第三题没怎么看；

第四题被c++的语法搞懵逼了，不知道int **boxes怎么用，搞了一个多小时没写一行代码，感觉思路可能和二维数组差不多；

第一题，9进制小数或整数相加，思路：先把数字分割成小数部分和整数部分，再分别对小数部分和整数部分求和，参考代码：

class Solution {
public:
    /**
     * 接收两个表示9进制数的字符串，返回表示它们相加后的9进制数的字符串
     * @param num1 string字符串 第一个加数
     * @param num2 string字符串 第二个加数
     * @return string字符串
     */
    void split_num(string &num,string &integ,string &decimal){
        int cnt=0;
        for(;cnt<num.size();cnt++){
            if(num[cnt]=='.') break;
            integ+=num[cnt];
        }
        while(++cnt<num.size()) decimal+=num[cnt];
    }
    int add_decimal(string &decimal1,string &decimal2,string &decimal){
        int s1=decimal1.size(),s2=decimal2.size(),sum=0;
        stack<char> st;
        for(int i=max(s1,s2)-1;i>=0;i--){
            if(i<s1) sum+=decimal1[i]-'0';
            if(i<s2) sum+=decimal2[i]-'0';
            if(sum>8) {
                st.push(sum-9+'0');
                sum=1;
            }else{
                st.push(sum+'0');
                sum=0;
            }
        }
        while(!st.empty()){
            decimal+=st.top();
            st.pop();
        }
        return sum;
    }
    void add_integ(string &integ1,string &integ2,string &integ,int carry){
        int s1=integ1.size(),s2=integ2.size();
        stack<char> st;
        for(int i=0;i<max(s1,s2);i++){
            if(s1-1-i>=0) carry+=integ1[s1-1-i]-'0';
            if(s2-1-i>=0) carry+=integ2[s2-1-i]-'0';
            if(carry>8){
                st.push(carry-9+'0');
                carry=1;
            }else{
                st.push(carry+'0');
                carry=0;
            }
        }
        if(carry==1) integ+='1';
        while(!st.empty()){
            integ+=st.top();
            st.pop();
        }
    }
    string add(string num1, string num2) {
        string i1,i2,d1,d2,integ,decimal;
        split_num(num1,i1,d1);
        split_num(num2,i2,d2);
        int carry=add_decimal(d1,d2,decimal);
        add_integ(i1,i2,integ,carry);
        string result=integ;
        if(!decimal.empty()){
            result+='.';
            result+=decimal;
        }
        return result;
    }
};

第二题：N个工人和N个任务，一个工人只能完成一个任务，一个任务必须且只能被一个工人完成，只有工人的能力Wi大于等于任务的难度Ti时，工人才能完成该任务，求可分配的方案种数，结果对M取余数。

思路：对N个工人的能力和N个任务从大到小排序，然后依次遍历每个任务，判断第i个任务可以被几个工人完成，相乘再取余数即可，参考代码。

#include<bits/stdc++.h>
using namespace std;
#define MAX_LEN 200000
long long W[MAX_LEN],T[MAX_LEN];
int main(){
    long long N,M;
    cin>>N;
    for(int i=0;i<N;i++) cin>>W[i];
    for(int i=0;i<N;i++) cin>>T[i];
    cin>>M;
    sort(W,W+N,greater<int>());
    sort(T,T+N,greater<int>());
    long long res=1,j=0;
    for(int i=0;i<N;i++){
        while((j<N)&&(W[j]>=T[i])) j++;
        res=(res*(j-i))%M;
    }
    cout<<res<<endl;
    return 0;
}

#网易互娱2020春招笔试##网易互娱##笔试题目#