A - An Easy Calculus Problem

签到题，a,b,c,da,b,c,d 都已经给你了.

AC Code
 
1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>

int a = -2, b = 1, c = -14, d = 17, x;

int main() {
    std::cin >> x;
    if (x <= -3) std::cout << 8 - (x + 4) * (x + 4) << '\n';
    else if (x <= 2) std::cout << a * x + b << "\n";
    else std::cout << x * x * x + c * x + d << "\n";
}

C - Conform Conforme

一个关键的发现是，假设上一次迭代有 nn 个数，则下一次迭代最多 O(n)O(\sqrt{n}) 个不同的数. 所以考虑暴力维护出现频率，可以猜测不会有很多轮，差不多是 O(log⁡n)O(\log n) 轮. 所以时间复杂度是 O(n×min⁡(k,log⁡n))O(n\times \min(k, \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
#include <bits/stdc++.h>
#include <random>
using umap = std::unordered_map<int, int>;
constexpr int N = 2e5 + 10;

int n, k;
int a[N];

umap get() {
    umap cnt;
    for (int i = 1; i <= n; i++) cnt[a[i]]++;
    return cnt;
}
void tf(umap &c) {
    for (int i = 1; i <= n; i++) a[i] = c[a[i]];
}

void gen() {
    std::mt19937 rng(std::random_device{}());
    n = rng() % N + 1;
    k = 1e9;
    for (int i = 1; i <= n; i++) a[i] = rng() % k + 1;
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0), std::cout.tie(0);

    // gen();
    std::cin >> n >> k;
    for (int i = 1; i <= n; i++) std::cin >> a[i];

    while (k--) {
        auto cnt = get();
        // check
        bool all = true;
        for (auto [c, v] : cnt) {
            if (c != v) {
                all = false;
                break;
            }
        }
        if (all) break;

        tf(cnt);
    }

    for (int i = 1; i <= n; i++) std::cout << a[i] << " \n"[i == n];
}

E - Escape from Markov

假设走到 uu 的时间为 tt，Dijkstra 过程里准备走 (u,v)(u,v) 边，这条边在第 ii 号巡逻车的路线 RiR_i 里是第 kk 条路，那么这条路不能走的条件是 d≡k(modℓ)d\equiv k\pmod \ell.

对于一条路 (u,v)(u,v)，它可能在不同路线上位于不同的位置，对于一条路 e=(u,v)e=(u,v)，我们记录下所有不能走的时刻 pep_e. 于是在 Dijkstra 过程里，假设当前时间为 dd，如果 dmod  ℓd \mod \ell 不在 pep_e 里，说明当前时刻可以通行；否则需要等到下一个可以通行的时刻 tt，这个 tt 满足 min⁡tt>d and (tmod  ℓ)∉pe\min_t t\gt d\texttt{ and } (t\mod \ell) \notin p_e. 这个可以通过二分完成.

需要注意的是，tmod  ℓt\mod \ell 可能 <(dmod  ℓ)\lt (d\mod \ell)，所以，可以在 pep_e 里同时加入 k,k+ℓk,k+\ell，这样可以在 pep_e 里直接二分 (tmod  ℓ)(t\mod\ell).

时间复杂度 O(nlog⁡2n)O(n\log^2 n).

AC Code

我写的时候第一版写的是 std::bitset 结合 _Find_next + 优先队列 Dijkstra 但老是被卡空间. 所以急了，直接写了一个线段树维护的 Dijkstra.

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
constexpr int N = 2e5 + 10, M = 2 * N;
constexpr int inf = 2e9;
using pii = std::pair<int, int>;

int n, m, p, l, a, b;
std::vector<int> g[N];
std::unordered_map<long long, std::vector<int>> c;
int dis[N];

long long pack(pii v) { return v.first * (n + 1) + v.second; }

// segment tree to maintain dijkstra
int val[N * 4], ind[N * 4];
void pullup(int p) {
    if (val[p << 1] <= val[p << 1 | 1]) val[p] = val[p << 1], ind[p] = ind[p << 1];
    else val[p] = val[p << 1 | 1], ind[p] = ind[p << 1 | 1];
}
void build(int p = 1, int lp = 1, int rp = n) {
    if (lp == rp) return val[p] = inf, ind[p] = lp, void();
    int mid = lp + ((rp - lp) >> 1);
    build(p << 1, lp, mid), build(p << 1 | 1, mid + 1, rp);
    pullup(p);
}
void set(int pos, int v, bool force, int p = 1, int lp = 1, int rp = n) {
    if (lp == rp) {
        if (force) val[p] = v;
        else val[p] = std::min(val[p], v);
        std::fprintf(stderr, "set %d to %d\n", pos, val[p]);
        return;
    }
    int mid = lp + ((rp - lp) >> 1);
    pos <= mid ? set(pos, v, force, p << 1, lp, mid) : set(pos, v, force, p << 1 | 1, mid + 1, rp);
    pullup(p);
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0), std::cout.tie(0);
    std::cin >> n >> m >> p >> l;
    for (int i = 1, u, v; i <= m; i++) {
        std::cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= p; i++) {
        std::vector<int> plan(l);
        for (auto &v : plan) std::cin >> v;
        plan.push_back(plan[0]);

        auto add = [&](int u, int v, int t) {
            g[u].push_back(v), g[v].push_back(u);
            if (u > v) std::swap(u, v);

            auto pair = pack(std::pair{u, v});
            c[pair].push_back(t), c[pair].push_back(t + l);
        };
        for (int j = 0; j < l; j++) add(plan[j], plan[j + 1], j);
    }
    std::cin >> a >> b;

    for (int i = 1; i <= n; i++) {
        dis[i] = inf;
        std::sort(all(g[i]));
        g[i].erase(std::unique(all(g[i])), g[i].end());
    }
    for (auto &[pair, time] : c) {
        std::sort(all(time));
        time.erase(std::unique(all(time)), time.end());
    }
    build();

    dis[a] = 0;
    set(a, 0, true);

    auto exists = [&](std::vector<int> &vec, int v) {
        auto it = std::lower_bound(all(vec), v);
        return it != vec.end() && *it == v;
    };
    auto find_next = [&](std::vector<int> &vec, int begin) {
        int lp = begin, rp = 2 * l + 1;
        while (lp + 1 < rp) {
            int mid = lp + ((rp - lp) >> 1);
            auto f = std::upper_bound(all(vec), mid - 1) - std::lower_bound(all(vec), begin);
            if (f == mid - begin) lp = mid;
            else rp = mid;
        }

        return rp;
    };

    while (val[1] != inf) {
        int d = val[1], u = ind[1];
        set(u, inf, true);
        if (d != dis[u]) continue;
        std::fprintf(stderr, "dis[%d] = %d\n", u, d);

        for (auto &v : g[u]) {
            std::fprintf(stderr, "%d -> %d\n", u, v);
            auto pair = pack(std::pair{std::min(u, v), std::max(u, v)});

            if (!c.count(pair)) { // no constraint
                if (dis[v] > dis[u] + 1) {
                    dis[v] = dis[u] + 1;
                    set(v, dis[v], true);
                }

                continue;
            }

            auto &vec = c[pair];
            int t1 = d % l;
            if (exists(vec, t1)) {
                auto t = find_next(vec, t1);
                std::fprintf(stderr, "delta = %d - %d\n", (int)t, t1);
                if (t >= 2 * l) continue;

                int delta = t - t1;
                if (dis[v] > dis[u] + delta) {
                    dis[v] = delta + dis[u];
                    set(v, dis[v], true);
                }
            } else {
                if (dis[v] > dis[u] + 1) {
                    dis[v] = dis[u] + 1;
                    set(v, dis[v], true);
                }
            }
        }
    }

    if (dis[b] == inf) std::cout << "IMPOSSIBLE\n";
    else std::cout << dis[b] << "\n";
}

