题解 | Codeforces Round 1084 (Div. 3)
|
54
|
0
|
Codeforces,题解

1874 字
|
29 分钟

A Eating Game

显然胜者是盘子数最多的，且等效位置最靠后的，答案即为盘子数最多的人数。

void solve() {
    int n, mx = 0;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        mx = max(mx, a[i]);
    }
    int cnt = 0;
    for (auto v : a) cnt += mx == v;
    cout << cnt << endl;
}

B Deletion Sort

只要最开始不是非递减的，就一定能删到只剩一个。（保留破坏单调性的那个元素，然后最后删掉）

void solve() {
    int n; 
    cin >> n;
    vector<int> a(n);
    bool f = 1;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (i && a[i] < a[i - 1]) f = 0;
    }
    if (f)
        cout << n << endl;
    else
        cout << 1 << endl;
}

C Specialty String

本质括号匹配问题。

void solve() {
    int n;
    string s;
    cin >> n >> s;
    vector<int> stk;
    for (auto v : s) {
        if (stk.empty())
            stk.pb(v);
        else {
            if (v == stk.back())
                stk.pob();
            else
                stk.pb(v);
        }
    }
    if (stk.size())
        cout << "NO" << endl;
    else
        cout << "YES" << endl;
}

D Portal

两个传送门把数组分成左中右三段，操作有且仅有以下结果：

  • 左段和右端互相转移
  • 中段循环移位

所以我们要使中段字典序最小，然后放在左右段中达到字典序最小的位置。

void solve() {
    int n, x, y;
    cin >> n >> x >> y;
    vector<int> p(n);
    for (int i = 0; i < n; ++i) cin >> p[i];

    vector<int> L(p.begin(), p.begin() + x), M(p.begin() + x, p.begin() + y), R(p.begin() + y, p.end());

    vector<int> S = L;
    S.insert(S.end(), all(R));

    auto it = min_element(all(M));

    vector<int> Ms(it, M.end());
    Ms.insert(Ms.end(), M.begin(), it);

    int ofs = S.size();
    for (int i = 0; i < S.size(); ++i) {
        if (S[i] > *it) {
            ofs = i;
            break;
        }
    }

    S.insert(S.begin() + ofs, all(Ms));
    for (auto v : S) cout << v << " ";
    cout << endl;
}

E Divisive Battle

我们分情况讨论：

  • 数组中存在某个元素含有至少 $2$ 种不同的质因数：那么它肯定能表示为 $P_{min}\times P_{max}\times t$ ，我们只需要让 $P_{min}$ 和 $P_{max}$ 逆序即可，这个逆序对是永远无法修复的。
  • 数组中的每一个元素都只包含 $1$ 种质因数（或者是 $1$ ），即 $a_i = p_i^{k_i}$：最后的结果一定是 $p_1,p_1,…,p_1,p_2,…,p_2,…,p_n,…,p_n$ ，所以检查一下 $p_i$ 是不是非递减的即可。
constexpr int maxn = 1e6;

vector<int> primes, spf(maxn + 1);

void init() {
    for (int i = 2; i <= maxn; ++i) {
        if (!spf[i]) primes.push_back(i), spf[i] = i;
        for (int j = 0; primes[j] * i <= maxn; ++j) {
            int m = primes[j] * i;
            spf[m] = primes[j];
            if (i % primes[j] == 0) break;
        }
    }
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    bool ok = true;
    for (int i = 0; i < n - 1; i++) {
        if (a[i] > a[i + 1]) {
            ok = false;
            break;
        }
    }

    if (ok) {
        cout << "Bob" << endl;
        return;
    }

    ok = false;

    auto get = [&](int x) {
        if (x == 1) return 1;
        int p = spf[x];
        while (x % p == 0) {
            x /= p;
        }
        if (x > 1) return -1;
        return p;
    };

    for (int i = 0; i < n; i++) {
        a[i] = get(a[i]);
        if (a[i] == -1) {
            ok = true;
        }
    }

    if (ok) {
        cout << "Alice" << endl;
        return;
    }

    ok = true;
    for (int i = 0; i < n - 1; i++) {
        if (a[i] > a[i + 1]) {
            ok = false;
            break;
        }
    }

    if (ok)
        cout << "Bob" << endl;
    else
        cout << "Alice" << endl;
}

F Mooclear Reactor 2

用 $C(k)$ 表示满足 $y\geq k−1$ 的所有粒子，$E(k)$ 表示在 $C(k)$ 中选取能量 $x$ 最大的 $k$ 个粒子的总和，$V(k)$ 表示在 $C(k)$ 中选取能量 $x$ 最大的 $k−1$ 个粒子的总和。那么不购买任何商店粒子的初始最大总能量即为 $M_0=\max\limits_{1\leq k\leq n}E(k)$ 。

如果购买了一个粒子，如果把此粒子包括在内并形成一个总大小为 $k$ 的集合，那么必须有 $k−1\leq y$ ，为此，需要从粒子中挑出 $k−1$ 个与它相配且满足条件 $y\geq k−1$ 的粒子，也就是 $V(k)$ ，此时的最大能量为 $\max\limits_{1\leq k\leq y+1}(x+v(k)) = x+\max\limits_{1\leq k\leq y+1}V(k)$ 。

我们可以将大小限制 $k$ 从 $n+1$ 递减到 $1$ 。由于条件的限制是 $y\geq k−1$ ，当 $k$ 减小时，可以利用的粒子越来越多。我们可以用一个优先队列来动态维护最大的若干个元素，当 $k$ 减小时弹出最小的元素使其恰好维持为所需数量 $k$ 和 $k−1$ ，即可高效取得 $E(k)$ 与 $V(k)$ 。

constexpr ll INF = 2e18;

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

    vector<vector<ll>> groups(n + 1);
    for (int i = 0; i < n; ++i) {
        ll x, y;
        cin >> x >> y;
        groups[y].pb(x);
    }

    vector<ll> E(n + 2, -INF), V(n + 2, -INF);
    priority_queue<ll> pq;
    ll sum = 0;
    for (int i = n + 1; i >= 1; --i) {
        for (auto x : groups[i - 1]) pq.push(-x), sum += x;

        while (pq.size() > i) sum += pq.top(), pq.pop();
        if (pq.size() == i) E[i] = sum;

        while (pq.size() > i - 1) sum += pq.top(), pq.pop();
        if (pq.size() == i - 1) V[i] = sum;
    }

    ll m0 = -INF;
    for (int i = 1; i <= n + 1; ++i) m0 = max(m0, E[i]);

    vector<ll> P(n + 2, -INF);
    ll mx = -INF;
    for (int i = 1; i <= n + 1; ++i) mx = max(mx, V[i]), P[i] = mx;

    while (m--) {
        ll x, y;
        cin >> x >> y;
        ll ans = m0;
        int k = min(n + 1, (int)y + 1);
        if (P[k] != -INF) ans = max(ans, x + P[k]);
        cout << ans << " ";
    }
    cout << endl;
}

G Operation Permutation

记乘法操作为 $a_i$ ，加法操作为 $b_i$ 。

根据期望的线性性质，初始值 $x$ 必然会被所有的乘法操作做一遍。因此 $x$ 的那部分贡献总是 $x\cdot \prod a_i$ 。

对于任意一个特定的加法操作 $b_j$ ，它对最终答案的贡献取决于排在它后面的乘法操作的数量及它们的值。

因为所有操作的排列是等概率随机的，如果我们共有 $N$ 个乘法操作，那么一个特定的加法操作插入到这些乘法操作之间的位置（共 $N+1$ 个空档）是均匀分布的。它排在倒数第 $k$ 个空档（即有 $k$ 个乘法操作排在它后面）的概率为 $\frac{1}{N+1}$ 。且当它后面有 $k$ 个乘法时，这 $k$ 个乘法是原 $N$ 个乘法的任意子集，概率均等。

于是，任一加法操作的期望放大倍数 $W$ 可以统一计算：
$$W=\frac{1}{N+1}\sum\limits_{k=0}^N\frac{e_k}{\binom{N}{k}}$$
其中 $e_k$ 是所有 $N$ 个乘法常数构成的第 $k$ 阶基本对称多项式（即所有大小为 $k$ 的子集乘积之和）。

令 $D=\sum d_j$ ，最终的期望即为：
$$x\cdot (\prod\limits_{i=1}^N a_i)+D\cdot W$$

void solve() {
    int n;
    Z x;
    cin >> n >> x;

    Z A = 1, B = 0;
    int N = 0;
    vector<Z> dp(n + 1);
    dp[0] = 1;

    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        char op = s[0];
        ll num = stoll(s.substr(1));

        if (op == '+') {
            B += num;
        } else if (op == '-') {
            B -= num;
        } else if (op == 'x') {
            A *= num;
            for (int j = N; j >= 0; --j) {
                dp[j + 1] += dp[j] * num;
            }
            ++N;
        } else if (op == '/') {
            A /= num;
            for (int j = N; j >= 0; --j) {
                dp[j + 1] += dp[j] / num;
            }
            ++N;
        }
    }

    Z W = 0;
    for (int i = 0; i <= N; i++) W += dp[i] / C.C(N, i);
    W /= N + 1;

    cout << x * A + B * W << endl;
}

H Six Seven

记 $f_k(j)$ 是能整除 $j$ 的 $k$ 的最大幂。

