第 26 次 CCF 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();
}