【考试总结】2022-2-21

排队

因为序列最终会变成有序的,那么没有说过悄悄话的女生的身高一定是单调的

那么问题转化成了求最长上升子序列的长度和求哪些元素是一定在 \(\rm LIS\) 中

那么计算 \(\rm LIS\) 的方案数使对大质数取模即可

我使用了 unsigned long long 就挂了

Code Display
int pref[N],suff[N];
int dp1[N],dp2[N],n,a[N];
struct Fenwick{
	int met[N];
	int c[N];
	inline void insert(int x,pair<int,int> v){
		for(;x<=n;x+=x&(-x)){
			if(c[x]==v.fir) ckadd(met[x],v.sec);
			else if(c[x]<v.fir) met[x]=v.sec,c[x]=v.fir;
		} return ;
	}
	inline pair<int,int> query(int x){
		pair<int,int> res={0,1};
		for(;x;x-=x&(-x)){
			if(c[x]>res.fir) res.fir=c[x],res.sec=met[x];
			else if(c[x]==res.fir) ckadd(res.sec,met[x]);
		} 
		return res;
	}
}T;
signed main(){
	freopen("queue.in","r",stdin); freopen("queue.out","w",stdout);
	n=read();
	rep(i,1,n){
		a[i]=read();
		pair<int,ull> now=T.query(a[i]);
		dp1[i]=now.fir+1;
		pref[i]=now.sec;
		T.insert(a[i],make_pair(dp1[i],pref[i]));
	}
	memset(T.met,0,sizeof(T.met));
	memset(T.c,0,sizeof(T.c));
	rep(i,1,n) a[i]=n-a[i]+1;
	Down(i,n,1){
		pair<int,ull> now=T.query(a[i]);
		dp2[i]=now.fir+1;
		suff[i]=now.sec;
		T.insert(a[i],make_pair(dp2[i],suff[i]));
	}
	int sum=0,Mx=0;
	rep(i,1,n) ckmax(Mx,dp1[i]+dp2[i]);
	rep(i,1,n) if(dp2[i]==1&&dp1[i]+dp2[i]==Mx) ckadd(sum,pref[i]);
	print(Mx-1); putchar('\n');
	for(int i=1;i<=n;++i){
		if(dp1[i]+dp2[i]==Mx&&mul(pref[i],suff[i])==sum) print(i);
	} putchar('\n');
	return 0;
}

树论

一个比较基础的 \(\rm DP\) 就是设 \(f_{x,i}\) 表示 \(x\) 为根的子树里面 \(x\) 的数值是 \(i\) 的方案数

暴力是以每个节点为根 \(dfs\) 求出来方案数乘权值 \(i\) 贡献给答案

我们将转移式子写出来看看:\(dp_{x,i}\times dp_{t,j}[(i,j)=1]\to dp_{x,i}\)

这个东西是非常基础的反演式子,使用调和级数复杂度的统计方式就行了

复杂度并不允许每个点 \(dfs\),所以就可以写个换根 \(\rm DP\)

Code Display
const int N=60,M=50010;
int dp[N][M],n,l[N],r[N];
vector<int> G[N];
bool fl[M];
int pri[M],mu[M],cnt;
int sum[M],ton[M];
inline void dfs(int x,int fat){
	rep(i,l[x],r[x]) dp[x][i]=1;
	for(auto t:G[x]) if(t!=fat){
		dfs(t,x);
		rep(i,1,r[t]){
			for(int j=(l[t]+i-1)/i*i;j<=r[t];j+=i) ton[i]+=dp[t][j];
		}
		for(int i=1;i<=r[x];++i) if(ton[i]){
			for(int j=(l[x]+i-1)/i*i;j<=r[x];j+=i){
				sum[j]+=ton[i]*mu[i];
			}
		}
		for(int i=l[x];i<=r[x];++i){
			sum[i]=(sum[i]%mod+mod)%mod;
			ckmul(dp[x][i],sum[i]);
			sum[i]=0;
		}
		rep(i,1,r[t]) ton[i]=0;
	}
	return ;	
}
int tmp[M];
inline void get_ans(int x,int fat){
	for(auto t:G[x]) if(t!=fat){
		rep(i,1,r[t]){
			for(int j=(l[t]+i-1)/i*i;j<=r[t];j+=i) ton[i]+=dp[t][j];
		}
		for(int i=1;i<=r[x];++i) if(ton[i]){
			for(int j=(l[x]+i-1)/i*i;j<=r[x];j+=i){
				sum[j]+=ton[i]*mu[i];
			}
		}
		for(int i=l[x];i<=r[x];++i){
			sum[i]=(sum[i]%mod+mod)%mod;
			tmp[i]=mul(ksm(sum[i],mod-2),dp[x][i]);
			sum[i]=0;
		}
		rep(i,1,r[t]) ton[i]=0;
		
		rep(i,1,r[x]){
			for(int j=(l[x]+i-1)/i*i;j<=r[x];j+=i) ton[i]+=tmp[j];
			tmp[i]=0;
		}
		for(int i=1;i<=r[t];++i) if(ton[i]){
			for(int j=(l[t]+i-1)/i*i;j<=r[t];j+=i){
				sum[j]+=ton[i]*mu[i];
			}
		}
		for(int i=l[t];i<=r[t];++i){
			ckmul(dp[t][i],(sum[i]%mod+mod)%mod);
			sum[i]=0;
		}
		rep(i,1,r[x]) ton[i]=0;
		get_ans(t,x);
	} return ;
}
signed main(){
	freopen("tree.in","r",stdin); freopen("tree.out","w",stdout);
	n=50000; mu[1]=1;
	for(int i=2;i<=n;++i){
		if(!fl[i]) pri[++cnt]=i,mu[i]=-1;
		for(int j=1;j<=cnt&&i*pri[j]<=n;++j){
			fl[i*pri[j]]=1;
			if(i%pri[j]==0) break;
			mu[i*pri[j]]=-mu[i];
		}
	}
	n=read(); 
	rep(i,1,n) l[i]=read(); 
	rep(i,1,n) r[i]=read();
	for(int i=1,u,v;i<n;++i){
		u=read(),v=read();
		G[u].pb(v); G[v].pb(u);
	}
	dfs(1,0);
	get_ans(1,0);
	rep(rt,1,n){
		int sum=0;
		for(int i=l[rt];i<=r[rt];++i) ckadd(sum,mul(i,dp[rt][i]));
		print(sum);
	}
	return 0;
}

