2026牛客寒假算法基础集训营6
|
miyan
|
23,939
|
牛客

1758 字
|
30 分钟

链接：https://ac.nowcoder.com/acm/contest/120565

题目按照通过人数降序排序。

K – 小L的游戏1

算法：

数学。

思路：

无。

关键代码：

void miyan()
{
    ll m, n, z;
    cin >> m >> n >> z;

    z %= (n + m);
    if (z == 0)
        z += (n + m);

    if (z <= m)
        cout << 0;
    else
        cout << 1;
}

G – 小L的散步

算法：

双指针，前缀和。

思路：

定义：

  • \(L, R\) 为当前脚占据的区间，初始 \(L = 0, R = l\)；
  • \(s[i]\) 表示第 \(i\) 块石头的终点，\(s[i] = \sum_{j = 1}^{i} x[j]\)；
  • 方便起见（避免过多边界判断），增加 \(s[n + 1] = \infty\)。

判断脚是否踩在缝隙上，就是判断脚是否在两块石头之间。

对于当前 \(L, R\)，想要判断是否在两块石头之间，等价于判断是否存在 \(i\) 使得 \(L < s[i]\) 且 \(R > s[i]\)。

由于每一步所在的位置都是严格递增的，考虑双指针维护当前脚后跟在哪块石头上。

关键代码：

void miyan()
{
    ll n, m, l;
    cin >> n >> m >> l;
    vector<int> a(n + 1), b(m + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= m; ++i)
        cin >> b[i];

    vector<ll> s(n + 2, 0);
    for (int i = 1; i <= n; ++i)
        s[i] = s[i - 1] + a[i];
    s[n + 1] = LLONG_MAX;

    ll L = 0, R = l;
    if (L < s[1] && R > s[1])
    {
        cout << "YES" << endl;
        return;
    }

    for (int i = 1, j = 1; i <= m; ++i)
    {
        L += b[i], R += b[i];

        while (j <= n && L >= s[j])
            ++j;

        if (L < s[j] && R > s[j])
        {
            cout << "YES" << endl;
            return;
        }
    }

    cout << "NO" << endl;
}

H – 小L的数组

算法：

可达性 \(dp\)。

思路：

观察到 \(n, a_i, b_i\) 的值域都小于 \(2048\)，考虑 \(dp\)。

定义 \(dp[i][j]\) 为前 \(i\) 次操作是否可以将 \(x\) 的值变为 \(j\)。

容易想到：当 \(dp[i – 1][j]\) 为 \(true\) 时，可以转移至 \(dp[i][max(0, j – a_i)]\) 与 \(dp[i][j \oplus a_i]\)。

由于 \(i\) 只依赖与 \(i – 1\)，因此可以开滚动数组。

关键代码：

二维数组。

void miyan()
{
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i)
        cin >> b[i];

    vector dp(n + 1, vector<int>(2049, 0));
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j < 2049; ++j)
        {
            if (dp[i - 1][j] == 0)
                continue;

            dp[i][max(0, j - a[i])] = dp[i][j ^ b[i]] = 1;
        }
    }

    for (int i = 2048; i >= 0; --i)
    {
        if (dp[n][i])
        {
            cout << i << endl;
            return;
        }
    }
}

滚动数组。

void miyan()
{
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (auto &x : a)
        cin >> x;
    for (auto &x : b)
        cin >> x;

    vector<int> dp(2048, 0);
    dp[0] = 1;
    for (int i = 0; i < n; ++i)
    {
        vector<int> ndp(2048);
        for (int j = 0; j < 2048; ++j)
        {
            if (!dp[j])
                continue;

            ndp[max(0, j - a[i])] = ndp[j ^ b[i]] = 1;
        }

        dp.swap(ndp);
    }

    for (int i = 2047; i >= 0; --i)
    {
        if (dp[i])
        {
            cout << i << endl;
            return;
        }
    }
}

A – 小L的三角尺

算法：

贪心，堆。

思路：

发现 \(w\) 的值域为 \([1, 10^6]\)，考虑 \(O(nlogn)\) 的解法。

由于每次减少某个三角形的 \(y\) 值时，无法快速判断其是否由于其他三角形，遂考虑对每个三角形每次只减少 \(1\) 点 \(y\) 值，从而进行大根堆贪心。

每次都从大根堆中取出可以减少最多斜边值的三角形，减少 \(1\) 点 \(y\) 值。

那么大根堆的排序关键字就为 \(\sqrt{(x^2 – y^2)} – \sqrt{(x^2 – (y – 1)^2)}\)。

关键代码：

using pll = pair<ll, ll>;
using ld = long double;

