首页 > 美团 8月22日 ac答案 参考
头像
牛客0X0001号
编辑于 2021-08-22 12:55
+ 关注

美团 8月22日 ac答案 参考

//小美的AI学习

#include <bits/stdc++.h>

using namespace std;
using ll     = long long;
using pii    = pair<int, int>;
const ll mod = 1e9 + 7;

vector<int> color, weight;
vector<vector<int>> v;

void dfs(int i, int fa)
{
    if (v[i].size() == 1 && v[i][0] == fa)
        return;
    map<int, int> mp;
    int Max = 0, sum = weight[i];
    for (auto j : v[i])
    {
        if (j == fa)
            continue;
        dfs(j, i);
        Max = max(Max, mp[color[j]] += weight[j] + 1);
    }
    weight[i] = Max;
}

int main()
{
    int n, k;
    cin >> n >> k;
    color.resize(n);
    weight.resize(n);
    v.resize(n);

    for (int i = 0; i < n; ++i)
    {
        int c;
        cin >> c;
        color[i] = c;
    }

    for (int i = 1; i < n; ++i)
    {
        int p;
        cin >> p;
        v[i].push_back(p - 1);
        ***bsp;- 1].push_back(i);
    }

    for (int i = 0; i < n; ++i)
    {
        cin >> weight[i];
    }

    dfs(0, -1);

    for (int i = 0; i < n; ++i)
    {
        printf("%d%c", weight[i], (i == n - 1 ? '
' : ' '));
    }
}




//小美的数学题

#include <bits/stdc++.h>
using namespace std;

using ll     = long long;
const ll mod = 1e9 + 7;

int main()
{
    string s;
    cin >> s;
    int n = s.size();

    vector<ll> stk;
    for (int i = 0; i < n; ++i)
    {
        if (s[i] == '(')
            stk.push_back(-1);
        else
        {
            if (stk.back() == -1)
            {
                stk[stk.size() - 1] = 2;
                if (stk.size() >= 2 && stk[stk.size() - 2] > 0)
                {
                    stk[stk.size() - 2] = (stk[stk.size() - 2] * stk[stk.size() - 1]) % mod;
                    stk.pop_back();
                }
            }
            else
            {
                stk[stk.size() - 2] = (1 + stk[stk.size() - 1]) % mod;
                stk.pop_back();
                if (stk.size() >= 2 && stk[stk.size() - 2] > 0)
                {
                    stk[stk.size() - 2] = (stk[stk.size() - 2] * stk[stk.size() - 1]) % mod;
                    stk.pop_back();
                }
            }
        }
    }
    cout << stk.back() << "
";
}



//小美当会计

//讲道理,op==3时间复杂度应该很高,我的代码应该过不了,原本我想着我先写了一个简单的,想等一会儿再写了时间复杂度低的,谁知道直接过了,就很无语。

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main()
{
    int n, T;
    cin >> n;
    vector<ll> v(n), Max(n), Sum(n + 1), Square(n + 1);
    for (int i = 0; i < n; ++i)
        scanf("%lld", &v[i]);
    for (int i = 1; i <= n; ++i)
    {
        //    Max[i] = max
        Sum[i] += Sum[i - 1] + v[i - 1];
        Square[i] += Square[i - 1] + v[i - 1] * v[i - 1];
    }

    cin >> T;
    while (T--)
    {
        int op, L, R;
        scanf("%d%d%d", &op, &L, &R);
        --L;

        if (op == 1)
        {
            cout << Sum[R] - Sum[L] << "
";
        }
        else if (op == 2)
        {
            ll A = Sum[R] - Sum[L];
            ll B = Square[R] - Square[L];
            cout << (R - L) * A * A + B - 2 * A * A << "
";
        }
        else
        {
            cout << *max_element(v.begin() + L, v.begin() + R) << "
";
        }
    }
}


//小美写作文

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string s;
    int n;
    cin >> s >> n;
    vector<set<int>> mp(26);
    for (int i = 0; i < s.size(); ++i)
    {
        mp[s[i] - 'a'].insert(i);
    }

    while (n--)
    {
        int op;
        scanf("%d ", &op);
        if (op == 1)
        {
            char c;
            cin >> c;
            mp[c - 'a'].insert(s.size());
            s += string(1, c);
        }
        else
        {
            int c;
            cin >> c;
            int pos = c - 1;
            auto &t = mp[s[c - 1] - 'a'];
            auto it = t.lower_bound(pos);
            int res = INT_MAX;
            if (next(it) != t.end())
                res = min(res, *next(it) - pos);
            if (it != t.begin())
                res = min(res, pos - *prev(it));
            cout << (res == INT_MAX ? -1 : res) << "
";
        }
    }
}


//小美的数字卡片

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) cin >> v[i];
    sort(v.begin(), v.end());
    vector<vector<int>> res;
    do {
        res.push_back(v);
    } while (next_permutation(v.begin(), v.end()));
    cout << res.size() << "
";
    for (auto &v : res) {
        for (int i = 0; i< n; ++i) {
            printf("%d%c", v[i], (i == n-1 ? '
' : ' '));
        }
    }
}

全部评论

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

相关热帖

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

热门推荐