F - Factions vs The Hegemon

其实用 std::set 维护一下就好了，一个 std::set 维护 {wi,i}\{w_i, i\}，一个 std::set 维护剩下的 faction index ii.

每次循环先判断是否处于 Hegemony. 然后 lower_bound 找 min 或者 max 元素，接着再用一次 lower_bound 找到 west-most faction index ii，然后更新两个 std::set 即可.

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/extc++.h>
#include <bits/stdc++.h>
#include <random>
constexpr int N = 2e5 + 10;
using ll = long long;
using pli = std::pair<ll, int>;

int n;
ll a[N], sum{0};
std::set<pli> s;
std::set<int> nb;

void gen() {
    std::mt19937_64 rng(std::random_device{}());
    n = rng() % N + 1;
    int V = 1e9;
    for (int i = 1; i <= n; i++) a[i] = rng() % V + 1;
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0), std::cout.tie(0);

    std::cin >> n;
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        sum += a[i];
        s.insert({a[i], i});
        nb.insert(i);
    }

    auto update_to = [&](int i, ll nval) {
        s.erase({a[i], i});
        sum -= a[i];

        a[i] = nval;

        s.insert({nval, i});
        sum += nval;
    };
    auto getId = [&](ll val) {
        auto it = s.lower_bound({val, -1});
        return it->second;
    };

    while (s.size() > 1) {
        // check hegemony
        auto [maxval, maxid] = *s.rbegin();

        ll val;
        int id;

        if (maxval <= sum - maxval) val = maxval;
        else val = s.begin()->first;

        id = getId(val);
        std::cout << id << " " << a[id] << "\n";
        sum -= val;

        auto it = nb.lower_bound(id);
        if (it != nb.begin()) {
            int ni = *std::prev(it);
            update_to(ni, a[ni] + val / 2);
        }
        if (std::next(it) != nb.end()) {
            int ni = *std::next(it);
            update_to(ni, a[ni] + val / 2);
        }

        // clear
        nb.erase(id);
        s.erase({a[id], id});
    }

    std::cout << s.begin()->second << " " << s.begin()->first << "\n";
}

