2017 清北学堂 Day 6终极考试报告
预计分数： 100+70+70 = 240
实际假分数 ： 40+80+70= 190 in cena（好吧不得不承认这个分数，，，，，，=.=）
实际真分数 ： 100+80+100 = 280 in luogu.org
一句话：stl，cena害我一生，，，，，，
消失的数字(number)
Time Limit:1000ms Memory Limit:128MB
题目描述
rsy拥有n个数，这n个数分别是a1,a2,…,an。
后来出现了一个熊孩子zhw，用橡皮擦去了其中若干个数字，并且打乱了剩下的数字。rsy赶到现场后只剩下了m个数字b1,b2,…,bm，她想知道哪些数字被擦去了。
现在你需要告诉rsy被擦去的n-m个数是什么。
输入格式(number.in)
第一行一个数n，第二行n个数ai，表示一开始的数字。
第三行一个数m，第四行m个数bi，表示被擦去后的数字。
输出格式(number.out)
一行n-m个数，从小到大输出所有被擦去的数字。
输入样例
5
1 3 5 7 8
3
3 5 8
输出样例
1 7
数据范围
对于30%的数据n<=1000，ai与bi都是有序的。
对于60%的数据n<=100000，ai与bi都是有序的。
对于80%的数据n<=100000，ai,bi<=n。
对于100%的数据n<=100000，1<=ai,bi<=10^9。
一开始傻乎乎的以为这是一眼题，随手敲了个map+栈感觉肯定AC，然后敲了个vector的暴力开始对拍，各种极端极限数据都没问题
结果！！！！
我还是高估cena了....
60分的超时也是醉了。。。。
在洛谷上最慢的点才700ms，，，，，
╮(╯▽╰)╭，，认命，，，，
正确做法：把两个数组都从小到大排一遍然后在A里把B中出现过得元素都删掉就好
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<queue>
6 #include<stack>
7 #include<cmath>
8 #include<map>
9 using namespace std;
10 int n,m;
11 int p;
12 map<int,int>a;
13 int maxn=-1;
14 int ans[100001];
15 int num=1;
16 int s[100001];
17 int top=1;
18 int main()
19 {
20 //freopen("number.in","r",stdin);
21 //freopen("number.out","w",stdout);
22 scanf("%d",&n);
23 for(int i=1;i<=n;i++)
24 {
25 scanf("%d",&p);
26 a[p]=a[p]+1;
27 if(p>maxn)maxn=p;
28 s[top]=p;top++;
29 }
30 scanf("%d",&m);
31 for(int i=1;i<=m;i++)
32 {
33 scanf("%d",&p);
34 a[p]=a[p]-1;
35 }
36 int q=a.size();
37 while(top!=0)
38 {
39 int p=s[top];top--;
40 if(a[p]!=0)
41 {
42 for(int i=1;i<=a[p];i++)
43 ans[num++]=p;
44 a[p]=0;
45 }
46 }
47 sort(ans+1,ans+num);
48 for(int i=1;i<=num-1;i++)
49 printf("%d ",ans[i]);
50 return 0;
51 } 1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<algorithm>
5 using namespace std;
6 int n,m;
7 int a[100001];
8 int b[100001];
9 int num=1;
10 int main()
11 {
12 scanf("%d",&n);
13 for(int i=1;i<=n;i++)
14 scanf("%d",&a[i]);
15 scanf("%d",&m);
16 for(int i=1;i<=m;i++)
17 scanf("%d",&b[i]);
18 sort(a+1,a+n+1);sort(b+1,b+m+1);
19 for(int i=1;i<=n;i++)
20 {
21 if(a[i]==b[num])
22 {
23 a[i]=0;
24 num++;
25 }
26 }
27 for(int i=1;i<=n;i++)
28 {
29 if(a[i]!=0)
30 {
31 printf("%d ",a[i]);
32 }
33 }
34 return 0;
35 }一道数论好题(math)
Time Limit:1000ms Memory Limit:128MB
题目描述
rsy最近在研究欧几里得算法，不会的同学可以去看下课件以及代码……
现在她想到了一个新的问题，求k个数的最大公约数！
事实上这个问题仍然很简单。所以rsy想强化一下，她觉得最大公约数等于1就不是很有趣了。因此她想在n个数中找最多的数，使得它们的最大公约数不等于1。
现在rsy想知道，能找最多多少个数。
输入格式(math.in)
第一行一个数n。
第二行n个数ai。
输出格式(math.out)
一个数表示答案。
输入样例
5
2 3 4 5 6
输出样例
3
数据范围
对于30%的数据n<=5。
对于50%的数据n<=20。
对于80%的数据n<=1000,ai<=1000。
对于100%的数据1<=n<=100000,1<=ai<=100000，数据几乎是随机的。
当我读完题立马就意思到- - > 骗分狗又要高兴咯=。=
为什么累?
因为这道题是让着求最大公约数
而偶数（也就是%2==0）是最普遍的最大公约数（因为自然数除了奇数就是偶数）
so 如果你能想到把%2==0的数的个数统计一下
那么恭喜你得到70分
但我还是没有这么不要脸滴
so我机智的选择用1000以内的素数筛（感觉自己更不要脸）
然而最后两个点一个莫名其妙的WA一个莫名其妙的TLE.......
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<queue>
6 #include<stack>
7 #include<cmath>
8 using namespace std;
9 int a[100001];
10 int num=0;
11 int vis[100001];
12 int tot[100001];
13 int xx[100001];
14 int js=0;
15 int main()
16 {
17 for(int i=2;i<=sqrt(100000);i++)
18 if(vis[i]==0)
19 for(int j=i*i;j<=100000;j=j+i)
20 vis[j]=1;
21 for(int i=1;i<=10000;i++)
22 if(vis[i]==0)
23 xx[++js]=i;
24 int n;
25 scanf("%d",&n);
26 for(int i=1;i<=n;i++)
27 {
28 int p;
29 scanf("%d",&p);
30 a[++num]=p;
31 }
32 for(int i=2;i<=js;i++)
33 {
34 for(int j=1;j<=num;j++)
35 {
36 if(a[j]%xx[i]==0)
37 tot[xx[i]]++;
38 }
39 }
40 int maxn=0;
41 for(int i=0;i<js;i++)
42 {
43 if(tot[xx[i]]>maxn)
44 maxn=tot[xx[i]];
45 }
46 printf("%d",maxn);
47 return 0;
48 } 1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 int a[1000001];
6 int main()
7 {
8 int n;
9 scanf("%d",&n);
10 for(int i=1;i<=n;i++)
11 {
12 int p;
13 scanf("%d",&p);
14 a[p]++;
15 }
16 int ans=-1;
17 for(int i=2;i<=100000;i++)
18 {
19 int maxnnow=0;
20 for(int j=i;j<=100000;j=j+i)
21 maxnnow+=a[j];
22 if(maxnnow>ans)
23 ans=maxnnow;
24 }
25 printf("%d",ans);
26 return 0;
27 }扫雷(mine)
Time Limit:1000ms Memory Limit:128MB
题目描述
rsy最近沉迷于一款叫扫雷的游戏。
这个游戏是这样的。一开始网格上有n*m个位置，其中有一些位置有雷。每次rsy可以左键点击一个方块，此时若这个方块是雷，则rsy被炸，游戏结束，否则如果这个位置周围8格有x个雷，则会显示数字x。特别地，当x=0时，系统会自动左键点击附近8个位置。（此时附近8个位置一定没有雷，假如附近8个位置仍存在x=0，则继续往外扩展）想要更进一步获得关于题目的信息，打开程序->附近->游戏->扫雷或者直接打开下发的可执行文件。
或者rsy右键点击一个位置，标注这个位置是雷。
不幸的是，她鼠标不能左右键同时点击，因此只需考虑她左键点击与右键点击就可以了。
注意游戏胜利的条件是所有非雷的位置都被左键点击到。（特别地，当一开始时n*m个位置都是雷时，LYK自动获得胜利）
rsy从网上下载了金手指，很轻易地就掌握了所有雷所在的位置。rsy想通过最少的点击次数获得胜利（这里的点击次数不包括系统自动点击）。于是他来请求你的帮助。
输入格式(mine.in)
第一行两个数n,m。
接下来n行，每行m个数ai,j，表示这个矩阵。若ai,j=’*’则表示这个位置是雷，若ai,j=’.’则表示不是雷。
输出格式(mine.out)
一个数表示答案。
输入样例
3 3
..*
...
..*
输出样例
2
对于30%的数据n=1;
对于另外20%的数据n,m<=3；
对于再另外20%的数据*大致占矩阵的2/3且数据随机。
对于100%的数据n,m<=1000。
Hint：
适度游戏益脑，沉迷游戏伤身。ok
一开始看这题还是有些懵逼的，但是手动过了一把扫雷之后就明白了
只要照着0一顿乱点就可以了呗。。。
然而！！！！
因为搜索需要，我机（tou）智（lan）的开了4个queue队列，
结果，，，，
最后三个点超时。。。。。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<queue>
6 #include<stack>
7 #include<cmath>
8 using namespace std;
9 int n,m;
10 int a[1001][1001];
11 int vis[1001][1001];
12 char p;
13 int xx[10]={-1,+1,0,0,-1,-1,+1,+1};
14 int yy[10]={0,0,-1,+1,-1,+1,-1,+1};
15 queue<int>qx;
16 queue<int>qy;
17 int ans=0;
18 void deal(int nowx,int nowy)
19 {
20 queue<int>needx;
21 queue<int>needy;
22 needx.push(nowx);
23 needy.push(nowy);
24 while(needx.size()!=0&&needy.size()!=0)
25 {
26 int nowneedx=needx.front();needx.pop();//当前为0的元素
27 int nowneedy=needy.front();needy.pop();
28 for(int i=0;i<8;i++)
29 {
30 int wx=nowneedx+xx[i];
31 int wy=nowneedy+yy[i];
32 if(wx>=1&&wx<=n&&wy>=1&&wy<=m)
33 {
34 if(a[wx][wy]==0&&vis[wx][wy]==0)
35 {
36 needx.push(wx);
37 needy.push(wy);
38 }
39 vis[wx][wy]=1;
40 }
41
42 }
43 }
44
45 }
46 int main()
47 {
48 scanf("%d%d",&n,&m);
49 for(int i=1;i<=n;i++)
50 for(int j=1;j<=m;j++)
51 {cin>>p; if(p=='*') a[i][j]=438;}
52 for(int i=1;i<=n;i++)
53 {
54 for(int j=1;j<=m;j++)
55 {
56 for(int k=0;k<8;k++)
57 {
58 if(a[i][j]!=438&&a[i+xx[k]][j+yy[k]]==438&&i+xx[k]>=1&&i+xx[k]<=n&&j+yy[k]>=1&&j+yy[k]<=m)
59 a[i][j]++;
60 }
61 if(a[i][j]==0&&vis[i][j]==0)
62 {qx.push(i);qy.push(j);vis[i][j]=1;}
63 }
64 }
65 memset(vis,0,sizeof(vis));
66 while(qx.size()!=0&&qy.size()!=0)
67 {
68 int nowx=qx.front();qx.pop();
69 int nowy=qy.front();qy.pop();
70 if(vis[nowx][nowy]==0)
71 {
72 ans++;
73 vis[nowx][nowy]=1;
74 deal(nowx,nowy);
75 }
76 }
77 for(int i=1;i<=n;i++)
78 {
79 for(int j=1;j<=m;j++)
80 {
81 if(vis[i][j]==0&&a[i][j]!=438)
82 ans++;
83 }
84 }
85 printf("%d",ans);
86 return 0;
87 }总结：这次考试终于发挥出真正水平了，但成绩仍然一般，，。，。虽然原因很多吧，但是也反映出了我的很多弱点:
1.思路太窄，第一题明明可以想到O（n*m）的做法，但是自己还是明知map慢偏用map做，其实有时候完全可以不用使劲照着一种思路走到死胡同，说不定换个角度就是海阔天空呢？
2.对极限和极端数据的分析不够深入，特别是在写对拍的时候，一定不要只注意程序在极限数据的结果，必须要先确保程序的运行时间在允许范围之内！