差别

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

--- 2020-2021:teams:legal_string:jxm2001:other:错题集_3 [2020/08/17 10:04]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:other:错题集_3 [2020/08/31 18:12] (当前版本)
jxm2001
@@ 行 216: / 行 216: @@
 		update(edge[t].u,1);update(edge[t].v,1);
 		enter(ans/2);
+	}
+	return 0;
+}
+</code>
+</hidden>
+===== 4、Tournament =====
+[[https://ac.nowcoder.com/acm/contest/5675/I|链接]]
+==== 题意 ====
+有 $n$ 支球队，每支球队需要两两间打一场比赛，一场比赛需要打一天且一天只能安排一场比赛。
+每个球队从它的第一场比赛入场，最后一场比赛退场，等待时间即中间的天数。输出所有球队等待时间最小的方案。
+==== 题解 ====
+大概思路就是将球队平均分成两组 $\text{A},\text{B}$，先 $\text{A}$ 内部打，然后 $\text{A},\text{B}$ 间打，然后 $\text{B}$ 内部打。
+$\text{A}$ 内部打的时候尽量让球队晚入场，$\text{B}$ 内部打的时候尽量让球队早退场。
+$\text{A},\text{B}$ 间打的时候均衡一下 $\text{B}$ 的入场速度和 $\text{A}$ 的退场速度。
+给出 $n=8$ 的构造供参考。
+|1,2|    |    |    |
+|1,3|2,3|    |    |
+|1,4|2,4|3,4|    |
+|1,5|2,5|3,5|    |
+|1,6|2,6|    |    |
+|1,7|    |    |    |
+|1,8|    |    |    |
+|2,7|2,8|    |    |
+|3,6|3,7|3,8|    |
+|4,5|4,6|4,7|4,8|
+|5,6|5,7|5,8|    |
+|6,7|6,8|    |    |
+|7,8|    |    |    |
+<hidden 查看代码>
+<code cpp>
+int main()
+{
+	int T=read_int();
+	while(T--){
+		int n=read_int();
+		_rep(i,2,n>>1)_for(j,1,i)
+		printf("%d %d\n",j,i);
+		_rep(i,(n>>1)+1,n)_rep(j,1,n-i)
+		printf("%d %d\n",j,i);
+		_rep(i,1,n>>1)_rep(j,n-i+1,n)
+		printf("%d %d\n",i,j);
+		_rep(i,(n>>1)+1,n)_rep(j,i+1,n)
+		printf("%d %d\n",i,j);
+	}
+	return 0;
+}
+</code>
+</hidden>
+===== 5、Snow Mountain =====
+[[https://www.luogu.com.cn/problem/P6787|链接]]
+==== 题意 ====
+给定长度为偶数的序列 $a$ 和序列 $x$，保证 $a_i$ 互异，且如果 $x_i\neq -1$ 则有 $a_i\lt a_{x_i}$。
+要求进行 $\frac n2$ 次删除操作，每次选择 $(a_i,a_j)$ 进行删除，要求删除满足 $x_i\neq j$ 且 $x_j\neq i$。删除后序列下标不变。
+第 $b$ 次删除的费用为 $b\times \min(a_i,a_j)$，求最小的删除费用和配对方案。
+==== 题解 ====
+先考虑没有 $x$ 限制的情况，考虑将序列 $a_i$ 从小到大排序，将其分成 $A=a[1,\frac n2],B=a[\frac n2+1,n]$ 两段。
+显然每次选择 $A$ 中最大的和 $B$ 中的任意一个删除最优。
+现考虑存在 $x$ 限制的情况，如果 $A$ 中某个元素的 $x$ 位于 $B$ ，则考虑在两元素间连一条边。
+情况 $1$：不存在 $B$ 中的某个点与 $A$ 中的所有元素连边
+考虑将 $B$ 中点按度数从大到小排序。
+同样从大到小考虑 $A$ 中每个元素，如果可以与当前 $B$ 中度数最大的点配对，则立刻配对，否则与当前 $B$ 中度数次大的元素配对。
+可以证明这样最终可以完成所有配对。定义如果 $A$ 中某个元素的 $x$ 仍然存在于 $B$ 中，则称改元素被锁定。
+如果遇到某次需要将 $B$ 中度数为 $0$ 的元素配对，如果此时取的是最大值，则说明剩余 $B$ 中所有元素均可配对。
+如果此时取得是次大值，说明剩余 $B$ 中除最大值外的所有元素均可配对。
+接下来如果之前操作中配对时删除的元素度数大于 $1$，则可以使得配对后 $A$ 至少有一个未锁定元素，该元素一定可以与 $B$ 当前最大值配对。
+否则说明 $A$ 中锁定的元素等于当前的配对个数，于是同样有未锁定元素可以配对。
+情况 $2$：存在 $B$ 中的某个点与 $A$ 中的所有元素连边
+从 $B$ 中选择一个值最小且可以与该元素配对的元素进行配对。
+如果无法找到指定元素，显然该元素永远无法配对。否则配对后将解锁所有 $A$ 中元素。考虑重新将 $A$ 的最大元素划分给 $B$。
+接下来可以直接按无限制的方式配对。
+总时间复杂度 $O(n\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5e5+5;
+struct Node{
+	int a,id,x,limt;
+	bool operator < (const Node &b)const{
+		return a<b.a;
+	}
+}node[MAXN];
+int rk[MAXN];
+struct cmp{
+	bool operator () (const Node &a,const Node &b)const{
+		return a.limt<b.limt||(a.limt==b.limt&&a.a>b.a);
+	}
+};
+priority_queue<Node,vector<Node>,cmp>q;
+int main()
+{
+	int n=read_int();
+	_rep(i,1,n)node[i].a=read_int(),node[i].id=i;
+	_rep(i,1,n)node[i].x=read_int();
+	sort(node+1,node+n+1);
+	_rep(i,1,n)rk[node[i].id]=i;
+	int m=n>>1;
+	_rep(i,1,n){
+		if(node[i].x==-1||rk[node[i].x]<=m)continue;
+		node[rk[node[i].x]].limt++;
+	}
+	_rep(i,m+1,n)q.push(node[i]);
+	Node temp=q.top();bool flag=false;
+	_rep(i,1,m){
+		if(node[i].x!=temp.id){
+			flag=true;
+			break;
+		}
+	}
+	LL ans=0;
+	if(flag){
+		for(int i=m,j=1;i;i--,j++)ans+=1LL*node[i].a*j;
+		enter(ans);
+		for(int i=m;i;i--){
+			if(node[i].x!=q.top().id){
+				printf("%d %d\n",node[i].id,q.top().id);
+				q.pop();
+			}
+			else{
+				Node cur=q.top();q.pop();
+				printf("%d %d\n",node[i].id,q.top().id);
+				q.pop();
+				q.push(cur);
+			}
+		}
+	}
+	else{
+		int sp=0;
+		for(int i=m+1;i<=n;i++){
+			if(node[i].x!=temp.id&&temp.x!=node[i].id&&node[i].id!=temp.id){
+				sp=i;
+				break;
+			}
+		}
+		if(!sp){
+			puts("-1");
+			return 0;
+		}
+		ans=min(node[sp].a,temp.a);
+		m--;
+		for(int i=m,j=2;i;i--,j++)ans+=1LL*node[i].a*j;
+		enter(ans);
+		printf("%d %d\n",node[sp].id,temp.id);
+		q.pop();
+		for(int i=m,j=m+1;i;i--,j++){
+			if(j==sp||node[j].id==temp.id){
+				i++;
+				continue;
+			}
+			printf("%d %d\n",node[i].id,node[j].id);
+		}
+	}
+	return 0;
+}
+</code>
+</hidden>
+===== 6、四月樱花 =====
+[[https://www.luogu.com.cn/problem/P6788|链接]]
+==== 题意 ====
+$$s=\prod_{x=1}^n\prod_{y\mid x}\cfrac {y^{\tau(x)}}{\prod_{z\mid y}(z+1)^2}$$
+==== 题解 ====
+$$\prod_{d\mid x}d^2=\prod_{d\mid x}d\frac xd=x^{\tau (d)}$$
+根据上式，有
+$$\prod_{x=1}^n\prod_{y\mid x}\cfrac {y^{\tau(x)}}{\prod_{z\mid y}(z+1)^2}$$
+$$
+\begin{equation}\begin{split}
+s&=\prod_{x=1}^n\prod_{y\mid x}\cfrac {y^{\tau(x)}}{\prod_{z\mid y}(z+1)^2}\\
+&=\prod_{x=1}^n\prod_{y\mid x}\cfrac {\prod_{z\mid y}z^2}{\prod_{z\mid y}(z+1)^2}\\
+&=\prod_{x=1}^n\prod_{y\mid x}\prod_{z\mid y}\cfrac {z^2}{(z+1)^2}\\
+&=\prod_{y=1}^n\left(\prod_{z\mid y}\cfrac {z^2}{(z+1)^2}\right)^{\lfloor\frac ny\rfloor}\\
+&=\prod_{z=1}^n\left(\cfrac z{z+1}\right)^{2\sum_{k=1}^{\lfloor\frac nz\rfloor}\lfloor\frac n{kz}\rfloor}
+\end{split}\end{equation}
+$$
+令 $f(n)=\sum_{i=1}^n \lfloor\frac ni\rfloor$，于是上式变为
+$$s=\prod_{z=1}^n\left(\cfrac z{z+1}\right)^{2f(\lfloor\frac nz\rfloor)}$$
+考虑分块，有
+$$\prod_{z=l}^r\left(\cfrac z{z+1}\right)^{2f(\lfloor\frac nz\rfloor)}=\left(\prod_{z=l}^r\cfrac z{z+1}\right)^{2f(\lfloor\frac nl\rfloor)}=\left(\frac l{r+1}\right)^{2f(\lfloor\frac nl\rfloor)}$$
+$f(\frac nl)$ 也可以通过分块计算。总时间复杂 $O\left(\sum_{i=1}^{\sqrt n}\sqrt i+\sqrt {\frac ni}\right)=O\left(n^{\frac 34}\right)$。
+<hidden 查看代码>
+<code cpp>
+int Mod;
+int quick_pow(unsigned int a,int b){
+	int ans=1;
+	while(b){
+		if(b&1)ans=1LL*ans*a%Mod;
+		a=1LL*a*a%Mod;
+		b>>=1;
+	}
+	return ans;
+}
+int cal(unsigned int n){
+	unsigned int l=1,r;
+	int ans=0;
+	while(l<=n){
+		r=n/(n/l);
+		ans=(ans+1LL*(r-l+1)*(n/l))%(Mod-1);
+		l=r+1;
+	}
+	return ans;
+}
+int main()
+{
+	unsigned int n=read_LL(),l=1,r;
+	Mod=read_int();
+	int ans=1;
+	while(l<=n){
+		r=n/(n/l);
+		ans=1LL*ans*quick_pow(1LL*l*quick_pow(r+1,Mod-2)%Mod,cal(n/l))%Mod;
+		l=r+1;
+	}
+	enter(1LL*ans*ans%Mod);
+	return 0;
+}
+</code>
+</hidden>
+==== 优化 ====
+$$\sum_{i=1}^n \lfloor\frac ni\rfloor=\sum_{i=1}^n \tau (i)$$
+考虑线性筛处理 $O\left(n^{\frac 23}\right)$ 的 $\tau (n)$ 的前缀和，大于 $n^{\frac 23}$ 的 $f(n)$ 暴力分块计算。
+时间复杂度变为 $O\left(n^{\frac 23}+\sum_{i=1}^{n^{\frac 13}}\sqrt {\frac ni}\right)=O\left(n^{\frac 23}\right)$。
+<hidden 查看代码>
+<code cpp>
+int Mod,Block;
+const int MAXS=2e6+5;
+int prime[MAXS],tau[MAXS],mpow[MAXS],cnt;
+void pre(){
+	tau[1]=1;
+	_for(i,2,Block){
+		if(!tau[i])prime[cnt++]=i,tau[i]=2,mpow[i]=1;
+		for(int j=0;j<cnt&&i*prime[j]<Block;j++){
+			if(i%prime[j])
+			tau[i*prime[j]]=tau[i]<<1,mpow[i*prime[j]]=1;
+			else{
+				tau[i*prime[j]]=tau[i]/(mpow[i]+1)*(mpow[i]+2),mpow[i*prime[j]]=mpow[i]+1;
+				break;
+			}
+		}
+	}
+	_for(i,2,Block)tau[i]=(0LL+tau[i]+tau[i-1])%(Mod-1);
+}
+int quick_pow(unsigned int a,int b){
+	int ans=1;
+	while(b){
+		if(b&1)ans=1LL*ans*a%Mod;
+		a=1LL*a*a%Mod;
+		b>>=1;
+	}
+	return ans;
+}
+int cal(unsigned int n){
+	if(n<Block)return tau[n];
+	unsigned int l=1,r;
+	int ans=0;
+	while(l<=n){
+		r=n/(n/l);
+		ans=(ans+1LL*(r-l+1)*(n/l))%(Mod-1);
+		l=r+1;
+	}
+	return ans;
+}
+int main()
+{
+	unsigned int n=read_LL(),l=1,r;
+	Mod=read_int();Block=pow(Mod,2.0/3)+1;
+	pre();
+	int ans=1;
+	while(l<=n){
+		r=n/(n/l);
+		ans=1LL*ans*quick_pow(1LL*l*quick_pow(r+1,Mod-2)%Mod,cal(n/l))%Mod;
+		l=r+1;
+	}
+	enter(1LL*ans*ans%Mod);
+	return 0;
+}
+</code>
+</hidden>
+===== 7、B-Suffix Array =====
+[[https://ac.nowcoder.com/acm/contest/5666/A|链接]]
+==== 题意 ====
+给出一个字符串，定义一个字符串 $S$ 对应序列 $B$，其中 $b_i=\min_{j\lt i,s_j=s_i} (i-j)$，如果不存在 $j$，$b_i=0$。
+求序列 $B$ 后缀排序后的结果。
+==== 题解 ====
+构造 $c_i=\min_{j\gt i,s_j=s_i}(j-i)$，如果不存在 $j$，$b_i=n$。特别的，$c_{n+1}$ 为 $c$ 的结束符且 $c_{n+1}=n+1$。
+有结论将 $B$ 序列后缀排序结果翻转后与 $C[1,n+1]$ 后缀排序前 $n$ 项相同。
+<hidden 查看代码>
+<code cpp>
+#include <cstdio>
+#include <algorithm>
+#define _for(i,a,b) for(int i=(a);i<(b);++i)
+#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
+#define mem(a,b) memset(a,b,sizeof(a))
+using namespace std;
+typedef long long LL;
+const int MAXN=1e5+5;
+namespace SA{
+	int sa[MAXN],x[MAXN],y[MAXN],c[MAXN];
+	void get_sa(int *s,int n,int m){
+		_rep(i,0,m)c[i]=0;
+		_rep(i,1,n)c[x[i]=s[i]]++;
+		_rep(i,1,m)c[i]+=c[i-1];
+		for(int i=n;i;i--)sa[c[x[i]]--]=i;
+		for(int k=1;k<n;k<<=1){
+			int pos=0;
+			_rep(i,n-k+1,n)y[++pos]=i;
+			_rep(i,1,n)if(sa[i]>k)y[++pos]=sa[i]-k;
+			_rep(i,0,m)c[i]=0;
+			_rep(i,1,n)c[x[i]]++;
+			_rep(i,1,m)c[i]+=c[i-1];
+			for(int i=n;i;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;
+			_rep(i,1,n)swap(x[i],y[i]);
+			pos=0,y[n+1]=0;
+			_rep(i,1,n)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?pos:++pos;
+			if(pos==n)break;
+			m=pos;
+		}
+	}
+}
+char buf[MAXN];
+int a[MAXN],last[2];
+int main()
+{
+	int n;
+	while(~scanf("%d%s",&n,buf+1)){
+		last[0]=last[1]=0;
+		for(int i=n;i;i--){
+			int c=buf[i]-'a';
+			if(last[c])a[i]=last[c]-i;
+			else a[i]=n;
+			last[c]=i;
+		}
+		a[n+1]=n+1;
+		SA::get_sa(a,n+1,n+1);
+		for(int i=n;i;i--)
+		printf("%d ",SA::sa[i]);
+		puts("");
 	}
 	return 0;

CVBB ACM Team

用户工具

站点工具

差别

页面工具