Tips

因为题目实在太多了,代码就不贴在博客里了。。。想看代码的童鞋可以去github上看看。
题目似乎看不了了,我只能凭感觉复述一下题意了。。。

Before

这个比赛有一个资格赛,但是跟蓝桥杯决赛冲突了所以不能参加,没想到老师帮我们申请了参赛资格,意外之喜。
热身刚结束实验室就断电了。。然后吃完饭背着电脑去了没空调的教室。。。

WarmUp

B题就不说了,反正一眼。A题首先肯定要把质数都筛出来,本来想在质数表里直接做的,但是发现写不出来。。。主要是因为对于 $a\leq x\leq b-m+1$ 都要成立,这个放到质数表里细节太多。。。所以想还不如直接交个很好写的二分答案,结果一发过了。。。很无语,要不是怕复杂度不太对这个也是看一眼就能写 = = 。。。C题比较难懂,它定义的线段能组成方形实际上跟线段本身的长度没有关系,读了好久才读懂,反正不会做也无所谓了 =。=

A

题意:D、E、E、S、T 做全排列并且按字典序排序,输出第$n$个$(n\leq 60)$。
题解:用next_permutation打个表就行啦 虽然CE了两次

B

题意:给出一个 $n\times n$ 四连通的字符地图$(n\leq 50)$,只包含’*‘,’#’两种字符,从’*‘到’#’要消耗1点能量,从’#’到其他也要消耗1点能量。问从$(1,1)$到$(n,n)$至少要消耗多少能量。
题解:每个字符与相邻的字符建图,做一次单源最短路。可以用dijkstra+队列优化,时间复杂度$O(2n^2logn+4n^2)$。

C

题意:给出$n$个数的序列$(n\leq 20)$,每个数之前可以加正号或者负号,各个数也可以换位置,问最终能有多少不用的结果。
题解:显然换位置对于最后答案没有影响,只需要考虑是正是负就可以了。直接dfs,用set去重一下,时间复杂度$O(2^nnlog2)$。

D

题意:有一个无穷的字符串序列${a,b,\dots,z,aa,\dots,az,ba,\dots }$,称不含a也不含bc的字符串为beautiful。给出一个串,问这个串之前有多少beautiful的字符串$(|S|\leq 100)$。
题目:很明显的数位dp,实际上跟hdu上的不要62差不多,不过这个是不能含a,相当于数字不能含0,那么就不能用前导0来补位了。。。刚开始也想怎么改一改模板,好像改了几十分钟都没搞定,最后就直接各种位数都算一遍就行了 =。= 单组时间复杂度$O(26n^2)$,不过根本到不了,多组就更无压力了。

E

题意:求最长回文子串的长度$(|S|<=50)$。
题解:枚举中心和中心对暴力,时间复杂度$O(n^2)$。manacher的板子当然更无压力。

F

题意:有$n$条公交路线,问从S到T至少转车几次,如果多个方案输出时间最短的。
题解:做过类似的,写起来太麻烦没写,所以数据范围也没记清楚。仍然是建图dijkstra,中间好像要处理一下不太记得了 = =

G

题意:A和B在$n\times m$的网格图中移动一枚棋子,棋子的初始位置是$(1,1)$,每次只能向右或者向下移动,不能移动者失败。B后手认为游戏不太公平,增加规则,他可以在游戏开始前破坏至多一个格子(不能破坏左上角和右下角),游戏中两人不能移动到这个格子。在A最优策略的情况下,问B有没有必胜策略。
题解:首先考虑不破坏的情况,显然总共需要$n-1+m-1$步,如果这个数是偶数,那B必胜。再考虑需要破坏的,不妨令$n \lt m$,先填入SG值,$(n,m)$没有后继。

0 1 2 4 5 6
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0

可以发现,破坏中间的格子是没有用的,始终都有向右向下两个方向,要破坏就破坏底边的格子。当底边某个格子被破坏后,它左边的格子会没有后继变成0,所以破坏当前是1的格子也是没有用的,我们试着破坏$(3,4)$。

1 2 3 4 5 6
0 2 1 0 1 0
1 0 2 1 0 1
0 1 0 X 1 0

可以发现,$(1,1)$的状态确实变了,变成了0,也就是先手必败。再仔细观察,$(1,4),(2,5)$也发生了改变,而且实际上右边还有多少列也没有关系,比如再多两列。

1 2 3 4 5 6 7 8
0 2 1 0 1 0 1 0
1 0 2 1 0 1 0 1
0 1 0 X 1 0 1 0

