差别

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

--- 2020-2021:teams:legal_string:jxm2001:other:错题集_2 [2020/08/02 15:54]
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)$。
 注意每次枚举完成可以给整棵树打上子树还原标记，不能暴力重建树，否则时间复杂度过高。
@@ 行 422: / 行 424: @@
 </hidden>
+===== 4、African sort =====
+[[https://ac.nowcoder.com/acm/contest/5671/A|链接]]
+==== 题意 ====
+给定排列 $p$，每次可以选一个下标集合等概率打乱包含的数并花费集合大小的代价。
+要求将 $p$ 转化为 $1,2\cdots n$，求最优策略下最小代价的期望。
+==== 题解 ====
+将 $p$ 转化为 $1,2\cdots n$ 等价于该置换只存在长度为 $1$ 的循环。
+有引理 $1$：随机打乱一个长度为 $n$ 的循环，则循环的每个元素将等概率出现在长度为 $1\sim n$ 的循环中。
+引理 $2$：每次选择一个完整的循环将其全部打乱一定是最佳选择。
+设将一个长度为 $n$ 的循环打乱成 $n$ 长度为 $1$ 的循环的最小期望代价为 $f(n)$。
+单独考虑每个点的期望代价，每个点在循环长度为 $i$ 的代价由 $i$ 个点均摊。
+最后总代价为单个点代价的 $n$ 倍，得到$f(n)=n\sum_{i=1}^n \frac{\frac {f(i)}{i}}n+n=\sum_{i=1}^n\frac {f(i)}i+n(n\gt 1)$。
+转化，得到 $f(n)=\frac {n(f(n-1)+1)}{n-1}(n\gt 2)$，边界条件 $f(2)=4,f(1)=0$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5,Mod=998244353;
+int a[MAXN],f[MAXN],inv[MAXN];
+bool vis[MAXN];
+void get_inv(){
+	inv[1]=1;
+	_for(i,2,MAXN)
+	inv[i]=1LL*(Mod-Mod/i)*inv[Mod%i]%Mod;
+}
+void get_f(){
+	f[1]=0,f[2]=4;
+	_for(i,3,MAXN)
+	f[i]=1LL*i*inv[i-1]%Mod*(f[i-1]+1)%Mod;
+}
+int main()
+{
+	get_inv();
+	get_f();
+	int n=read_int(),m=read_int();
+	while(m--){
+		int ans=0;
+		_rep(i,1,n)a[i]=read_int(),vis[i]=false;
+		_rep(i,1,n){
+			if(!vis[i]){
+				int cnt=0,pos=i;
+				while(!vis[pos]){
+					vis[pos]=true,cnt++;
+					pos=a[pos];
+				}
+				ans=(ans+f[cnt])%Mod;
+			}
+		}
+		enter(ans);
+	}
+	return 0;
+}
+</code>
+</hidden>
+===== 5、Hacker Cups and Balls =====
+[[https://codeforces.com/gym/101234/problem/A|链接]]
+==== 题意 ====
+给定一个 $1\sim n$ 的排列，一共 $m$ 个操作。
+每个操作为选择一个区间，将其按升序或降序排序。
+问经过所有操作后排列中间的数为多少，保证 $n$ 为奇数。
+==== 题解 ====
+于是考虑二分答案 $v$，答案的意义是验证中间的数是否不超过 $v$，显然这样的结果具有单调性。
+对序列中的数，如果该数大于 $v$，则置为 $1$，否则置为 $0$。
+于是区间排序操作可以使用线段树处理，最后查询中间的数的数值是否为 $0$ 即可，时间复杂度 $O(n\log^2 n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5;
+int a[MAXN],lef[MAXN<<2],rig[MAXN<<2],sum[MAXN<<2],lazy[MAXN<<2];
+void build(int k,int L,int R,int v){
+	lef[k]=L,rig[k]=R;
+	lazy[k]=0;
+	int M=L+R>>1;
+	if(L==R)
+	return sum[k]=(a[M]>v),void();
+	build(k<<1,L,M,v);
+	build(k<<1|1,M+1,R,v);
+	sum[k]=sum[k<<1]+sum[k<<1|1];
+}
+void push_down(int k){
+	if(lazy[k]){
+		lazy[k<<1]=lazy[k<<1|1]=lazy[k];
+		sum[k<<1]=(rig[k<<1]-lef[k<<1]+1)*(lazy[k]-1);
+		sum[k<<1|1]=(rig[k<<1|1]-lef[k<<1|1]+1)*(lazy[k]-1);
+		lazy[k]=0;
+	}
+}
+int query(int k,int L,int R){
+	if(L<=lef[k]&&rig[k]<=R)
+	return sum[k];
+	push_down(k);
+	int mid=lef[k]+rig[k]>>1;
+	if(mid>=R)return query(k<<1,L,R);
+	if(mid<L)return query(k<<1|1,L,R);
+	return query(k<<1,L,R)+query(k<<1|1,L,R);
+}
+void update(int k,int L,int R,int v){
+	if(L<=lef[k]&&rig[k]<=R){
+		sum[k]=(rig[k]-lef[k]+1)*v;
+		lazy[k]=v+1;
+		return;
+	}
+	push_down(k);
+	int mid=lef[k]+rig[k]>>1;
+	if(mid>=L)update(k<<1,L,R,v);
+	if(mid<R)update(k<<1|1,L,R,v);
+	sum[k]=sum[k<<1]+sum[k<<1|1];
+}
+int n,m,ql[MAXN],qr[MAXN],qv[MAXN];
+bool check(int v){
+	build(1,1,n,v);
+	int cnt0,cnt1;
+	_for(i,0,m){
+		cnt1=query(1,ql[i],qr[i]);
+		cnt0=qr[i]-ql[i]+1-cnt1;
+		if(qv[i]==0){
+			if(cnt0)update(1,ql[i],ql[i]+cnt0-1,0);
+			if(cnt1)update(1,ql[i]+cnt0,qr[i],1);
+		}
+		else{
+			if(cnt1)update(1,ql[i],ql[i]+cnt1-1,1);
+			if(cnt0)update(1,ql[i]+cnt1,qr[i],0);
+		}
+	}
+	return !query(1,(n+1)/2,(n+1)/2);
+}
+int main()
+{
+	n=read_int(),m=read_int();
+	_rep(i,1,n)a[i]=read_int();
+	_for(i,0,m){
+		ql[i]=read_int(),qr[i]=read_int();
+		if(ql[i]>qr[i]){
+			qv[i]=1;
+			swap(ql[i],qr[i]);
+		}
+	}
+	int lef=1,rig=n,mid,ans;
+	while(lef<=rig){
+		mid=lef+rig>>1;
+		if(check(mid)){
+			ans=mid;
+			rig=mid-1;
+		}
+		else
+		lef=mid+1;
+	}
+	enter(ans);
+	return 0;
+}
+</code>
+</hidden>
+===== 6、Zero Game =====
+[[https://codeforces.com/gym/101234/problem/J|链接]]
+==== 题意 ====
+给定一个长度为 $n$ 的 $01$ 串，$q$ 个询问。
+每次询问允许进行 $k_i$ 次操作，每次操作可以任意移动一个字符，问 $k_i$ 次操作后的最长的连续 $0$ 串的长度。
+==== 题解 ====
+考虑贪心，不难发现最佳答案一定为选择一段区间，移除区间的所有 $1$，如果还有剩余的操作此数，则将区间外的 $0$ 移入区间。
+记 $\text{pre}_i$ 表示前 $i$ 个字母中有多少个 $1$，$a_i=i-2\text{pre}_i$。
+对一个合法的区间 $[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-(\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

用户工具

站点工具

差别

页面工具