4.7生日当天测

4.7生日当天测

先：

今天生日，他们sx，我也考试。

今天挺开心的，死兔子给我带了饺子，lwl妹妹做的蛋糕盒子真的是很好吃。

sx成绩到现在肯定是出来了。

我，，，为什么要hh。。。

T1：

题目描述

rsy拥有n个数，这n个数分别是a1,a2,…,an。 后来出现了一个熊孩子zhw，用橡皮擦去了其中若干个数字，

并且打乱了剩下的数字。rsy赶到现场后只剩下了m个数字b1,b2,…,bm，她想知道哪些数字被擦去了。

现在你需要告诉rsy被擦去的n-m个数是什么。

输入输出格式

输入格式：

 

第一行一个数n，

第二行n个数ai，表示一开始的数字。

第三行一个数m，

第四行m个数bi，表示被擦去后的数字。

 

输出格式：

 

一行n-m个数，从小到大输出所有被擦去的数字。

 

输入输出样例

输入样例#1： 复制

5
1 3 5 7 8
3
3 5 8

输出样例#1： 复制

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

 

 

听说这是去年五月份的清北基础题，，我好像，应该不会AC。

因为我想不到。

 

官方上交解题报告如下：

 

题意看起来比较简单，那就定义两个数组a，b，一个记录一开始的数字，

另一个记录被擦去后的数字。一般来说b数组要比a数组小。首先是输入，

记住排序。因为数组长度不一样，比较简单的是按长的那个为基准来判断。

所以首先定义一个变量x，初始值为1，记录b数组下标。从i=1到i=n，

那个长的数组来循环。因为先前已经排好序了，所以从最小的开始判断，

如果a[i]和b[x]相等的话，那说明这个数没有被擦去，所以x++，继续循环，

看下一个数，如果a[i]和b[x]不相等，那就说明a[i]这个数已经被擦去了，

此时输出a[i]。继续循环。

完毕。

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 int n,m;
 7 long long a[100002],b[100002];
 8 int main()
 9 {
10     //freopen("number.in","r",stdin);
11     //freopen("number.out","w",stdout);
12     scanf("%d",&n);
13     for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
14     sort(a+1,a+n+1);
15     scanf("%d",&m);
16     for(int i=1;i<=m;++i) scanf("%lld",&b[i]);
17     sort(b+1,b+m+1);
18     int x=1;
19     for(int i=1;i<=n;++i)
20     {
21         if(a[i]==b[x]) x++;
22         else printf("%lld ",a[i]);
23     }
24 }

View Code

T2：

题目背景

我这题居然拿了80.。。 标程真短，心酸。

题目描述

rsy最近在研究欧几里得算法，不会的同学可以去看下课件以及代码……

现在她想到了一个新的问题，求k个数的最大公约数！ 事实上这个问题仍然很简单。

所以rsy想强化一下，她觉得最大公约数等于1就不是很有趣了。

因此她想在n个数中找最多的数，使得它们的最大公约数不等于1。

现在rsy想知道，能找最多多少个数。

输入输出格式

输入格式：

 

第一行一个数n。 第二行n个数ai。

 

输出格式：

 

一个数表示答案

 

输入输出样例

输入样例#1： 复制

5
2 3 4 5 6

输出样例#1： 复制

3

说明

数据范围 对于30%的数据n<=5。

对于50%的数据n<=20。

对于80%的数据n<=1000,ai<=1000。

对于100%的数据1<=n<=100000,1<=ai<=100000，数据几乎是随机的。

 

