第 24 次 CCF CSP 题解

A

推式子，统计每个数 $a_i$ 的贡献，显然每有一个比它大且比它的后继小的数都会产生 $1$ 的贡献。于是可以得到下式：

直接求和即可。

#include<iostream>
#include<cstdio>
typedef long long ll;
const int N=205;
int n,m;
int a[N];
inline void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	ll ans=0;
	for(int i=1;i<n;++i){
		ans+=(a[i+1]-a[i])*i;
	}
	ans+=(m-a[n])*n;
	printf("%lld\n",ans);
}


int main(){
	init();
	return 0;
}

 

B

对于这题我们仍然想统计贡献，于是考虑如何去绝对值符号。

我们上一题中的贡献关键节点是 $a_i$， 现在我们考虑 $g_i$ 的值发生变化的点，它们是 $i * r$ 。将这些点和数列 $a$ 拼接并排序后得到新的序列 $b$ ，在序列 $b$ 中，每一段的 $f$ 和 $g$ 的值都是相同的。于是可以继续统计贡献，得到：

#include<iostream>
#include<cstdio>
#include<algorithm>
typedef long long ll;
const int N=100005;

inline ll Abs(ll X){
	return X>=0?X:-X;
}
ll n,m,r;
ll a[N],b[N<<1];
inline ll f(ll X){
	return std::upper_bound(a+1,a+1+n,X)-a-1;
}
inline ll g(ll X){
	return X/r;
}

inline void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	r=m/(n+1);ll tot;
	for(tot=1;tot*r<=m;++tot){
		b[n+tot]=tot*r;
	}
	tot+=n;
	b[++tot]=m;
	std::sort(b+1,b+1+tot);
	ll ans=0;
	for(int i=1;i<tot;++i){
		ans+=(b[i+1]-b[i])*Abs(f(b[i])-g(b[i]));
	}
	printf("%lld\n",ans);
}


int main(){
	init();
	return 0;
}

 

C

依题意模拟即可。

有一个数论成份：中间需要进行一次多项式除法。所幸时间复杂度要求较低，直接模拟即可。

#include<iostream>
#include<cstdio>
#include<cstring>
const int N = 2005;
const int MOD = 929;

int typ(char X){
	return ('0'<=X&&X<='9')?3:('a'<=X&&X<='z')?2:1;
}

int id(char X){
	return (typ(X)==1)?X-'A':((typ(X)==2)?X-'a':X-'0'); 
}


int w,s,n,k;
char ch[N];
int ans[N],tp=1;
int str[N],stp=0;
int pw3[N];
int d[N],g[N],r[N],tmp[N];

//now max x^(A-1), tms x+B;
inline void mlt(int A,int B){
	for(int i=0;i<A;++i){
		tmp[i]=g[i];
	}
	for(int i=A;i>0;--i){
		g[i]=g[i-1];
	}
	g[0]=0;
	for(int i=0;i<A;++i){
		g[i]+=tmp[i]*B%MOD;
		g[i]%=MOD;
	}
}

// reduce which tms A*x^B
inline void red(int A,int B){
	for(int i=B;i<=B+k;++i){
		d[i]-=(g[i-B]*A%MOD);
		d[i]+=MOD;d[i]%=MOD;
	}
}

inline void div(){
	for(int i=tp+k-1;i>=k;--i){
		red(d[i],i-k);
	}
}

inline void genG(){
	g[0]=1;
	for(int i=1;i<=k;++i){
		mlt(i,(MOD-pw3[i])%MOD);
	}
//	for(int i=0;i<=k;++i){
//		printf("%d ",g[i]);
//	}
//	puts("");
}

inline void init(){
	scanf("%d%d",&w,&s);
	k=(s>=0)?(1<<(s+1)):0;
	std::cin>>ch+1;
	n=strlen(ch+1);
	ch[0]=='S';
	for(int i=1;i<=n;++i){
		if(typ(ch[i])!=typ(ch[i-1])){
			if(typ(ch[i])==2){
				str[++stp]=27;
			}else if(typ(ch[i])==3){
				str[++stp]=28;
			}else if(typ(ch[i-1])==3){
				str[++stp]=28;
			}else{
				str[++stp]=28;
				str[++stp]=28;
			}
		}
		str[++stp]=id(ch[i]);
	}
	if(stp&1){
		str[++stp]=29;
	}
	for(int i=1;i<=stp;i+=2){
		ans[++tp]=30*(str[i])+str[i+1];
	}
	while((tp+k)%w){
		ans[++tp]=900;
	}
	ans[1]=tp;
	if(s==-1){
		return;
	}
	for(int i=0;i<k;++i){
		d[i]=0;
	}
	for(int i=1;i<=tp;++i){
		d[i+k-1]=ans[tp-i+1];
	}
	genG();
	div();
	for(int i=0;i<k;++i){
		ans[++tp]=(MOD-d[k-i-1])%MOD;
	}
}


int main(){
	pw3[0]=1;
	for(int i=1;i<=1000;++i){
		pw3[i]=pw3[i-1]*3%MOD;
	}
//	for(int i=0;i<=8;++i){
//		k=(1<<i+1);
//		genG();
//	}
	init();
	for(int i=1;i<=tp;++i){
		printf("%d\n",ans[i]);
	}
	return 0;
}

 

D

据称是线段树模板题。我用的是平衡树模拟区间操作，同样可以通过此题。

