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.对极限和极端数据的分析不够深入,特别是在写对拍的时候,一定不要只注意程序在极限数据的结果,必须要先确保程序的运行时间在允许范围之内!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏tkokof 的技术,小趣及杂念

'24点'编码小感

之前看到了一道四则运算相关的程序题,遂而想到了24点游戏,觉得有趣,就想自己随手编写了一个,起初觉得应该比较简单,但实际的路途却并不平坦~

1062
来自专栏java一日一条

Java高级软件工程师面试考纲

如果要应聘高级开发工程师职务,仅仅懂得Java的基础知识是远远不够的,还必须懂得常用数据结构、算法、网络、操作系统等知识。因此本文不会讲解具体的技术,笔者综合自...

691
来自专栏熊二哥

.NET工作准备--01前言

01应聘须知(已过时) -1.了解软件开发大环境。 -2.准备简历:不宜超过一页,永远准备中文,模板。 -3.渠道:3大网站,中华英才,前程无忧(51job最...

2148
来自专栏Java编程技术

UML建模(类图)

类图是面向对象系统建模中重要的图,是定义其它图的基础。类图主要是用来展现软件系统中的类、接口以及它们之间的静态结构。

1312
来自专栏北京马哥教育

一文总结学习 Python 的 14 张思维导图

? 本文主要涵盖了 Python 编程的核心知识(暂不包括标准库及第三方库,后续会发布相应专题的文章)。 首先,按顺序依次展示了以下内容的一系列思维导图:基础...

4507
来自专栏斑斓

响应式编程的实践

作者 | 张逸 特别说明:本文包含大量代码片段,若要获得更好阅读观感,请点击文末“阅读原文”或访问我的博客。 响应式编程在前端开发以及Android开发中有颇多...

3858
来自专栏AI科技大本营的专栏

一文总结学习Python的14张思维导图

本文主要涵盖了 Python 编程的核心知识(暂不包括标准库及第三方库,后续会发布相应专题的文章)。 首先,按顺序依次展示了以下内容的一系列思维导图:基础知识,...

36010
来自专栏程序人生

如何愉快地写个小parser

(一) 在前几日的文章『软件随想录』里,我随性写了一句:「现在似乎已经不是lex/yacc 或 bison/flex的时代了。我亲眼看见一个同事在费力地用per...

5789
来自专栏Crossin的编程教室

【每周一坑】校验文件哈希

先说个通知,给参与了码上行动的同学:又一期展示学习成果的编程擂台活动开始了,即是练手的好机会,又能得到助教的全程支持,还可以得积分赢奖金。赶紧来报名吧!从课程首...

36111
来自专栏大数据钻研

Java高级软件工程师面试考纲

如果要应聘高级开发工程师职务,仅仅懂得Java的基础知识是远远不够的,还必须懂得常用数据结构、算法、网络、操作系统等知识。因此本文不会讲解具体的技术,笔者综合自...

34914

扫码关注云+社区

领取腾讯云代金券