差别

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

--- 2020-2021:teams:legal_string:组队训练比赛记录:contest4 [2021/07/20 15:25]
王智彪
+++ 2020-2021:teams:legal_string:组队训练比赛记录:contest4 [2021/07/25 00:00] (当前版本)
jxm2001 [题解]
@@ 行 2: / 行 2: @@
 ====== 题解 ======
+===== A. Arithmetic Progression =====
+==== 题意 ====
+给定一个序列，问有多少连续子串从小到大排列后可以构成等差序列。
+==== 题解 ====
+给定一个序列 $a_1,a_2\cdots a_n$，则 $\max(a_i)-\min(a_i)\ge (n-1)\times \text{gcd}(a_2-a_1,a_3-a_2\cdots a_n-a_{n-1})$。
+等号成立充要条件为 $a_1,a_2\cdots a_n$ 从小到大排列后可以构成等差序列。具体见 [[..:jxm2001:other:结论_3#等差序列判定|证明]]。
+于是问题转化为统计有多少区间满足 $\max(a[l\sim r])-\min(a[l\sim r])=(r-l)\text{gcd}(a_{l+1}-a_l\cdots a_r-a_{r-1})$。
+考虑构造序列 $b_i=\max(a[i\sim r])-\min(a[i\sim r])+i\times \text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$。
+线段树维护区间最小值和最小值个数，对固定的 $r$，统计 $[i,r](i\lt r)$ 贡献时，枚举 $\text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 不同的区间。
+对每个区间将 $b_i=r\times \text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 的数值个数计入贡献。
+易知 $\text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 不同的区间最多只有 $O(\log v)$ 个，于是总询问次数 $O(n\log v)$。
+然后移动 $r$ 更新区间，需要维护 $\max(a[l\sim r]),\min(a[l\sim r]),i\times \text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 的变化。
+对 $\max(a[l\sim r]),\min(a[l\sim r])$ 的变化可以用单调栈维护，总更新次数 $O(n)$。
+对 $i\times \text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 的变化，可以维护 $\text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 不同的段。
+每次 $r$ 变化时暴力遍历 $O(\log v)$ 个段，每个段的值发生变化时暴力遍历整个段更新。
+由于每个位置的 $\text{gcd}$ 值最多变化 $O(\log v)$ 次，所以总更新次数 $O(n\log v)$。
+于是线段树只需要支持区间加操作和区间查询操作，总时间复杂度 $O(n\log n\log v)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5;
+struct Node{
+	LL v;
+	int cnt;
+	Node operator + (const Node &b)const{
+		Node c;
+		if(v==b.v)c.v=v,c.cnt=cnt+b.cnt;
+		else if(v<b.v)c=*this;
+		else c=b;
+		return c;
+	}
+}s[MAXN<<2];
+LL tag[MAXN<<2];
+int lef[MAXN<<2],rig[MAXN<<2];
+void push_up(int k){
+	s[k]=s[k<<1]+s[k<<1|1];
+}
+void push_add(int k,LL v){
+	s[k].v+=v;
+	tag[k]+=v;
+}
+void push_down(int k){
+	if(tag[k]){
+		push_add(k<<1,tag[k]);
+		push_add(k<<1|1,tag[k]);
+		tag[k]=0;
+	}
+}
+void build(int k,int L,int R){
+	lef[k]=L,rig[k]=R,tag[k]=0;
+	if(L==R){
+		s[k].v=0;
+		s[k].cnt=1;
+		return;
+	}
+	int M=L+R>>1;
+	build(k<<1,L,M);
+	build(k<<1|1,M+1,R);
+	push_up(k);
+}
+void update(int k,int L,int R,LL v){
+	if(L<=lef[k]&&rig[k]<=R){
+		push_add(k,v);
+		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);
+	push_up(k);
+}
+Node query(int k,int L,int R){
+	if(L<=lef[k]&&rig[k]<=R)
+	return s[k];
+	push_down(k);
+	int mid=lef[k]+rig[k]>>1;
+	if(mid>=R)
+	return query(k<<1,L,R);
+	else if(mid<L)
+	return query(k<<1|1,L,R);
+	else
+	return query(k<<1,L,R)+query(k<<1|1,L,R);
+}
+int gcd(int a,int b){
+	while(b){
+		int t=b;
+		b=a%b;
+		a=t;
+	}
+	return a;
+}
+int a[MAXN],st1[MAXN],st2[MAXN];
+pair<int,int> st3[MAXN];
+int main()
+{
+	int T=read_int();
+	while(T--){
+		int n=read_int();
+		_rep(i,1,n)a[i]=read_int();
+		build(1,1,n);
+		LL ans=n;
+		int top1=0,top2=0,top3=0;
+		_rep(i,1,n){
+			while(top1&&a[st1[top1]]<=a[i]){
+				update(1,st1[top1-1]+1,st1[top1],a[i]-a[st1[top1]]);
+				top1--;
+			}
+			st1[++top1]=i;
+			while(top2&&a[st2[top2]]>=a[i]){
+				update(1,st2[top2-1]+1,st2[top2],a[st2[top2]]-a[i]);
+				top2--;
+			}
+			st2[++top2]=i;
+			if(i==1)continue;
+			st3[++top3]=make_pair(abs(a[i]-a[i-1]),i-1);
+			update(1,i-1,i-1,1LL*(i-1)*st3[top3].first);
+			for(int j=top3-1;j;j--){
+				if(st3[j+1].first%st3[j].first!=0){
+					int temp=st3[j].first;
+					st3[j].first=gcd(st3[j].first,st3[j+1].first);
+					_rep(k,st3[j-1].second+1,st3[j].second)
+					update(1,k,k,1LL*k*(st3[j].first-temp));
+				}
+			}
+			int temp=0;
+			_rep(j,1,top3){
+				if(st3[j].first==st3[temp].first)
+				st3[temp].second=st3[j].second;
+				else
+				st3[++temp]=st3[j];
+			}
+			top3=temp;
+			_rep(j,1,top3){
+				Node temp=query(1,st3[j-1].second+1,st3[j].second);
+				if(temp.v==1LL*i*st3[j].first)
+				ans+=temp.cnt;
+			}
+		}
+		enter(ans);
+	}
+	return 0;
+}
+</code>
+</hidden>
 ===== B. Cannon =====
@@ 行 15: / 行 178: @@
 对于第一个子问题，我们发现可以把 $k!$ 提出来，之后对于里面的式子，可以变成两个组合数的乘积，再利用组合数的常用结论，可以推出其等于 $2^{k}k!C(n+m,k)$ ，这个式子可以通过预处理 $2$ 的方幂，阶乘以及阶乘的逆来 $O(1)$ 求得，于是总共复杂度 $O(n+m)$ 。
-对于第二个子问题， $2^{k} \sum {\frac {n!} {(n-i)!}} {\frac {m!} {(m-(k-i))!}} = 2^{k} \sum {\frac {n!m!} {(n+m-k)!}} {\frac {(n+m-k)!} {(n-i)!(m-(k-i))!}} = 2^{k} {\frac {n!m!} {(n+m-k)!}} \sum_{i=n-k}^{n} C(n+m-k,i)$
+对于第二个子问题， $2^{k} \sum {\frac {n!} {(n-i)!}} {\frac {m!} {(m-(k-i))!}} = 2^{k} \sum {\frac {n!m!} {(n+m-k)!}} {\frac {(n+m-k)!} {(n-i)!(m-(k-i))!}} = 2^{k} {\frac {n!m!} {(n+m-k)!}} \sum_{i=k-m}^{n} C(n+m-k,i)$
 虽然没有直接的结论，但是这个可以用步移算法来解决。
@@ 行 179: / 行 342: @@
 其中我们需要预处理出 $P$ 的所有素因子（为了求欧拉函数值），处理出序列中有多少个数字能除开范围内的任意一个数字。处理出组合数对欧拉函数值取模，最后统计答案就是找所有的素数，看他们的方幂出现的次数，相加，对欧拉函数值取模，最后再快速幂乘起来，就可以愉悦 $AC$ 本题了。
-<hidden 代码>
+当然，如果觉得慢可以用 $Pollard\_rho$ 来加速分解质因数过程，这样筛的时候就没必要筛到根号 $P$ 了，效率会快很多，如下面第二份代码所示。
+<hidden 代码1>
 <code cpp>
@@ 行 292: / 行 457: @@
 </hidden>
+<hidden 代码2>
+<code cpp>
+#include<bits/stdc++.h>
+using namespace std;
+typedef long long ll;
+const int maxn=80000+5,maxs=40000+5,maxk=30+2;
+int T,S,k;
+ll P,maxv;
+int sum[maxn],prime[maxn],ps;
+long long C[maxs][maxk];
+bool isPrime[maxn];
+inline void initial() {
+	memset(isPrime, 1, sizeof(isPrime));
+	for (int i = 2; i < maxn; ++i) {
+		if (isPrime[i]) {
+			prime[ps++]=i;
+			for (int j = i + i; j < maxn; j += i) {
+				isPrime[j] = false;
+			}
+		}
+	}
+}
+inline int read() {
+	int X=0,w=1;
+	char c=getchar();
+	while (c<'0'||c>'9') {
+		if (c=='-') w=-1;
+		c=getchar();
+	}
+	while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
+	return X*w;
+}
+inline void write(int x) {
+	char c[21],len=0;
+	if(!x)return putchar('0'),void();
+	if(x<0)x=-x,putchar('-');
+	while(x)c[++len]=x%10,x/=10;
+	while(len)putchar(c[len--]+48);
+}
+inline ll quick_mul(ll a,ll b,ll p) {
+	return (ll)((__int128)a*b%p);
+}
+inline ll quick_power(ll a,ll b,ll p) {
+	ll ret=1;
+	while(b) {
+		if(b&1) ret=quick_mul(ret,a,p);
+		a=quick_mul(a,a,p);
+		b>>=1;
+	}
+	while(ret<0) ret+=p;
+	return ret%p;
+}
+struct Pollard_rho {
+	bool check(ll a,ll n,ll x,ll t) {
+		ll ans=quick_power(a,x,n);
+		ll aans=ans;
+		for(int i=1; i<=t; i++) {
+			ans=quick_mul(ans,ans,n);
+			if(ans==1&&aans!=1&&aans!=n-1) return true;
+			aans=ans;
+		}
+		if(ans!=1) return true;
+		return false;
+	}
+	bool Miller_Rabin(ll n) {
+		if(n<2) return false;
+		if(n==2) return true;
+		if(!(n&1)) return false;
+		ll x=n-1,t=0;
+		while(!(x&1)) {
+			x>>=1;
+			t++;
+		}
+		for(int i=0; i<20; i++) {
+			ll a=rand()%(n-1)+1;
+			if(check(a,n,x,t)) return false;
+		}
+		return true;
+	}
+	ll gcd(ll x,ll y) {
+		if(!x) return y;
+		if(!y) return x;
+		if(x<0) x=-x;
+		if(y<0) y=-y;
+		ll t=__builtin_ctzll(x|y);
+		x>>=__builtin_ctzll(x);
+		do {
+			y>>=__builtin_ctzll(y);
+			if(x>y) swap(x,y);
+			y-=x;
+		} while(y);
+		return x<<t;
+	}
+	ll pollard_rho(ll x,ll c) {
+		ll ci=1,k=2;
+		srand(time(NULL));
+		ll x0=rand()%(x-1)+1;
+		ll y=x0,t=1;
+		while(1) {
+			ci++;
+			x0=(quick_mul(x0,x0,x)+c)%x;
+			t=quick_mul(y-x0,t,x);
+			if(!t||!(y^x0)) return x;
+			if(ci==k) {
+				ll d=gcd(t,x);
+				if(d!=1) return d;
+				y=x0;
+				k<<=1;
+			}
+		}
+	}
+	void findfac(ll n,ll k) {
+		if(n==1) return;
+		if(Miller_Rabin(n)) {
+			if(n>maxv) maxv=n;
+			return;
+		}
+		ll p=n,c=k;
+		while(p>=n) {
+			p=pollard_rho(p,c--);
+		}
+		findfac(p,k);
+		findfac(n/p,k);
+	}
+}pr;
+int main() {
+	initial();
+	T=read();
+	while(T--) {
+		S=read();
+		k=read();
+		scanf("%lld",&P);
+		for(int i=0; i<maxn; i++) sum[i]=0;
+		for(int i=0,tmp; i<S; i++) {
+			tmp=read();
+			sum[tmp]++;
+		}
+		for(int i=2; i<maxn; i++) {
+			for(int j=i+i; j<maxn; j+=i) {
+				sum[i]+=sum[j];
+			}
+		}
+		long long tmp=P,phi_ans=1;
+		maxv=0;
+		while(tmp!=1) {
+			pr.findfac(tmp,324757);
+			tmp/=maxv;
+			phi_ans*=(maxv-1);
+			while(tmp%maxv==0) {
+				tmp/=maxv;
+				phi_ans*=maxv;
+			}
+			maxv=0;
+		}
+		for(int i=0; i<=S; i++) {
+			C[i][0]=1;
+			for(int j=1; j<=i&&j<=k; j++) {
+				C[i][j] = C[i-1][j] + C[i-1][j-1];
+				while(C[i][j]>=phi_ans+phi_ans) C[i][j]-=phi_ans;
+			}
+		}
+		long long num;
+		ll ans=1;
+		for(int i=2; i<maxn; i++) {
+			if(isPrime[i]) {
+				num=0;
+				for(ll j=i; j<maxn; j*=i) {
+					num+=C[sum[j]][k];
+					while(num>=phi_ans+phi_ans) num-=phi_ans;
+				}
+				ans=quick_mul(ans,quick_power(i,num,P),P);
+			}
+		}
+		printf("%lld\n",ans);
+	}
+	return 0;
+}
+</code>
+</hidden>
+===== L. WeChat Walk =====
+==== 题意 ====
+给定一张图 $n$ 个点 $m$ 条边。每个点初始权值为 $0$，接下来 $q$ 个单位时间，每个单位时间仅增加一个点的权值。
+当一个点的权值严格大于所有与自己相邻的点时，这个点成为冠军。问每个点作为冠军的时间。
+==== 题解 ====
+考虑分块，设分块大小为 $S\sim O(\sqrt n)$。每个点 $u$ 维护自己作为冠军的开始时间，当一个点不再是冠军时加入答案。
+称度数不大于 $S$ 的点为一类点，其余点为二类点。
+对于一类点，暴力遍历相邻的点判断自己是否称为冠军顺便更新相邻的点即可。
+对于二类点 $u$，先考虑如何更新相邻点的冠军，考虑维护 $S(u,w)$ 表示与 $u$ 相邻且权值等于 $w$ 的点的集合。
+设 $u$ 权值更新前为 $w_1$，更新后为 $w_2$，不难发现更新 $u$ 只会导致权值位于 $(w_1,w_2]$ 之间的点的冠军情况发生变化，于是暴力扫描即可。
+最后需要判定 $u$ 是否为冠军，考虑维护 $\text{maxw}(u)$ 表示与 $u$ 相邻的点的最大权值。
+于是只需要在更新所有类型点权值时暴力遍历相邻的二类点并更新他们即可。
+由于二类点最多只有 $O(\sqrt n)$ 个，所以每次更新最多使得 $\sum |S(u,w)|$ 增加 $O(\sqrt n)$。于是总时间复杂度 $O(n\sqrt n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=2e5+5,MAXS=505,MAXW=1e4+5;
+vector<int> g[MAXN],g2[MAXN],g3[MAXS][MAXW];
+int ans[MAXN],val[MAXN],last[MAXN],maxw[MAXN],bmap[MAXN],bsz;
+void update(int u,int v,int t){
+	if(last[v]!=-1&&val[v]<=val[u]){
+		ans[v]+=t-last[v];
+		last[v]=-1;
+	}
+	if(g[v].size()>bsz){
+		maxw[v]=max(maxw[v],val[u]);
+		g3[bmap[v]][val[u]].push_back(u);
+	}
+}
+int main()
+{
+	int n=read_int(),m=read_int(),q=read_int(),bcnt=0;
+	bsz=sqrt(n)+1;
+	_for(i,0,m){
+		int u=read_int(),v=read_int();
+		g[u].push_back(v);
+		g[v].push_back(u);
+	}
+	_rep(u,1,n){
+		if(g[u].size()>bsz){
+			bmap[u]=bcnt++;
+			_for(i,0,g[u].size()){
+				int v=g[u][i];
+				if(g[v].size()>bsz)
+				g2[u].push_back(v);
+			}
+		}
+	}
+	mem(last,-1);
+	_rep(tim,1,q){
+		int u=read_int(),w=read_int();
+		val[u]+=w;
+		if(g[u].size()<=bsz){
+			if(last[u]==-1)
+			last[u]=tim;
+			_for(i,0,g[u].size()){
+				int v=g[u][i];
+				if(val[v]>=val[u])
+				last[u]=-1;
+				update(u,v,tim);
+			}
+		}
+		else{
+			if(val[u]>maxw[u]&&last[u]==-1)
+			last[u]=tim;
+			_for(i,0,g2[u].size()){
+				int v=g2[u][i];
+				update(u,v,tim);
+			}
+			int idx=bmap[u];
+			_rep(k,val[u]-w+1,val[u]){
+				_for(i,0,g3[idx][k].size()){
+					int v=g3[idx][k][i];
+					update(u,v,tim);
+				}
+			}
+		}
+	}
+	_rep(u,1,n){
+		if(last[u]!=-1)
+		ans[u]+=q-last[u];
+		enter(ans[u]);
+	}
+	return 0;
+}
+</code>
+</hidden>
 ====== 赛后总结 ======

CVBB ACM Team

用户工具

站点工具

差别

页面工具