麻烦的杂货店

设 \(pre_i=\min\{j|sum_j=sum_i,\forall\ k\in[j,i]sum_k\ge sum_i\}\),\(next_i=\max\{j|sum_j=sum_i,\forall\ k\in[i,j]sum_k\ge sum_i\}\),这个正反两边扫就能找到了

对于每组询问,找到区间内部前缀和最小的点的第一和最后一次出现位置 \(fa,la\) ,那么选择这段子区间是合法的

对于 \([ql,fa]\) 和 \([la,qr]\) 两部分,本质上是求区间里面 \(i-pre_i,nxt_i-i\) 和最大值,使用 \(\rm ST\) 表维护即可,同时上面找最小值第一/最后一次出现也可以使用 \(\rm ST\) 表维护

Code Display
const int N=2e5+10;
int lst[N],lef[20][N],lg[N],rig[20][N],sum[N],n;
char s[N];
int pre[N],nxt[N],st[20][N],ed[20][N],Q;
inline int argmin(int a,int b){return sum[a]<=sum[b]?a:b;}
signed main(){
	freopen("grocery.in","r",stdin); freopen("grocery.out","w",stdout);
	n=2e5; for(int i=2;i<=n;++i) lg[i]=lg[i>>1]+1;
	n=read(); Q=read(); scanf("%s",s+1);
	for(int i=1;i<=n;++i) sum[i]=sum[i-1]+(s[i]=='F'?1:-1);
	for(int i=1;i<=n;++i) lef[0][i]=rig[0][i]=i;
	for(int j=1;(1<<j)<=n+1;++j){
		for(int i=0;i+(1<<j)-1<=n;++i){
			lef[j][i]=argmin(lef[j-1][i],lef[j-1][i+(1<<(j-1))]);
			rig[j][i]=argmin(rig[j-1][i+(1<<(j-1))],rig[j-1][i]);
		}
	}
	const int Delt=1e5;
	memset(pre,-1,sizeof(pre));
	memset(nxt,-1,sizeof(nxt));
	memset(lst,-1,sizeof(lst)); lst[Delt]=0;
	for(int i=1;i<=n;++i){
		if(sum[i]<sum[i-1]) lst[sum[i-1]+Delt]=-1;
		if(~lst[sum[i]+Delt]){
			int id=lst[sum[i]+Delt];
			pre[i]=id;
			nxt[id]=i;
		}
		lst[sum[i]+Delt]=i;
	}
	Down(i,n,0){
		if(nxt[i]!=-1&&nxt[nxt[i]]!=-1) nxt[i]=nxt[nxt[i]];
		st[0][i]=nxt[i]!=-1?nxt[i]-i:0;
	}
	rep(i,0,n){
		if(pre[i]!=-1&&pre[pre[i]]!=-1) pre[i]=pre[pre[i]];
		ed[0][i]=pre[i]!=-1?i-pre[i]:0;
	}
	for(int j=1;(1<<j)<=n+1;++j){
		for(int i=0;i+(1<<j)-1<=n;++i){
			st[j][i]=max(st[j-1][i],st[j-1][i+(1<<(j-1))]);
			ed[j][i]=max(ed[j-1][i],ed[j-1][i+(1<<(j-1))]);
		}
	}
	while(Q--){
		int l=read()-1,r=read();
		int ans=0,t=lg[r-l+1];
		int minl=argmin(lef[t][l],lef[t][r-(1<<t)+1]);
		int minr=argmin(rig[t][r-(1<<t)+1],rig[t][l]);
		ans=minr-minl; 
		if(l<minl){
			int t=lg[minl-l];
			ckmax(ans,max(st[t][l],st[t][minl-(1<<t)]));
		}
		if(minr<r){
			int t=lg[r-minr];
			ckmax(ans,max(ed[t][minr+1],ed[t][r-(1<<t)+1]));
		}
		print(ans);
	}
	return 0;
}

这场放到联赛前可能多数同学和现在考试得到的分数是类似的

上一篇:linux下yum无法安装lrzsz,Error: Failed to download metadata for repo ‘appstream‘: Cannot prepare internal


下一篇:递归执行机制