抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

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

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

随机练习

随机练习题是 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’ 和实际答案满足下面两个关系的任一个就算正确:

  • aa7|a - a'| \leq 7
  • 12aa2\frac 1 2 \leq \frac a {a'} \leq 2

数字 X 不大于 1e9,你询问的数字 Q 不大于 1e18;

分析

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

x=p1a1p2a2...pnanx = p_1^{a_1}p_2^{a_2}...p_n^{a_n}

公式中,n 是这个数字的质因数数目,pip_i 表示质因数,aia_i 表示质因数的幂次,是一个正整数。显然,这样的一个数的约数数目可以表示为:

σ0(x)=Πi=1n(1+ai)\sigma_0(x) = Π_{i=1}^n (1 + a_i)

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

第一层:每次询问Πpiai1018Π p_i^{a_i} \leq 10^{18},且piai+1109p_i^{a_i+1} \geq 10^9

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

第二层:考虑容错机制,压缩询问次数

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

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

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

还有没有什么可以优化的地方呢?假设我们从 2 开始尝试质数,尝试到了第 n 个质数,已经确定的约数乘积为 w 的时候:当满足wpn+1pn+2pn+3109wp_{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;
}

评论