分类： CSP

A

依照题意，推式子得到欲使平均值归一化，只须：

其中 $avg$ 是原平均值。

欲使方差归一化，只须在上文的基础上：

其中 $sqr$ 是原方差。

#include<iostream>
#include<cmath>
const int N = 1005;
int n;
double a[N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%lf",a + i);
	}
	double avg = 0;
	for(int i=1;i<=n;++i){
		avg += a[i];
	}
	avg /= n;
	for(int i=1;i<=n;++i){
		a[i] -= avg;
	}
	double sqr = 0;
	for(int i=1;i<=n;++i){
		sqr += a[i] * a[i];
	}
	double dlt = std::sqrt(n / sqr);
	for(int i=1;i<=n;++i){
		a[i] *= dlt;
	}
	for(int i=1;i<=n;++i){
		printf("%.20lf\n",a[i]);
	}
	return 0;
}

 

B

观察到 $S$ 较小，我们只需要存储每个点作为左下角，其右上 $S * S$ 区域的情况即可。

之后暴力校验即可。

#include<iostream>
#include<cmath>
const int N = 2005;
int n,L,s;
int locx[N],locy[N],mp[N][55][55],sd[55][55];
int main(){
	scanf("%d%d%d",&n,&L,&s);
	int nx,ny;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&nx,&ny);
		mp[i][0][0]=1;
		for(int j=1;j<i;++j){
			if(nx>=locx[j]&&ny>=locy[j]&&nx-locx[j]<=50&&ny-locy[j]<=50){
				mp[j][nx-locx[j]][ny-locy[j]]=1;
			}
			if(nx<=locx[j]&&ny<=locy[j]&&locx[j]-nx<=50&&locy[j]-ny<=50){
				mp[i][-nx+locx[j]][-ny+locy[j]]=1;
			}
		}
		locx[i]=nx,locy[i]=ny;
	}
	for(int i=0;i<=s;++i){
		for(int j=0;j<=s;++j){
			scanf("%d",&sd[s-i][j]);
		}
	}
//	for(int i=1;i<=n;++i){
//		for(int j=0;j<=s;++j){
//			for(int k=0;k<=s;++k){
//				printf("%d ",mp[i][j][k]);
//			}
//			puts("");
//		}
//	}
	int ans=0;
	for(int i=1;i<=n;++i){
		bool bo=0;
		if(locx[i]+s>L || locy[i]+s>L){
			continue;
		}
		for(int j=0;j<=s;++j){
			for(int k=0;k<=s;++k){
				if(sd[j][k]!=mp[i][j][k]){
					bo=1;break;
				}
			}
		}
		if(!bo){
			++ans;
		}
	}
	printf("%d\n",ans);
	
}

 

C

依题意模拟即可。需要注意的是数据范围较大，因此需要调整次序，并采用 map 或 unordered_map 等结构维护映射。

#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<string>
using namespace std;
struct Character{
	set<string> v, o, n;
	bool opVaild(string oper, string type, string name) {
		return (v.count(oper) || v.count("*")) && (o.count(type) || o.count("*")) && (n.count(name) || n.empty());
	}
};
map<string, Character> cL;
map< string, vector<string> > uL, gL;
int n,m,q;
set<string> nowC;
void init(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;++i){
		string nowName;
		int X; string S;
		cin>>nowName;
		scanf("%d",&X);
		for(int j=1;j<=X;++j){
			cin>>S;
			cL[nowName].v.insert(S);
		}
		scanf("%d",&X);
		for(int j=1;j<=X;++j){
			cin>>S;
			cL[nowName].o.insert(S);
		}
		scanf("%d",&X);
		for(int j=1;j<=X;++j){
			cin>>S;
			cL[nowName].n.insert(S);
		}
	}
	for(int i=1;i<=m;++i){
		string s1, s2;
		char typ[2];
		int ns;
		cin>>s1>>ns;
		for(int j=1;j<=ns;++j){
			cin>>typ>>s2;
			if(typ[0]=='u'){
				uL[s2].push_back(s1);
			}else{
				gL[s2].push_back(s1);
			}
		}
	}
	for(int i=1;i<=q;++i){
		nowC.clear();
		string uN,gN,op,typ,sou;
		int ng;
		cin>>uN>>ng;
		nowC.insert(uL[uN].begin(), uL[uN].end());
		for(int i=1;i<=ng;++i){
			cin>>gN;
			nowC.insert(gL[gN].begin(), gL[gN].end());
		}
		cin>>op>>typ>>sou;
		bool bo=0;
		for(auto it=nowC.begin();it!=nowC.end();++it){
//			puts((*it).c_str());
			bo|=cL[*it].opVaild(op, typ, sou);
			if(bo){
				break;
			}
		}
		puts(bo?"1":"0");
	}
}
int main(){
	init();
}

