因为摸鱼的原因，搞到现在才整理好总结…… 至少现在，尽量地把每次训练内容和成果进行总结吧。之后的个人训练就采取先随机题部分题解，后专题板子的顺序来讲解内容好了；希望人没事，希望一个月后我还活在校队里（
随机练习
随机练习题是 Codeforces 往届的一些比赛题目，都是 div2 的；用群内巨佬神犇的话说就是没有算法的算法题。
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 中查的话，还可以找到一种申必的权值线段树的做法。
这是一个交互题：有一个正整数 X，你可以询问 Q，交互机器返回 gcd(Q, X)；要求在不超过 22 次询问之内，求出 X 的约数个数；只要你的猜测 a’ 和实际答案满足下面两个关系的任一个就算正确：
- ∣a−a′∣≤7
- 21≤a′a≤2
数字 X 不大于 1e9，你询问的数字 Q 不大于 1e18；
分析
首先，任何一个数可以按照下面的形式被唯一分解：
x=p1a1p2a2...pnan
公式中，n 是这个数字的质因数数目，pi 表示质因数，ai 表示质因数的幂次，是一个正整数。显然，这样的一个数的约数数目可以表示为：
σ0(x)=Πi=1n(1+ai)
这也很容易证明，这样我们就可以想到询问的思路：
第一层：每次询问Πpiai≤1018，且piai+1≥109
这样的好处是一定可以询问出准确的约数个数——根据唯一分解定理；但是缺点就是不可能在22次之内询问结束；也就是说，仅仅凭借22次询问是不可能得到约数的准确值的。
第二层：考虑容错机制，压缩询问次数
既然不能做到准确的询问，那么就想办法减少询问的次数，省去不必要的询问（比如上面方法会导致大量的 1）。减少询问的思路显然是压缩对于每一个质数的幂次，让更多的素数可以压缩再一次询问中。
然后，显而易见地，我们可以找到的答案 out 一定会比真实的答案小：因为答案的误差只会来自于对部分情况的未考虑；所以，为了保证最优的状况，输出答案时可以按照 2out 输出，可以覆盖的真实答案的范围就扩展到了 [out, 4out]，更有利。
接下来，观察唯一分解定理，上面得到的 4 倍误差可以被表示为真实答案的唯一分解式中的 (1 + 1)(1 + 1) 或者 (1 + 3)；也就是说，允许两个幂次为 1 的质数没有被考虑，或者是 1 个幂次不超过 3 的质数没有被考虑；前者一定处于[109,109] 的范围之内，且最多出现一个；后者一定出现在[3109,109] 区间内，且最多出现一个；
还有没有什么可以优化的地方呢？假设我们从 2 开始尝试质数，尝试到了第 n 个质数，已经确定的约数乘积为 w 的时候：当满足wpn+1pn+2pn+3≥109 时，就已经满足了容错规定的情况了；此外，当找到的答案比较小，或者确定答案不会很大的时候（比如没有小因数），可以直接输出 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;
}
|
