2019-12-07 23:45 C++

关注

【题解】2019年广东工业大学腾讯杯新生程序设计竞赛

A

签到题,按题意输出这些数字里面的最大值即可.

B

因为是后手且两样武器不同，不存在败，如果手中存在克制的则赢，无则平(其实就是个剪刀石头布)

C

签到,要注意无效票也算人数.如果反对和赞成各占一半优先考虑赞成票.

D

对于1操作，直接修改即可。
对于2操作，把区间[l,r]范围的数复制到另一个数组里，排个序，然后相同的数字就变成连续的了，只需找出连续最多的数连续了几次就可以了。

E

假设第1个检查的日期为a，第n个为b。
先考虑最差的情况，就是连续工作b-a+1天。
如何优化呢？n个检查日期把[a,b]划分为n-1个连续的段，
比如123456789中123和789是检查时间，用1次连续工作机会就是消耗9天，
多用一次连续工作的机会就相当于把1次连续工作断成2次，即变成123和789，共消耗6天。
基于这样的思想，我们把这n-1个连续的段从大到小排个序，依次断开1次为2次。

F

原本的题意是:

有n个一字排开的山洞,有一只狐狸藏在其中一个洞中(但是猎人不知道是哪个洞).

每天白天,他都可以检查其中一个洞,如果狐狸在洞中,那么他就抓住了狐狸.

否则,每天晚上,狐狸都会随机移动到一个相邻的洞中(如果狐狸在第n个洞那么只能移动到第n-1个洞中,如果在第1个洞同理),不能呆在原地.

思路

既然要确保使用的方案能够确保抓住狐狸,那么不妨做这样的假设:

一开始每一个洞中都有狐狸,而且每天晚上他们都会分身往两边的洞移动(影流之主)

所以确保能够抓住狐狸的方案,在这种假设下就变成能够抓住全部狐狸的方案.

可以意识到一点:

在当前抓捕次数是奇数的时候,如果检查偶数洞,那么抓到的一定是开局就在偶数洞的狐狸;如果检查奇数洞,那么抓到的一定是开局就在奇数洞的狐狸.

抓捕次数为偶数同理.

因为每天狐狸都要移动到相邻的位置,所以如果天数为奇数的时候(开局时第一天,所以是奇数),某狐狸在奇数洞,那么天数为偶数的时候,他一定是在偶数洞.

开局在偶数洞的狐狸同理.

以下用X代表一定没有狐狸的洞口,用O代表有狐狸的洞口:

考虑先把奇数(先抓偶数的也行)的狐狸抓住.

方法就是从最边上开始,奇数天就检查奇数洞,偶数天就检查偶数洞.

对于5的样例,第一天的情况如下:

OOOOO

如果检查一个最右边的奇数洞(5):

OOOOX

那么检查之后5号洞的右边不会存在[开局位于奇数洞]的狐狸(废话),经过一晚上之后:

OOOOO

第二天(偶数天),这时检查4号洞:

OOOXO

那么检查之后4号洞的右边不会存在[开局位于奇数洞]的狐狸(5号洞的狐狸一开始位于4号洞),经过一晚上之后:

OOOOX

第三天(奇数天),检查3号洞:

OOXOX

一晚上后:

OOOXO

第四天(偶数天),检查2号洞:

OXOXO

抓捕之后发现,这一天已经没有[开局位于奇数洞]的狐狸了,

这时可能会有一个疑问,为什么"检查之后的洞的右边不会存在[开局位于奇数洞]的狐狸".

因为从一个奇(偶)数洞走到另一个奇(偶)数洞需要2个晚上,手动模拟一下:

如果检查了4号洞,这时2号有一只狐狸:

XOXXX

那么二号洞的狐狸想要跑到4的右边,那么这个晚上就要往右走:

XXOXX

但是按照方案,这一天应该检查3号洞,所以他就白给了.

但是如果往左走,最终还是会被抓到.

以上的操作,抓捕所有[开局位于奇数洞]的狐狸,需要4天,如果先抓捕[开局位于偶数洞]的狐狸呢?

1:OOOOO

检查4:OOOXO

2:OOOOX

检查3:OOXOX

3:OOOXO

检查2:OXOXO

则只需要3天,开始抓[开局位于奇数洞]的狐狸:

4:XOXOX

检查4:XOXXX

5:OXOXX

检查3:OXXXX

6:XOXXX

检查2:XXXXX