相当于用X在左边规划了一个正方形,后手一定能把棋子移动到X的左边。那么样例的$(3,4)$为什么不行呢?因为要划一个$3\times 3$的正方形必须要破坏$(3,4)$,然而B不能破坏右下角,所以就不能必胜了。
综上,$n+m$是偶数或者$abs(n-m)$是大于1的奇数时有必胜策略。

H

题意:$n$个数,大小为$k$的滑动窗口从左往右滑动$(k\leq n\leq 10^7)$,求滑动过程中,最大值的平均数、平均数的最大值、标准差的最小值。
题解:求平均数和标准差只要维护一下区间和跟区间平方和就行了,求最大值的话参考poj2823,可以用双端队列维护。计算过程可以用long doublescanfprintf要用double。。。

I

题意:环上有$0\dots n-1$这$n$个点$(n\leq 1000000)$,青蛙从$0$开始每一步跳$x$,问有多少$x$使得青蛙能到达所有的点,青蛙可以跳无穷多次。
题解:题意即 $ax-bn=c$ 对于 $c>0$ 均有解。由裴蜀定理可以推知 $gcd(x,n)=1$。输出 $\varphi(n)$ 即可,预处理$O(N)$,回答$O(1)$。

J

题意:二维平面有$n$个点,以第一个点为起点、终点,每次走直线段去其他的点,直线段不能相交,问最后能围住多大的面积。
题解:刚读完的时候以为求个凸包就行了,后来发现规定了起点终点可能走不了凸包。。。然后就没做了,所以题目记得也不是很清楚。

K

题意:在$n\times m$的方格中从(1,1)开始顺时针地蛇形填数,输出结果$(n,m\leq 100)$。

输入:
3 3
1 2 3 4 5 6 7 8 9
输出:
1 2 3
8 9 4
7 6 5

题解:好像有个巧妙的方法,实在不行四种情况都判断一下就行,总之就是模拟。

L

没读

M

题意:给一个$n\times m$的矩阵D,再给一个kernel,即$3\times 3$的矩阵K,求D关于K的卷积$(n,m\leq 100)$。
题解:这题要是不给卷积的公式还真能难倒很多人。。。实际上就是按公式计算一下$$\large C_{i,j}=\sum_{a=0}^{min(n-i-1,2)}\sum_{b=0}^{min(m-j-1,2)}D_{i+a,j+b}\times K_{a,b}$$时间复杂度$O(3^2nm)$。

N

题意:$n$可以分解成$k$个正整数$(k\leq n\leq 1000)$,即$\sum_{i=1}^{k}a_i=n$,$a_i$递增,对于每种分解,它的值是这些数两两相乘的和,即$\sum_{i=1}^{k-1}\sum_{j=i+1}^{k}a_i*a_j$。求所有分解的和模$p$,保证$p$是一个奇质数。

输入:
5 1000000007
输出:
44
输出解释:
5=1+1+1+1+1 值为10
5=1+1+1+2 值为9
5=1+2+2 值为8
5=1+1+3 值为7
5=2+3 值为6
5=1+4 值为4
5=5 值为0

题解:$$记S=\sum_{i=1}^{k-1}\sum_{j=i+1}^{k}a_i*a_j$$ $$\because (\sum_{i=1}^{k}a_i)^2=\sum_{i=1}^{k}a_i^2+2S$$ $$\therefore S=\frac{1}{2}(n^2-\sum_{i=1}^{k}a_i^2)$$由于$S$的值很难维护,我们转而去求所有分解中的数的平方和。借用整数划分的记忆化搜索方法,getspilit(n,m)表示要分解$n$,且分解中出现的数都不超过$m$。分为 $m>n$,$m==n$,$m<n$ 三种情况,后两种再分为最终分解中包不包含m,这样不会重复。同时用f[][]记录不同分解数,g[][]记录所有分解的所有数字的平方和,用f[n][n]倍的$n^2$减去g[n][n],最后再乘以2的逆元就可以了,时间复杂度$O(n^2)$。

O

题意:给出$2n$个数,两两一组,使得每组两个数的差的绝对值之和最小,求这个最小的和。
题解:由绝对值的性质,排序后两两分组即可。(可以用初中的数形结合全都标到数轴上证明)

After

比赛的时候查了不少资料,还复制粘贴了很多模板,结果竟然还是没打过现场赛的人。。。感觉很多知识点虽然知道但是不太熟练。。。继续学习。。。