8-8日网易笔试（1-3-4）题解

第一道

所有大于3的数都能被分解成若干个2和一个3的和，比如:
4 = 2 + 2, 素数个数= 4 / 2 = 2
5=2 + 3, 素数个数= 5 / 2 = 2, 取下整
6=2 + 2 + 2, 素数个数= 6 / 2 = 2
7=2 + 2 + 3, 素数个数= 7 / 2 = 3，取下整
所以对于数num， 其素数个数 = num/ 2, 取下整

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

void solver(vector<long>& nums, int n)
{

    long  ans = 0;
    for(int i = 0; i < n; i++)
    {
        if(nums[i] == 1)
            continue;
        else
            ans += floor(nums[i] / 2);

    }
    cout<<ans<<endl;
}

int main()
{
    int n;
    cin>>n;
    vector<long> nums(n);
    for(int i = 0; i< n;i++)
        cin>>nums[i];
    solver(nums, n);
    return 0;
}

第三道 平分物品

0、遍历一次数组，计算所有物品的总价值sum，丢弃的物品价值初始化为res = sum;
1、初始化两个桶，每个桶表示一个同学分的的价值之和
2、将数组从小到大排序，从最后一个元素开始，放入第一个桶或第2个桶
3、每次迭代检查两个桶的物品价值是否相等，如果相等，则丢弃的物品价值res=min(res,sum-bucket[0]*2)

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>

using namespace std;
void push(int i, vector<int>& bucket, vector<int> & V, int& res, int& sum)
{
    if(bucket[0] == bucket[1])
        res = min(res, sum - bucket[0] * 2);
    if(i < 0)
        return ;//bucket[0] == bucket[1];
    for(int j = 0; j < 2; j++)
    {
        if(bucket[j] + V[i] > ceil(sum / 2)) //放入第j个桶前判断是否大于sum/2,大于则剪枝
            continue;
        bucket[j] += V[i]; //放第j个桶
        push(i-1, bucket, V, res, sum);
        bucket[j] -= V[i]; // 回溯
    }
}

void solver(vector<int>& V, int n)
{
    if(n == 1)
    {
        cout<<V[0]<<endl;
        return;
    }
    sort(V.begin(), V.end()); //从小到大排序
    vector<int> bucket(2, 0); //  初始化两个桶
    int sum = 0;
    for(int i = 0; i < n;i++) //对数组求和
        sum += V[i];
    int res = sum; //丢弃的物品价值
    for(int i = n-1; i >= 0; i--)
    {
        push(i, bucket, V, res, sum);
    }

    cout<<res<<endl;
}

int main()
{

    int T;
    cin>>T;
    for(int i = 0; i< T;i++)
    {
        int n;
        cin>>n;
        vector<int> V(n);
        for(int j = 0; j< n;j++)
            cin>>V[j];
        solver(V, n);
    }
    return 0;
}

第四题 学术认可

1、根据输入建立一个有向图
2、教授i和教授j相互认可==> （从教授i开始经过深度优先遍历能访问到教授j） && （从教授j开始经过深度优先遍历能访问到教授i）

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

bool dfs(int a, int b, vector<vector<int> > & mat, vector<int>& visit)
{
    /*
    深度优先遍历判断是否能从节点i走到节点j

    */
    if(mat[a][b] == 1)
        return true;
    visit[a] = 1; //记录已访问过的节点
    for(int i = 0; i < mat.size(); i++)
    {
        if(i != a && visit[i] == 0 && mat[a][i] == 1)
        {
            if(dfs(i, b, mat, visit))
                return true;

        }
    }
    return false;
}
void solver(vector<vector<int> > & egde, int n, int m)
{

    //邻接矩阵存储有向图
    vector<vector<int> > mat(n, vector<int>(n, 0));
    for(int i = 0; i< m;i++)
    {
        int x = egde[i][0]-1;
        int y = egde[i][1]-1;
        mat[x][y] = 1;
    }
    int ans = 0;
    for(int i = 0; i < n;i++)
    {
        for(int j = i+1; j < n;j++)
        {
            vector<int> visit1(n, 0);
            vector<int> visit2(n, 0);
            if(dfs(i, j, mat, visit1) && dfs(j, i, mat, visit2))
                ans += 1;
        }
    }
    cout<<ans<<endl;
    return;

}

int main()
{

    int n, m;
    cin>>n>>m;
    vector<vector<int> >  egde(m, vector<int>(2));
    for(int i = 0; i< m;i++)
    {
        for(int j = 0; j<2;j++)
            cin>>egde[i][j];
    }
    solver(egde, n, m);

    return 0;
}