米哈游笔试03/27 部分思路+代码

代码不保证完全正确，但思路基本上清晰，仅供参考。

第一道题最长好子字符序列

输入一个字符串s ，找出最长的子字符串满足1807的顺序（但不能是1087或其他顺序其中 1 8 0 7 可以重复）

比如 1180080108707 最长的就是118000007或者118000077 也就是长度为9 所以输出9

很多人用dp只能过90%的原因，事后有人发现普通的dp实现导致881807会输出5，但实际应该是4，所以应该提前对字符串做处理，保证1之前没有其他字符。

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

string preprocess(string s) {
    string ts = "";
    string s1807 = "x1807";
    bool find_one = false;
    for(int i = 0; i < s.size(); i++) {
        if(!find_one && s[i] == '1') {
            find_one = true;
        }
        if(find_one && s1807.find(s[i]) != string::npos) {
            ts += s[i];
        }
    }
    return ts;
}

int main() {
    string s;
    getline(cin, s);
    string s1807 = "x1807";
    s = preprocess(s);
    vector<vector<int>> dp(s.size() + 1, vector<int>(s1807.size(), 0));
    for(int i = 0; i < s.size(); i++) {
        for(int j = 1; j < s1807.size(); j++) {
            if(s[i] == s1807[j]) {
                dp[i + 1][j] = max(dp[i][j], dp[i][j-1]) + 1;
            } else {
                dp[i + 1][j] = dp[i][j];
            }
        }
    }
    cout << dp[s.size()][s1807.size() - 1] << endl;
    return 0;
}

第二道小明去游乐园

游乐场有n个项目

每个项目必须在时间ti前才能玩玩一个项目需要花一个小时小明0点进入游乐场

每个项目有对应的积分玩了能获得积分没玩要扣除相应的积分

求最多能获得多少分

比如

3 1 1

3 6 9

3个项目

分别在3点前 1点前 1点前参加分别的积分是 3 6 9

算上游玩要花的一个小时其实是要在 2点 0点 0 点之前去玩

所以样例最多积分是 9+3-6=6分

这道题，个人认为类似任务调度的题，例如 P2949 [USACO09OPEN]Work Scheduling G

首先所有项目按照时间排序，使用堆（优先队列）管理已选的项目，把获利最小的项目放在堆顶，然后如果已选的项目数量（也可以当作已经消耗的时间）和当前比较的项目的时间更短，证明可以直接选择项目（加入堆），否则判断当前项目和堆顶项目谁的获利更大，更大的就加入其中。

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

struct Game {
    int t;
    int w;
    Game(int tt, int tw) : t(tt), w(tw) {};
    bool operator<(const Game& other) const {
        // 让优先队列从小到大排序
        return w > other.w;
    }
};

bool t_cmp(const Game& g1, const Game& g2) {
    // 按ddl排序
    return g1.t < g2.t;
}

void input(int n, vector<Game>& all, vector<int>& ts, vector<int>& ws) {
    for(int j = 0; j < n; j++) {
        int t;
        cin >> t;
        ts.push_back(t);
    }
    for(int j = 0; j < n; j++) {
        int w;
        cin >> w;
        ws.push_back(w);
    }
    for(int j = 0; j < n; j++) {
        all.push_back(Game(ts[j], ws[j]));
    }
}

long long max_value_games(const vector<Game>& all) {
    long long ans = 0;
    priority_queue<Game> take;
    for(int i = 0; i < all.size(); i++) {
        if(all[i].t <= take.size()) {
            if(take.top().w < all[i].w) {
                ans = ans - take.top().w * 2 + all[i].w;
                take.pop();
                take.push(all[i]);
            }
        } else {
            ans += all[i].w;
            take.push(all[i]);
        }
    }
    return ans;
}

int main() {
    int T;
    cin >> T;
    for(int i = 0; i < T; i++) {
        int n;
        cin >> n;
        vector<Game> all;
        vector<int> ts;
        vector<int> ws;
        input(n, all, ts, ws);
        sort(all.begin(), all.end(), t_cmp);
        cout << max_value_games(all) << endl;
    }
    return 0;
}

第三题输入两个数字作为左右区间求区间内奇数位的和和偶数位的和相等的数字的个数

例如 9-130 有 11 22 33 44 55 66 77 88 99 110 121 等11个输出11

比如 1221这种就是奇数位和偶数位和相等的数字

暂时没有找到非常好的方法，初步理论是奇数位和和偶数位和的差值是 11的倍数（包括0倍）的时候，这个数可以被11整除，而题目里面的相等（也就是0倍数）是一个特殊情况，所以按照11步长递增，判断每个数是不是满足要求。

每个数直接去判断算有点太慢，所以使用数组来模拟进位，并在过程中记录奇数位和偶数位的变换，当没有进位的时候，提前停止，减少复杂度。

#include <iostream>
#include <vector>

using namespace std;

vector<int> i2v(int num) {
    vector<int> v(10, 0);
    int i = 0;
    while(num) {
        v[i++] = num % 10;
        num /= 10;
    }
    return v;
}