H - HIIT

因为第一件事是保证在不超过 xx 的情况下，让 00 尽可能少. 所以这一步是对 aia_i 进行排序后，贪心地从小往大取.

接下来是要最大化 22 的数量. 有两种情况可以在不增减 00 的数量的情况将 11 变成 22.

  • i[1]→i[2]i[1] \to i[2] 直接将 ii 从 11 升级为 22.

    这个操作会新增加 bi−aib_i-a_i 的 cost

  • i[1]→i[0] and j[0]→j[2]i[1]\to i[0] \texttt{ and } j[0]\to j[2] 将 ii 降级后，将 jj 升为 22.

    这步操作会新增加 bj−aib_j-a_i 的 cost

这里依然可以考虑贪心：每一次升级必然伴随总 cost 的提升，所以我们总是从所有操作里选择 cost 最小的那个. 这样才能进行更多的操作.

操作一可以用 std::set 维护 std::pair(bi−ai,i)\texttt{std::pair}(b_i-a_i, i)，操作二可以分别用 std::set 维护 (ai,i),(bj,j)(a_i,i),(b_j,j). 这里 ii 表示第一次贪心完后被选择的，jj 表示没有被选上的.

每一步循环取操作一里 cost 最小的那一步和操作二里 cost 最小的那一步，然后打擂台，并更新剩余 cost 以及两种操作的 std::set.

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

AC Code

有一坨 std::set 的增删改查，看起来很乱……

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define endl std::endl
using ll = long long;
constexpr int N = 2e5 + 10;

ll n, x;
struct Item {
    ll a, b;
    int id;
    bool operator<(Item rhs) const { return b < rhs.b; }
} ab[N];
int ans[N];

void preselect() {
    ll t = x;
    for (int i = 1; i <= n && t >= ab[i].a; i++) {
        ans[ab[i].id] = 1;
        t -= ab[i].a;
    }
}

void answer() {
    for (int i = 1; i <= n; i++) std::cout << ans[i];
    std::cout << endl;
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0), std::cout.tie(0);
    std::cin >> n >> x;
    for (int i = 1; i <= n; i++) std::cin >> ab[i].a, ab[i].id = i;
    for (int i = 1; i <= n; i++) std::cin >> ab[i].b;

    std::sort(ab + 1, ab + 1 + n, [](Item &x, Item &y) { return x.a < y.a; });
    preselect();

    std::sort(ab + 1, ab + 1 + n, [](auto &i, auto &j) { return i.id < j.id; });
    std::set<std::pair<ll, int>> s, sp, ns;
    for (int i = 1; i <= n; i++) {
        assert(i == ab[i].id);

        if (ans[i] == 1) {
            s.insert({ab[i].b - ab[i].a, i});
            sp.insert({ab[i].a, i});
            x -= ab[i].a;
        } else ns.insert({ab[i].b, i});
    }

    while (true) {
        auto op1 = s.begin();
        auto op2i = sp.rbegin();
        auto op2j = ns.begin();

        ll delta;
        if (op2j == ns.end() || (op1 != s.end() && op1->first <= op2j->first - op2i->first)) {
            delta = op1->first;
            if (x < delta) break;

            int id = op1->second;
            ans[id] = 2;
            x -= delta;
            s.erase(op1), sp.erase({ab[id].a, id});
        } else if (op1 != s.end() && op2i != sp.rend() && op2i != sp.rend()
                   && op1->first >= op2j->first - op2i->first) {
            delta = op2j->first - op2i->first;
            if (x < delta) break;

            ans[op2i->second] = 0;
            ans[op2j->second] = 2;
            x -= delta;

            int id = op2i->second;
            sp.erase(*op2i), s.erase({ab[id].b - ab[id].a, id});
            ns.erase(op2j);

            ns.insert({ab[id].b, id});
        } else break;
    }

    answer();
}

