王清楚

2019-11-26 17:09 已编辑牛客运营

关注

【题解】四川大学第二届SCUACM新生赛

A-丁姐姐喜欢Fibonacci

由偶数+奇数=奇数，奇数+奇数=偶数

易得Fibonacci数列的奇偶规则为：奇奇偶奇奇偶奇奇偶.……
对于每一项，模3后直接输出结果即可

时间复杂度 $\operatorname{O}(1)$

代码点击此处链接查看~

B-丁姐姐喜欢LCS

对于两个串A和B，首先判断两串中最短的串，让B串按照最长衔接的状态依次衔接A串尾部，若不符合，则向A串的次长衔接状态衔接时间复杂度 $\operatorname{O}(n^2)$

代码点击此处链接查看~

C-俏兔子大战傻贼鹰-Easy Version

判断有无定缺牌，统计每张牌出现的次数，判断是否有7对一样的牌，四张一样的可以算两对，或者考虑有一对一样的，和四坎牌（三张一样的），其余情况不能胡牌。
数据比较小，时间复杂度为 $\operatorname{O}(NT)$
代码点击此处链接查看~

D-俏兔子大战傻贼鹰-Hard Version

贪心的模拟一下就好了，先判断有无定缺，然后7对子，然后平胡可以考虑先把一对的牌确定，然后剩下的牌，对于第张牌只有一张我们肯定只能做顺子，如果有两张我们也只能做两对顺子，有三张则不做顺子。四张其实是一张和三张的组合情况。

时间复杂度为 $\operatorname{O}(NT)$

当然也可以用DFS做。

代码点击此处链接查看~

E-【模板】欧拉筛

通过情况：

牛客同步赛：190/1721S

CUoJ现场赛：12/67

题解

由于每支股票的价值等于其编号的阶乘，而最终答案要求价值之和对P取模，注意到P很小，最大仅有1e5，而显然当n>P时，n!%P=0，因此我们只需要计算出n<P时，每个n!%P的值就好了。
于是我们可以首先通过欧拉筛（或者埃氏筛也行，其实速度影响不是很大）筛出1e5以内的质数并作上相应标记，然后对于每个P，枚举|1，P-11范围内的数，同时计算其阶乘模P后的值，如果当前枚举的数x是一个质数，将x!%P累加进答案即可。

时间复杂度： $\operatorname{O}(1e5)$ ，即欧拉筛 $\operatorname{O}(MAXP)$ 的复杂度。

Ps：本题出题人的std可以做到200ms左右AC本题，而牛客上的提交记录中也有接近这个时间的AC代码。不过大部分AC的代码都是按照上述思路做的，运行时间普遍在800ms-2000ms之间，本着新生赛友善第一的态度，本题没有卡时限，时限是按照上述一般思路写出的程序运行时间来给的，不过200ms左右的解法大家可以自行思考

代码点击此处链接查看~

牛客0J运行时间：1140ms占用内存：984KB
SCUoJ运行时间：1060ms占用内存：904KB

F-【模板】后缀自动机

题目描述
给定两个字符串s和T，问你S中是否存在一个后缀P，使得T的任何一个前缀的字典序都大于P。
题解
很明显S的后缀P应该小于字典序最小的前缀，很明显T最小的前缀就是第一个字符，要使P比他小，只能P的第一个字符比他小，所以实际上就检查一下是否 $\exists i\in[0,strlen(S) )$ S[i]< T[0]

复杂度显然是 $\operatorname{O}(n)$

代码点击此处链接查看~

G- 走迷宫

容易发现，这样走迷宫总是一圈一圈地走的。
我们用二分的方法求出第 k 步位于哪一圈，然后在这一圈上用 if-else 判断位于哪一条边即可。
而二分的方法，大概就是，设一个 n*m 区域的最外圈为第 1 圈，那么第 x 圈就已经走过了前 x-1 圈，就已经走过了 n*m-(n-2*(x-1))*(m-2*(x-1))，判断这个数与 k 的大小关系即可。
由于每一圈都会导致两边各减 2 ，因此最大圈数为 min((n+1)/2,(m+1)/2)。

单组数据时间复杂度为 $O(q*log_2min(n,m))$ 。

代码点击此处链接查看~

H- 捡金币

