9/13，感觉这一场的出题人比较仁慈（

E - Enduring the Pokémon

【题意】
有 nn 只宝可梦，每只拥有力量 aia_i 和购买费用 bib_i。

  1. 你可以任选任意多只买下，作为“自己的宝可梦”。
  2. 安排其余只按自定顺序与它单挑。
  3. 若当前力量严格大于对手则获胜，力量 +1+1，继续；否则立刻淘汰。
  4. 若最终击败全部对手，则赢得比赛。

求能完成上述目标的最小购买费用，若无解输出 −1-1。

首先可以判断的是如何安排剩下的 pokemon，肯定是先把力量低的放在前面刷经验，initial strength 比他大的则从小到大放在后面。

然后一个重要的观察是，如果某只 strength 为 xx 的 pokemon 可以作为答案，那么所有 strength ≥x\ge x 的都可以作为答案。

接着我们发现，我们只需要一只 pokemon 即可。考虑两只 pokemon 其力量分别为 x,y,x<yx,y,x\lt y，如果 x,yx,y 有一个可以，那么我们只需要一个；如果 x,yx,y 都不行，说明 yy 就算刷经验了也打不过 boss，那么两个臭皮匠也还是打不过诸葛亮。

所以我们发现了可以二分的性质：把 pokemon 按力量排序，找到力量最小的 xx，使得其可以可以通过刷经验的方式干掉所有其他的 pokemon. check() 的话可以直接 O(n)O(n) 扫描判断。找到后还要找出力量 ≥x\ge x 最小的花费。

总时间复杂度 O(nlog⁡n)O(n\log n)

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
#define FOR(i, l, r) for(int i = (l); i <= (r); i++)
#define ROF(i, r, l) for(int i = (r); i >= (l); i--)
#define sz(a) int((a).size())
#define ll long long
#define vi vector<int>
#define pii pair<int, int>
using namespace std;
const int N = 1e5 + 10;
int n, a[N], b[N];
pii c[N];
int check(int x) {
    int v = a[x];
    FOR(i, 1, n) {
        if(i != x) {
            if(a[i] < v) {
                v++;
            } else return 0;
        }
    }
    return 1;
}
int main() {
    ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 1, n) cin >> b[i];
    FOR(i, 1, n) c[i] = {a[i], b[i]};
    sort(c + 1, c + n + 1);
    FOR(i, 1, n) {
        a[i] = c[i].first;
        b[i] = c[i].second;
    }
    int l = 1, r = n, best = -1;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(check(mid)) best = mid, r = mid - 1;
        else l = mid + 1;
    }
    if(best == -1) {
        cout << "-1\n";
        return 0;
    }
    int ans = b[n];
    FOR(i, best, n) ans = min(ans, b[i]);
    cout << ans << "\n";
}

H - Hashing

【题意】给定长度为 nn 的数组 aa，计算所有连续子数组 a[l…r]a[l\dots r] 的“kk 进制模 pp 哈希值”等于 xx 的子数组个数。保证 pp 是素数，x,k<px,k\lt p.
子数组 a[l…r]a[l\dots r] 哈希值定义为：H(l,r)=∑i∈[l,r]a[i]×kr−imod  pH(l,r)=\sum_{i\in[l,r]}a[i]\times k^{r-i} \mod p

经典的序列统计数对思想：用数据结构维护 1∼i−11\sim i-1 并用数据结构来求 (x,i),x<i(x,i),x\lt i 的个数。这样可以做到不重不漏。

考虑如何条件的 (l,r),l<r(l,r),l\lt r 满足什么条件

H(l,r)≡x(modp) H(l,r)\equiv x\pmod p

我们计算哈希的前缀和 H(i)=H(1,i)H(i)=H(1,i)，用两段前缀相减计算 H(l,r)H(l,r)

H(r)−H(l−1)×kr−l+1≡x(modp) H(r)-H(l-1)\times k^{r-l+1}\equiv x\pmod p

移项，使得一侧只有 ll 另一侧只有 rr

H(r)−xkr≡H(l−1)kl−1(modp) \frac{H(r)-x}{k^r}\equiv \frac{H(l-1)}{k^{l-1}} \pmod p

所以，计算出 rr 对应的值（等式左侧），我们只需要在数据结构里查询多少 ll 满足上式即可。考虑到 pp 比较大，这里选用的是 std::map. 时间复杂度 O(nlog⁡n)O(n\log n)

AC Code

注意插入 H(0)=1H(0) = 1，把 l=1l=1 的情况算进去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using ll        = long long;
constexpr int N = 2e5 + 10;
 
ll n, k, p, x;
ll a[N], h[N];
std::map<ll, int> cnt;
ll base[N], ibase[N];
 
ll fpow(ll b, ll p, ll m) {
    ll res = 1;
    while (p) {
        if (p & 1) res = res * b % m;
        b = b * b % m;
        p >>= 1;
    }
    return res;
}
 