L. LCG Manipulation

递推式为 xn≡axn−1+b(modp)x_n\equiv ax_{n-1}+b \pmod p，那么我们想找到一个通项公式，则不妨变形成

(xn−k)≡a(xn−1−k)(modp)xn≡axn−1−ak+k(modp) \begin{aligned} (x_n-k)&\equiv a(x_{n-1}-k) \pmod p\\ x_n&\equiv ax_{n-1}-ak+k \pmod p \end{aligned}

故

(1−a)k≡b(modp) (1-a)k\equiv b\pmod p

因为 a∈(0,p)a\in (0,p)，如果 1−a≡0(modp)1-a\equiv 0\pmod p，则 a=1a=1，此时数列可以算出通项公式 xn≡nb+x0(modp)x_n\equiv nb+x_0\pmod p. 所以有

v≡nb+s(modp)n≡(v−s)b−1(modp) \begin{aligned} v&\equiv nb+s\pmod p\\ n&\equiv (v-s)b^{-1} \pmod p \end{aligned}

否则若 a≠1a\ne 1，此时由于 pp 为素数，1−a1-a 必有逆元，故 k≡b(1−a)−1(modp)k\equiv b(1-a)^{-1}\pmod p. 所以我们也可以算出数列的通项公式：

xn−k≡an(x0−k)(modp)v−k≡an(s−k)(modp)an≡(v−s)(s−k)−1(modp) \begin{aligned} x_n-k&\equiv a^n(x_0-k)\pmod p\\ v-k&\equiv a^n(s-k) \pmod p\\ a^n&\equiv (v-s)(s-k)^{-1} \pmod p \end{aligned}

这里需要特判 s=ks=k 的情况

所以，令 t≡(v−s)(s−k)−1(modp)t\equiv (v-s)(s-k)^{-1} \pmod p，则原式等于

an≡t(modp) a^n\equiv t\pmod p

且 a⊥pa\perp p. 于是我们可以使用 Baby-Step Giant-Step 算法在 O(p)O(\sqrt{p}) 的时间内求解.

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
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using ll = long long;

int a, b, s, p, v;

int norm(ll x, ll c = p) { return (x % c + c) % c; }
int fpow(int b, int p, int m) {
    int res = 1;
    for (; p; p >>= 1, b = 1ll * b * b % m)
        if (p & 1) res = 1ll * res * b % m;
    return res;
}
int inv(int x) { return fpow(x, p - 2, p); }

int solve(int a, int b, int n) {
    std::unordered_map<int, int> umap;
    int S = std::ceil(std::sqrt(n * 1.0));

    int t = 1;
    for (int B = 0; B <= S; B++) {
        umap[1ll * b * t % p] = B;
        t = 1ll * t * a % p;
    }

    int fac = fpow(a, S, p);
    t = 1;
    int ans = (1ll << 31) - 1;
    for (int A = 0; A <= S; A++) {
        auto it = umap.find(t);
        if (it != umap.end()) {
            int val = norm(1ll * A * S - it->second, n - 1);
            ans = std::min(ans, val);
        }
        t = 1ll * t * fac % p;
    }
    return ans >= n ? -1 : ans;
}

void run() {
    std::cin >> a >> b >> s >> p >> v;
    if (a == 1) {
        std::cout << 1ll * norm(v - s) * inv(b) % p << "\n";
        return;
    }

    int k = 1ll * b * inv(p - a + 1) % p;
    if (s == k) {
        if (v == k) std::cout << "0\n";
        else std::cout << "IMPOSSIBLE\n";
        return;
    }
    int t = 1ll * norm(v - k) * inv(norm(s - k)) % p;

    int x = solve(a, t, p);
    if (x == -1) std::cout << "IMPOSSIBLE\n";
    else std::cout << x << "\n";
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0), std::cout.tie(0);

    int t;
    std::cin >> t;
    while (t--) run();
}
ICPC/APAC/2022
License

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。