差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:other:错题集_2 [2020/08/06 21:22]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:other:错题集_2 [2020/08/09 00:16] (当前版本)
jxm2001
@@ 行 23: / 行 23: @@
 考虑倒序枚举每个最小距离，求出该最小距离至少需要的关键点个数，然后更新该关键点个数对应的答案。
-总操作数为 $O(\sum_{i=1}^{n-1} \frac ni)=O(n\log n)$，删除子树和查询祖先操作时间复杂度为 $O(\log n)$，于是总时间复杂度为 $O\left(n\log^2 n\right)$。
+总操作数为 $O(\sum_{i=1}^{n-1} \frac ni)=O(n\log n)$，删除子树和查询祖先操作时间复杂度为 $O(\log n)$。
+于是总时间复杂度为 $O\left(n\log^2 n\right)$。
 注意每次枚举完成可以给整棵树打上子树还原标记，不能暴力重建树，否则时间复杂度过高。
@@ 行 610: / 行 612: @@
 考虑贪心，不难发现最佳答案一定为选择一段区间，移除区间的所有 $1$，如果还有剩余的操作此数，则将区间外的 $0$ 移入区间。
-记 $pre_i$ 表示前 $i$ 个字母中有多少个 $1$，$a_i=i-2pre_i$。
+记 $\text{pre}_i$ 表示前 $i$ 个字母中有多少个 $1$，$a_i=i-2\text{pre}_i$。
-对一个合法的区间 $[l,r]$，区间中原有 $0$ 的个数为 $r-l+1-(pre_r-pre_{l-1})$，可以额外移入的 $0$ 的个数为 $k-(pre_r-pre_{l-1})$。
+对一个合法的区间 $[l,r]$，区间中原有 $0$ 的个数为 $r-l+1-(\text{pre}_r-\text{pre}_{l-1})$，可以额外移入的 $0$ 的个数为 $k-(\text{pre}_r-\text{pre}_{l-1})$。
-于是该区间的答案为 $r-l+1-(pre_r-pre_{l-1})+k-(pre_r-pre_{l-1})=k+(r-pre_r)-(l-1-pre_{l-1})=k+a_r-a_{l-1}$。
+于是该区间的答案为 $r-l+1-(\text{pre}_r-\text{pre}_{l-1})+k-(\text{pre}_r-\text{pre}_{l-1})=k+(r-\text{pre}_r)-(l-1-\text{pre}_{l-1})=k+a_r-a_{l-1}$。
+考虑对每个右端点 $r$，寻找满足 $\text{pre}_r-\text{pre}_i\le k$ 的最小的 $i$。
+由于 $\text{pre}_{i}$ 递增，于是可以用单调队列维护维护递增的 $a_i$ 序列。对每个右端点，枚举后加入队列即可。
+时间复杂度 $O(nq)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e6+5;
+char buf[MAXN];
+int pre[MAXN],a[MAXN],que[MAXN];
+int main()
+{
+	scanf("%s",buf+1);
+	int n=strlen(buf+1),m=read_int();
+	_rep(i,1,n){
+		pre[i]=pre[i-1]+buf[i]-'0';
+		a[i]=i-2*pre[i];
+	}
+	while(m--){
+		int k=read_int(),head=0,tail=0,ans=0;
+		que[0]=0;
+		_rep(i,1,n){
+			while(head<=tail&&a[que[tail]]>=a[i])tail--;
+			que[++tail]=i;
+			while(head<=tail&&pre[que[tail]]-pre[que[head]]>k)head++;
+			ans=max(ans,k+a[que[tail]]-a[que[head]]);
+		}
+		ans=min(ans,n-pre[n]);
+		enter(ans);
+	}
+	return 0;
+}
+</code>
+</hidden>
+===== 7、Enigmatic Partition =====
+[[https://ac.nowcoder.com/acm/contest/5673/E|链接]]
+==== 题意 ====
+定义 $f(n)$ 等于满足下列条件的排列数：
+  - $a_1+a_2+\cdots a_k=n$
+  - $a_{i+1}-1\le a_i\le a_{i+1}$
+  - $a_k=a_1+2$
+求 $\sum_{i=l}^rf(i)$。
+==== 题解一 ====
+考虑枚举 $a_1$，当 $a_1\lt k$ 时，考虑 $\text{dp}$。$\text{dp}(s,i,pos)$ 表示当前和为 $s$，同时 $a_1=i$，并且已经选择了 $i\sim i+pos$ 的数的方案数。
+$\text{dp}$ 状态数为 $3nm$，于是时间复杂度为 $O(nm)$。
+当 $a_1\le k$ 时，记 $a_1=\text{lef},a_1+1=\text{mid},a_1+2=\text{rig}$，$\text{lef}$ 的个数为 $l$，$\text{mid}$ 的个数为 $m$，$\text{rig}$ 的个数为 $r$。
+于是考虑先将 $\text{lef},\text{rig}$ 合并为 $\text{mid}$，然后如果 $l\gt r$，则枚举 $l$ 与 $m$，然后再考虑拆分 $m$ 的方案，有 $\lfloor\frac {m-1}2\rfloor$ 种。
+同样如果 $l\le r$，则枚举 $r$ 与 $m$，然后再考虑拆分 $m$ 的方案，有 $\lfloor\frac {m-1}2\rfloor$ 种。
+时间复杂度 $O\left(\sum_{i=m}^n (\frac ni)^2\right)$，可以近似为 $O\left(\frac {n^2}m\right)$。
+于是总时间复杂度 $O\left(nm+\frac {n^2}m\right)$。取 $m=O(\sqrt n)$，时间复杂度为 $O(n\sqrt n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5,block=100;
+int dp[MAXN][block][3];
+LL ans[MAXN];
+int main()
+{
+	_for(i,1,block)
+	dp[i][i][0]=1;
+	_for(i,1,MAXN)
+	_for(j,1,block){
+		if(i+j<MAXN)
+		dp[i+j][j][0]+=dp[i][j][0];
+		if(i+j+1<MAXN)
+		dp[i+j+1][j][1]+=dp[i][j][1]+dp[i][j][0];
+		if(i+j+2<MAXN)
+		dp[i+j+2][j][2]+=dp[i][j][2]+dp[i][j][1];
+	}
+	_for(i,1,MAXN)
+	_for(j,1,block)
+	ans[i]+=dp[i][j][2];
+	_for(lef,block,MAXN){
+		int mid=lef+1,rig=lef+2;
+		for(int cnt_l=1;cnt_l*lef<MAXN;cnt_l++)
+		for(int cnt_m=3;cnt_l*lef+cnt_m*mid<MAXN;cnt_m++)
+		ans[cnt_l*lef+cnt_m*mid]+=(cnt_m-1)/2;
+		for(int cnt_r=0;cnt_r*rig<MAXN;cnt_r++)
+		for(int cnt_m=3;cnt_r*rig+cnt_m*mid<MAXN;cnt_m++)
+		ans[cnt_r*rig+cnt_m*mid]+=(cnt_m-1)/2;
+	}
+	_for(i,1,MAXN)
+	ans[i]+=ans[i-1];
+	int t=read_int(),kase=0;
+	while(t--){
+		int l=read_int(),r=read_int();
+		printf("Case #%d: %lld\n",++kase,ans[r]-ans[l-1]);
+	}
+	return 0;
+}
+</code>
+</hidden>
+==== 题解二 ====
+考虑差分维护，观察 $a_1=1,k=7$ 的表格。
+^  n  ^  10  ^  11  ^  12  ^  13  ^  14  ^   15  ^   16  ^   17  ^   18  ^   19  ^  20  ^  21  ^
+|5个3|    |    |    |    |    |    |    |    |  1233333  |    |    |    |
+|4个3|    |    |    |    |    |    |  1123333  |  1223333  |    |    |    |    |
+|3个3|    |    |    |    |  1112333  |  1122333  |  1222333  |    |    |    |    |    |
+|2个3|    |    |  1111233  |  1112233  |  1122233  |  1222233  |    |    |    |    |    |    |
+|1个3|  1111123  |  1111223  |  1112223  |  1122223  |  1222223  |    |    |    |    |    |    |    |
+|num|  1  |  1  |  2  |  2  |  3  |  2  |  2  |  1  |  1  |  0  |  0  |  0  |
+|一阶差分|  1  |  0  |  1  |  0  |  1  |  -1  |  0  |  -1  |  0  |  -1  |  0  |  0  |
+|二阶隔项差分|  1  |  0  |  0  |  0  |  0  |  -1  |  -1  |  0  |  0  |  0  |  0  |  1  |
+|对应位置|  $a_1k+3$  |  0  |  0  |  0  |  0  |  $(a_1+1)k+1$  |  $(a_1+1)k+2$  |  0  |  0  |  0  |  0  |  $(a_1+2)k$  |
+于是考虑枚举 $a_1,k$ 即可，时间复杂度 $O(n\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5;
+LL sum[MAXN];
+int main()
+{
+	_for(i,1,MAXN)
+	for(int k=3;i*k<MAXN;k++){
+		if(i*k+3<MAXN)sum[i*k+3]++;
+		if((i+1)*k+1<MAXN)sum[(i+1)*k+1]--;
+		if((i+1)*k+2<MAXN)sum[(i+1)*k+2]--;
+		if((i+2)*k<MAXN)sum[(i+2)*k]++;
+	}
+	_for(i,2,MAXN)//二阶隔项差分还原一阶差分
+	sum[i]+=sum[i-2];
+	_for(i,1,MAXN)//一阶差分还原原序列
+	sum[i]+=sum[i-1];
+	_for(i,1,MAXN)//前缀和
+	sum[i]+=sum[i-1];
+	int t=read_int(),kase=0;
+	while(t--){
+		int l=read_int(),r=read_int();
+		printf("Case #%d: %lld\n",++kase,sum[r]-sum[l-1]);
+	}
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具