首页 > 米哈游笔试03/27 部分思路+代码
头像
这像画码
编辑于 2021-04-17 13:09
+ 关注

米哈游笔试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
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;
}



全部评论

(6) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