牛客寒假算法基础集训(白给)营3象征性题解

目测至少有五个题可做,然而我只做出来俩= =


C 处女座点名

原题:https://ac.nowcoder.com/acm/contest/329/C

真实签到题,求1到n里面哪一个数字没有出现,保证只有一个没有出现的数字。

数据量不大,完全可以开桶解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#define maxn 2333333
using namespace std;
int dm[maxn];
int n;
int a;
int main() {
cin >> n;
for (int i=1;i<=n;i++){
cin >> a;
dm[a] = 1;
}
for (int i=1;i<=n;i++){
if (dm[i]==0){
cout << i;
break;
}
}

return 0;
}

E 处女座和小姐姐

原题:https://ac.nowcoder.com/acm/contest/329/E

一开始没读懂题意,以为答案只有一种情况,实则不然。

可以知道的是,处女座和小姐姐坐的位置的连线显然是这个“班级矩阵”的对角线,提问到(1,1)处无法叠千纸鹤,提问到(n,m)处也无法叠千纸鹤,其余时间都可以(您这手速够快的),那显然想到的是数一下矩阵的元素个数。显然想到答案是n×m-2,实际上还要考虑一下其他情况。

最早我发现,当n变化(指奇数或偶数)时,答案可能不会是n×m-2,因为可能存在下面这种情况:

然后很兴奋的写了个判断n是奇偶数的程序,如果n是奇数,答案不变,如果n是偶数,最后一列的上半部分就走不了,答案就是n×m-n-1。交了上去,发现仍然不对。

其实这里我是比较草率了,没有想到去考虑m的可能情况,最后是划归了四种情况,合并为两种,发现最后起作用的其实是m而不是n。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#define maxn 2333333
using namespace std;
typedef long long ll;
ll n,m;
int main() {
ll t;
cin >> t;
while (t--) {
cin >> n >> m;
if (m % 2 == 0){
cout << n * m - n - 1 << endl;
}
else
cout << n * m - 2 << endl;
}
return 0;
}

D 处女座的训练

待添加

G 处女座和小姐姐(三)

待添加


-------------本文结束,感谢您的阅读转载请注明原作者及出处-------------


本文标题:牛客寒假算法基础集训(白给)营3象征性题解

文章作者:Shawn Zhou

发布时间:2019年01月26日 - 17:01

最后更新:2019年01月26日 - 18:01

原始链接:http://shawnzhou.xyz/2019/01/26/19-01-26-01/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

知识无价,码字不易。对您有用,敬请打赏。金额随意,感谢关心。
0%