美团笔试4-9

网络or网站trick?，10分钟没登上，我重新退出好几次才登上QAQ
第一题 100%
给定当前时间星期x以及ab:cd（时:分），问k分钟前是星期几以及何时何分

#include <iostream>
#include <cstdio>

using namespace std;

int main() {
    int week, beforeTime;
    string nowT;
    cin >> week >> nowT >> beforeTime;
    int allTime = (week-1)*24*60-beforeTime;
    int addTime = ((nowT[0]-'0')*10+(nowT[1]-'0'))*60+((nowT[3]-'0')*10+(nowT[4]-'0'));
    allTime += addTime;

    while (allTime < 0) { // 必须为0才跳出，小trick
        allTime += 7*24*60;
    }
    week = allTime/(24*60)+1; //
    if(week == 8) {
        week = 1;
    }
    int left = allTime%(24*60);
    int hours = left/60;
    int mins = left%60;
    nowT[0] = hours/10+'0', nowT[1] = hours%10+'0';
    nowT[3] = mins/10+'0', nowT[4] = mins%10+'0';
    cout << week << endl;
    cout << nowT << endl;
}

第二题 100%
给定n个编号的顺序，再给n个编号的顺序，如果第二次存在某个编号出现在任意编号之前，结果加1

#include <iostream>
#include <cstdio>

using namespace std;
const int NMAX = 1e5+5;
int main() {
    int beforeI[NMAX], h[NMAX];
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        int cur;
        cin >> cur;
        beforeI[cur] = i;
        h[i] = cur;
    }
    int cnt = 0;
    int nowH[NMAX], nowI[NMAX];
    for(int i = 0; i < n; i++) {
        cin >> nowH[i];
        nowI[nowH[i]] = i;
    }
    for(int i = 0; i < n; i++) {
        if(beforeI[nowH[i]] > i) {
            cnt++;
        } else {
            for(int k = beforeI[nowH[i]]-1; k >= 0; k--) { // 不能直接判断循环遍历
                if(nowI[h[k]] > i) {
                    cnt++;
                    break;
                }
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

第三题 100%
解决n个Bug，第一天可解决x个Bug,第二天x/k，第三天x/k^2...以此内推（都是向下取整），给定n,k,求最小x

// 二分走起
#include <iostream>
#include <cstdio>

using namespace std;

int check(int x, int k) {
    int cnt = x;
    int cur = k;
    while(x/cur) {
        cnt += x/cur;
        cur *= k;
    }
    return cnt;
}

int main() {
    int n, k;
    cin >> n >> k;
    int low = 1;
    int high = n;
    while(low < high) {
        int mid = (low + high) >> 1;
        int cur = check(mid, k);
        if(cur >= n) {
            high = mid;
//        } else if(cur == n) {
//            ans = mid;
//            break;
//        }
    }
        else {
            low = mid+1;
        }
    }
    cout << high << endl;
    return 0;
}

第四题 9%
三菱锥（四个顶点六条边），从顶点S出发K次能到达出发点的可能性（K=1e6，对p=1e9+7取模）

// 混一波分
#include <iostream>
#include <cstdio>

using namespace std;

int main() {
    int k;
    cin >> k;
    int ans;
    if(k <= 1) {
        ans = 0;
    }
    if(k == 2) {
        ans = 3;
    }
    if(k == 3) {
        ans = 3;
    }
    if(k == 4) {
        ans = 3+3+6;
    }
    cout << ans << endl;
    return 0;
}

第五题，望评论区补充