拼多多2018年秋校招题目解析和答案（自己编写，可能有问题） ...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
using namespace std;

int main()
{
    int offset, n, list1, list2;
    int start1, end1, start2, end2;

    while (cin >> offset >> n >> list1 >> list2)
    {
        //offset还在list1中--start
        if (offset<list1)
        {
            start1 = offset;
            //展示都在list1时
            if (n < list1 -offset )
            {
                end1 = offset + n;
                start2 = 0;
                end2 = 0;
            }
            //当展示填满了list1，去了list2
            else
            {
                end1 = list1;
                start2 = 0;
                if ((n - (list1 - offset)) < list2)//当list2够用的时候
                    end2 = n - (list1 - offset);
                //当list2不够用的时候
                else
                    end2 = list2;
            }
        }
        //如果offset在list1最后一个或者到了list2的时候
        else if ((offset >= list1) &&(offset<=list1+list2))
        {
            start1 = list1;
            end1 = list1;
            start2 = offset - list1;
            //list2够用的话
            if (n < (list2 - (offset - list1)))
            {
                end2 = offset - list1 + n;
            }
            //如果list2不够用的话
            else
                end2 = list2;
        }
        else
        {
            start1 = list1;
            end1 = list1;
            start2 = list2;
            end2 = list2;
        }

        cout << start1 << " " << end1 << " " << start2 << " " << end2 << endl;
    }

    system("pause");
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include<vector>
#include<set>
using namespace std;

using Array = vector<int>;

set<int> dfs(int root, vector<Array> &sons, Array &d, int m)
{
    if (sons[root].size() == 0)
        return set<int>({ 0 });
    vector<set<int> > sts;
    for (auto it = sons[root].begin(); it != sons[root].end(); ++it) {
        sts.push_back(dfs(*it, sons, d, m));
    }
    set<int> ret({ 0 });
    for (auto it = sts.begin(); it != sts.end(); ++it)
        for (auto it2 = it->begin(); it2 != it->end(); ++it2)
            if (d[sons[root][it - sts.begin()]] + *it2 <= m)
                ret.insert(d[sons[root][it - sts.begin()]] + *it2);
    for (auto it_i = sts.begin(); next(it_i) != sts.end(); ++it_i) {
        for (auto it_j = it_i + 1; it_j != sts.end(); ++it_j) {
            for (auto it = it_i->begin(); it != it_i->end(); ++it) {
                for (auto it2 = it_j->begin(); it2 != it_j->end(); ++it2) {
                    if (d[sons[root][it_i - sts.begin()]] + d[sons[root][it_j - sts.begin()]] + *it + *it2 <= m)
                        ret.insert(d[sons[root][it_i - sts.begin()]] + d[sons[root][it_j - sts.begin()]] + *it + *it2);
                }
            }
        }
    }
    return ret;
}

int main()
{
    for (int m, n; cin >> m >> n; ) {
        vector<Array > sons(n);
        Array father(n, -1), d(n, 0);
        int root = 0;
        for (int i = 0, u, v, dd; i < n - 1; i++)
            cin >> u >> v >> dd, d[v] = dd, sons[u].push_back(v), father[v] = u;
        for (; root < (int)father.size() && father[root] != -1; ++root) {}
        set<int> st(dfs(root, sons, d, m));
        cout << (st.size() == 0 ? 0 : *st.rbegin()) << endl;
    }
    system("pause");
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;

int main()
{
    int n;//点数
    int count=0;//计数
    cin >> n;
    vector<vector<int> >point(n, vector<int>(2));
    for (int i = 0; i < n; i++)
    {
        cin >> point[i][0] >> point[i][1];
    }
    for (int i = 0; i < n - 2; i++)
    {
        for (int j = i + 1; j < n - 1; j++)
        {
            int temp1 = point[i][0] * point[j][1] - point[i][1] * point[j][0];
            for (int k = j + 1; k < n; k++)
            {
                int temp2 = point[j][0] * point[k][1] - point[j][1] * point[k][0];
                int temp3 = point[k][0] * point[i][1] - point[k][1] * point[i][0];
                if ((temp1 + temp2 + temp3) != 0)
                    ++count;
            }
        }
    }
    cout << count;
    system("pause");
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <cmath>

using namespace std;
#define MAXSIZE 1000
int main()
{
    long long mmin=0,min=0,max1=0,max2=0,max3 = 3;
    //这个题的关键就在于学会在O(n)的时间复杂度寻找大于最小的2个值和最大的3个值
    //以后还可以递推到最小的m个值和最大的n个值等
    int n;//数组大小
    int i;
    long long a[MAXSIZE];
    cin >> n;
    for (i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (i = 0; i < n; i++)
    {
        if (a[i] < mmin)
        {
            min = mmin;
            mmin = a[i];
        }
        else if (a[i] < min)
            min = a[i];
        else if (a[i] > max3)
        {
            max1 = max2;
            max2 = max3;
            max3 = a[i];
        }
        else if ((a[i] > max2)&&(a[i]<max3))//这里一定要判断小于max3
        {
            max1 = max2;
            max2 = a[i];
        }
        else if ((a[i] > max1)&&(a[i]<max2))//这里一定要判断小于max2
            max1 = a[i];
    }
    long long result;
    long long res1 = mmin*min*max3;
    long long res2 = max1*max2*max3;
    result = (res1 > res2) ? res1 : res2;
    cout << result;
    //system("pause");
    return 0;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
class Bear {
public:
    Bear(int f = 0, int h = 0, int id = 0) :fight(f), hungry(h), id(id) {}
    int fight;//战斗力
    int hungry;//饥饿值
    int id;//熊的ID
};
//定义几个比较
bool cmp_fight(const Bear &a, const Bear &b)
{
    return a.fight > b.fight;
}

bool cmp_id(const Bear &a, const Bear &b)
{
    return a.id < b.id;
}
bool cmp_sugar(const int a, const int b)
{
    return a > b;
}

//主函数
int main()
{
    int n = 0, m = 0;//n个熊，m颗糖
    int i;
    cin >> n >> m;
        vector<int> sugar(m);
        vector<Bear> bear(n);
        for (i = 0; i < m; i++)
        {
            cin >> sugar[i];
        }
        sort(sugar.begin(), sugar.end(), cmp_sugar);
        for (i = 0; i < n; i++)
        {
            cin >> bear[i].fight >> bear[i].hungry;
            bear[i].id = i;
        }
        //为了方便让战斗力强的先吃到，就排序，让战斗力强的在前面
        sort(bear.begin(), bear.end(), cmp_fight);
        //下面开始吃
        for (i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                //如果饥饿值大于等于糖的能量才吃，否则就不吃
                if (bear[i].hungry >= sugar[j])
                {
                    bear[i].hungry -= sugar[j];
                    sugar[j] = 0;
                }
            }
        }
        //把熊的排序恢复过来
        sort(bear.begin(), bear.end(), cmp_id);
        for (i = 0; i < n; i++)
        {
            cout << bear[i].hungry << endl;
        }
        system("pause");
        return 0;
}