void miyan()
{
    int n, w;
    cin >> n >> w;

    priority_queue<tuple<ld, ll, ll>> q;
    for (int i = 0; i < n; ++i)
    {
        ll x, y;
        cin >> x >> y;

        ld s = sqrtl(x * x + y * y);
        ld e = sqrtl(x * x + (y - 1) * (y - 1));
        q.push({s - e, x, y - 1});
    }

    vector<pll> ans;
    while (q.size() && w--)
    {
        auto [d, x, y] = q.top();
        q.pop();

        if (y == 0)
        {
            ans.push_back({x, y});
            continue;
        }

        ld s = sqrtl(x * x + y * y);
        ld e = sqrtl(x * x + (y - 1) * (y - 1));
        q.push({s - e, x, y - 1});
    }

    while (q.size())
    {
        auto [d, x, y] = q.top();
        q.pop();

        ans.push_back({x, y + 1});
    }

    ld res = 0;
    for (auto [x, y] : ans)
        res += sqrtl(x * x + y * y);

    cout << fixed << setprecision(15) << res << endl;
}

B – 小L的彩球

算法：

组合数学。

思路：

形式化描述：对于一个 \(01\) 串，要求有 \(x\) 个 \(0\) 且相邻位置存在 \(t\) 处不同，问有多少种可能。

题目要求 \(01\) 串存在 \(t\) 处不同等价于将 \(01\) 串分为 \(t + 1\) 段，定义 \(tot = t + 1, y = n – x\)。

分类讨论：

  • 当 \(tot\) 为偶数时，只会有 \(tot / 2\) 段 \(0\) 和 \(tot / 2\) 段 \(1\)，可能为 \(0101…..\) 或者 \(1010….\)，两种情况的方案数相同；
    • 该情况实际是求将 \(0\) 分为 \(tot / 2\) 段的方案数 \(\times\) 将 \(1\) 分为 \(tot / 2\) 段的方案数，采用隔板法，得方案数 \(C_{x – 1}^{tot – 1} * C_{y – 1}^{tot – 1}\)，注意需要判断 \(x\) 与 \(y\) 的值是否大于等于 \(tot\)。
  • 当 \(tot\) 为奇数时，会有 \(tot / 2 + 1\) 段 \(0\) 和 \(tot / 2\) 段 \(1\)，或者 \(tot / 2 + 1\) 段 \(1\) 和 \(tot / 2\) 段 \(0\)，计算方法同理。

特判：\(t = 0\) 时，需要 \(x = n\) 或者 \(y = n\)，满足答案为 \(1\)，否则为 \(0\)。

关键代码：

void miyan()
{
    ll n, x, t;
    cin >> n >> x >> t;

    ll y = n - x;
    if (t == 0)
    {
        if (x == n || y == n)
            cout << 1 << endl;
        else
            cout << 0 << endl;

        return;
    }

    ll ans = 0;
    ll h = (t + 1) / 2;
    if ((t + 1) & 1)
    {
        if (x >= h && y >= h + 1)
        {
            ll cur = C(x - 1, h - 1) * C(y - 1, h) % MOD;

            ans = (ans + cur) % MOD;
        }

        if (x >= h + 1 && y >= h)
        {
            ll cur = C(x - 1, h) * C(y - 1, h - 1) % MOD;

            ans = (ans + cur) % MOD;
        }
    }
    else
    {
        if (x >= h && y >= h)
        {
            ll cur = C(x - 1, h - 1) * C(y - 1, h - 1) % MOD * 2 % MOD;

            ans = (ans + cur) % MOD;
        }
    }

    cout << ans << endl;
}

D – 小L的扩展

算法：

\(bfs\)，贪心，堆。

思路：

容易想到，对于一个蓝色格子 \(u\) 其被染黑的时间为 \(max(dist[u], time[u])\)，其中 \(dist[u]\) 为其余黑色格子染至 \(u\) 的时间，\(time[u]\) 为 \(u\) 点变白时间。

直接堆跑 \(bfs\) 即可。

贪心证明略。

关键代码：

const int inf = 2e9;
using A = array<int, 3>;

void miyan()
{
    int n, m, a, b;
    cin >> n >> m >> a >> b;

    priority_queue<A, vector<A>, greater<>> q;
    vector dist(n + 1, vector<ll>(m + 1, inf));
    vector g(n + 1, vector<int>(m + 1, 0));
    for (int i = 0; i < a; ++i)
    {
        int x, y;
        cin >> x >> y;
        dist[x][y] = 0;
        q.push({0, x, y});
    }

    for (int i = 0; i < b; ++i)
    {
        int x, y, t;
        cin >> x >> y >> t;
        g[x][y] = t;
    }

    auto check = [&](int x, int y) -> bool
    {
        return x >= 1 && x <= n && y >= 1 && y <= m;
    };

    while (q.size())
    {
        auto [d, x, y] = q.top();
        q.pop();

        for (int i = 0; i < 4; ++i)
        {
            int nx = x + dx[i], ny = y + dy[i];

            if (check(nx, ny) == 0)
                continue;

            int time = max(d + 1, g[nx][ny]);

            if (time < dist[nx][ny])
            {
                dist[nx][ny] = time;
                q.push({time, nx, ny});
            }
        }
    }

    ll ans = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            ans = max(ans, dist[i][j]);

    cout << ans << endl;
}

