9.4美团笔试(AK代码)

T1:DP

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 50;
const LL MOD = 998244353;
LL dp[N][2][2];//dp[i][j][k] 表示前i个字符 倒数第二个是j,倒数第一个是k的方案数。0表示a,1表示b
int main() {
    int n; cin >> n;
    if(n <= 3) {
        cout <<n * 2;
        return 0;
    }
    dp[3][0][0] = dp[3][1][1] = 2;
    dp[3][0][1] = dp[3][1][0] = 1;
    for(int i = 4; i <= n; i++) {
        dp[i][0][0] = (dp[i-1][0][0] + dp[i-1][1][0]) % MOD;
        dp[i][0][1] = dp[i-1][0][0];
        dp[i][1][0] = dp[i-1][1][1];
        dp[i][1][1] = (dp[i-1][0][1] + dp[i-1][1][1]) % MOD;
    }
    LL ans = 0;
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 2; j++) {
            ans += dp[n][i][j];
            ans %=MOD;
        }
    }
    cout << ans;
    return 0;
}

/*
3

6
*/

T2:跑floyd

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e2+ 50;
const LL MOD = 998244353;
LL dp[N][2][2];
int f[N][N];
vector<int> e[N];
int main() {
    int n, m; cin >> n >> m;
    memset(f, 63, sizeof f);
    int limit = f[0][0];
    for(int i = 1; i <= n; i++) {
        f[i][i] = 0;
        int k; cin >> k;
        while(k--) {
            int x; cin >> x;
            e[x].push_back(i);
        }
    }
    for(int i = 1; i < N; i++){
        for(int j = 0; j < e[i].size(); j++) {
            for(int k = 0; k < e[i].size(); k++) {
                int S = e[i][j];
                int T = e[i][k];
                f[S][T] = f[T][S] = min(f[S][T], 1);
            }
        }
    }

    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(f[i][j] == limit) {
                f[i][j] = -1;
            }
            cout << f[i][j];
            if(j != n) {
                cout << ' ';
            }
        }
        cout << "\n";
    }
    return 0;
}
/*

3 2
1 1
2 1 2
1 2

0 1 2
1 0 1
2 1 0
*/

T3:变成ccccc...aaaaa..就行,倒着计数每个a后面有多少个c

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 50;
const LL MOD = 998244353;
LL dp[N][2][2];
int main() {
    int n; cin >> n;
    string s; cin >> s;
    LL ans = 0;
    int cnt_c = 0;
    for(int i = n-1; ~i; i--){
        cnt_c += s[i] == 'c';
        if(s[i] == 'a') {
            ans += cnt_c;
        }
    }
    cout << ans;
    return 0;
}
/*
4
acca

2
*/

T4:四元环计数

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e2 + 50;
const LL MOD = 998244353;
int mp[N][N];
vector<int>e[N], q[N];
int ID[N], du[N],RANK[N], num[N];
int main() {    
    int n; cin >> n;
    for(int i = 1; i <= n; i++) {
        ID[i] = i;
        for(int j = 1; j <= n; j++) {
          int x; cin >> x;
          if(x){
              e[i].push_back(j);
          }
        }
    }
    for(int i = 1; i <= n; i++) {
        du[i] = e[i].size();
    }
    sort(ID + 1, ID + n + 1,[](int a,int b) {
        if(du[a] == du[b]) {
            return a < b;
        }
        return du[a] < du[b] ;
    });
    LL ans = 0;
    for(int i = 1; i <= n; i++) {
        RANK[ID[i]] = i;
    }
    for(int i = 1; i <= n; i++) {
        for(int x : e[i]) {
            if(RANK[x] > RANK[i]) {
                q[i].push_back(x);
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int x : e[i]) {
            for(int y : q[x]) {
                if(RANK[y] > RANK[i]) {
                    ans += num[y];
                    num[y]++;
                }
            }
        }
        for(int x : e[i]) {
            for(int y : q[x]) {
                if(RANK[y] > RANK[i]) {
                    num[y] = 0;
                }
            }
        }
    }
    cout << ans;
    return 0;
}

/*

6
0 1 1 1 0 0
1 0 1 0 1 0
1 1 0 0 0 1
1 0 0 0 1 1
0 1 0 1 0 1
0 0 1 1 1 0

3
*/

T5:滑动窗口求区间最大/最小值 + 枚举

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 50;
const LL MOD = 998244353;
LL a[N];
int MAX[N], MIN[N];
deque<int> que, quee;
int main() {
    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        while(!que.empty() && i - que.front() + 1 > m) que.pop_front();
        while(!que.empty() && a[i] >= a[que.back()] ) que.pop_back();
        que.push_back(i);
        if(i>=m) {
            MAX[i] = a[que.front()];
        }
    }

    for(int i = 1; i <= n; i++) {
        while(!quee.empty() && i - quee.front() + 1 > m) quee.pop_front();
        while(!quee.empty() && a[i] <= a[quee.back()] ) quee.pop_back();
        quee.push_back(i);
        if(i>=m) {
            MIN[i] = a[quee.front()];
        }
    }
    for(int i = 1; i <= n; i++) {
        a[i] += a[i-1];
    }
    int ans = -1;
    LL ave = 0;
    for(int i = m; i <= n; i++) {
        LL now = (a[i] - a[i-m] - MAX[i] - MIN[i]) ;
        if(now > ave) {
            ans = i - m + 1;
            ave = now;
        }
    }
    cout << ans;
    return 0;
}
/*
5 3
3 2 3 1 1

1

10 3
14 24 14 22 44 29 33 45 36 48 

8

*/
#美团笔试##美团##笔经#
全部评论
这就是大佬吗  
1 回复
分享
发布于 2021-09-04 18:02
1 回复
分享
发布于 2021-09-04 18:11
饿了么
校招火热招聘中
官网直投
好家伙,第二题我写bfs写晕了
点赞 回复
分享
发布于 2021-09-04 18:07
第一题斐波那契就过了
点赞 回复
分享
发布于 2021-09-04 18:20
大佬真强
点赞 回复
分享
发布于 2021-09-04 18:20
你这也太强了吧
点赞 回复
分享
发布于 2021-09-04 19:08
请问你是搞ACM的么
点赞 回复
分享
发布于 2021-09-04 19:09
妈耶美团笔试怎么这么难了
点赞 回复
分享
发布于 2021-09-04 21:14
第3题逆序对
点赞 回复
分享
发布于 2021-09-05 10:21
大佬你不是985-211竟然有这么强的实力,是自学的吗
点赞 回复
分享
发布于 2021-09-05 11:15
第三题这么简单吗?ac了吗?
点赞 回复
分享
发布于 2021-09-06 22:30
请问你是后台还是算法岗 笔试只有编程题吗
点赞 回复
分享
发布于 2021-09-24 22:34

相关推荐

11 32 评论
分享
牛客网
牛客企业服务