HOI R1 Overall

Register_int · 2024-03-11 18:43:44 · 题解

A

首先有个比较显然的 dp。设 dp_i 为从 i 开始开到 n 的最大金币数量，显然有：

dp_i=\max(a_i,\max_{1\le j\le a_i}dp_{i+j}+\sum^{j-1}_{k=1}a_{i+k})

含义是枚举拿不拿 a_i 和开完之后拿多少个。这是 O(n^2) 的所以考虑优化，拆开式子后，发现一次转移等价于：

上个线段树即可，复杂度 O(n\log n)。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

struct node {
    int l, r; ll v, add;
} t[MAXN << 2];

inline 
void upd(int p, ll v) {
    t[p].add += v, t[p].v += v;
}

inline 
void pushup(int p) {
    t[p].v = max(t[p << 1].v, t[p << 1 | 1].v);
}

inline 
void pushdown(int p) {
    if (!t[p].add) return ;
    upd(p << 1, t[p].add), upd(p << 1 | 1, t[p].add), t[p].add = 0;
}

void build(int l, int r, int p) {
    if (l > r) return ;
    t[p].l = l, t[p].r = r, t[p].v = t[p].add = 0;
    if (l == r) return ; int mid = l + r >> 1;
    build(l, mid, p << 1), build(mid + 1, r, p << 1 | 1);
}

void modify(int l, int r, ll v, int p) {
    if (l > r) return ;
    if (l <= t[p].l && t[p].r <= r) return upd(p, v);
    pushdown(p); int mid = t[p].l + t[p].r >> 1;
    if (l <= mid) modify(l, r, v, p << 1);
    if (r > mid) modify(l, r, v, p << 1 | 1); pushup(p);
}

ll query(int l, int r, int p) {
    if (l > r) return 0;
    if (l <= t[p].l && t[p].r <= r) return t[p].v;
    pushdown(p); int mid = t[p].l + t[p].r >> 1; ll res = 0;
    if (l <= mid) res = max(res, query(l, r, p << 1));
    if (r > mid) res = max(res, query(l, r, p << 1 | 1)); return res;
}

int T, n; ll a[MAXN], dp[MAXN];

int main() {
    for (scanf("%d", &T); T--;) {
        scanf("%d", &n), build(1, n, 1);
        for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
        for (int i = n, l, r; i; i--) {
            dp[i] = a[i], l = i + 1, r = min<ll>(i + a[i], n);
            dp[i] = max(dp[i], query(l, r, 1));
            modify(l, n, a[i], 1), modify(i, i, dp[i], 1);
        }
        printf("%lld\n", dp[1]);
    }
}

Bonus：如何做到 O(n\alpha(n))？

B

放 B 纯粹是怕 A 放分讨会被骂。

首先判掉一些显然有/无解的情况，比如初始就有环或者 x\le0 之类的。

本题关键在于一个交换操作。若一个空位填要填的数会导致成环，那么将其与其它空位交换即可消环。这个是好理解的，否则说明之前就存在环。