只需6天就能完成抓捕(之前的方案需要7天).

但是这明显不是字典序最小的方案,因为可以从左往右抓{2,3,4,2,3,4} < {4,3,2,4,3,2}

但是答案不完全是2抓到n-1再2抓到n-1,因为当n是偶数时(比如4),{2,3,2,3}压根不会抓到[开局位于奇数洞]的狐狸.

如下:

1:OOOO

检查2:OXOO

2:XOOO

检查3:XOXO

3:OXOX

检查2:OXOX(抓了一个X洞)

4:XOXO

检查3:XOXO(抓了一个X洞)

还是会有剩下的狐狸.

所以当n时偶数时,应该是2到n-1再n-1到2,所以4应该是{2,3,3,2}(具体自己模拟).

那么这个题的规律就找到了:

n是奇数时:2,3,4....n-1,2,3,4...n-1

n是偶数时:2,3,4....n-1,n-1...4,3,2

G

其实这里有两个关键的地方，第一个是排序，在这里我们选择桶排序，因为题目涉及的出牌方式与数量有关。第二个是顺子的处理，关于顺子，如果我们用了桶排序，就可以取“桶”里面，长度为5的区间，根据组合数学的乘法原理，就可以得到答案了，“桶”为0的情况也可以处理，详情可以看一下标程。剩下的三带一和三带二也是考组合数学的知识。能掌握上面的几点这道题基本就能AC了。

H

打一下表会发现,对于每一个 $2^x$ <n时,当 $x$ 相等时,答案相等

所以只要预处理出64种答案出来,然后直接输出.

记忆化搜索会被卡掉

I

对于 $(p-1)^n \% p$ 这条式子，我们可以考虑用高中组合数学课本学过的“二项式定理”展开 $(p-1)^n$ 。展开后，会发现前n项都是p的倍数，第n+1项(最后一项)是： $(-1)^n$ 。
然后，我们可以分类讨论：
1.当n为偶数时， $(p-1)^n$ 通过二项式定理展开后，可以这样表示：原式= $X\times p + 1$ ( $X$ 是一个大于等于0的整数)。又通过题目输出对取模的理解可以知道： $(X\times p + 1) \% p = 1$ ，所以 $(p-1)^n \% p = 1$ .
2.当n为奇数时， $(p-1)^n$ 通过二项式定理展开后，可以这样表示： $X \times p - 1 = (X-1)*p + (p-1)$ (X是一个大于0的整数)。 $( (X-1)\times p + (p-1)) \% p = p-1$ ，所以 $(p-1)^n \% p = p-1$ .
综上所述，我们只需要判断n的奇偶性，就可以得到答案了。
因为n设置的很大，所以题目已经提示要用char数组存。如果仅是判断n的奇偶性，其实只要判断最后一位是奇数还是偶数就行了。

J

解法1：

手算前几项或许可以找到规律

解法2：

设 $f(x)_n=\frac{(x-1)(x-2)...(x-n)}{(x+1)(x+2)...(x+n)}$ ,
则有 $f(x)_n=f(x)_{n-1}\times \frac{x-n}{x+n}(n>1)$ ,
求导得 $f'(x)_n=f'(x)_{n-1}\times \frac{x-n}{x+n}+f(x)_{n-1}\times (\frac{x-n}{x+n})'$ ,
显然 $f(1)_n=0$ ,
所以有递推式 $f'(1)_{n}=f'(1)_{n-1}\times \frac{1-n}{1+n}$ , $f'(1)_1=\frac{1}{2}$ ,
所以 $f'(1)_n=\frac{1\times (-1) \times (-2)\times...\times(1-n)}{2\times3\times4\times...\times(1+n)}=(-1)^{n-1}\times\frac{1}{n(n+1)}$ ,
最终答案为 $\frac{1}{f'(1)}=(-1)^{n-1}\times n(n+1)$

K

$假设存在x,y(x>y),使得x^3-y^3=p$
$则(x-y)\times (x^2+xy+y^2)=p$
$因p为素数，所以x-y=1，将x=y+1代入上式$
$得到y\times (y+1)=\frac{p-1}{3}$
$因为x,y为整数，只需判断(p-1) \%3==0\&\&\lfloor\sqrt{\frac{p-1}{3}}\rfloor*(\lfloor\sqrt{\frac{p-1}{3}}\rfloor+1)==\frac{p-1}{3}即可$