题解：P17761 「奶龙OI」Round 3 - 红石大佬

_initializer_list_ · 2026-10-24 12:31:37 · 题解

题目传送门

思路

先来分析上界 g：

• 上界一：因为每个种子最多有 3 个邻居，记上界 g_1=3k。
• 上界二：又因为有种子的地方不能长西瓜，所以上界 g_2 = \text{空格总数} = 2n-k。

结合起来，上界 g = \min(3k,2n-k)。

分 3 种情况讨论：

• 当 2k < n：
  • 相当于 3k < 2n - k，可以隔列放种子，互不重叠，每个可以激活 3 个，答案为 3k。
• 当 2k > n:
  • 相当于 3k > 2n - k，可以覆盖所有空格，答案为 2n-k。
• 当 2k = n：
  • 相当于 3k = 2n - k，此时 g = 3k 不可达，至少损失 1，答案为 3k - 1。

整理得：

代码

::::success[AC Code]

// Problem: T810639 「奶龙OI」Round 3 - 红石大佬
// Contest: Luogu - 【LGR-312-Div.3】洛谷基础赛 #41 & 奶龙 OI Round 3
// URL: https://www.luogu.com.cn/problem/T810639?contestId=345405
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// Code by wangxy0311

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

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
template <class T>
T randint(T l, T r) {
    uniform_int_distribution<T> dist(l, r);
    return dist(rnd);
}

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef __int128 i128;
typedef unsigned __int128 u128;
typedef long double ld;

#define rep(x, y, z) for (int x = (y); x <= (z); ++x)
#define per(x, y, z) for (int x = (y); x >= (z); --x)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fileIO(s)               \
  freopen(s ".in", "r", stdin); \
  freopen(s ".out", "w", stdout);
#define endl '\n'
#define all(x) begin(x), end(x)

inline void fast_io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

template <typename T>
void chkmax(T &a, T b) { if (b > a) a = b; }
template <typename T>
void chkmin(T &a, T b) { if (b < a) a = b; }

template <int MOD>
struct Modint {
    ll val;
    Modint(ll v = 0) { val = (v % MOD + MOD) % MOD; }
    Modint operator+(const Modint & x) const { return Modint(val + x.val); }
    Modint operator-(const Modint & x) const { return Modint(val - x.val); }
    Modint operator*(const Modint & x) const { return Modint((i128)val * x.val % MOD); }
    Modint operator^(ll b) const { Modint res = 1, a = *this; for (; b; b >>= 1, a *= a) if (b & 1) res *= a; return res; }
    Modint operator^(const Modint & b) const { return *this ^ b.val; }
    Modint operator~() const { return *this ^ MOD - 2; }
    Modint operator/(const Modint & x) const { return *this * ~x; }
    Modint operator-() const { return Modint(-val); }
    Modint & operator+=(const Modint & x) { val = (val + x.val) % MOD; return *this; }
    Modint & operator-=(const Modint & x) { val = (val - x.val + MOD) % MOD; return *this; }
    Modint & operator*=(const Modint & x) { val = (i128)val * x.val % MOD; return *this; }
    Modint & operator^=(ll b) { return *this = *this ^ b; }
    Modint & operator^=(const Modint & b) { return *this = *this ^ b.val; }
    Modint & operator/=(const Modint & x) { return *this = *this / x; }
    Modint & operator++() { return *this += Modint(1); }
    Modint operator++(int) { Modint tmp = *this; ++*this; return tmp; }
    Modint & operator--() { return *this -= Modint(1); }
    Modint operator--(int) { Modint tmp = *this; --*this; return tmp; }
    bool operator==(const Modint & x) const { return val == x.val; }
    bool operator!=(const Modint & x) const { return val != x.val; }
    bool operator<(const Modint & x) const { return val < x.val; }
    bool operator>(const Modint & x) const { return val > x.val; }
    bool operator<=(const Modint & x) const { return val <= x.val; }
    bool operator>=(const Modint & x) const { return val >= x.val; }
    friend Modint operator+(ll v, const Modint & x) { return Modint(v) + x; }
    friend Modint operator-(ll v, const Modint & x) { return Modint(v) - x; }
    friend Modint operator*(ll v, const Modint & x) { return Modint(v) * x; }
    friend Modint operator/(ll v, const Modint & x) { return Modint(v) / x; }
    friend Modint operator^(ll v, const Modint & x) { return Modint(v) ^ x; }
    friend ostream & operator<<(ostream & os, const Modint & x) { return os << x.val; }
    friend istream & operator>>(istream & is, Modint & x) { ll v; is >> v; x = Modint(v); return is; }
};

const int inf = 1e9;
const ll infll = 1e18;
const double eps = 1e-8;
const ld epsll = 1e-12;

int main() {
    fast_io();
    int t;
    cin >> t;
    while (t--) {
        ll n, k;
        cin >> n >> k;
        if (2 * k < n) cout << k * 3 << endl;
        else if (2 * k > n) cout << n * 2 - k << endl;
        else cout << k * 3 - 1 << endl;
    }
    return 0;
}

:::: 时间复杂度为 \mathcal{O}(T)。