Rockdu's Blog
“Where there is will, there is a way”
亲 您的浏览器不支持html5的audio标签
Toggle navigation
Rockdu's Blog
主页
数据结构
字符串算法
图论
数论、数学
动态规划
基础算法
[其它内容]
计算几何
科研笔记
归档
标签
2020ICPC·小米邀请赛第二场 J-Hamming Distance
? 解题记录 ?
? 数学 ?
2020-11-01 12:13:03
997
0
0
rockdu
? 解题记录 ?
? 数学 ?
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; } ```
上一篇:
洛谷P2765 魔术球问题
下一篇:
2020ICPC·小米邀请赛第二场 G-Shift and Reverse
0
赞
997 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
没有帐号? 立即注册