首页 > 网易雷火笔试4.1 第三题
头像
离朱一龙就差10cm
编辑于 2021-04-04 19:02
+ 关注

网易雷火笔试4.1 第三题

非常简单的dp 观察题目可以知道复杂度而且跑不满。
一小时做完3题之后,做了半小时第四题,不知道哪里错了就随机交了。

第三题表示在第个 少搞了个苹果。
然后显然排个序,然后简单dp
(代码风格 from jiangly)

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int v, x0, n, m;
    cin >> v >> x0 >> n >> m;

    vector<array<int, 3>> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    }
    a[0][0] = x0;
    a[0][1] = 0;
    a[0][2] = 0;
    sort(a.begin(), a.end(), [&](array<int, 3> u, array<int, 3> v) { return u[1] < v[1]; });
    int INF = 2e9;
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, -INF));
    dp[0][0] = 0;
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        auto [x, y, w] = a[i];
        //cout << x << " " << y << " " << w << endl;
        for (int j = max(0, i - m); j < i; j++)
        {
            if (abs(x - a[j][0]) <= v * (y - a[j][1]))
            {
                int out = i - j - 1;
                for (int k = 0; k < m - out; k++)
                {
                    dp[i][k + out] = max(dp[j][k] + w, dp[i][k + out]);
                    ans = max(dp[i][k + out], ans);
                }
            }
        }
    }
    cout << ans << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    //cin >> T;
    while (T--)
    {
        solve();
    }
}

第四题 请大佬帮我看看错在哪

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int n;
    cin >> n;
    vector<char> a(n);
    vector<int> st(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int m;
    cin >> m;
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
    }
    vector<int> vis(n);
    function<void(int)> dfs = [&](int x) {
        vis[x] = 1;

        for (int to : g[x])
        {
            if (vis[to])
                continue;
            if (a[to] == 'D')
            {
                st[to]++;
                dfs(to);
            }
            else if (a[to] == 'B')
            {

                if (st[to] == 0)
                    st[to] ^= 1, dfs(to);
                else
                    st[to] ^= 1;
            }
            else if (a[to] == 'C')
            {
                if (st[to] == 1)
                    dfs(to);
            }
            else
                dfs(to);
        }
    };
    int q = 0;
    cin >> q;
    for (int i = 0; i < n; i++)
        if (!vis[i] && a[i] == 'A')
            dfs(i);

    while (q--)
    {
        vis = vector<int>(n, 0);
        int u;
        cin >> u;
        u--;
        if (a[u] == 'C')
        {
            st[u] ^= 1;
            for (int i = 0; i < n; i++)
                if (!vis[i] && a[i] == 'A')
                    dfs(i);
        }
    }
    for (int i = 0; i < n; i++)
        if (a[i] == 'D')
            cout << min(99, st[i]) << " ";
    cout << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    //cin >> T;
    while (T--)
    {
        solve();
    }
}

全部评论

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

推荐话题

相关热帖

近期热帖

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

近期精华帖

热门推荐