-
csp-202206
题目一：归一化处理【100分】
水题，直接上
AC代码：#includeusing namespace std; int N=1001; int main(){ int n=0,a[N]={0},sum=0; cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; sum+=a[i]; } //平均数 double aa=0,D=0,Da=0,fa=0,m=0; aa=(double)sum/n; for(int i=0;i<n;i++){ D+=pow(a[i]-aa,2); } //方差 Da=(double)D/n; //标准差 m=sqrt(Da); //printf("%.6lf\n", m); for(int i=0;i<n;i++){ fa=(double)(a[i]-aa)/m; printf("%.16lf\n", fa);//保留小数点后16位 } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
题目二：寻宝！大冒险！【100分】
- 简单的模拟题，枚举藏宝图的左下角对应的绿化图的位置，相当于切下来一个跟藏宝图大小一样的块儿，然后遍历整个藏宝图判断是否与这个块儿相同，相同就匹配成功得到一个宝藏
- 一开始想的是遍历整个绿化图来切块儿，但是数据规模为1e9，肯定超时，果不其然，最后只有40分，然后想办法进行优化，想办法去掉这两个循环，仔细读题发现每个藏宝图要求左下角一定是一个宝藏，所以枚举切块儿的时候左下角是1的才判断，即将绿化图中的所有有树的位置存起来，每次将有树的位置作为左下角
- 题目中所说的左下角要转变成二维数组里的(0,0)即左上角来进行存储和比对
40分的代码:
#include#include #include using namespace std; const int NUM=1000000000; int N,L,S; typedef pair<int,int>PII; map<PII,int>A; int B[52][52]; int main() { scanf("%d %d %d",&N,&L,&S); for(int i=0;i<N;i++) { int v,u; scanf("%d %d",&v,&u); A[{v,u}]=1; } for(int i=S;i>=0;i--) { for(int j=0;j<=S;j++) scanf("%d",&B[i][j]); } int sum=0; for(int i=0;i<=L-S;i++) //离左上角的偏移量 { for(int j=0;j<=L-S;j++) //这两重循环是导致超时的地方 { bool f=true; for(int m=0;m<=S;m++) { for(int n=0;n<=S;n++) { if(B[m][n]!=A[{m+i,n+j}]) { f=false;break; } } if(!f) break; } if(f) sum++; } } printf("%d",sum); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
AC代码：
#include#include #include #include using namespace std; const int NUM=1000000000; int N,L,S; typedef pair<int,int>PII; set<PII>A; int B[52][52]; int main() { scanf("%d %d %d",&N,&L,&S); for(int i=0;i<N;i++) { int v,u; scanf("%d %d",&v,&u); A.insert({v,u}); } for(int i=S;i>=0;i--) { for(int j=0;j<=S;j++) { scanf("%d",&B[i][j]); } } int sum=0; for(set<PII>::iterator it=A.begin();it!=A.end();it++) { int i=(*it).first; int j=(*it).second; if(i>L-S||j>L-S) continue; bool f=true; for(int m=0;m<=S;m++) { for(int n=0;n<=S;n++) { // printf("B：%d %d A：%d %d\n",m,n,m+i,n+j); int t=A.count({m+i,n+j}); if(B[m][n]&&!t||!B[m][n]&&t) //A和B不匹配 { // printf("%d %d\n",B[m][n],t); f=false;break; } } if(!f) break; } if(f) sum++; } printf("%d",sum); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
题目三：角色授权【100分】
- 大模拟题，我自己是边读题边在草稿纸上整理信息和思路，基本整理一遍题后就不用一直反复看题，看草稿重要信息，然后具体的授权判断和角色关联的规则才会回去读题
- 熟练使用set、map、及其常用方法：insert()、empty()、clear()
- 第一遍写完调试后提交只有70分，超时了，然后就是苦恼的优化过程，最大的耗时点就是遍历所有用户组，对每个用户组遍历所有的角色，判断该角色里是否有该用户组的关联，加上最外层的q，n* m* q，肯定TL，然后想一下，咱反过来存，我们不存角色对应的用户或者用户组，我们存用户或用户组对应的角色，那在这个地方，就直接可以得到某个用户组的全部角色了，不需要去遍历全部角色
- 然后再加上提升cin和cout输入输出速度的语句，（尝试用了scanf和printf，但是效果不咋样）: ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
- 最后。。90.。呜呜呜，还是被卡主了，再进行最后的挣扎：少写注释，少声明局部变量，少分支语句（多if语句合并写） ，代码尽量简洁,haha，刚好卡过
70分的代码：
#include#include #include #include using namespace std; int n,m,q; typedef map<string,set<string>> MSS; MSS Op; //角色能进行的操作 MSS Op_class; //角色能操作的资源种类 MSS Op_name; //角色能操作的资源名称 MSS User; //角色关联的用户 MSS Group; //角色关联的用户组 set<string> User_jue; //用户关联上的角色,保证存储不重复 int main() { cin>>n>>m>>q; //读入角色及其操作 for(int i=0;i<n;i++) { string name,op,op_class,op_name; int t; cin>>name; cin>>t; //读入操作清单 for(int j=0;j<t;j++) { cin>>op; Op[name].insert(op); } cin>>t; //读入操作资源种类 for(int j=0;j<t;j++) { cin>>op_class; Op_class[name].insert(op_class); } cin>>t; //读入操作资源名称 for(int j=0;j<t;j++) { cin>>op_name; Op_name[name].insert(op_name); } } //读入角色及角色关联 for(int i=0;i<m;i++) { string name,user,group; char c; int t; cin>>name; cin>>t; //读入关联用户或用户组 for(int j=0;j<t;j++) { cin>>c; if(c=='g') //读入用户组 { cin>>group; Group[name].insert(group); } else //读入用户 { cin>>user; User[name].insert(user); } } } for(int i=0;i<q;i++) { string name,op,op_class,op_name; int g_num; cin>>name>>g_num; //读入用户所属的组 bool f=false; //关联到角色,遍历所有角色，看哪个里面有该用户 for(MSS::iterator it=User.begin();it!=User.end();it++) { if(it->second.count(name)) //有该用户,将角色存起来 { User_jue.insert(it->first); f=true; } } for(int j=0;j<g_num;j++) { string group;cin>>group; //联到角色,遍历所有角色，看哪个里面有该用户所属的组 for(MSS::iterator it=Group.begin();it!=Group.end();it++) { if(it->second.count(group)) //有该用户组,将角色存起来 { User_jue.insert(it->first); f=true; } } } cin>>op; //读入操作 cin>>op_class; //读入资源种类； cin>>op_name; //读入资源名称 //该用户根本没有对应的角色，结束 if(!f) { cout<<0<<endl; continue; } f=false;; //遍历所有的角色，判断操作是否有权限 for(set<string>::iterator it=User_jue.begin();it!=User_jue.end();it++) { string jue=(*it); //检查操作清单 if(!Op[jue].count(op)&&!Op[jue].count("*")) { continue; } //检查资源种类 if(!Op_class[jue].count(op_class)&&!Op_class[jue].count("*")) { continue; } //检查资源名称 if(!Op_name[jue].count(op_name)&&Op_name[jue].size()!=0) { continue; } cout<<1<<endl; f=true; break; } User_jue.clear(); if(!f) cout<<0<<endl; } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
100分代码：
#include#include #include using namespace std; int n,m,q; typedef map<string,set<string>> MSS; MSS Op; MSS Op_class; MSS Op_name; set<string> User_jue; MSS g_jue; int i,j,t; string name,op,op_class,op_name,user; int main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin>>n>>m>>q; for(i=0;i<n;i++) { cin>>name; cin>>t; for(j=0;j<t;j++) { cin>>op; Op[name].insert(op); } cin>>t; for(j=0;j<t;j++) { cin>>op_class; Op_class[name].insert(op_class); } cin>>t; for(j=0;j<t;j++) { cin>>op_name; Op_name[name].insert(op_name); } } for(i=0;i<m;i++) { char c; cin>>name; cin>>t; for(j=0;j<t;j++) { cin>>c; cin>>user; g_jue[user].insert(name); } } for(i=0;i<q;i++) { cin>>name>>t; User_jue.insert(g_jue[name].begin(),g_jue[name].end()); for(j=0;j<t;j++) { cin>>user; User_jue.insert(g_jue[user].begin(),g_jue[user].end()); } cin>>op; cin>>op_class; cin>>op_name; if(User_jue.empty()) { cout<<0<<endl; continue; } set<string>::iterator it; for(it=User_jue.begin();it!=User_jue.end();it++) { string jue=(*it); if((!Op[jue].count(op)&&!Op[jue].count("*"))|| (!Op_class[jue].count(op_class)&&!Op_class[jue].count("*"))|| (!Op_name[jue].count(op_name)&&Op_name[jue].size()!=0)) { continue; } else break; } if(it==User_jue.end()) cout<<0<<endl; else cout<<1<<endl; User_jue.clear(); } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
优化心得：
优化超时：少循环卡时间：
*少写注释，少声明局部变量，少分支语句（多if语句合并写） ，代码尽量简洁
奋斗史：太南了
题目四：光线追踪【15分】
不行了，整不出来，写了半天拿了15分，运行错误，不知道哪里错了，网上找也没找到
采用的递归算法
15分AC代码：#include#include using namespace std; const int INF=10000000; typedef struct Node { int x1,y1,x2,y2; double a; int k; //斜率 int b; //截距 }*Mian,MianNode; map<int,Mian>All; int m,op; void output(int x,int y,int I) { if(I==0) cout<<0<<" "<<0<<" "<<0<<endl; else cout<<x<<" "<<y<<" "<<I<<endl; } void Turn(int x,int y,int d,double I,int t) { if(t==0) //时间为0，不继续走了 { output(x,y,I); return ; } if(I<1) //没必要再反射下去了 { cout<<0<<" "<<0<<" "<<0<<endl; return ; } if(d==0) //y保持不变，向x增加方向 { int min_index=0,min=INF; //y相同，找大于x的x最小的面 for(map<int,Mian>::iterator it=All.begin();it!=All.end();it++) { int xi=(y-it->second->b)/it->second->k; //交点坐标(xi,y) //只能在这个线段内 int minx=it->second->x1<it->second->x2?it->second->x1:it->second->x2; int maxx=it->second->x1>it->second->x2?it->second->x1:it->second->x2; if(xi<=x||xi<=minx||xi>=maxx) continue; if(xi<min) //找离得最近的 { min=xi; min_index=it->first; } } int xi=min; if((xi-x)<=t) //能到达这个面 { Mian p=All[min_index]; if(p->k>0) //斜率大于0,向上反射 { Turn(xi,y,1,I*p->a,t-(xi-x)); } else //斜率小于0，向下反射 { Turn(xi,y,3,I*p->a,t-(xi-x)); } } else //不能到达最近的反射面 { output(x+t,y,I); } } else if(d==1) //x保持不变，向y增加方向 { int min_index=0,min=INF; //x相同，找大于y的y最小的面 for(map<int,Mian>::iterator it=All.begin();it!=All.end();it++) { int yi=it->second->k*x+it->second->b; //交点坐标(x,yi) int miny=it->second->y1<it->second->y2?it->second->y1:it->second->y2; int maxy=it->second->y1>it->second->y2?it->second->y1:it->second->y2; if(yi<=y||yi<=miny||yi>=maxy) continue; if(yi<min) //找离得最近的 { min=yi; min_index=it->first; } } int yi=min; if((yi-y)<=t) //能到达这个面 { Mian p=All[min_index]; if(p->k>0) //斜率大于0,向右反射 { Turn(x,yi,0,I*p->a,t-(yi-y)); } else //斜率小于0，向左反射 { Turn(x,yi,2,I*p->a,t-(yi-y)); } } else //不能到达最近的反射面 { output(x,y+t,I); } } else if(d==2) //y保持不变，向x减小方向 { int max_index=0,max=-INF; //y相同，找小于等于x的x最大的面 for(map<int,Mian>::iterator it=All.begin();it!=All.end();it++) { int xi=(y-it->second->b)/it->second->k; //交点坐标(xi,y) int minx=it->second->x1<it->second->x2?it->second->x1:it->second->x2; int maxx=it->second->x1>it->second->x2?it->second->x1:it->second->x2; if(xi>=x||xi<=minx||xi>=maxx) continue; if(xi>max) //找离得最近的 { max=xi; max_index=it->first; } } int xi=max; if((x-xi)<=t) //能到达这个面 { Mian p=All[max_index]; if(p->k>0) //斜率大于0,向下反射 { Turn(xi,y,3,I*p->a,t-(x-xi)); } else //斜率小于0，向上反射 { Turn(xi,y,1,I*p->a,t-(x-xi)); } } else //不能到达最近的反射面 { output(x-t,y,I); } } else //x保持不变，向y减小方向 { int max_index=0,max=-INF; //x相同，找小于等于y的y最大的面 for(map<int,Mian>::iterator it=All.begin();it!=All.end();it++) { int yi=it->second->k*x+it->second->b; //交点坐标(x,yi) int miny=it->second->y1<it->second->y2?it->second->y1:it->second->y2; int maxy=it->second->y1>it->second->y2?it->second->y1:it->second->y2; if(yi>=y||yi<=miny||yi>=maxy) continue; if(yi>max) //找离得最近的 { max=yi; max_index=it->first; } } int yi=max; if((y-yi)<=t) //能到达这个面 { Mian p=All[max_index]; if(p->k>0) //斜率大于0,向左反射 { Turn(x,yi,2,I*p->a,t-(y-yi)); } else //斜率小于0，向右反射 { Turn(x,yi,0,I*p->a,t-(y-yi)); } } else //不能到达最近的反射面 { output(x,y-t,I); } } } int main() { cin>>m; for(int i=1;i<=m;i++) { cin>>op; if(op==1) //插入反射面 { int x1,y1,x2,y2; double a; cin>>x1>>y1>>x2>>y2>>a; int k=(y2-y1)/(x2-x1); int b=y1-k*x1; Mian p=new MianNode; p->k=k; p->b=b; p->x1=x1; p->y1=y1;p->x2=x2;p->y2=y2; p->a=a; All[i]=p; } else if(op==2) //删除反射面 { int k;cin>>k; All.erase(k); //按照键删除 } else //发射光源 { int x,y,d,t; double I; cin>>x>>y>>d>>I>>t; Turn(x,y,d,I,t); } } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
-
相关阅读:
02-MongoDB基本概念
2023 年 数维杯（D题）国际大学生数学建模挑战赛 |数学建模完整代码+建模过程全解全析
netty系列之: 在netty中使用 tls 协议请求 DNS 服务器
C++ Primer学习笔记-----附录：标准库
Sqlite安装配置及使用
HTTP协议
Mac中LaTex无法编译的问题
前端项目使用指定字体样式
【RL+Transformer综述】A Survey on Transformers in Reinforcement Learning论文笔记
SpringBoot整合JWT实现登录认证
- 原文地址：https://blog.csdn.net/m0_58642116/article/details/126675893