2018年爱奇艺春招C++研发工程师笔试题题解

第一题：牌游戏，纯模拟，没什么好说的

#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
int arr1[15];
int arr2[15];
int pos1, pos2, pos3;
int n, k;
bool flag;
int main() {
    ios::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);
    for (int i = 12; i >= 0; --i) {
        cin >> arr1[i];
    }
    cin >> n;
    flag = true;
    while(n --) {
        cin >> k;
        pos1 = 13 - k;
        pos2 = 0;
        pos3 = 0;
        while(true) {
            if (pos1 < 13) {
                if (flag) {
                    arr2[pos3 ++] = arr1[pos1 ++];
                } else {
                    arr1[pos3 ++] = arr2[pos1 ++];
                }
            }
            if (pos2 < 13-k) {
                if (flag) {
                    arr2[pos3 ++] = arr1[pos2 ++];
                } else {
                    arr1[pos3 ++] = arr2[pos2 ++];
                }
            }
            if (pos1 >= 13 && pos2 >= (13-k)) break;
        }
        flag = !flag;
    }
    if(flag) {
        cout << arr1[12];
        for (int i = 11; i >= 0; --i) cout << " " << arr1[i];
        cout << endl;
    } else {
        cout << arr2[12];
        for (int i = 11; i >= 0; --i) cout << " " << arr2[i];
        cout << endl;
    }
    return 0;
}

第二题：A B C, 两种操作，最短步数相等
动态规划，如果不会的话可以试试我的方法，用优先队列加记忆化水过 233

#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
int a, b, c;
struct node {
    int a, b, c;
    int step;
    bool operator < (const node& t) const {
        return step > t.step;
    }
};
priority_queue<node> pq;
bool vis[105][105][105];

bool check(node tmp) {
    if (tmp.a > 100 || tmp.a < 0) return false;
    if (tmp.b > 100 || tmp.b < 0) return false;
    if (tmp.c > 100 || tmp.c < 0) return false;
    if (vis[tmp.a][tmp.b][tmp.c]) return false;
    vis[tmp.a][tmp.b][tmp.c] = true;
    return true;
}

int solve() {
    memset(vis, false, sizeof(vis));
    node first, t, tmp;
    first.a = a;
    first.b = b;
    first.c = c;
    first.step = 0;
    pq.push(first);
    while(!pq.empty()) {
        t = pq.top();
        //cout << t.step << endl;
        if (t.a == t.b && t.b == t.c) {
            return t.step;
        }
        pq.pop();
        tmp.a = t.a + 1;
        tmp.b = t.b + 1;
        tmp.c = t.c;
        tmp.step = t.step + 1;
        if (check(tmp)) {
            pq.push(tmp);
        }
        tmp.a = t.a + 1;
        tmp.b = t.b;
        tmp.c = t.c + 1;
        tmp.step = t.step + 1;
        if (check(tmp)) {
            pq.push(tmp);
        }
        tmp.a = t.a;
        tmp.b = t.b + 1;
        tmp.c = t.c + 1;
        tmp.step = t.step + 1;
        if (check(tmp)) {
            pq.push(tmp);
        }
        tmp.a = t.a + 2;
        tmp.b = t.b;
        tmp.c = t.c;
        tmp.step = t.step + 1;
        if (check(tmp)) {
            pq.push(tmp);
        }
        tmp.a = t.a;
        tmp.b = t.b + 2;
        tmp.c = t.c;
        tmp.step = t.step + 1;
        if (check(tmp)) {
            pq.push(tmp);
        }
        tmp.a = t.a;
        tmp.b = t.b;
        tmp.c = t.c + 2;
        tmp.step = t.step + 1;
        if (check(tmp)) {
            pq.push(tmp);
        }    
    }
    return 1;
}

int main() {
    ios::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);
    cin >> a >> b >> c;

    cout << solve() << endl;

    return 0;
}

第三题：组成最多的餐盘，每个餐盘放3种糖果，餐盘最多只能放1种酸的和1种苦的，某些苦的和酸的不能放在一起。
做法：用匈牙利算法求出苦的和酸的最大匹配数，再考虑甜的糖果。这样能组成的餐盘数肯定最优。

#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;


int dx[505];
int N, M;
char ch;
int tiannum;
int kunum;
int suannum;
int ku[505];
int suan[505];
int kupos;
int suanpos;
int ta, tb;
int ma[505][505];
int used[505];
int lin[505];
int n;
int dfs(int a)
{
    int i;
    for(i=1;i<=n;i++)
    {
        if(!used[i]&&ma[a][i])
        {
            used[i]=1;
            if(lin[i]==-1||dfs(lin[i]))
            {
                lin[i]=a;
                return 1;
            }
        }
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);
    memset(ma,0,sizeof(ma));
    memset(lin,-1,sizeof(lin));
    cin >> N >> M;
    tiannum = 0;
    kunum = 0;
    suannum = 0;
    kupos = 0;
    suanpos = 0;
    for (int i = 1; i <= N; ++i) {
        cin >> ch;
        if (ch == 'T') {
            dx[i] = 1;
            tiannum ++;
        } else if (ch == 'K') {
            dx[i] = 2;
            ku[kupos ++] = i;
            kunum ++;
        } else {
            dx[i] = 3;
            suan[suanpos ++] = i;
            suannum ++;
        }
    }
    for (int i = 0; i < kupos; ++i) {
        for (int j = 0; j < suanpos; ++j) {
            ma[ku[i]][suan[j]] = 1;
            ma[suan[j]][ku[i]] = 1;
        }
    }
    while(M --) {
        cin >> ta >> tb;
        ma[ta][tb] = 0;
        ma[tb][ta] = 0;
    }

    int sum = 0;
    for(int i=1;i<=N;i++) {
        memset(used,0,sizeof(used));
         if(dfs(i))
              sum++;
    }
    int ans = 0;
    if (tiannum >= sum) {
        ans += sum;
        int left_other = suannum - sum + kunum - sum;
        int left_tian = tiannum - sum;

        if (left_tian >= left_other * 2) {
            ans += left_other;
            left_tian -= left_other * 2;
            ans += left_tian / 3;
        } else {
            ans += left_tian / 2;
        }
    } else {
        ans = tiannum;
    }
    cout << ans << endl;

    return 0;
}