6.4 模拟赛

A 宝石

开场看错题 1.5h ,一直以为不能拿连续 $k$ 个宝石,然后发现 15pts 都不会,直接导致 T3 暴力都没打。。

我们考虑找出第一个位置,使得这个位置的颜色在之前出现过了,那么如果想继续往后选择,就必须把这个位置丢掉。我们一直重复找这种位置的过程,知道找到了第 $k+1$ 个,此时我们就只会在前面的东西种选择 $k$ 个扔掉。具体来说,对于每个出现了大于等于 $2$ 次的颜色我们只会保留最大的。

由于 $k$ 很小,我们可以考虑暴力做上面那个过程。每次之需要找到后面第一个重复出现的颜色即可。具体来说,我们可以记一个 $nxt_i$ 表示下一个与 $i$ 颜色相同的位置,然后我们就只需要找到 $s\sim n$ 中 $nxt_i$ 最小的位置即可。这个可以用线段树来维护 $nxt$ 的区间最小值。

于是我们暴力跳,暴力维护所有出现大于等于 $2$ 次的元素即可。

复杂度 $O(mk\log n)$ 。

B 字串

考虑一种最为暴力的过程,我们建出 ACAM ,然后设 $dp[u]$ 为 $u$ 出发期望走多少次会停止,然后转移就是

于是我们暴力高消,就有了一个 $O(n^3m^3)$ 的优秀做法。

收到 $n = 1$ 的启发,我们考虑把后面的 $\sum$ 用 $dp[fail]$ 代替掉,于是有:

考虑移一下项,有

于是设 $g[u] = dp[u] - dp[fail]$ ,那么有

于是我们考虑对每个叶子设一个元,然后每个点的 $g$ 都可以用 $x_{1 \dots n}$ 来表示。当然,根是没有 $g$ 的定义的。

然后我们考虑怎么列方程。由于对于所有叶子,有 $dp[u] = 0$ ,也就是说有 $g[u] + g[fail[u]] + g[fail[fail[u]]] + \cdots + dp[rt] = 0$ ,于是如果我们把 $dp[rt]$ 设成一个元,对每个叶子都可以列出一个方程,就有了 $n+1$ 个元和 $n$ 个方程。我们再考虑根的 $dp$ 值,有 $dp[rt] = \sum_{c\in son[rt]} p_c(g[son[rt][c]] + dp[rt]) + 1$ ,因此有

于是就有了 $n + 1$ 个方程和 $n + 1$ 个元,可以解决这个问题。

C 数论

乱搞题,但是有正经做法。

期望情况下,可以看出这个玩意需要进行的操作次数是 $O(len)$ 的。

我们考虑单独拿出最后 $B$ 位。首先可以发现,我们可以不考虑除以 $2$ 操作,直接把每次 $+1$ 变成加 lowbit ,最后加上末尾零的个数即可。于是我们考虑进行 $O(B)$ 次操作把最后 $B$ 位清零的过程(因为每次 $\times 3 + \text{lowbit}$ 一定会使得末尾零增多)。我们可以把 $\times 3$ 的过程分开来看,也就是说后面 $B$ 位直接乘三再加上 lowbit ,前面的位打一个标记表示乘三了。直到当你发现最后 $B$ 位全是 $0$ 的时候,就丢掉最后 $B$ 位,然后给前面乘上之前打的标记,再把最后 $24$ 位进位的东西加上去。

考虑这样做的复杂度是啥,一共要进行 $O(\frac{len}{B})$ 次这样的操作,然后每次的复杂度都是 $O(\frac{len}{B})$ ,因此总复杂度是 $O(\frac{len^2}{B^2})$ 。我们来优秀取一下块大小。为了不让最后一个块的值炸出 long long ,可以发现最后一个块一共会乘上 $3^B$ ,而最开始它是 $2^B$ 的,因此最后一个块的大小会变成 $6^B$ ,可以发现前面的每个位乘完后达到的最大值也是 $6^B$ ,因此取 $B = 24$ 就不会炸 long long 了。这东西由于常数小跑的飞快。

实际上是有有理有据的做法的。我们可以把前面说的这个乱搞做法扩展到类似分治 FFT 的过程,本质上就是把 B 取到 $\frac n 2$ 来分治做。复杂度可以做到 $O(\frac{n \log^2n}{\omega})$ 。

实际上我这乱搞极限数据只跑了 0.3s

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 300006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
#define lb( x ) ( ( x ) & -( x ) )
int n , len;
char ch[MAXN];

ll A[MAXN] , lz;

void solve() {
scanf("%s",ch + 1);
len = strlen( ch + 1 );
int cur = 0 , cw = 0;
per( i , len , 1 ) {
if( cw == 24 ) cw = 0 , ++ cur;
A[cur] |= ( ch[i] - '0' << cw );
++ cw;
}
cw = 0;
int opt = 0;
int all = ( 1 << 24 ) - 1;
for( int k = cw ; k <= cur ; ++ k ) {
lz = 1;
while( A[k] & all ) {
if( k == cur && __builtin_popcount( A[k] ) == 1 ) break;
++opt , lz = lz * 3;
A[k] = A[k] * 3 + lb( A[k] );
}
rep( t , k + 1 , cur ) {
A[t] = A[t] * lz + ( A[t - 1] >> 24 );
A[t - 1] &= all;
}
if( A[cur] >> 24 ) ++ cur , A[cur] = A[cur - 1] >> 24 , A[cur - 1] &= all;
if( A[cur] >> 24 ) ++ cur , A[cur] = A[cur - 1] >> 24 , A[cur - 1] &= all;
}
opt += 24 * cur + __builtin_ctz( A[cur] );
cout << opt << endl;
}

signed main() {
freopen("number.in","r",stdin) , freopen("number.out","w",stdout);
// int T;cin >> T;while( T-- ) solve();
solve();
}


文章作者: yijan
文章链接: https://yijan.co/2021/06/05/64-mo-ni-sai/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog