剑锋OI普及组多校联盟系列赛(20)解题报告(致敬2017第二学期最后一次模拟赛)

xiaoxiao2021-02-28  11

地址:http://swordoj.win/contest/49 第一题:模拟,但不能纯模拟,需要一点数学知识,我的思路就是先计算出一次命令的结果,再算出T秒可以执行几次命令,最后的余数特殊处理。 代码://平时没有整理代码的习惯,看起来有点乱

#include <bits/stdc++.h> using namespace std; int len,x=0,y=0; string ml; void move() { for(int i=0; i<len; i++) switch(ml[i]) { case 'E': x++; break; case 'S': y--; break; case 'W': x--; break; case 'N': y++; break; } } int main() { int ax=0,ay=0;//记录下一次行走的方位 cin>>ml>>len;//用字符串保存命令 for(int i=0; i<ml.length(); i++)//先执行一次 switch(ml[i]) { case 'E': ax++; break; case 'S': ay--; break; case 'W': ax--; break; case 'N': ay++; break; } int f=len/ml.length(); x=ax*f;//算出可以执行几次 y=ay*f;//同上 len%=ml.length()//算出还有几步没有走; move(); cout<<x<<" "<<y<<endl;//输出结果 return 0; }

第二题:刚看去觉得挺难的,但是经过分析就可以发现其实就是求[1,n]的所有素数,记为p[i]。对于每个p[i],求出最大的p[i]^k,满足p[i]^k<=n。把所有这些p[i]^k乘起来就是答案。 做的时候自己先写了普通筛素数法,后来把1e8放进去跑了半天愣是没出来。然后就想起曾经在NOIP吧看到的快速线性筛。 代码://数组很大,占用内存119M,要是限制内存再小些…

#include <bits/stdc++.h> #define mod 100000007 using namespace std; int n, cnt, p[11111111];//存储质数 bool vis[111111111]; int main() { cin>>n; long long ans = 1; for(int i = 2; i <= n; i++) {//快速筛法 if(!vis[i]) { p[cnt++] = i; for(long long s = i; s <= n; s *= i)//求p[i]^k ans = ans*i%mod;//每步取模 } for(int j = 0; j < cnt; j++) { long long v = i*p[j];//质数的倍数是合数 if(v > n) break; vis[v] = 1; if(i%p[j] == 0) break;//快速筛的精髓所在,防止同一个数字被重复筛除 } } cout<<ans<<endl; return 0; }

第三题:很感谢各位神牛,尤其是我们的胡老师,给我们提供了宝贵的思路:DP 大概思路就是先打个表,然后用滚动数组存储结果,最后输出.

代码://看了root的深搜,感觉…和Sooke大佬的代码异常相似?

#include<bits/stdc++.h> using namespace std; int i,j,k,t; int cho[35][35][55]; int main() { memset(cho,0x7f,sizeof(cho));//初始化极大值 for(i=1; i<=30; i++) for(j=1; j<=30; j++) if(j*i<=50) cho[i][j][j*i]=0;//如果是整块的当然不用切喽! for(i=1; i<=30; i++) for(j=1; j<=30; j++) for(k=1; k<=50; k++) { for(t=1; t<i; t++) {//按横着来切 cho[i][j][k]=min(cho[i][j][k],cho[i-t][j][k]+j*j);//不丢掉这一块,计算 if(k>t*j) cho[i][j][k]=min(cho[i][j][k],cho[i-t][j][k-t*j]+j*j);//丢掉这一块 } for(t=1; t<j; t++) {//竖着切 cho[i][j][k]=min(cho[i][j][k],cho[i][j-t][k]+i*i);//同上 if(k>i*t) cho[i][j][k]=min(cho[i][j][k],cho[i][j-t][k-i*t]+i*i); } } cin>>t; while(t--) {//打完表直接输出啦awa cin>>i>>j>>k; cout<<cho[i][j][k]<<endl; } return 0; }

第四题:看root的代码貌似是某种拓扑排序+二分?检测拓扑序列是否是一条直线?不是直线就返回false?神牛%%%,赛时想到过拓扑的,但是拓扑没有去仔细看过,所以就awa.

转载请注明原文地址: https://www.6miu.com/read-1650271.html

最新回复(0)