2020ICPC·小米邀请赛第二场 J-Hamming Distance

https://ac.nowcoder.com/acm/contest/7502/J

#### 题目大意：
定义串
$$S^1=[1]\\
S^m=S^{m-1}+[m]+S^{m-1}$$
其中$'+'$表示连接
给定数组$\{a_n\}$和$m$求出：
1、S^m所有长度为$n$子串与$\{a_n\}$的编辑距离之和
2、S^m所有长度为$n$子串与$\{a_n\}$的最小编辑距离
*编辑距离即修改多少字符可以变成另一个串
多组数据
$1\le m\le 10^5,1\le n\le min(|S^m|,10^5),1\le a_i\le m,\Sigma n\le 2\times 10^6$

#### 题外话：
这题细节有亿点，比赛现场大概写加调了一个半小时，最后还剩8分钟的时候过了，惊险又刺激(x)。

#### 题解：
#### 第一小问：
第一小问比较简单。
我们可以算"匹配个数"，总长减去匹配个数就是编辑距离
首先$|S^m|=2^m-1$
同时记$a_i$在$S^m$中$[l,r]$的出现次数为$C[l,r]$
考虑对每一个$a_i$统计贡献，考虑$a_i$能匹配哪些位置，那么只要对每个$a_i$算出在$C[i,2^m-n+i]$的区间内出现的次数，加起来就行了。

结论1：$C[1,|S^m|]=2^{m-a_i}$
可以通过归纳法简单证明

结论2：$C[1,n]=\lfloor{\frac{n}{2^{a_i}}}\rfloor + [n \ mod \ l \ge 2^{a_i-1}]$
不难发现$a_i$总是在$S^m_{2^{a_i-1}}$第一次出现，随后间隔$S^m_{2^{a_i}}$出现，结论2容易证明

结论3：$S^m$为回文串
显然

那么我们用总的减去两边就得到中间了，可以得知：
结论4：$C[i,2^m-n+i]=C[1,2^m-1]-C[1,i]-C[1,n-i+1]$

由结论4，我们可以$O(n)$计算出匹配个数之和，只需要用总数减去这个答案就得到编辑距离之和。

#### 第二小问：
第二小问就比较复杂
同样的，我们算相同的个数——即匹配数最大即可
首先我们考虑，如果$|S^m|$长度非常短，要如何算出最大匹配个数，并且复杂度在$O(|S^m|n)$的暴力以下。
容易发现性质：$S^m$中的元素只有$m$种，换句话说，元素个数为$log|S^m|$级别。
考虑对每种元素分别统计贡献
对一种元素$x$，我们知道它是间隔$2^{x}$出现一次，那么可以对原数组处理，计算所有${mod\ 2^{x}}$相等的位置上一共有多少个$x$，简单推一下公式就可以计算出每一个长度为$n$的子串匹配了多少个$x$
我们对$m$个$x$都做一遍这样的处理，就得到每一个长度为$n$子串的匹配数
复杂度为$mn\sim nlogn$

发现$S^m$一定可以表示为$S^t+[c_1]+S^t+[c_2]+...+[c_n]+S^t$的形式$(t\in [1,m),t < c_i \leq m)$
令$t=2^{\lceil logn\rceil}$，发现$\{a_i\}$只会跨过一个$[c_i]$，那么我们只需要对$S^t+[c_i]+S^t$处理出匹配数就可以了，用上文提到的方法，再特判一下跨过$[c_i]$的部分，就可以计算出匹配数。
总复杂度$O(nlogn)$
```
#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 5;
const int mod = 1e9 + 7;
int n, M, N;
int sm[maxn], a[maxn], mch[maxn];
int cnt[maxn], mxans, cntans, mx2p;
int mul(int a, int b) {
	return 1ll * a * b % mod;
}
int fpow(int x, int a) {
	int ans = 1;
	while(a) {
		if(a & 1) ans = mul(ans, x);
		a >>= 1, x = mul(x, x);
	}
	return ans;
}
int dec(int a, int b, int p) {
	return ((a % p) - (b % p) + p) % p;
} 
void Add(int &x, int a) {
	x = (x % mod + a % mod) % mod;
}
void GetSm(int m) {
	int len = (1 << m) - 1;
	for(int i = 1, l = 2; l <= (len * 2); ++i, l <<= 1) 
		for(int p = l >> 1; p <= len; p += l) {
			sm[p] = i;
		}
	for(int i = 1; i <= len; ++i)
		printf("%d ", sm[i]);
	putchar('\n');
}
void GetMch(int m) {
	int len = (1 << m) - 1;
	N = len * 2 + 1;
	for(int i = 1, l = 2; l <= N; ++i, l <<= 1) {
		for(int p = 1; p <= n; ++p)
			if(a[p] == i) ++cnt[p % l];
		for(int p = 1; p <= N - n + 1; ++p) {
			//if((M == m) && p > len - n + 1)
				//continue;
			mch[p] += cnt[dec(((l >> 1) + 1) % l, p % l, l)];
		}
		for(int p = 0; p < l; ++p)
			cnt[p] = 0;
	}
	for(int p = len - n + 2; p <= len + 1; ++p)
		mch[p] += (a[len - p + 2] <= M) && (a[len - p + 2] > m);
	//for(int i = 1; i <= N; ++i)
	//	printf("%d ", mch[i]);
	//putchar('\n');
}
int QF(int n, int a) {
	if(a > mx2p + 1) return 0;
	int l = 1 << a;
	return n / l + (n % l >= l / 2);
}
int main() {
	//mx2p = 100000;
	//cerr << QF(5, 2);
	//freopen("test.in", "r", stdin);
	while(~scanf("%d%d", &n, &M)) {
		cntans = mxans = 0;
		for(int i = 1; i <= n; ++i)
			scanf("%d", &a[i]);
		int l = 1;
		mx2p = 0;
		while(l < n) l <<= 1, ++mx2p;
		//GetSm(M);
		GetMch(mx2p);
		for(int i = 1; i <= N; ++i)
			mxans = max(mxans, mch[i]), mch[i] = 0;
		for(int i = 1; i <= n; ++i) {
			Add(cntans, fpow(2, M - a[i]));
			cntans = dec(cntans, QF(i - 1, a[i]), mod);
			cntans = dec(cntans, QF(n - i, a[i]), mod);
		}
		int tot = mul(dec(dec(fpow(2, M), 1, mod), n - 1, mod), n);
		printf("%d %d\n", n - mxans, dec(tot, cntans, mod));
		for(int i = 1; i <= n; ++i)
			a[i] = 0;
	}
	return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链