- 若仅有一个位置为 $0$，直接硬填判。 - 否则，先判 $x<2$ 显然无解： - 若 $x\le n+1$，则存在用两个位置解决的方法：找一个 $-1$ 全填满，不合法的话换用第二个 $-1$ 填。可以证明是一定合法的。 - 否则，如果仅有两个空位，那么直接暴力枚举这两个空位是什么。此时有三个空位。如果 $rt_n$ 是待定的，那么将 $a_{rt_n}$ 设为最大的 $k$ 使得 $rt_k$ 也待定即可。这样是为了贪心地取到最大的总和。取完后，剩余的每个空位最多有 $n+1$ 的贡献。排掉不够的情况，不妨设还差的部分为 $x'$，算出 $t=\left\lfloor\frac{x'}{n+1}\right\rfloor$ 与 $y=x'\bmod(n+1)$。继续对 $y$ 讨论： - $y=0$。可以暴力填前 $t$ 个。 - $y=1$。如果只剩两个空位，那么稍加分析可以发现只有 $t=y=1$ 的情况，那么直接硬放，若不满足再和 $rt_n$ 交换。否则，以一个空位作为调整的自由元，填掉剩下两个，不满足就和第三个空位交换。 - $y>1$。这是平凡的，用一个空位硬放后再找一个空位交换即可。所以这些情况都是有解的，时间复杂度 $O(n)$。 ```cpp #include <bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 10; typedef long long ll; int n, cnt, rt[MAXN]; ll x, a[MAXN]; bool l[MAXN]; vector<int> p, g[MAXN]; bool dfs(int u, int f) { cnt++, rt[u] = f; for (int v : g[u]) if (rt[v] || dfs(v, f)) return 1; return 0; } void solve() { int u, v, w, y, k; ll t; for (int i = 1; i <= n; i++) { if (!~a[i] && dfs(i, i)) { printf("Rick"); return; } } if (cnt < n) return puts("Rick"), void(); if (!x) { for (int i = 1; i <= n; i++) printf("%lld ", a[i]); return ; } if (p.size() == 1) { u = p[0]; a[u] += x; if (a[u] < 1 || a[u] > n || rt[a[u]] == u) return puts("Rick"), void(); } else if (p.size() > 1) { if (x < 2) return puts("Rick"), void(); if (x <= n + 1) { u = p[0], a[u] += x; if (rt[a[u]] == u) v = p[1], swap(a[u], a[v]); } else if (p.size() == 2) { u = p[0], v = p[1]; for (a[u] = 1; a[u] <= n; a[u]++) { a[v] = x - a[u] - 2; if (a[v] > 0 && a[v] <= n && rt[a[u]] != u && rt[a[v]] != v && (rt[a[u]] != v || rt[a[v]] != u)) break; } if (a[u] > n) return puts("Rick"), void(); } else { k = rt[n]; if (l[k]) { for (a[k] = n - 1; a[k] && l[rt[a[k]]]; a[k]--); if (!a[k]) a[k] = -1; x -= a[k] + 1; p.erase(lower_bound(p.begin(), p.end(), k)); } if (x > (ll)(n + 1) * p.size()) return puts("Rick"), void(); t = x / (n + 1), y = x % (n + 1); for (int i = 0; i < t; i++) a[p[i]] = n; if (y == 1) { if (p.size() == 2 && l[k] && a[k] == -1) p.push_back(k); if (p.size() == 2) { x += a[k] + 1, x -= n + 1, a[k] = -1; u = p[1], a[u] += x; if (rt[a[u]] == u) swap(a[k], a[u]); } else { u = p[0], a[u] = 1; v = p.back(), a[v] = n - 1; w = p[1]; if (rt[a[u]] == u || rt[a[u]] == v && rt[a[v]] == u) swap(a[u], a[w]); if (rt[a[v]] == v) swap(a[v], a[w]); } } else if (y > 1) { u = p.back(), a[u] += y; if (rt[a[u]] == u) v = p[p.size() - 2], swap(a[u], a[v]); } } } for (int i = 1; i <= n; i++) printf("%lld ", a[i]); } int main() { scanf("%d%lld", &n, &x); for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); if (!a[i]) p.emplace_back(i), a[i] = -1, l[i] = 1; x -= a[i]; if (a[i] > 0) g[a[i]].emplace_back(i); } solve(); return 0; } ``` ### C 记 $n+m$ 为 $s$，$a_i$ 和 $b_i$ 的值域为 $v$，$p$ 的值域为 $P$，$q$ 的值域为 $Q$。需要一定的数论基础。先考虑 Subtask 5，此时分母为 $1$，有以下观察： $0\le x<y\Rightarrow x\bmod y=x

此时可以直接取一个大质数，在该质数的模意义下求解即可。除法可以直接转成逆元。

