第 26 次 CCF CSP 题解
A
依照题意，推式子得到欲使平均值归一化，只须：
其中
欲使方差归一化，只须在上文的基础上：
其中
#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
观察到
之后暴力校验即可。
#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
线段树/分块维护矩阵乘法。
据称
#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();
}
