广东工业大学第12届文远知行杯新生程序设计竞赛-题解

A-迫真算法部・ACの裏技

按照题意模拟即可，样例已经把所有可能错的地方都列出来了，所以样例过了应该就行了

B-qqdd抢餐券

用桶把每个时间点出现的人数存下来，遍历模拟即可。

C-智慧之神的简单题

枚举签到题，首先发现数据范围只有500，我们只要三个for循环枚举所有情况，然后if判断两个条件是否成立即可

D-赚硬币

首先我们可以算出硬币的总数为 27 + 14 + 14 = 55，所以可以得出 A + B + C 的值可能为 1， 5， 11 ， 55，然后容易排除1 和 55 ，又因为 A, B , C 为正整数且 A > B > C，所以可以确定 A + B + C = 11 , 则 N = 5 。

接下来确定 A， B ， C 的值。

由 A + B + C = 11 可以得到以下几种可能的排列：

8， 2， 1

7， 3， 1

6， 4， 1

6， 3， 2

5， 4， 2，

因为Alice 的硬币最多，而且最多只可能拿四次第一，一次第二，那么我们可以排除 5,4,2 这个排列，因为 4 × 5 + 4 = 24 < 27.

然后因为Mazige没有拿过第一名，所以最多拿五次第二，那么可以排除8， 2， 1。

因为 5 × 2 = 10 < 14。

对于 7, 3, 1 这种情况，因为 Bob 必定拿过第一名，而对于其他四场比赛不管怎么组合都凑不出 7枚硬币，所以排除。

对于6 ， 4 ， 1 这种情况，我们会发现怎么都凑不出 Alice 的 27 枚硬币，所以排除。

最终只剩下 6 ， 3 ， 2这种组合，而且容易推出最终情况。

最终结果为，在 ICPC这场比赛中， Bob 第一， Alice 第二， Mazige第三，其他四场比赛，Alice都是第一， Mazige都是第二， Bob 都是第三。

所以在CCPC中获胜的为Mazige。

E-柒小队打麻将

考场上可以直接暴力打表找规律。要证明的话，首先，对于任何一个数，其的幂次对10取模一定有一个长度为4的循环节，所以 $n^{9^k} \% 10 = n^{(9^k) \% 4} \% 10 = n^{1^k} \% 10 = n \% 10$

F-亚子和燐子的game

好像题目有万千种方法做，只要不是枚举那个基数貌似都能过的样子。

出题人的思路：

将所有数字都用三进制表示，然后找所有三进制的最长公共前缀（是所有，所以没必要用什么特别的算法，只要搞个数组模拟下，每次记录下最长匹配到哪位就行）。如果一位都匹配不到就输出lose，否则每个怪血量的三进制表示的位数减掉最后最长前缀的长度的和就是答案。

G-我最好的朋友

按照棋盘的长度 $L$ 分类讨论：

若 $L$ 为偶数，当 $L \%4=0$ 时，后手采取这个策略可以必赢：
1. 当先手单下对称位置未被占据的格子时，后手单下另外一个对称位置未被占据的格子
2. 当先手单下对称位置被占据的格子时，后手单下另外一个对称位置被占据的格子（由于后手策略(1)(2)，对称位置被占据的空格子必定成对出现，成对消失）
3. 当先手双下对称格子时，后手双下另外一个对称双空格子
这样，每4个格子的攻防转换次数必定是偶数（2或4），又因为 $L \%4=0$ ，所以后手必胜
若 $L$ 为偶数且 $L \% 4=2$ 时，先手第一手双下对称空格子即可把场面转化为自己后手的 $L \%4=0$ 情况
若 $L$ 为奇数时，先手可根据场面情况选择下中间或单下对称位置未被占据的格子将场面变为 $L \%4=0$ 自己后手或者 $L \% 4=2$ 自己先手，故此时先手必赢

H-马子哥的奖金

贪心+双指针.

想要乘积乘积最大,每次取两个最小的负数的乘积或者两个最大的正数的乘积.因此先对数组进行排序,之后利用双指针,比较a[l]*a[l+1]和a[r]*a[r-1]的乘积,并加入ans中.

需要注意的细节:

要考虑最终的结果的正负值,所以先对k进行判断,如果k是偶数显然可以构造出不是负数的结果.所以先对k判断是否为奇数,若k为奇数则先令ans=a[n].之后判断当前ans的正负性,由于数组已经是有序的,所以如果a[n]为负数,则证明整个数组都是负数,则最后的结果一定为负数,所以我们需要取乘积较小的一端加入ans中.如果a[n]为正数,则最终结果一定为正数,直接取乘积最大的一端加入ans中即可.

I-奇迹和魔法都是存在的

考虑对一个区间 $A [l . . . r]$ 进行操作，如果想把其中一个数 $A [i]$ 放到最前方而且 $i \ne l$ ，那么他必须得比第一个数大才能被留下来

而众所周知，当数组剩下最后一个数字时，这个数字也是这个长度为一的数组的第一个数。不难发现，每次操作后新数组的第一个数是非递减的，所以，若希望一个数变成第一个数并留下来，那么他一定得要比一开始数组的第一个数大才行。

所以，对于任意一个区间，其答案就是这个区间内大于等于第一个数的数的个数。

for(int i=l;i<=r;++i)
	if(boss[l]<=boss[i]) ++ans;
printf("%d\n",ans);

J-狐臭的等比数列

正解:

我们设q_i=\frac{u_i}{d_i}=\frac{a_{i+1}}{a_i},1\leq i \leq n-1, 其中gcd(u_i,d_i)=1,假设该等比数列的一个最小公比为q_0,不难发现对于每个q_i一定存在一个整数k_i,满足{q_0}^{k_i}=q_i,

