差别

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

--- 2020-2021:teams:legal_string:jxm2001:other:错题集_2 [2020/08/06 21:32]
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)$。
 注意每次枚举完成可以给整棵树打上子树还原标记，不能暴力重建树，否则时间复杂度过高。
@@ 行 646: / 行 648: @@
 		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;

CVBB ACM Team

用户工具

站点工具

差别

页面工具