我确实没什么思路，，就打出了如下代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 int n,a[100002],b[100002];
 7 int main()
 8 {
 9     //freopen("math.in","r",stdin);
10     //freopen("math.out","w",stdout);
11     scanf("%d",&n);
12     for(int i=1;i<=n;++i) scanf("%d",&a[i]);
13     sort(a+1,a+n+1);
14     for(int i=1;i<=n;++i)
15     {
16         if(a[i]%2==0) b[2]++;
17         if(a[i]%3==0) b[3]++;
18         if(a[i]%5==0) b[5]++;
19         if(a[i]%7==0) b[7]++;
20         if(a[i]%11==0) b[11]++;
21         if(a[i]%13==0) b[13]++;
22         if(a[i]%17==0) b[17]++;
23         if(a[i]%23==0) b[23]++;
24         if(a[i]%29==0) b[29]++;
25         if(a[i]%31==0) b[31]++;
26         if(a[i]%37==0) b[37]++;
27         if(a[i]%39==0) b[39]++;
28         if(a[i]%41==0) b[41]++;
29         if(a[i]%43==0) b[43]++;
30         if(a[i]%47==0) b[47]++;
31         if(a[i]%53==0) b[53]++;
32         if(a[i]%59==0) b[59]++;
33         if(a[i]%61==0) b[61]++;
34     }
35     sort(b+1,b+n+1);
36     printf("%d",b[n]);
37 }

View Code

看数据范围，，觉得不可能拿80这么多，，，amazing。

然后我就去看std了，，我一开始没看懂第二个循环，我太菜了。

于是我就去问了机房里存在的，我最欣赏的人。

为什么这么说，，因为别人去省选啦！，然后，我就懂了。

 

官方上交解题报告如下：

 

这个题的题意也很好理解，就是说输入一串数字，找出尽量多（the most）的数字，

使他们的gcd不为1。但是代码实现没有什么好的思路，于是考场上打表。

 

Std思路：循环输入数A，用一个数组a来记录每个数字出现的次数，

因为1不算，数据范围到十万，所以输入记录完毕后，

从2到十万开始循环枚举，二层循环j从i开始，小于等于十万，j+=i，

意思是枚举看有几个数是i的倍数，然后提前定义一个变量x，

记录是i的倍数的个数，二层循环完毕后，取max。

最终max即为所求的最多的gcd不为1的数的个数。

完毕。

 

std如下：

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 int n,A,a[1000005],now,MAX,i,j;
 8 int main()
 9 {
10     //freopen("math.in","r",stdin);
11     //freopen("math.out","w",stdout);
12     scanf("%d",&n);
13     for (i=1; i<=n; i++)
14     {
15         scanf("%d",&A);
16         a[A]++;                 //记录次数 
17     }
18     for (i=2; i<=1000000; i++)  //1舍去 
19     {
20         now=0;
21         for (j=i; j<=1000000; j+=i) 
22             now+=a[j];          //枚举看有几个数是i的倍数 
23         MAX=max(MAX,now);       //取最多的就OK了 
24     }
25     cout<<MAX;
26     return 0;
27 }

View Code

T3：

没错我是唯一一个爆零的。

题目背景

全场唯一一个零分。

题目描述

rsy最近沉迷于一款叫扫雷的游戏。 这个游戏是这样的。

一开始网格上有nm个位置，其中有一些位置有雷。

每次rsy可以左键点击一个方块，此时若这个方块是雷，则rsy被炸，游戏结束，否则如果这个位置周围8格有x个雷，则会显示数字x。

特别地，当x=0时，系统会自动左键点击附近8个位置。

（此时附近8个位置一定没有雷，假如附近8个位置仍存在x=0，则继续往外扩展）想要更进一步获得关于题目的信息，

打开程序->附近->游戏->扫雷或者直接打开下发的可执行文件。或者rsy右键点击一个位置，标注这个位置是雷。

不幸的是，她鼠标不能左右键同时点击，因此只需考虑她左键点击与右键点击就可以了。

注意游戏胜利的条件是所有非雷的位置都被左键点击到。（特别地，当一开始时nm个位置都是雷时，LYK自动获得胜利）

rsy从网上下载了金手指，很轻易地就掌握了所有雷所在的位置。

rsy想通过最少的点击次数获得胜利（这里的点击次数不包括系统自动点击）。于是他来请求你的帮助。

输入输出格式

输入格式：

 

第一行两个数n,m。

接下来n行，每行m个数ai,j，表示这个矩阵。

若ai,j=’*’则表示这个位置是雷，若ai,j=’.’则表示不是雷。

 

输出格式：

 

一个数表示答案。

 

输入输出样例

输入样例#1： 复制

3 3
..*
...
..*

输出样例#1： 复制

2

说明

