Day1

2014-A 生活大爆炸版石头剪刀布

类型: 模拟     综合难度: 1     考场目标: 100 分

1.解决猜拳顺序循环--取余

2.如何计算得分--打表

时间复杂度O(N)轻松通过所有数据

2014-B 联合权值

类型: 简单图论     综合难度: 3 - 4     考场目标: 60 - 100 分     需要掌握:邻接表储存

0.不要陷进误区,看到树,距离就想dfs过程中计算2点的距离,先分析何时满足条件

1.突破口:每条边的长度为1,(u,v)两点距离为2 等价于 这两点之间有一个点

2.枚举每个点t,枚举与t相连的点u,v,累加Wu * Wv就是权值之和,max(Wu * Wv)就是最大值

最差情况,一个点连接其余各点,此时时间复杂度O(N^2),而数据N <= 200,000,不能通过所有数据,期望得分70分.

优化:时间复杂度O(n)或O(nlogn)才能通过全部数据,需要枚举到每个点t时,将2重循环u,v,降到1重循环完成统计权值之和与最大值.

假设这个点与4个点相连,那么

权值之和 = 2*(w1 * w2 + w1 * w3 + w1 * w4 + w2 * w3 + w2 * w4 + w3 * w4)            =w1 * (w2 + w3 + w4) + w2 * (w1 + w3 + w4) + w3 * (w1 + w2 + w4) + w4 * (w1 + w2 + w3)       

 =w1 * (s - w1) + w2 * (s - w2) + w3 * (s - w3) + w4 * (s - w4)

此时对于各点t,只要循环一遍u,累加Wu * (s - Wu)就是权值之和.max(Wu * Wv)等价与最大的Wu与第二大的Wu相乘,所以需要记录下每个点相连的最大与次大值即可.

时间复杂度O(n)轻松通过所有数据

注意:权值之和需要对10007取余,最大值不用取余

2014-C 飞扬的小鸟

类型: 动态规划     综合难度: 4 - 5     考场目标: 70 - 100 分

1.读完题看数据规模n <= 10,000,而且飞到下个位置的点击数肯定只与上一个位置的点击数有关,应马上意识到这是个动态规划问题.

2.状态F[i][j]横向走到i,纵向飞到j所用的最小点击数,ans = max{f[n][j]}

3.转移方程

向下降:

f[i][j] = min(f[i][j], f[i - 1][j + Y[i]])

向上升:

f[i][j + k * X[i]] = min(f[i][j + k * X[i]], f[i - 1][j] + k), j + k * X[i] < M

f[i][M] = min(f[i][M], f[i - 1][j] + k), j + k * X[i] >= M

初始值: 位置0,任意高度大于0小于等于M的高度点击次数都是0,即f[0][i] = 0;

此时复杂度O(KNM),过不了全部数据,预计得分75分

优化:

状态肯定减少不了,只能在转移降低复杂度,也就是不用k循环怎么O(1)解决转移.

F[i][j]只考虑点击一次,要么从i位置j - X[i]高处再点击一次,要么从i - 1位置j - X[i]高处再点击一次,所以

f[i][j + X[i]] = min(f[i][j] + 1, f[i - 1][j] + 1), j + k * X[i] < M

f[i][M] = min(min(f[i][j] + 1, f[i - 1][j] + 1), f[i][M]), j + k * X[i] >= M

Day2

2014-D 无线网络发射器选址

类型: 模拟    综合难度: 1     考场目标: 100 分

1.直接四重循环判断每个点覆盖多少个点即可

2.注意不要边界越界

2014-E 寻找道路

类型: 简单图论    综合难度: 4     考场目标: 60 - 100 分     需要掌握:dfs,bfs

关键点:路径上的所有点的出边所指向的点都直接或间接与终点连通解决这个关键点后就是个单源最短路问题.

出边要指向终点,反过来思考,可以从终点走反向边,经过u这个点几次,就等价于从t出发有几条边能最终通向终点所以反向建边,判断终点到u点的次数IN与u点的出边数OUT是否相等,相等则可以走u这个点,否则不能经过u因为各边长度都为1,所以最短路不必写spfa,直接bfs即可

2014-F 解方程

类型: 数学题     综合难度: 5     考场目标: 30-100 分

由于高次方程没有求根公式,只能是带入判断是否等于0.

然而数据范围:

对于30%的数据:0<=100,an!=0,m<100< p="">

对于50%的数据:0<=10^100,an!=0,m<100< p="">

对于70%的数据:0<=10^10000,an!=0,m<10000< p="">

对于100%的数据:0<=10^10000,an!=0,m<1000000< p="">

直接带入有30分,加高精度也只有50分,极限数据m=1,000,000显然存在O(nm)或以下的算法也就是说要优化大系数10^10000的处理方式.所以一定是个数学问题.

考虑必要性,如果计算结果对一个大质数取余不等于0则不可能结果等于零,如果对多个大质数取余都为0则有极高的把握计算的结果为0.

时间复杂度为O(nm),10^8量级,由于取模速度较慢,可能会被卡常数

优化:如果f(x) % PR不等于0则f(x + PR)%PR也一定不为0,从这点入手,可以第一次模一个10^4级的质数,如果f(k)%PR不等于0,类似筛选法求素数,无需再计算f(x + k * PR)的值,一定不可能为0.

--end--

声明：本文章由网友投稿作为教育分享用途，如有侵权原作者可通过邮件及时和我们联系删除：freemanzk@qq.com