序列中一段元素的和可以由前缀和相减得到，即用 $sum_i$ 表示序列中前 i 个元素的和，那么第 x 个元素到第 y 个元素的和可以表示为 $sum_y-sum_{x-1}$ 。
推广到矩阵，用二维前缀和 $sum_{i,j}$ 表示以 (1,1) 为左上角，(i,j) 为右下角的子矩阵的和。那么稍微应用一下容斥原理，一个以 (a,b) 为左上角，(c,d) 为右下角的子矩阵的和可以表示为 $sum_{c,d} - sum_{c,b-1}-sum_{a-1,d}+sum_{a-1,b-1}$ 。
回到这个问题上，容易发现需要求和的是一个旋转 45 度后的正方形区域。

Solution.1

我们用 sum[i][j] 来表示这样的二维前缀和，以图中紫***域包含的前缀和范围为例：

大概就是以某个点为下顶点的无限大三角形区域。
那么在忽略细节的情况下，题目中的一组询问 (x,y,k) 就可以表示为 sum[x+k][y]-sum[x][y-k]-sum[x][y+k]+sum[x-k][y] ，只不过这样会导致菱形区域的两条边被减掉，因此我们还需要用两个前缀和 sum2[i][j] 和 sum3[i][j] （具体意义参考下图中的黄色(sum2)与蓝色(sum3)区域）来把这两条被减掉的边给加回来。

最后的式子就是

sum[x+k][y]-sum[x][y-k]-sum[x][y+k]+sum[x-k][y]
+sum2[x][y-k]-sum2[x-k][y]
+sum3[x][y+k]-sum3[x-k][y]+num[x-k][y]

最后再考虑一个细节，就是这个式子中，如果出现越界的情况，那我们需要找一个合法的等效替代点，很好找，找法参考代码。

思路都是很暴力的，只不过细节稍多一点。
单组数据时间复杂度 $\operatorname{O}(n*m+q)$

代码点击此处链接查看~

Solution.2
把给出的矩阵旋转 45 度后存储，以下面这个 3*3 的矩阵为例：

1 2 3
4 5 6
7 8 9

旋转 45 度后存储为：

- - 3 - -
- 2 - 6 -
1 - 5 - 9
- 4 - 8 -
- - 7 - -

在这个新矩阵里直接用普通的矩阵二维前缀和求子矩阵和的方式就可以了。
具体的旋转方式不唯一，能保证最后转了 45 度就行。
单组数据时间复杂度也是 $\operatorname{O}(n*m+q)$

代码点击此处链接查看~

代码简短一些，不过对位置的细节处理要稍微麻烦一点。

I- 排序

没啥好说的，模拟 ACM 规则排序。

代码点击此处链接查看~

J- n=abc

暴力分解出这个数的因数，然后 $O(n^2)$ 枚举 a,b ，再利用 c=n/(a*b) 得到 c，用此时的 a,b,c 更新答案即可。

代码点击此处链接查看~

K- 梅森素数

首先和大家道歉，因为我的失误然后手抖把3写成2呢。我有罪。后面也没认真写代码去验题。
首先我们分析梅森数的形式 $2^n-1$ ，当n为偶数的时候，显然可以通过平方差公式因式分解，所以可以得出，当n为偶数的时候，这个梅森数一定不是梅森素数。

于是我们可以尝试判断每个奇数是不是梅森素数。然后判断到13就够了。

代码点击此处链接查看~

L- 双流机场

因为题目要求询问是否任意两点能够互相到达。实际上就是求是否所有的点处在同一个强连通中。
题目中点的数量是 $\operatorname{O}(n*m)$ 量级的，简单的tarjan算法显然不能通过本题。(如果是大一的新生，可以稍微百度一下这个算法。但是不用深入学习。)

于是我们尝试简化本题目：最外圈的任意两点是否能够互相到达，经过观察发现只有两种情况能够互相到达。分别为顺时针和逆时针。然后我们直接判断外圈的箭头方向是否为顺时针或者是逆时针走向。如果是的话，外圈任意两点可以互相到达，然后我们考虑内圈的所有点，都可以走到外圈，又因为外圈是一个循环的圈，所以可以到达所有的点。于是我们只用判断最外圈是否为逆时针或者是顺时针走向就好了。

代码点击此处链接查看~