> 科技资讯 > 2023牛客寒假算法基础集训营4 A-H+JLM

2023牛客寒假算法基础集训营4 A-H+JLM

科技资讯 投稿 6500℃ 0 评论

2023牛客寒假算法基础集训营4 A-H+JLM

比赛链接

A

题解

知识点：数学。

\(3\ 最好，\(2,4\ 并列，\(4\ 以后递减。于是，特判 \(3\，其他取最小值。

\(e\ 进制最好qwq。

\(O(1\

\(O(1\

代码

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

int main( {
    std::ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
    int x, y;
    cin >> x >> y;
    cout << (x == 3 || y == 3 ? 3 : min(x, y << '\n';
    return 0;
}

B

题解

知识点：数论，构造。

\[\begin{aligned} c_i + c_{n-1-i} \equiv 2a_i \pmod m\\ c_i - c_{n-1-i} \equiv 2b_i \pmod m\\ \end{aligned} \]

\(m\ 是个素数，显然当 \(m>2\ 时一定有解。因为 \(2\ 的逆元一定存在，故无论 \(c_i,c_{n-1-i}\ 计算结果为多少，\(a_i,b_i\ 一定可求。我们可以通过 \(c_i,c_{n-1-i}\ 计算结果，是偶数直接除以 \(2\，否则加减一次 \(m\，就可以得到 \(a_i,b_i\ 。

\(m = 2\ 时，就不一定有解，因为同余式右侧恒为 \(0\，要先满足相加减以后的余数为 \(0\ 否则无解。如果有解，那我们可以令 \(a_i = c_i,b_i = 0\ 。

\(O(n\

\(O(n\

代码

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

int c[100007];
int main( {
    std::ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
    int n, m;
    cin >> n >> m;
    for (int i = 0;i < n;i++ cin >> c[i];
    bool ok = 1;
    if (m == 2 for (int i = 0;i < n;i++ ok &= !((c[i] + c[n - 1 - i] & 1;
    if (!ok cout << "NO" << '\n';
    else {
        for (int i = 0;i < n;i++ {
            int t = c[i] + c[n - i - 1];
            cout << (t % 2 ? (t - m / 2 : t / 2 << " \n"[i == n - 1];
        }
        for (int i = 0;i < n;i++ {
            int t = c[i] - c[n - i - 1];
            cout << (t % 2 ? (t + m / 2 : t / 2 << " \n"[i == n - 1];
        }
    }
    cout << "YES" << '\n';
    return 0;
}

CD

题解

知识点：背包dp，枚举。

\(1\ 开始到 \(n\ 直接一个状态跑完，但这道题需要知道一定选和一定不选第 \(i\ 件物品带来的价值之差，从而得到使第 \(i\ 件物品一定选的价值严格大于一定不选的价值。

\(i\ 以外的其他物品的选择情况，考虑设 \(f_{i,j},g_{i,j}\ 分别为考虑 \([1,i]\ / \([i,n]\ 的物品且总体积不超过 \(j\ 的最大价值。转移方程和普通背包dp一样就不写了。

\(i\ 个物品，我们求 \(a = \max_\limits{j \in [0,m]}(f_{i - 1,j} + g_{i + 1,m - j}\ 表示除去第 \(i\ 个物品的最大贡献，以及 \(b = \max_\limits{j \in [0,m-v_i]}(f_{i - 1,j} + g_{i + 1,m-v_i - j}+w_i\ 表示一定选第 \(i\ 个物品的最大贡献。随后，\(\max(0,a-b+1\ 即让一定选的价值超过不选的价值，那么 \(i\ 就变成必选物品了。

时间复杂度 \(O(nm\

\(O(nm\

代码

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

ll f[5007][5007], g[5007][5007];
ll v[5007], w[5007];
int main( {
    std::ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
    int n, m;
    cin >> n >> m;
    for (int i = 1;i <= n;i++ cin >> v[i] >> w[i];
    for (int i = 1;i <= n;i++ {
        for (int j = 0;j <= m;j++ {
            if (j < v[i] f[i][j] = f[i - 1][j];
            else f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i];
        }
    }
    for (int i = n;i >= 1;i-- {
        for (int j = 0;j <= m;j++ {
            if (j < v[i] g[i][j] = g[i + 1][j];
            else g[i][j] = max(g[i + 1][j], g[i + 1][j - v[i]] + w[i];
        }
    }
    for (int i = 1;i <= n;i++ {
        ll a = 0, b = 0;
        for (int j = 0;j <= m;j++ a = max(a, f[i - 1][j] + g[i + 1][m - j];
        for (int j = 0;j <= m - v[i];j++ b = max(b, f[i - 1][j] + g[i + 1][m - v[i] - j] + w[i];

        cout << max(0LL, a - b + 1 << '\n';
    }
    return 0;
}

E

题解

知识点：模拟。

\(cnt\，分类讨论：

    \(a \geq h_i\，则一次能死的次数加一。
  1. 否则，若 \(a \leq tv_i\ 则无法击杀。否则，次数为 \(1+\left\lceil \dfrac{h-a}{a-tv_i} \right\rceil\，表示先攻击一次，后面每次攻击前都会恢复 \(tv_i\，所以下一次攻击有效伤害为 \(a- tv_i\ 。

\(1+t \cdot (cnt-1\ 。

\(O(n\

\(O(n\

代码

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

int main( {
    std::ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
    int n;
    ll t, a;
    cin >> n >> t >> a;
    vector<pair<ll, ll>> mon;
    for (int i = 1;i <= n;i++ {
        ll h, v;
        cin >> h >> v;
        mon.push_back({ h,v };
    }
    ll cnt = 0;
    for (auto [h, v] : mon {
        if (h <= a cnt++;
        else {
            if (a <= t * v {
                cout << -1 << '\n';
                return 0;
            }
            cnt += (h - a + a - t * v - 1 / (a - t * v + 1;
        }
    }
    cout << 1 + (cnt - 1 * t << '\n';
    return 0;
}

F

题解

知识点：树，DFS，位运算。

    对于 \(fa\，其左右孩子满足 \(fa \mp lowbit(fa/2\，因此如果 lowbit 处有连续两个 \(1\ 则是右孩子，否则为左孩子。
  1. 对于 \(x\ 为根的子树（除了 \(2^k\ ），节点数等于 \(2^{\text{x的高度}}-1 = 2 \cdot lowbit(x-1\ 。

对于答案计数，可以考虑 \(x\ 爬到 \(2^k\，中间分类讨论走两侧的不同情况。

    先算上自己，答案加 \(1\ 。
  1. \(x\ 是 \(fa\ 的左孩子，那么答案加 \(1\ 。
  2. \(x\ 是 \(fa\ 的右孩子，那么答案加上左子树节点数再加一。

中序遍历：即 \(x\ 。

    先加上 \(x\ 为根的子树，答案加节点数。
  1. \(x\ 是 \(fa\ 的左孩子，答案不变。
  2. \(x\ 是 \(fa\ 的右孩子，那么答案加上左子树节点数。

时间复杂度 \(O(qk\

\(O(1\

代码

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

int k, q;
ll f(ll x { return x & -x; }
ll fo(ll x {
    ll ans = 1;
    while (x != (1LL << k {
        ll fa;
        if ((x >> 1 & f(x {
            fa = x - f(x;
            ans += 2 * f(fa - f(x;
        }
        else {
            fa = x + f(x;
            ans++;
        }
        x = fa;
    }
    return ans;
}

ll lo(ll x {
    ll ans = x == (1LL << k ? x : 2 * f(x - 1;
    while (x != (1LL << k {
        ll fa;
        if ((x >> 1 & f(x {
            fa = x - f(x;
            ans += 2 * f(fa - f(x - 1;
        }
        else fa = x + f(x;
        x = fa;
    }
    return ans;
}

int main( {
    std::ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;

    cin >> k >> q;
    while (q-- {
        ll x;
        cin >> x;
        cout << fo(x << ' ' << x << ' ' << lo(x << '\n';
    }
    return 0;
}

GH

题解

知识点：bfs，倍增，二分。

\(s(x_s,y_s\ 到所有点的最短路 \(dis_{x,y}\，因为花费都是 \(1\ 可以直接bfs。

\(t(x_t,y_t\ 出发开始走的路径，如果途中 \(dis_{x,y}\ 小于等于qcjj走到 \((x,y\ 的距离，那这个点就是答案，这是EZ版本的解。

\(k\ 步qcjj的坐标 \((x,y\，如果 \(k \geq ans\，那一定有 \(dis_{x,y} \leq ans\，否则一定有 \(dis_{x,y} > ans\，因此答案是符合单调性的。

\(k\ 步的确切坐标就成了问题。我们考虑使用倍增的思想，求出 \(pos_{k,i,j}\ 表示 \((i,j\ 为起点第 \(2^k\ 步的坐标，这样就能在线性复杂度预处理，对数复杂度求出确切坐标。

时间复杂度 \(O((nm + q\log (nm\

\(O(nm \log (nm\

代码

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

struct node {
    int x, y;
};
int n, m;
char dt[807][807];

const int dir[4][2] = { {0,-1},{0,1},{-1,0},{1,0} };
int dis[807][807];
queue<node> q;
void bfs(node s {
    for (int i = 0;i < n;i++
        for (int j = 0;j < m;j++
            dis[i][j] = -1;
    dis[s.x][s.y] = 0;
    q.push(s;
    while (!q.empty( {
        auto [x, y] = q.front(;
        q.pop(;
        for (int i = 0;i < 4;i++ {
            int xx = x + dir[i][0];
            int yy = y + dir[i][1];
            if (~dis[xx][yy] || dt[xx][yy] == '#' continue;
            dis[xx][yy] = dis[x][y] + 1;
            q.push({ xx,yy };
        }
    }
}

map<char, int> mp = { {'L',0},{'R',1},{'U',2},{'D',3} };
node pos[20][807][807];
void pos_init( {
    for (int i = 0;i < n;i++ {
        for (int j = 0;j < m;j++ {
            if (dt[i][j] == '#' pos[0][i][j] = { -1,-1 };
            if (dt[i][j] == '.' pos[0][i][j] = { i,j };
            else {
                int xx = i + dir[mp[dt[i][j]]][0];
                int yy = j + dir[mp[dt[i][j]]][1];
                if (xx < 0 || xx >= n || yy < 0 || yy >= m || dt[xx][yy] == '#' pos[0][i][j] = { i,j };
                else pos[0][i][j] = { xx,yy };
            }
        }
    }
    for (int k = 1;k < 20;k++ {
        for (int i = 0;i < n;i++ {
            for (int j = 0;j < m;j++ {
                auto [x, y] = pos[k - 1][i][j];
                pos[k][i][j] = pos[k - 1][x][y];
            }
        }
    }
}

int main( {
    std::ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;

    cin >> n >> m;
    int sx, sy;
    cin >> sx >> sy;
    node s = { sx,sy };
    int q;
    cin >> q;
    for (int i = 0;i < n;i++
        for (int j = 0;j < m;j++
            cin >> dt[i][j];

    bfs(s;
    pos_init(;
    while (q-- {
        int xt, yt;
        cin >> xt >> yt;
        node t = { xt,yt };
        int ans = 0;
        for (int i = 19;i >= 0;i-- {
            auto [x, y] = pos[i][t.x][t.y];
            if (!~dis[x][y] || dis[x][y] > ans + (1 << i {
                t = { x,y };
                ans += 1 << i;
            }//不能等于，ans的意义是不可行的最大值；加了等于意义就乱了
        }
        cout << (++ans == 1 << 20 ? -1 : ans << '\n';
    }
    return 0;
}

J

题解

方法一

知识点：拓扑排序，枚举。

我们知道拓扑排序能在不破坏DAG节点顺序下，求出节点的相对顺序。因此我们可以使用拓扑排序，同时记录节点位置 \(pos\ 。通过 \(pos\，我们可以得到一个节点的位置上下确界 \([maxl,minr]\，显然如果节点 \(i\ 是确定的那么这个区间只会包括 \(i\，如果不是，那么被这个区间包括的所有点都是不能确定的。因此，我们可以对所有点枚举边界即可排除不确定的点。

\(O(n+m\

\(O(n+m\

方法二

知识点：dfs，STL，枚举。

最后，对每个点记录小于等于自己和大于等于自己的个数和，如果等于 \(n+1\ 那说明这个点和其他 \(n-1\ 个点的关系完全确定，就能知道位置了。

\(O\left(\dfrac{nm}{w} \right\

\(O(n+m\

代码

方法一

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

int n, m;
vector<int> g[1007];

int deg[1007];
queue<int> q;
int ans[1007];
int pos[1007], cnt;
void toposort( {
    for (int i = 1;i <= n;i++ if (!deg[i] q.push(i;
    while (!q.empty( {
        int u = q.front(;
        q.pop(;
        cnt++;
        ans[cnt] = u;
        pos[u] = cnt;
        for (auto v : g[u] {
            deg[v]--;
            if (!deg[v] q.push(v;
        }
    }
}

int maxl[1007], minr[1007];
int b[1007];

int main( {
    std::ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
    cin >> n >> m;
    for (int i = 1;i <= m;i++ {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v;
        deg[v]++;
    }
    toposort(;
    for (int i = 1;i <= n;i++ minr[i] = n + 1;
    for (int i = 1;i <= n;i++ {
        for (auto v : g[i] {
            minr[i] = min(minr[i], pos[v];
            maxl[v] = max(maxl[v], pos[i];
        }
    }

    for (int i = 1;i <= n;i++ b[i] = ans[i];
    int r = 1;
    for (int i = 1;i <= n;i++ {
        if (r > i b[i] = -1;
        r = max(r, minr[ans[i]];
    }
    int l = n;
    for (int i = n;i >= 1;i-- {
        if (l < i b[i] = -1;
        l = min(l, maxl[ans[i]];
    }

    for (int i = 1;i <= n;i++cout << b[i] << " \n"[i == n];
    return 0;
}

方法二

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

int n, m;
vector<int> g[1007];

bool vis[1007];
bitset<1007> bs[1007];
void dfs(int u {
    if (vis[u] return;
    vis[u] = 1;
    for (auto v : g[u] {
        dfs(v;
        bs[u] |= bs[v];
    }
}

int b[1007];

int main( {
    std::ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
    cin >> n >> m;
    for (int i = 1;i <= n;i++ bs[i][i] = 1, b[i] = -1;
    for (int i = 1;i <= m;i++ {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v;
    }
    for (int i = 1;i <= n;i++ if (!vis[i] dfs(i;
    for (int i = 1;i <= n;i++ {
        int cnt = 0;
        for (int j = 1;j <= n;j++ cnt += bs[j][i];
        if (bs[i].count( + cnt == n + 1 b[cnt] = i;
    }
    for (int i = 1;i <= n;i++cout << b[i] << " \n"[i == n];
    return 0;
}

L

题解

知识点：数学。

\(l_b\，再求出 \(l_a,l_c\，随后复制一份排序判断，因为输出要按原来顺序。

\(O(1\

\(O(1\

代码

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

bool solve( {
    int A, B, C;
    cin >> A >> B >> C;
    if ((A - B + C & 1 return false;
    vector<int> v(4;
    v[2] = (A - B + C / 2;
    v[3] = A - v[2];
    v[1] = C - v[2];
    auto g = v;
    sort(g.begin( + 1, g.end(;
    if (g[1] <= 0 || g[1] + g[2] <= g[3] return false;
    cout << "YES" << '\n';
    cout << v[1] << ' ' << v[2] << ' ' << v[3] << '\n';
    return true;
}

int main( {
    std::ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
    int t = 1;
    cin >> t;
    while (t-- {
        if (!solve( cout << "NO" << '\n';
    }
    return 0;
}

M

题解

知识点：构造。

\(1,2,3\ 是构造不出三角形的，循环打就行。

\(O(n\

\(O(1\

代码

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

int main( {
    std::ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
    int n;
    cin >> n;
    for (int i = 0;i < n;i++ cout << "123"[i % 3] << ' ';
    cout << '\n';
    return 0;
}

编程笔记 » 2023牛客寒假算法基础集训营4 A-H+JLM

赞同 (37) or 分享 (0)
游客 发表我的评论   换个身份
取消评论

表情
(0)个小伙伴在吐槽