E – 小L的空投

算法：

并查集。

思路：

如果正序处理（水位从低到高），需要考虑删点与删边，其在代码上不容易实现且复杂度不是很优。

考虑逆序处理（水位从高到低），只需考虑加点与加边，此时只需维护连通块与连通块大小，每次只需将露出水面的点加入到连通块中即可。

具体实现看代码。

关键代码：

void miyan()
{
    int n, m, x, d;
    cin >> n >> m >> x >> d;

    vector<pii> h(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> h[i].first;
        h[i].second = i;
    }

    ranges::sort(h, greater<>());

    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);
        g[v].push_back(u);
    }

    vector<int> H(x);
    for (int i = 0; i < x; ++i)
        cin >> H[i];

    vector<int> p(n);
    vector<int> siz(n, 0);
    for (int i = 0; i < n; ++i)
        p[i] = i;

    auto find = [&](auto &self, int x) -> int
    {
        if (x != p[x])
            p[x] = self(self, p[x]);

        return p[x];
    };

    vector<int> st(n, 0);
    int idx = 0;
    vector<int> ans(x, 0);
    set<int> now;
    for (int i = x - 1; i >= 0; --i)
    {
        while (idx < n && h[idx].first > H[i])
        {
            int u = h[idx].second;

            siz[u] = 1;
            st[u] = 1;

            if (siz[u] >= d)
                now.insert(u);

            for (auto v : g[u])
            {
                if (st[v] == 0)
                    continue;

                int fu = u, fv = v;
                fu = find(find, fu), fv = find(find, fv);

                if (fu != fv)
                {
                    if (siz[fu] >= d && now.count(fu))
                        now.erase(fu);
                    if (siz[fv] >= d && now.count(fv))
                        now.erase(fv);

                    siz[fv] += siz[fu];
                    p[fu] = fv;

                    if (siz[fv] >= d)
                    {
                        now.insert(fv);

                        ++ans[i];
                    }
                }
            }

            ++idx;
        }

        ans[i] = now.size();
    }

    for (int i = 0; i < x; ++i)
        cout << ans[i] << endl;
}

C – 小L的线段树

算法：

线段树。

思路：

模板。

关键代码：

struct SegmentTree
{
    struct Node
    {
        int l, r;
        int flag;
        int cnt;
    };

    // 线段树大小
    int N;
    vector<Node> tr;

    SegmentTree(int _N)
    {
        N = _N;
        tr.resize(4 * N);
        build(1, 1, N);
    }

// 左右子区间
#define LC (u << 1)
#define RC ((u << 1) | 1)

    inline void pushup(int u)
    {
        tr[u].cnt = 0;
        if (tr[LC].flag)
            ++tr[u].cnt;
        else
            tr[u].cnt += tr[LC].cnt;

        if (tr[RC].flag)
            ++tr[u].cnt;
        else
            tr[u].cnt += tr[RC].cnt;
    }

    inline void build(int u, int l, int r)
    {
        tr[u] = {l, r, 1, 0};

        if (l == r)
            return;

        int mid = l + r >> 1;
        build(LC, l, mid);
        build(RC, mid + 1, r);
        pushup(u);
    }

    inline int query(int u, int l, int r)
    {
        int ans = tr[u].flag;

        if (l <= tr[u].l && r >= tr[u].r)
        {
            if (tr[u].flag)
                return ans;
            else
                return tr[u].cnt;
        }

        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid)
            ans += query(LC, l, r);
        if (r > mid)
            ans += query(RC, l, r);
        return ans;
    }

    inline void update(int u, int l, int r)
    {
        if (tr[u].l == l && tr[u].r == r)
        {
            tr[u].flag = 0;
            return;
        }

        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid)
            update(LC, l, r);
        if (r > mid)
            update(RC, l, r);
        pushup(u);
    }

    inline int query(int l, int r) { return query(1, l, r); }

    inline void update(int l, int r) { update(1, l, r); }
};

void miyan()
{
    int n;
    cin >> n;

    SegmentTree st(n);

    for (int i = 0; i < n; ++i)
    {
        int op, l, r;
        cin >> op >> l >> r;

        if (op == 1)
            st.update(l, r);
        else
            cout << st.query(l, r) << endl;
    }
}
26寒假训练营牛客
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
牛客周赛 Round 132

							
							

							
牛客周赛 Round 115

							
							

							
牛客周赛 Round 131

							
							

							
2026牛客寒假算法基础集训营5

							
							

							
牛客周赛 Round 130

							
							

							
2026牛客寒假算法基础集训营3

							
							

							
2026牛客寒假算法基础集训营2

							
							

							
2026牛客寒假算法基础集训营1

							
							

							
牛客小白月赛128

							
							

							
牛客周赛 Round 129