int count(int l, int r) {
    vector<int> v = i2v(l);
    int odd_sum = 0;
    int even_sum = 0;
    int count = 0;
    for(int i = 0; i < v.size(); i++) {
        if(i & 0x1) {
            even_sum += v[i];
        } else {
            odd_sum += v[i];
        }
    }
    int carry;
    int old_value;
    for(int i = l; i <= r; i += 11) {
        if(even_sum == odd_sum) {
            count++;
        }

        v[0] += 1;
        odd_sum += 1;
        v[1] += 1;
        even_sum += 1;

        carry = 0;
        for(int j = 0; j < v.size(); j++) {
            if(j > 1 && carry == 0) {
                break;
            }
            old_value = v[j];
            v[j] = v[j] + carry;
            carry = v[j] / 10;
            v[j] = v[j] % 10;
            if(j & 0x1) {
                // 偶数位
                even_sum += (v[j] - old_value);
            } else {
                // 奇数位
                odd_sum += (v[j] - old_value);
            }
        }
    }
    return count;
}

int main() {
    int l, r;
    cin >> l >> r;
    for(int i = l; i <= r; i++) {
        if(i % 11 == 0) {
            l = i;
            break;
        }
    }
    cout << count(l, r) << endl;
    return 0;
}

第四道由序列化先序遍历求中序遍历

给一个由先序遍历序列化的二叉树（字符串）求出它的中序遍历（数字）

比如 A

B C

D E

输入“A(B(D,),C(,E))”

输出 DBACE

扣细节，主要思路是 '（ ' 前面的就是根节点，之后的话，使用栈来处理'（' '）'符号，当栈里面只有一个'（' 并且当前字符是 ' ,'，就可以拆分成左右两个子树，然后递归处理即可，记得处理好叶子节点的情况，叶子节点没有'('和')'。

#include <iostream>
#include <stack>
#include <string>
#include <vector>

using namespace std;

vector<string> output;

void mid_order(const string& s, int l, int r) {
    if(l >= r) {
        return;
    }
    string o;
    stack<char> stk;
    bool find = false;
    for(int i = l; i < r; i++) {
        if(s[i] == '(') {
            find = true;
            o = s.substr(l, i - l);
            for(int j = i; j < r; j++) {
                if(s[j] == '(') {
                    stk.push(s[j]);
                } else if(s[j] == ')' && !stk.empty() && stk.top() == '(') {
                    stk.pop();
                } else if(s[j] == ',' && stk.size() == 1) {
                    mid_order(s, i + 1, j);
                    output.push_back(o);
                    mid_order(s, j + 1, r - 1);
                    break;
                }
            }
            break;
        }
    }
    if(!find) {
        o = s.substr(l, r - l);
        output.push_back(o);
    } 
}

int main() {
    int t;
    cin >> t;
    cin.ignore();
    for(int i = 0; i < t; i++) {
        string s;
        getline(cin, s);
        output.clear();
        mid_order(s, 0, s.size());
        for(int i = 0; i < output.size() - 1; i++) {
            cout << output[i] << " ";
        }
        cout << output.back() << endl;
    }
    return 0;
}

第五题判断凸多边形

给一系列平面坐标把他们按输入顺序首尾相连判断是不是一个凸多边形

tip: 对于边AB BC 如果C在边的同一侧则这个点满足凸多边形

计算几何，简单暴力的去判断就可以通过，重点在如何判断点在边的那一边，这个和判断一个点是否在三角形内部有异曲同工之处，使用向量叉积的z值符号是否同号来判断，叉积只需要计算z = x1*y2 - x2*y1。

#include <iostream>
#include <vector>

using namespace std;

struct Point {
    double x, y;
    Point(double tx, double ty) : x(tx), y(ty) {};
};

double get_side(Point* p1, Point* p2, Point* p3) {
    double x1, x2, y1, y2;
    x1 = p3->x - p1->x;
    x2 = p2->x - p1->x;
    y1 = p3->y - p1->y;
    y2 = p2->y - p1->y;
    return (x1 * y2 - x2 * y1);
}

bool is_porly(const vector<Point*>& ps) {
    for(int i = 0; i < ps.size(); i++) {
        double res = 0;
        int count = 0;
        Point* pi = ps[i], *pj;
        int j;
        if(i == ps.size() - 1) {
            pj = ps[0];
            j = 0;
        } else {
            pj = ps[i + 1];
            j = i + 1;
        }
        for(int k = 0; k < ps.size(); k++) {
            if(k == i || k == j) continue;
            Point* pk = ps[k];
            double side = get_side(pi, pj, pk);
            if(count == 0) {
                res = side;
            } else if(res * side < 0) {
                return false;
            }
            count++;
        }
    }
    return true;
}

int main() {
    int T;
    cin >> T;
    for(int i = 0; i < T; i++) {
        int n;
        cin >> n;
        vector<Point*> ps;
        for(int j = 0; j < n; j++) {
            double x, y;
            cin >> x >> y;
            ps.push_back(new Point(x, y));
        }
        cout << is_porly(ps) << endl;
    }
    return 0;
}

#米哈游##笔经##C++工程师#