要使最后的等比数列最短，那么应该尽可能让q_0取最大值,设其为q_{max}={q_0}^k,则有{q_{max}}^{\frac{k_i}{k}}=q_i,易得k=gcd(k_i,k_{i+1}),1\leq i \leq n- 2,即对于q_i和q_{i+1},

我们把它们写成{q_0}^a,{q_0}^b,我们所要求的最大公比即为{q_0}^{gcd(a,b)}。下面我们讲如何求出{q_0}^{gcd(a,b)}:对于q_1\leq q_2,分别写成{q_0}^a,{q_0}^b,我们有{q_0}^{gcd(a,b)}={q_0}^{gcd(a-b,b)}

故可以定义函数GCD(a,b)为求a,b的最大公比,有GCD(q_1,q_2)=GCD(\frac{q_1}{q_2},q_2)，求出全部的最大公比后即可求出最后答案。

暴力解:

用\frac{a_i}{a_{i-1}}将n-1个数用\frac{分子}{分母}（注意分子分母化为互质形式）表示出来,若这n-1个数完全一样,则输出n,否则有更多的数,接着我们要找到n-1个数中最小的数x,

它 一 定 是 公 比 q 的 k 次 方, 于 是 我 们 就 暴 力 枚 举 q 即 可 (即 对 最 小 值 x 暴 力 开 根 号), 对 x 开 i 次 方 根 得 到 公 比 q, 代 码 为 q = p o w (x, 1.0 / i) + 0.5, 并 判 断 q 是 否 恰 好 是 整 数,

接 着 暴 力 对 n - 1 扫 一 遍 是 否 满 足 条 件 即 可 。

K-玩石头

关键的点是层数很小，因为可以发现石头重量增长的速度类似于斐波那契数列，打表可以发现，在给定数据的范围下，石头塔最多为三十层，则时髦值之和最大为3000，然后我们发现石头塔的重量从上到下，一定是严格递增的，不妨设dp[j]代表时髦值为j的情况下的最小重量，然后将所有石头按重量从小到大排序，然后按照题目的要求DP即可。时间复杂度为 $O (3 e 8)$ ，所以时限给了三秒，事实上常数很小，标程和验题人的代码只需要不到300ms，但是怕干扰选手的判断，最后还是给了3s的时限。

L-jjgg的难题

我们可以把n写成

n = p b + q

当 $b \leq \sqrt{n}$ 时,我们完全可以枚举 2~ $\sqrt{n}$ 作为进制数b,在log(n)的时间内求出对应的s来寻找最小的b。

当 $b>\sqrt{n}$ 时，可以证明n在b进制下最多两位数

此时 $s = p + q$

并且

n = p b + q > = p b > p^{2}

可得 $p<\sqrt{n}$

又 $b = (n - s) / p + 1$

即我们枚举所有p，得到的正整数b来验证是否 $f (b, n) = s$ ，取最小的b。

若上述找不到符合的b，则不存在。

特判：当两个数相同时，n=s，b=n+1

M-Poppin'Party的star

首先我们先确定几个前提。

第一，当五角星与矩形的角度固定之后，五角星的最大面积实际上就固定了。这是很容易证明的，因为当五角星的角度固定之后，他的△x和△y的比例就已经确定了，那我们只需要将他等比放大直到到达x或y的边界就行。于是我们的任务变成了找到一个合适的角度。

第二，首先根据五角星的中心对称原则，可以把360°的转角平分五份，每份72°，每份的情况是一样的。然后在这72°里面，前36°和后36°其实也是对称的，如图：

alt

从左至右依次为图1,2,3.图一为未旋转前，图二为旋转36°后，可发现旋转36°之后出现了一条过五角星中心的竖直对称轴，根据图三可以发现，以这个状态为起点，顺时针旋转n°和逆时针旋转n°所得到的图形是根据该竖直对称轴对称的，（图三黑色为图二五角星，红色为顺时针旋转8°，蓝色为逆时针旋转8°）所以得到的两个五角星水平对称，水平对称就说明，这两个五角星的x/y是完全一样的。所以我们只需要算前36°的时候的情况即可。

同理，前36°也可以分为前18°和后18°，有垂直对称的关系。证明过程就不再赘述。 alt

上图为五角星旋转18°后

当然，实际上你不去找这些对称轴，将这72°直接算完也是可以的。

于是我们的任务变成了求18°转角内，怎么样能让五角星的面积最大。

alt

上图左为未转动，右为转动18°后。

我们设图中五角星AC长度为d。则AD，BE等的长度也为d，通过观察可以发现，在这18°的转角中，y跨度最大的边实际上只有AD，x跨度最大的边实际上只有BE，设转角为θ，根据图我们就可以得到式子， $\Delta x = d \times \cos \theta (1)$

$\Delta y = d \times \cos (\frac{\pi}{10}-\theta)(2)$

然后只要 $\Delta x \le A ,\Delta y \le B$ 是 $d$ 和 $\theta$ 的不等式，在 $0\le \theta \le \frac{\pi}{10}$ 范围内去得 $d$ 的最大值即可

$d = \frac{A}{\cos \theta}$ 在区间内单调递增

$d = \frac{B}{\cos(\frac{\pi}{10}-\theta)}$ 在区间内单调递减，且在区间内均有意义。如果两函数在区间内没有交点就在两个端点处找最大值，如果有交点就取交点。即可得到 $d$ 。最后可以得到在有交点的情况下

$\theta = \tan^{-1}(\frac{\frac{B}{A}-\cos(\frac{\pi}{10})}{\sin (\frac{\pi}{10})})$

套入1或2公式即可得到 $d$ 。然后就可以根据 $d$ 算出五角星面积。