首页 > 代码库 > 2017.7.15清北夏令营精英班Day1解题报告
2017.7.15清北夏令营精英班Day1解题报告
成绩：
预计分数：20+10+40
实际分数：100+10+40.
一百三十多人的比赛全场rand7还水了个鼠标+键盘
unbelievable！
考试题目链接：
https://www.luogu.org/team/show?teamid=1353
T1
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<queue> 7 #include<stack> 8 #define lli long long 9 using namespace std;10 const int mod=998244353;11 void read(int &n)12 {13 char c=‘+‘;int x=0;bool flag=0;14 while(c<‘0‘||c>‘9‘){c=getchar();if(c==‘-‘)flag=1;}15 while(c>=‘0‘&&c<=‘9‘)16 x=(x<<1)+(x<<3)+c-48,c=getchar();17 flag==1?n=-x:n=x;18 }19 lli n,m;20 int fastmul(int x,int p)21 {22 int now=x;23 int ans=0;24 while(p)25 {26 if(p&1)27 {28 --p;29 ans=(ans+now)%mod;30 }31 p>>=1;32 now=(now+now)%mod;33 }34 return (ans-1)%mod;35 }36 int main()37 {38 freopen("bpmp.in","r",stdin);39 freopen("bpmp.out","w",stdout);40 //read(n);read(m);41 cin>>n>>m;42 cout<<fastmul(n,m)%mod;43 return 0;44 }
一开始搞了个贪心不知道对不对，所以不期望能拿多少分，但没想到居然AC了
而且我以为这个题没有那么水于是就写了个快速乘、
事实上只要输出(n*m-1)%mod 就能AC，
（表示差点被卡成rank8,没奖）
http://www.cnblogs.com/zwfymqz/p/7186080.html
T2
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<queue> 7 #include<stack> 8 #include<cstdlib> 9 using namespace std; 10 inline void read(int &n) 11 { 12 char c=‘+‘;int x=0;bool flag=0; 13 while(c<‘0‘||c>‘9‘){c=getchar();if(c==‘-‘)flag=1;} 14 while(c>=‘0‘&&c<=‘9‘) 15 x=(x<<1)+(x<<3)+c-48,c=getchar(); 16 flag==1?n=-x:n=x; 17 } 18 int n,m; 19 struct node 20 { 21 int a[101][101]; 22 int nowmaxn; 23 int bgx,bgy,edx,edy; 24 }now,nxt; 25 int ans=-0x7ffff; 26 queue<node>q; 27 int tot=0; 28 inline void calc() 29 { 30 /*memset(nxt.a,0,sizeof(nxt.a)); 31 for(int i=now.bgx;i<=now.edx;i++) 32 for(int j=now.bgy;j<=now.edy;j++) 33 nxt.a[i][j]=now.a[i][j];*/ 34 nxt=now; 35 } 36 inline void print() 37 { 38 39 for(int i=now.bgx;i<=now.edx;i++) 40 { 41 for(int j=now.bgy;j<=now.edy;j++) 42 printf("%d ",now.a[i][j]); 43 printf("\n"); 44 } 45 printf("*********************************\n"); 46 } 47 inline void getans() 48 { 49 for(int i=now.bgx;i<=now.edx;i++) 50 for(int j=now.bgy;j<=now.edy;j++) 51 ans=max(ans,now.a[i][j]); 52 } 53 void check() 54 { 55 tot++; 56 //cout<<tot<<"---"<<endl; 57 if(tot>63843800) 58 { 59 cout<<ans; 60 exit(0); 61 } 62 63 } 64 inline void bfs(int hc,int lc) 65 { 66 q.push(now); 67 while(!q.empty()) 68 { 69 now=q.front(); 70 q.pop(); 71 int num=0; 72 for(int i=now.bgx;i<=now.edx;i++) 73 for(int j=now.bgy;j<=now.edy;j++) 74 if(now.a[i][j]>0) 75 num+=now.a[i][j],check(); 76 if(ans>num) 77 continue; 78 79 getans(); 80 calc(); 81 // print(); 82 for(int i=now.bgy;i<now.edy;i++)//横向折叠 83 { 84 for(int j=1;j<=(min((i-now.bgy),(now.edy-i))+1);j++) 85 { 86 for(int k=1;k<=now.edx;k++) 87 { 88 nxt.a[k][i+j]+=nxt.a[k][i-j+1]; 89 nxt.a[k][i-j+1]=0; 90 check(); 91 } 92 } 93 // cout<<now.bgy<<"&"<<i<<endl; 94 nxt.bgy=i+1; 95 // cout<<nxt.bgy<<"^"<<endl; 96 nxt.edy=max(now.edy,i+i-now.bgy+1); 97 nxt.bgx=now.bgx; 98 nxt.edx=now.edx; 99 q.push(nxt);100 calc();101 }102 for(int i=now.bgx;i<now.edx;i++)103 {104 for(int j=1;j<=(min((i-now.bgx),(now.edx-i+1))+1);j++)105 {106 for(int k=1;k<=now.edy;k++)107 {108 nxt.a[i+j][k]+=nxt.a[i-j+1][k];109 nxt.a[i-j+1][k]=0;110 check();111 }112 }113 nxt.edy=now.edy;114 nxt.bgy=now.bgy;115 nxt.bgx=i+1;116 nxt.edx=max(now.edx,i+i-now.bgx+1);117 q.push(nxt);118 calc();119 }120 }121 122 }123 int main()124 {125 freopen("cfyw.in","r",stdin);126 freopen("cfyw.out","w",stdout);127 read(n);read(m);128 for(int i=1;i<=n;i++)129 for(int j=1;j<=m;j++)130 read(now.a[i][j]);131 now.bgx=now.bgy=1;132 now.edx=n;133 now.edy=m;134 bfs(0,0);135 printf("%d",ans);136 return 0;137 }
一开始以为是矩阵什么乱七八糟的肯定不会于是就写超级暴力广搜，
本来以为能过50%的数据结果发现连4*4的都跑不出来。
没办法加了个最优性剪枝又加了个卡时，
结果。
除了第一个点AC其他全MLE,,,,,,,,,,,,,
What‘ a pity！
http://www.cnblogs.com/zwfymqz/p/7185970.html
T3
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<queue> 7 #include<stack> 8 #define lli long long int 9 using namespace std;10 inline void read(int &n)11 {12 char c=‘+‘;int x=0;bool flag=0;13 while(c<‘0‘||c>‘9‘){c=getchar();if(c==‘-‘)flag=1;}14 while(c>=‘0‘&&c<=‘9‘)15 x=(x<<1)+(x<<3)+c-48,c=getchar();16 flag==1?n=-x:n=x;17 }18 int mod=998244353; 19 int n,m;20 int ans=0;21 int gcd(int a,int b)22 {23 return b==0?a%mod:gcd(b,a%b)%mod;24 }25 int hash[40000001];26 int main()27 {28 //freopen("hoip.in","r",stdin);29 // freopen("hoip.out","w",stdout);30 read(n);read(m);31 if(n<4000&&m<4000)32 {33 for(int i=1;i<=n;i++)34 for(int j=1;j<=m;j++)35 ans=(ans+gcd(i,j))%mod;36 printf("%d",ans%mod);37 }38 else if(n>6001&&m>6001)39 {40 printf("0");41 }42 else43 {44 for(int i=1;i<=n;i++)45 for(int j=1;j<=m;j++)46 {47 if(hash[(i*257)%23456789+(j*359)%23456789])48 {49 ans+=hash[(i*257)%23456789+(j*359)%23456789];50 continue;51 }52 lli p=gcd(i,j)%mod;53 lli a=i,b=j;54 while(a<n&&b<m)55 {56 p=p+p;57 a=a+a;58 b=b+b;59 hash[(i*257)%23456789+(j*359)%23456789]=p;60 }61 }62 printf("%d",ans);63 }64 return 0;65 }
暴力暴力暴力！！！
http://www.cnblogs.com/zwfymqz/p/7189521.html
总结：
这次考试也是比较无语，
感觉自己运气成分比较大，
全场40多个140分.......
也就是说T2接近150行的暴力救了我一命=.=///
不过我们学校居然有A了T3的（但那孩子T1炸了。。。）
以后继续努力吧！
2017.7.15清北夏令营精英班Day1解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。