抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

七つの海

今日、海を見た。もう怖くない

博客

随笔

朋友

归档

关于

校队训练：个人训练 - 第 1 周

七海

题解

发布于：2020年5月26日

次浏览

因为摸鱼的原因，搞到现在才整理好总结…… 至少现在，尽量地把每次训练内容和成果进行总结吧。之后的个人训练就采取先随机题部分题解，后专题板子的顺序来讲解内容好了；希望人没事，希望一个月后我还活在校队里（

随机练习

随机练习题是 Codeforces 往届的一些比赛题目，都是 div2 的；用群内巨佬神犇的话说就是没有算法的算法题。

CF1236E Alice and the Unfair Game

1 个小球，n 个盒子，m 次操作；每次操作询问 a[i] 盒子里有没有小球，若有则输；为了赢，你在每一次操作之前可以将小球从当前位置移到相邻的盒子中，在所有询问结束后还可以移动一次；

现在规定小球开始位置为 x，结束位置为 y，不同的 (x, y) 为不同的状态；问所有可能使得你胜利的状态数。

数据范围：n, m ≤ 1e5

分析

显然，从某个点出发可以到达的终点构成了一个连续的区间；所以，问题转化成从起点出发最远可达的左右端点；显然找到某一个方向的端点应该尽可能的向该方向移动，但是当向某方向前进时，会因为当前位置冲突（将要移动的目标位置将会被询问）而停止一格；

这样停留之后，相当于它反方向一格的那个格子移动过来但是没有停，所以可以直接转移过来：统计 X[i] 表示向某方向行走的时候，因障碍止步的次数；这样转移方程就可以写成 X[i] = X[i±1] + 1；

实际的统计方法：可以倒过来统计；设我们现在要求从起点 i 开始向右到达的最远距离，向右走会因为障碍中断 X[i] 次，那么最远可以到达的距离就是 i + (1 + m) - X[i]；因为是倒过来统计，所有的障碍数组的初值是 0：当遇到了 a[i] 阻碍的时候，显然，我们要为 XR[ a[i] - i ] 增加一个障碍；根据上面的讨论，这个转移关系始终成立，所以只要按照上面的转移方程进行转移就可以了。

实现上有一些策略：可以开三倍数组考虑偏移，这样不仅解决了边界问题，且因为统计的时候并不会访问这些实际不存在的盒子，所以不会对答案造成什么影响。因为是逆推，所以也不需要考虑开始的障碍：等到考虑它们的时候，它们也会使用转移方程对于相关位置进行更新。

在统计的时候，因为数组使用了偏移，需要保证边界不超过实际存在的边界。

代码

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
#include <iostream>
#include <algorithm>

using namespace std;
using longs = long long;

const int N = 1e5 + 5;
const int off = 1e5;

int a[N], lb[3 * N], rb[3 * N];

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

    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; ++ i)
        cin >> a[i];
    if (n <= 1) cout << 0 << endl;
    else
    {
        for (int i = m; i >= 1; -- i)
        {
            rb[off + a[i] - i] = rb[off + a[i] - i - 1] + 1;
            lb[off + a[i] + i] = lb[off + a[i] + i + 1] + 1;
        }
        longs cnt = 0;
        for (int i = 1; i <= n; ++ i)
            cnt += min(n, i + (m + 1) - rb[off + i]) - max(1, i - (m + 1) + lb[off + i]) + 1;
        cout << cnt << endl;
    }

    return 0;
}

附录

这个题目如果在 Google 中查的话，还可以找到一种申必的权值线段树的做法。

CF1355F Guess Divisors Count