int main() {
#ifdef ONLINE_JUDGE
    std::cin.tie(0)->sync_with_stdio(0);
#endif
 
    std::cin >> n >> k >> p >> x;
    for (int i = 1; i <= n; i++) std::cin >> a[i];
 
    base[0] = 1;
    for (int i = 1; i <= n; i++) base[i] = base[i - 1] * k % p;
    ibase[n] = fpow(base[n], p - 2, p);
    for (int i = n - 1; i >= 0; i--) ibase[i] = ibase[i + 1] * k % p;
 
    h[0]   = 0;
    ll ans = 0;
    cnt[0] = 1;
    for (int i = 1; i <= n; i++) {
        h[i] = (h[i - 1] * k + a[i]) % p;
        ll q = ((h[i] - x) % p + p) % p * ibase[i] % p;
        ans += cnt[q];
        cnt[h[i] * ibase[i] % p]++;
    }
    std::cout << ans << "\n";
}

J - Just a Turtle Problem

给定长度 nn 的数组 aa，构造 n×nn\times n 表格：

  • 第 11 行：a1,a2,…,ana_1,a_2,\dots,a_n；
  • 第 ii 行 (i≥2)(i\ge 2)：把第 i−1i-1 行做左循环移位（首元素移到末尾）。

海龟从左上 (1,1)(1,1) 出发，每次只能向右或向下走一步，目标到达右下 (n,n)(n,n)。求经过格子数字之和的最小值。1≤n≤100 0001\le n\le 100\,000，∣ai∣≤109\lvert a_i\rvert\le 10^9。

结论：无论怎么走，路径和是固定的。

这是因为考虑 n×nn\times n 方格的从左下往右上的斜线上的数，由于每行都是 left shift，所以都是相等的。所以 (i,j)(i,j) 出发可以到达的两个点 (i+1,j),(i,j+1)(i+1,j),(i,j+1) 上的数是一样的。

所以答案就是 2∑i=1nai−an2\sum_{i=1}^n a_i-a_n（因为 ana_n 的大斜线只有一条）

AC Code

代码是从 00 下标开始的，所以有些许出入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using ll = long long;

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int &x : a) {
        std::cin >> x;
    }

    ll ans = a[0];
    for (int i = 1; i <= 2 * (n - 1); i++) {
        ans += a[i % n];
    }
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T = 1;
    while (T--) {
        solve();
    }
    return 0;
}

K - Keeping the Medians Close 1

首先我们可以猜到答案的下界是 cn+1−cnc_{n+1}-c_n.

于是任务就是把 n−12\frac{n-1}{2} 个小于和大于中位数的数通过 swap 换到两个序列里面，而这个一定是可以做到的。不妨设 aa 序列里面 <cn\lt c_n 的数更多（有 m>n−12m\gt \frac{n-1}{2} 个），那么 bb 里面最多有 n−m<n−12n-m\lt \frac{n-1}{2} 个 <cn\lt c_n 的数，于是最多有 n−mn-m 个 ii 使得 ai<cn,bi<cna_i\lt c_n,b_i\lt c_n（即交换后没有效果），所以至少 2m−n2m-n 个 ii 满足 ai<cn,bi>cn+1a_i\lt c_n,b_i\gt c_{n+1}，所以交换他们一定可以组成答案。

时间瓶颈在排序，时间复杂度 O(nlog⁡n)O(n\log n)

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>

void run() {
    int n;
    std::cin >> n;
    std::vector<int> a(n), b(n), c;
    for (int i = 0; i < n; i++) std::cin >> a[i], c.push_back(a[i]);
    for (int i = 0; i < n; i++) std::cin >> b[i], c.push_back(b[i]);
    std::sort(c.begin(), c.end());

    int x = c[n - 1], y = c[n];
    std::vector<int> pos;
    for (int i = 0; i < n; i++)
        if (a[i] == x || a[i] == y || b[i] == x || b[i] == y) pos.push_back(i);

    if (pos.size() == 2) {
        int t = 0;
        for (auto i : pos)
            if (a[i] == x || a[i] == y) t++;
        if (t == 2 || t == 0) std::swap(a[pos[0]], b[pos[0]]);
    } else pos.push_back(pos[0]);

    int t = (a[pos[0]] < x) + (a[pos[1]] < x);
    for (int i = 0; i < n; i++) {
        if (i == pos[0] || i == pos[1]) continue;
        if (a[i] < x) {
            if (t * 2 + 1 < n) t++;
            else if (b[i] > y) std::swap(a[i], b[i]);
            else t++;
        }
    }

    if (t * 2 + 1 < n) {
        for (int i = 0; i < n && t * 2 + 1 < n; i++) {
            if (i == pos[0] || i == pos[1]) continue;
            if (a[i] > y && b[i] < x) std::swap(a[i], b[i]), t++;
        }
    }
    if (t * 2 + 1 > n) {
        for (int i = 0; i < n && t * 2 + 1 > n; i++) {
            if (i == pos[0] || i == pos[1]) continue;
            if (a[i] < x && b[i] > y) std::swap(a[i], b[i]), t--;
        }
    }
    
    for (int i = 0; i < n; i++) std::cout << a[i] << " \n"[i == n - 1];
    for (int i = 0; i < n; i++) std::cout << b[i] << " \n"[i == n - 1];
}

int main() {
#ifdef ONLINE_JUDGE
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0);
#endif
    int t;
    std::cin >> t;
    while (t--) run(); //, std::fprintf(stderr, "----------------\n");
}