6.4 模拟赛

A 宝石

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

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

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

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

复杂度 O(mklogn)O(mk\log n)

B 字串

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

dp[u]=1+cpcdp[nxt[u][c]]dp[u] = 1 + \sum_{c} p_c dp[nxt[u][c]]

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

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

dp[u]=dp[fail]+cson[u](dp[son[u][c]]dp[son[fail][c]])dp[u] = dp[fail] + \sum_{c \in son[u]} (dp[son[u][c]] - dp[son[fail][c]])

考虑移一下项,有

dp[u]dp[fail]=cson[u](dp[son[u][c]]dp[son[fail][c]])dp[u] - dp[fail] = \sum_{c \in son[u]}(dp[son[u][c]] - dp[son[fail][c]])

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

g[u]=cson[u]g[son[u][c]]g[u] = \sum_{c \in son[u]} g[son[u][c]]

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

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

cson[rt]pcg[son[rt][c]]+1=0\sum_{c \in son[rt]} p_c g[son[rt][c]] + 1 = 0

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

C 数论

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

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

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

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

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

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

#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();
}


\