如果 $f_7(j)=m$ ，这意味着 $j$ 能被 $7^m$ 整除，但不能被 $7^{m+1}$ 整除。要使 $f_6(j)>f_7(j)$ ，即要求 $f_6(j)\geq m+1$ ，这也意味着 $j$ 必须至少能被 $6^{m+1}$ 整除。因此：

  • 对于所有的 $i$ ，要求 $a_i+x$ 都能被 $6$ 整除
  • 如果全相同，可以求出一个最小的偏移量 $x_0\in[0,5]$ 使得 $(a_i+x_0)\equiv 0 \pmod 6$ 。那么操作数 $x=x_0+6y$ ，目标即求出最小的非负整数 $y$ 。
  • 令 $b_i=(a_i+x_0)/6$ ，上述条件即可转化为对于所有的 $k\geq 1$ 和所有的 $i$ ，如果 $y\equiv −b_i \pmod {7k}$ ，则必须有 $y\equiv −b_i \pmod {6k}$ 。

因为指数增长十分迅速，所以我们可以直接搜索，从小到大逐位确定 $y\mod 42^k$ 。在每一层 $k$ ，我们只在区间 $[0,41]$ 内枚举系数 $c$ ，设 $yk = cur + c * 42^{k-1}$ 。随后检查是否能够满足：对于那些恰好让 $(yk+b_i) \mod 7k = 0$ 的数字 $b_i$ ，它们也必须满足 $(yk+b_i) \mod 6k=0$ 。如果满足，我们就将这批数字分流到 $k+1$ 的更深层中继续检验；如果不包含任何受此约束影响的数字，这也就意味着我们走完了一个局部解，把结果记为候选。

constexpr ll INF = 4e18;

vector<ll> p6(13), p7(13), p42(12);

void init() {
    p6[0] = p7[0] = p42[0] = 1;
    for (int i = 1; i <= 12; ++i) {
        p6[i] = p6[i - 1] * 6;
        p7[i] = p7[i - 1] * 7;
        if (i <= 11) p42[i] = p42[i - 1] * 42;
    }
}

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n);
    bool f = true;
    for (int i = 0; i < n; ++i) cin >> a[i];

    ll rem = a[0] % 6;
    for (int i = 1; i < n; ++i) {
        if (a[i] % 6 != rem) {
            f = false;
            break;
        }
    }

    if (!f) {
        cout << -1 << endl;
        return;
    }

    ll x0 = (6 - rem) % 6;
    vector<ll> b;
    for (int i = 0; i < n; ++i) b.pb((a[i] + x0) / 6);

    sort(all(b));
    b.erase(unique(all(b)), b.end());

    ll mn = INF;
    function<void(int, ll, vector<ll>)> dfs = [&](int k, ll cur, vector<ll> S) {
        if (k > 12 || cur >= mn) return;

        ll P6 = p6[k], P7 = p7[k], P42 = p42[k - 1];
        for (int c = 0; c < 42; ++c) {
            ll yk = cur + c * P42;
            if (yk >= mn) break;

            bool ok = true;
            vector<ll> nS;
            for (auto v : S) {
                if ((yk + v) % P7 == 0) {
                    nS.pb(v);
                    if ((yk + v) % P6) {
                        ok = false;
                        break;
                    }
                }
            }

            if (ok) {
                if (nS.empty()) {
                    if (yk < mn) mn = yk;
                } else {
                    dfs(k + 1, yk, nS);
                }
            }
        }
    };
    dfs(1, 0, b);

    if (mn == INF)
        cout << -1 << endl;
    else
        cout << x0 + 6 * mn << endl;
}

自动取模

constexpr int MOD = 1e9 + 7;

template <class T>
constexpr T ksm(T a, ll b) {
    T res = 1;
    while (b) {
        if (b & 1) res *= a;
        b >>= 1;
        a *= a;
    }
    return res;
}

template <int P>
struct MInt {
    int x;
    constexpr MInt() : x() {}
    constexpr MInt(ll x) : x{norm(x % getMod())} {}
    static int Mod;
    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) { Mod = Mod_; }
    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const { return x; }
    explicit constexpr operator int() const { return x; }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return ksm(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & { return *this *= rhs.inv(); }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr istream &operator>>(istream &is, MInt &a) {
        ll v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr ostream &operator<<(ostream &os, const MInt &a) { return os << a.val(); }
    friend constexpr bool operator==(MInt lhs, MInt rhs) { return lhs.val() == rhs.val(); }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) { return lhs.val() != rhs.val(); }
};

template <>
int MInt<0>::Mod = 998244353;

template <int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

using Z = MInt<MOD>;

组合数学

struct Comb {
    int n;
    vector<Z> _fac, _inv;

    Comb() : n(0), _fac{1}, _inv{1} {}
    Comb(int n) : Comb() { init(n); }
    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _inv.resize(m + 1);
        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _inv[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _inv[i - 1] = _inv[i] * i;
        }
        n = m;
    }
    Z fac(int x) {
        if (x > n) init(x);
        return _fac[x];
    }
    Z inv(int x) {
        if (x > n) init(x);
        return _inv[x];
    }
    Z C(int x, int y) {
        if (x < 0 || y < 0 || x < y) return 0;
        return fac(x) * inv(y) * inv(x - y);
    }
    Z A(int x, int y) {
        if (x < 0 || y < 0 || x < y) return 0;
        return fac(x) * inv(x - y);
    }
} C;
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

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

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