D

注意到数据范围中有信息的点数量较少，我们可以暴力维护每个点。

首先用一个能维护映射的数据结构（如哈希或者平衡树）离散化每行/每列，于是问题转化为求前驱或后继，只须再套上一个平衡树即可。均可使用 std::map 实现。

之后，对每个询问暴力模拟即可。算一下对数发现折射的次数是较少的。

#include<iostream>
#include<map>
#include<cmath>
using namespace std;
const int N=100005;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
struct Face{
	int x1,y1,x2,y2,dir;
	double a;
}f[N];
int m;
map< int,map<int,int> > mx,my;
void prnt(int X,int Y,double I){
	printf("%d %d %d\n",X,Y,(int)I);
}
int dD(int D,int dlt){
	return (D + 4 + dlt) % 4;
}
void srch(int X,int Y,int D,double I,int T){
	if(I <= 1.0 - 1e-10){
		prnt(0,0,0);
		return;
	}
//	printf("%d %d %d %lf %d\n", X, Y, D, I, T);
	switch(D){
		case 0:{
			auto it = my[Y].upper_bound(X);
			if(it == my[Y].end() || it -> first - X > T) {
				prnt(X+T, Y, I);
				return;
			}
			int id = it->second;
			srch(it->first, Y, dD(D, (f[id]).dir), I*(f[id]).a, T - (it->first - X));
			break;
		}
		case 1:{
			auto it = mx[X].upper_bound(Y);
			if(it == mx[X].end() || it -> first - Y > T) {
				prnt(X, Y+T, I);
				return;
			}
			int id = it->second;
			srch(X, it->first, dD(D, -(f[id]).dir), I*(f[id]).a, T - (it->first - Y));
			break;
		}
		case 2:{
			auto it = my[Y].lower_bound(X);
			if(my[Y].empty() || it == my[Y].begin()){
				prnt(X-T, Y, I);
				return;
			}
			--it;
			if(X - it->first > T){
				prnt(X-T, Y, I);
				return;
			}
			int id = it->second;
			srch(it->first, Y, dD(D, (f[id]).dir), I*(f[id]).a, T - (X - it->first));
			break;
		}
		case 3:{
			auto it = mx[X].lower_bound(Y);
			if(mx[X].empty() || it == mx[X].begin()){
				prnt(X, Y-T, I);
				return;
			}
			--it;
//			printf("%d %d\n",it->first, it->second);
			if(Y - it->first > T){
				prnt(X, Y-T, I);
				return;
			}
			int id = it->second;
			srch(X, it->first, dD(D, -(f[id]).dir), I*(f[id]).a, T - (Y - it->first));
			break;
		}
	}
}
void init(){
	scanf("%d",&m);
	for(int i=1;i<=m;++i){
		int op;
		scanf("%d",&op);
		if(op==1){
			int nx1,nx2,ny1,ny2,dir;double a;
			cin>>nx1>>ny1>>nx2>>ny2>>a;
			if(nx1>nx2){
				swap(nx1,nx2);swap(ny1,ny2);
			}
			dir=1ll*(nx1-nx2)*(ny1-ny2)>0?1:-1;
			f[i]=(Face){nx1,ny1,nx2,ny2,dir,a};
			for(int j=nx1+1,k=ny1+dir;j<nx2;++j,k+=dir){
				mx[j][k] = i;my[k][j] = i;
			}
		}else if(op==2){
			int x;
			scanf("%d",&x);
			for(int j=f[x].x1+1,k=f[x].y1+f[x].dir;j<f[x].x2;++j,k+=f[x].dir){
				mx[j].erase(k);my[k].erase(j);
			}
		}else{
			int x,y,d,t;double I;
			scanf("%d%d%d%lf%d",&x,&y,&d,&I,&t);
			srch(x,y,d,I,t);
		}
	}
}


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

 