对于30%的数据n=1;

对于另外20%的数据n,m<=3；

对于再另外20%的数据*大致占矩阵的2/3且数据随机。

对于100%的数据n,m<=1000。

Hint： 适度游戏益脑，沉迷游戏伤身。

 

0分代码就不放了，，反正也是瞎搞的。

一看标程这么长，，，我就不想看。。。

先上std，等我弄彻了，，再补吧。

他们说是个大搜素，像luogu上的1451.。

 

补：

官方上交解题报告：

 

题目看起来相当复杂，，关键是提取关键信息。

直接看样例，输入矩阵，‘*’代表有雷，‘.’代表安全。

问：在已经知道哪里有雷的前提下，最少要点多少次才能把安全的地方都点了。

要求：一个安全的地方如果周围没有雷，那么他周围的就相当于也被点了。

如果周围有雷，那么就只能一个一个点。

如果没理解错的话，那大概就是这样的，所以就类似于一个搜索题。

用一个bool数组v[i][j]记录整个矩阵标记为false，其余外围部分标记为true，

然后输入矩阵s[i][j]，枚举这个矩阵，如果这个位置是安全的，

就看看这个位置附近有没有雷，用一个数组a[i][j]记录每个位置周围的雷的数量。

全部记录完毕后，重新循环枚举矩阵，if (!a[i][j] && s[i][j]=='.' && !v[i][j])，

就是如果这个位置是安全的，并且这个位置周围都没有雷，并且这个位置是存在于

扫雷矩阵中的，那么点击次数就++，将原来的v[i][j]的false标记为true，

继续搜索下一个点，如果这个点是安全的并且没有被标记，但他周围有雷，

那只能一个一个点击，点击次数++；全部枚举完毕后，输出点击次数。

完毕。

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <iostream>
 5 #include <algorithm>
 6 #include <string>
 7 #include <cstring>
 8 using namespace std;
 9 int a[1005][1005],k,sum,X,n,m,i,j,sx[1000005],sy[1000005],L,R;
10 bool v[1005][1005];
11 const int F1[8]={-1,-1,-1,0,0,1,1,1};
12 const int F2[8]={-1,0,1,-1,1,-1,0,1};
13 char s[1005][1005];
14 void dfs(int x,int y)
15 {
16     L=0; R=1;
17     sx[1]=x; sy[1]=y;
18     while (L!=R)
19     {
20         L++;
21         if (!a[sx[L]][sy[L]] && s[sx[L]][sy[L]]=='.')
22         for (int i=0; i<8; i++)
23             if (!v[F1[i]+sx[L]][F2[i]+sy[L]])
24             {
25                 v[F1[i]+sx[L]][F2[i]+sy[L]]=true;
26                 sx[++R]=F1[i]+sx[L]; sy[R]=F2[i]+sy[L];
27             }
28     }
29 }
30 int main()
31 {
32     //freopen("mine.in","r",stdin);
33     //freopen("mine.out","w",stdout);
34     scanf("%d%d",&n,&m);
35     for (i=0; i<=n+1; i++) for (j=0; j<=m+1; j++) v[i][j]=true;
36     for (i=1; i<=n; i++) for (j=1; j<=m; j++) v[i][j]=false;
37     for (i=1; i<=n; i++) scanf("%s",s[i]+1);
38     for (i=1; i<=n; i++)
39       for (j=1; j<=m; j++)
40         if (s[i][j]=='.')
41         {
42             X=0;
43             for (k=0; k<8; k++) if (s[i+F1[k]][j+F2[k]]=='*') X++;
44             a[i][j]=X;
45         }
46     for (i=1; i<=n; i++)
47         for (j=1; j<=m; j++)
48           if (!a[i][j] && s[i][j]=='.' && !v[i][j]) {sum++; v[i][j]=true; dfs(i,j);}
49     for (i=1; i<=n; i++)
50         for (j=1; j<=m; j++)
51             if (s[i][j]=='.' && !v[i][j]) sum++;
52     cout<<sum;
53     return 0;
54 }

View Code

完毕。

终：

我希望，从蓝天到名利，所有你想要的，都别随风去。

 

转载于:.html