这是一个交互题：有一个正整数 X，你可以询问 Q，交互机器返回 gcd(Q, X)；要求在不超过 22 次询问之内，求出 X 的约数个数；只要你的猜测 a' 和实际答案满足下面两个关系的任一个就算正确：

  • \(|a - a'| \leq 7\)
  • \(\frac 1 2 \leq \frac a {a'} \leq 2\)

数字 X 不大于 1e9，你询问的数字 Q 不大于 1e18；

分析

首先，任何一个数可以按照下面的形式被唯一分解：

\[ x = p_1^{a_1}p_2^{a_2}...p_n^{a_n} \]

公式中，n 是这个数字的质因数数目，\(p_i\) 表示质因数，\(a_i\) 表示质因数的幂次，是一个正整数。显然，这样的一个数的约数数目可以表示为：

\[ \sigma_0(x) = Π_{i=1}^n (1 + a_i) \]

这也很容易证明，这样我们就可以想到询问的思路：

第一层：每次询问 \(Π p_i^{a_i} \leq 10^{18}\)，且 \(p_i^{a_i+1} \geq 10^9\)

这样的好处是一定可以询问出准确的约数个数——根据唯一分解定理；但是缺点就是不可能在22次之内询问结束；也就是说，仅仅凭借22次询问是不可能得到约数的准确值的。

第二层：考虑容错机制，压缩询问次数

既然不能做到准确的询问，那么就想办法减少询问的次数，省去不必要的询问（比如上面方法会导致大量的 1）。减少询问的思路显然是压缩对于每一个质数的幂次，让更多的素数可以压缩再一次询问中。

然后，显而易见地，我们可以找到的答案 out 一定会比真实的答案小：因为答案的误差只会来自于对部分情况的未考虑；所以，为了保证最优的状况，输出答案时可以按照 2out 输出，可以覆盖的真实答案的范围就扩展到了 [out, 4out]，更有利。

接下来，观察唯一分解定理，上面得到的 4 倍误差可以被表示为真实答案的唯一分解式中的 (1 + 1)(1 + 1) 或者 (1 + 3)；也就是说，允许两个幂次为 1 的质数没有被考虑，或者是 1 个幂次不超过 3 的质数没有被考虑；前者一定处于 \([\sqrt{10^9}, 10^9]\) 的范围之内，且最多出现一个；后者一定出现在 \([ \sqrt[3]{10^9}, \sqrt{10^9} ]\) 区间内，且最多出现一个；

还有没有什么可以优化的地方呢？假设我们从 2 开始尝试质数，尝试到了第 n 个质数，已经确定的约数乘积为 w 的时候：当满足 \(wp_{n+1}p_{n+2}p_{n+3} \geq 10^9\) 时，就已经满足了容错规定的情况了；此外，当找到的答案比较小，或者确定答案不会很大的时候（比如没有小因数），可以直接输出 8，当实际答案在 [1, 15] 范围内都可通过。

第三层：实现

虽然讲踢人提供了这些思路，但是也没说一个具体的实现过程；所以最后我就直接去看的题解了。

代码

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 <iostream>
#include <queue>
#include <algorithm>
#include <vector>

#define ask cout<<"? "
#define chk cout<<"! "

using namespace std;
using longs = long long;

template <int n> const int *EulerSieve()
{
    static int prime[n + 5];
    bool vis[n + 5] {false};
    int &cnt = prime[0] = 0;
    for (int i = 2; i <= n; ++ i)
    {
        if (!vis[i]) prime[++ cnt] = i;
        for (int j = 1; j <= cnt && (longs)i * prime[j] <= n; ++ j)
        {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
    return prime;
}

struct triple
{
    int p, a;
    longs v;

    triple(int p, int a, longs v) : p(p), a(a), v(v) {}

    bool operator<(const triple &rhs) const
    {
        if (a == rhs.a) return v > rhs.v;
        else return a < rhs.a;
    }
};

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

    int t;
    longs response, ans;
    auto p = EulerSieve<31623>();
    auto cnt = p[0];
    cin >> t;
    while (t --)
    {
        priority_queue<triple> pq;
        for (int i = 1; i <= cnt; ++ i)
            pq.push({p[i], 1, p[i]});
        vector<triple> used; ans = 1;
        for (int i = 0; i < 22; ++ i)
        {
            used.clear();
            longs query = 1;
            while (!pq.empty())
            {
                auto &front = pq.top();
                if ((double)query * front.v > 1e18) break;
                used.push_back(front);
                query *= front.v; pq.pop();
            }
            ask << query << endl; cin >> response;
            for (auto &ii : used) if (response % ii.v == 0)
                {
                    ans = (ans / ii.a) * ++ ii.a;
                    ii.v *= ii.p; pq.push(ii);
                }
        }
        chk << ans * 2 << endl;
    }

    return 0;
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://shiraha.cn/2020/icpc-team-personal-training-1/

更新于：2020年5月26日

算法

ACM

校队

评论