可以发现我们并不关心约分后的结果，只希望找到一个映射，使得映射后的答案 便于计算 且 能对应到原式的唯一解。还是考虑取一个大质数。设大质数为 y，观察到，y\ge PQ 时是足够的，具体地：

y\ge PQ,\dfrac{p'}{q'}\equiv\dfrac{p}{q}\pmod y\Rightarrow\dfrac{p'}{q'}=\dfrac{p}{q}

其中，1\le p,p'\le P，1\le q,q'\le Q。证明不难，倒一倒值域即可。在该模意义下找到答案 x 后，本质上是要解这样一个方程：

xq\bmod y\le P

可以用 BSGS 解决。取一个根号级别的 B，把 q 拆成 kB+l，预处理出所有 xkB\bmod y 和 xl\bmod y，合并的时候稍微讨论一下，设前面那个值为 z_1，后面那个值为 z_2，则有两种情况：

对于情况一直接取最小值，对于情况二需要排序二分。当然都是容易的。大整数乘法可以 __int128 草过去，复杂度为 O(s+\sqrt{Q}\log{Q})，可以通过。

#include <bits/stdc++.h>

using namespace std;

// using fread
#define INPUT_OPTIMIZE

// using fwrite
//#define OUTPUT_OPTIMIZE

namespace IO {
    // by R_i.
}

using namespace IO;

typedef long long ll;
typedef __int128 lll;
typedef pair<lll, lll> plll;

const int MAXN = 6e4 + 10, B = 6e4;
const lll mod = 9000000000000000041ll;

inline 
lll qpow(lll b, lll p) {
    lll res = 1;
    for (; p; p >>= 1, b = b * b % mod) if (p & 1) res = res * b % mod;
    return res;
}

int n, m; ll tmp; lll p = 1, q = 1, x, y, z;

plll a[MAXN];

int main() {
    read(n, m, tmp);
    for (int i = 1; i <= n; i++) read(tmp), p = p * tmp % mod;
    for (int i = 1; i <= m; i++) read(tmp), q = q * tmp % mod;
    p = p * qpow(q, mod - 2) % mod, x = p;
    for (int i = 1; i < B; i++) a[i] = plll(x, i), x = (x + p) % mod;
    sort(a, a + B), y = p;
    for (ll i = 1, j; ; i += B) {
        if (y <= 3e9) return printf("%lld %lld", (ll)y, i), 0;
        j = lower_bound(a, a + B, plll(mod - y + 1, 0)) - a;
        if (j < B) {
            z = a[j].first + y - mod;
            if (z <= 3e9) return printf("%lld %lld", (ll)z, (ll)a[j].second + i), 0;
        }
        y = (y + x) % mod;
    }
}

D

放 D 纯粹是怕前三题放交互会被骂。

可以通过表现来判断是否是 \verb!aa!。考虑有 \verb!aa! 的情况。我们发现，\verb!aa! 跟剩下两种基因型杂交会有以下情况：

与 \verb!Aa! 杂交，相等概率出现 \verb!Aa,aa!，即 \frac12 概率表现为 \verb!a!。
与 \verb!AA! 杂交，只会出现 \verb!Aa!，永远表现为 \verb!A!。

于是我们可以用 \verb!aa! 与其余基因型杂交 k_1 次，若出现 \verb!a! 则为 \verb!Aa!，否则为 \verb!AA!。这部分失误概率为 2^{-k_1}。

但是没有 \verb!aa! 这个做法就爆炸了。重新考虑，对原序列两两分组，每一组有 \{\verb!AA!,\verb!AA!\},\{\verb!Aa!,\verb!Aa!\},\{\verb!AA!,\verb!Aa!\},\{\verb!Aa!,\verb!AA!\} 四种可能。还是通过杂交出 \verb!aa! 来判断。有如下方法：

两个基因型（我们称为亲代）杂交 k_2 次，得到 k_2 个基因型（我们称为子代）。每个子代再分别与两个亲代各杂交一次。