E

线段树/分块维护矩阵乘法。

据称 $n * q$ 亦可通过此题。

#include<iostream>
#include<cstdio>
#include<cmath>
const int N=500005;
int n,q;
struct Point{
	double x,y;
	
	Point operator+(const Point &B)const{
		return (Point){x+B.x,y+B.y};
	}
	
	Point operator-(const Point &B)const{
		return (Point){x-B.x,y-B.y};
	}
	
	Point operator+=(const Point &B){
		*this = *this + B;
		return *this;
	}
	
	Point operator-=(const Point &B){
		*this = *this - B;
		return *this;
	}
	
	Point operator-(){
		return (Point){0, 0} - *this;
	}
	
	void pRot(const Point &B, double theta){
		Point C = *this - B;
		double ct = cos(theta), st = sin(theta);
		C = (Point){C.x * ct - C.y * st, C.x * st + C.y * ct};
		C += B;
		x=C.x,y=C.y;
	}
	void pScale(const Point &B, double lamb){
		Point C = *this - B;
		C.x *= lamb, C.y *= lamb;
		C += B;
		x=C.x,y=C.y;
	}
	void pShot(double theta, double y0){
		double k0 = tan(theta);
		double sx = 1 / sqrt(k0 * k0 + 1);
		double sy = k0 * sx;
		y -= y0;
		double len = x * sx + y * sy;
		x = sx * len, y = sy * len;
		y += y0;
	}
	void pMirr(double theta, double y0){
		Point C = *this;C.pShot(theta, y0);
		pScale(C, -1);
	}
}p[N];

void slv1(){
	for(int i=1;i<=q;++i){
		int op,l,r;
		scanf("%d%d%d",&op,&l,&r);
		switch(op){
			case 1:{
				double x,y;
				scanf("%lf%lf",&x,&y);
				for(int j=l;j<=r;++j){
					p[j] += (Point){x,y};
				}
				break;
			}
			case 2:{
				double x,y,theta;
				scanf("%lf%lf%lf",&x,&y,&theta);
				for(int j=l;j<=r;++j){
					p[j].pRot((Point){x,y}, theta);
				}
				break;
			}
			case 3:{
				double x,y,lamb;
				scanf("%lf%lf%lf",&x,&y,&lamb);
				for(int j=l;j<=r;++j){
					p[j].pScale((Point){x,y}, lamb);
				}
				break;
			}
			case 4:{
				double theta, y0;
				scanf("%lf%lf",&theta,&y0);
				for(int j=l;j<=r;++j){
					p[j].pMirr(theta, y0);
				}
				break;
			}
			case 5:{
				double theta, y0;
				scanf("%lf%lf",&theta,&y0);
				for(int j=l;j<=r;++j){
					p[j].pShot(theta, y0);
				}
				break;
			}
			case 6:{
				double x=0,y=0;
				int len=r-l+1;
				for(int j=l;j<=r;++j){
					x+=p[j].x;y+=p[j].y;
				}
				printf("%.10lf %.10lf\n",x/len,y/len);
				break;
			}
			case 7:{
				double x=0,y=0,x2=0,y2=0;
				double A,B;int len=r-l+1;
				scanf("%lf%lf",&A,&B);
				for(int j=l;j<=r;++j){
					x+=p[j].x;y+=p[j].y;x2+=p[j].x*p[j].x;y2+=p[j].y*p[j].y;
				}
				printf("%.10lf\n",x2+y2-2*A*x-2*B*y+A*A*len+B*B*len);
				break;
			}
		}
	}
}

int main(){
//	freopen("./E/5.in","r",stdin);
//	freopen("./E/5.out","w",stdout);
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i){
		scanf("%lf%lf",&p[i].x,&p[i].y);
	}
	slv1();
}

 

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;
}