#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
struct Data{
	int l;int r;int id;int v;mutable bool bo;
	bool operator<(const Data &B)const{
		return r<B.r;
	}
};

std::set<Data> st;
int n,m,q;

inline std::set<Data>::iterator srch(int X){
	return st.lower_bound((Data){0,X,0,0,0});
}

//split between X & X+1:
inline void split(int X){
//	printf("split from:%d\n",X);
	std::set<Data>::iterator it = srch(X);
	if(it == st.end() || X == m || it->r == X || it->l > X){
		return;
	}
	int l=it->l,r=it->r,id=it->id,v=it->v,bo=it->bo;
	st.erase(it);
	st.insert((Data){l,X,id,v,bo});
	st.insert((Data){X+1,r,id,v,bo});
}


inline int add(int L,int R,int ID,int X){
	split(L-1);split(R);
	std::set<Data>::iterator itx = srch(L);
	if(itx == st.end() || itx->l > R){
		st.insert((Data){L,R,ID,X,1});
		return R;
	}
	int R1=L-1;
	std::set<Data>::iterator ity;
	bool nbo=0;
	for(ity = itx; ity!=st.end()&&ity->l<=R;++ity){
		R1=ity->l-1;
		if(ity->id != ID && ity->bo){
			nbo=1;
			break;
		}
	}
	if(!nbo){
		R1=R;
	}
	if(R1<L){
		return -1;
	}
	st.erase(itx,ity);
	st.insert((Data){L,R1,ID,X,1});
	return R1; 
}

inline void prnt(std::set<Data>::iterator it){
	if(it==st.end()){
		puts("end");
		return;
	} 
	printf("%d %d %d %d %d\n",it->l,it->r,it->id,it->v,it->bo);
}

inline bool del(int L,int R,int ID){
	split(L-1);split(R);
	std::set<Data>::iterator itx = srch(L);
	if(itx == st.end() || itx->l!=L){
		return 0;
	}
	std::set<Data>::iterator ity;
	int R1=L-1;
	for(ity = itx; ity!=st.end()&&ity->l<=R;++ity){
//		prnt(ity);
		if(ity->id != ID || (!ity->bo) || ity->l!=R1+1){
			return 0;
		}
		R1=ity->r;
	}
	if(R1<R){
		return 0;
	}
	for(ity = itx; ity!=st.end()&&ity->l<=R;++ity){
		ity->bo=0;
	}
	return 1;
}

inline bool rbck(int L,int R,int ID){
	split(L-1);split(R);
	std::set<Data>::iterator itx = srch(L);
	if(itx == st.end() || itx->l!=L){
		return 0;
	}
	std::set<Data>::iterator ity;
	int R1=L-1;
	for(ity = itx; ity!=st.end()&&ity->l<=R;++ity){
		if(ity->id != ID || ity->bo || ity->l != R1+1){
			return 0;
		}
		R1=ity->r;
	}
	if(R1<R){
		return 0;
	}
	for(ity = itx; ity!=st.end()&&ity->l<=R;++ity){
		ity->bo=1;
	}
	return 1;
}

inline void init(){
	scanf("%d%d%d",&n,&m,&q);
	int op,id,l,r,p,v;
	for(int i=1;i<=q;++i){
		scanf("%d",&op);
		switch(op){
			case 0:{
				scanf("%d%d%d%d",&id,&l,&r,&v);
				printf("%d\n",add(l,r,id,v));
				break;
			}
			case 1:{
				scanf("%d%d%d",&id,&l,&r);
				puts(del(l,r,id)?"OK":"FAIL");
				break;
			}
			case 2:{
				scanf("%d%d%d",&id,&l,&r);
				puts(rbck(l,r,id)?"OK":"FAIL");
				break;
			}
			case 3:{
				scanf("%d",&p);
				std::set<Data>::iterator it = srch(p);
				if(it == st.end() || it->l>p || it->bo == 0){
					puts("0 0");
				}else{
					printf("%d %d\n",it->id,it->v);
				}
				break;
			}
		}
	}
}


int main(){
	init();
	return 0;
}

 

E

来不及了，打个暴力走人

#include<iostream>
#include<cstdio>
typedef long long ll;
const int N=100005;
const int INF=0x3f3f3f3f;

inline int Max(int A,int B){
	return A>B?A:B;
}

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int nxt;
}e[N<<1];
int et=0,h[N];
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}

int n,k1,k2;

int rt;
int mx[N],mn[N];
ll dfs(int X,int FA){
	mx[X]=Max(mx[FA],X);
	mn[X]=Min(mn[FA],X);
	ll ret=(mn[X]>=(Min(X,rt)-k1))&&mx[X]<=(Max(X,rt)+k2)&&X>=rt;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v!=FA){
			ret+=dfs(e[i].v,X);
		}
	}
	return ret;
}
inline ll calc(int X){
	rt=X;
	for(int i=1;i<=n;++i){
		mx[i]=INF;
		mn[i]=0;
	}
	mn[0]=mx[0]=X;
	return dfs(X,0);
}

inline void slv1(){
	ll ans=0;
	for(int i=1;i<=n;++i){
		ans+=calc(i);
	}
	printf("%lld\n",ans);
}

inline void init(){
	scanf("%d%d%d",&n,&k1,&k2);
	int u,v;
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	if(n<=5000){
		slv1();
	}
}


int main(){
	init();
	return 0;
}