如果子代里已经有了 \verb!a!，那么可以确定这一组是 \{\verb!Aa!,\verb!Aa!\} 了。否则，在子代里很有可能出现 \verb!Aa!。此时再与亲代杂交会出现 \verb!Aa!\times\verb!Aa! 的情况，有 \frac14 的概率出现 \verb!aa!。若出现了即可直接判定。

由于对于每组两个基因型，我们需要操作 3k_2 次，所以这种方法对于每个基因型的平均操作次数是 \frac 32 k_2。他能否达到我们的准确度要求呢？不妨来算一算：

\begin{aligned} &\dfrac1{2^{k_2}}\sum^{k_2}_i\dbinom{k_2}i\left(1-\dfrac14\right)^{k_2i}\\ =&\dfrac1{2^{k_2}}\left(2-\dfrac14\right)^{k_2}\\ =&\left(\dfrac78\right)^{k_2}\\ \end{aligned}

在题目的限制下，k_2\le 15。此时光单组的最大误判概率就约为 0.135，总共一万多组就直接爆炸了。

有这样一个小优化。在该方法的过程中，判断 \verb!Aa! 出现的标志正是杂交出 \verb!aa!。也就是说，若找到一个 \verb!Aa!，我们就再也不需要这个方法了，因为我们用这个 \verb!aa! 来判剩下的即可。

然后这个做法就直接对了。为什么呢？因为这个方法是不会将 \verb!AA! 错判的，而判 \verb!Aa! 也只有最多一次判断机会，因为只要判成功了也就造出了一个 \verb!aa!，换用有 \verb!aa! 的方法即可。所以乘进概率里面只用乘一次，不会对最终正确率造成多大影响。

最后就是调参了。取 k_1=22,k_2=15，操作次数为 n\times\max(k_1,\frac32k_2)=22.5n\le 4.5\times10^5，单组数据错误概率约为 0.135。本题数据下有 15 个点需要动用此方法，通过概率为 (1-0.135)^{15}\approx0.123，期望交 8 次可过。此处估算有较大误差，事实上标程经过五次重复试验得到的期望提交次数是 3.4 次。

#include <bits/stdc++.h>

using namespace std;

char query(int k);
void cross(int i, int j);

vector<string> guess(int n) {
    int p = 0, tot = n;
    vector<char> a(n);
    vector<string> ans(n);
    for (int i = 1; i <= n; i++) a[i - 1] = query(i);
    for (int i = 0; i < n; i++) if (islower(a[i])) ans[i] = "aa", p = i + 1;
    if (!p) {
        int pre = 0, f = 0;
        for (int i = 2; i <= n; i += 2) {
            for (int j = 0; j < 15; j++) cross(i - 1, i), a.push_back(query(++tot));
            f = 0;
            for (int j = 1; j <= 15; j++) if (islower(a[tot - j])) { f = 1, p = tot - j + 1; break; }
            if (f) { ans[i - 2] = ans[i - 1] = "Aa"; break; }
            pre = tot, ans[i - 2] = ans[i - 1] = "AA";
            for (int j = 0; j < 15; j++) cross(i - 1, pre - j), a.push_back(query(++tot));
            for (int j = 1; j <= 15; j++) if (islower(a[tot - j])) { f = 1; p = tot - j + 1; break; }
            if (f) { ans[i - 2] = "Aa"; break; }
            for (int j = 0; j < 15; j++) cross(i, pre - j), a.push_back(query(++tot));
            for (int j = 1; j <= 15; j++) if (islower(a[tot - j])) { f = 1; p = tot - j + 1; break; }
            if (f) { ans[i - 1] = "Aa"; break; }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (ans[i - 1] != "") continue;
        for (int j = 0; j < 22; j++) {
            cross(i, p);
            if (islower(query(++tot))) { ans[i - 1] = "Aa"; break; }
        }
        if (ans[i - 1] == "") ans[i - 1] = "AA";
    }
    return ans;
}