1.优秀的拆分
算法分析
奇数不存在优秀的拆分。
偶数一定存在优秀的拆分。
从大到小枚举2的
i
i
i次方,从24到1。
如果
n
n
n能被
2
i
2^i
2i整除,说明
2
i
2^i
2i是他的一个拆分项,输出。
2
i
2^i
2i可以表示为
1
<
<
i
1<1<<i。 算法拓展 打表。 预处理出
2
i
2^i
2i次方的值,用数组存起来。 对每个预处理的值进行标记。 倒序枚举
n
n
n,如果枚举的值被标记了,说明他是
2
i
2^i
2i。 可以直接输出,相应的
n
n
n的值也要减去
2
i
2^i
2i。 2.直播获奖 算法分析 每个选手的成绩取值范围是
[
0
,
600
]
[0, 600]
[0,600],可以用hash思想。 读到一个成绩的时候,就标记一下。 然后从600到0倒序枚举分数线统计个数,当个数大于等于获奖人数时退出,此时就是答案。 时间复杂度
O
(
600
n
)
O(600n)
O(600n),
n
n
n最大为10万,可以过。 注意事项:对于
p
∗
w
%
p * w\%
p∗w%的下取整,要注意精度跳变,可以用整除替换:
p
∗
w
/
100
p * w / 100
p∗w/100。 算法拓展 1.插入排序。 由大到小排序,增加一个人时,直接向前邻项交换。 由大到小取。 排到最后,其实就相当于一遍完整插入排序的时间复杂度。 插入排序时间复杂度不稳定,最坏情况是
O
(
n
2
)
O(n^2)
O(n2),最好情况是
O
(
n
)
O(n)
O(n),不知道能过多少点。 2.对顶堆。 对顶堆可以维护单调区间第k大数或第k小数。 本题适用于求第k大数。 左边的是小根堆q1,右边的是大根堆q2。 两者拼接起来就是由大到小。 假设该轮的获奖人数为t。 第x个选手成绩出来后,如果此时q1的个数小于t,则把x丢进q1。 如果q1的个数还是小于t,则q2的堆顶出堆,进入q1,直到q1的个数等于t。 此时q1的堆顶分数就是答案。 入堆和出堆时间复杂度都是
l
o
g
log
log的,整体复杂度
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)。 3.表达式 算法分析 对于后缀表达式的计算,朴素的算法可以借助数字栈。 从左到右扫描,遇到数字就入栈,遇到 *** 作符op,从栈中依次d出两个数字x2和x1,进行运算
x
1
o
p
x
2
x1 \,op \,x2
x1opx2,然后将运算结果再入栈。 如果是动态取反某个数字q次查询,这个复杂度就高了,为
O
(
n
∗
q
)
O(n*q)
O(n∗q)。 对于这种改变的地方很少,但是需要整体结果的,就需要考虑将改变的影响降到最少。 表达式树。 建立表达式树的时候还得借助栈。 在表达式中,数字都是叶结点,运算符都是非叶结点。 叶结点的编号按照1~n进行,运算符按照从左到右的顺序在n的基础上分别加1。 结点开结构体,存父节点、左右儿子、值、字符。 字符串用
g
e
t
c
h
a
r
getchar
getchar读入。 当读入
x
x
x的时候,后面跟的就是数字,把数字处理出来,然后建立结点并入栈。 当读入
!
!
!的时候,建立结点,栈顶的结点作为该结点的左儿子。 当读入
&
\&
&和
∣
|
∣时,建立结点,栈顶的结点分别作为他们的右儿子和左儿子。 这样就建成了表达式树。 根结点的值就是整体结果。 查询时。 取反的结点都是叶结点。 只需要改变该叶结点到根结点之间的结点的值就可以了。 如果数据是随机的,每次查询的平均复杂度就是
l
o
g
log
log级别的。 一个很重要的优化:当某个结点的值和原先的值相同时,则直接返回根节点的值。 本题有特殊数据,以下代码官方数据能得95分。 以上表达式树不是平衡树,有3种特殊情况会过不了。 1.全都是
!
!
!或大部分是。 树退化成了链。 树几乎退化成了链。 树几乎退化成了链。 如下图: 比如
0
&
a
0\,\&\,a
0&a,
a
a
a的值无论怎么改变都不会影响结果,此时我们可以给值为
a
a
a的这个点打个标记。 相似的还有
1
∣
a
1\,|\,a
1∣a。 建立表达式树后,从根结点开始向下
O
(
n
)
O(n)
O(n)的复杂度就可以完成打标记。 如果一个叶结点到跟结点的路径上,有一个点被打标记了,那么该结点也要被打标记,即标记可以下传。 这样我们最终只要判断取反的叶结点是否打了标记。 如果打标记了,则结果为根结点的值。 如果没打标记,则结果为根结点的值取反。 为什么?假设取反的叶结点没有打标记,则该叶结点到根结点的路径上都没有打标记。 则该叶结点的父结点的值就要取反,该父结点的父结点的值也要取反,依次类推,到根结点之间包含根结点的值都要取反。 查询的复杂度是
O
(
1
)
O(1)
O(1)。 4.方格取数 算法分析 这种矩阵上求最值的题目,dp无疑了。 但是每次可以向上、向下和向右走,定义两个维度如
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示从
(
1
,
1
)
(1, 1)
(1,1)走到
(
i
,
j
)
(i, j)
(i,j)的最值会有后效性。 可以考虑以列作为阶段,从左到右推进。 对于每个点
(
i
,
j
)
(i, j)
(i,j)有从上到下、从左到右和从下到上、从左到右两种方式到达。 然后再合并两种方式的最值。
f
[
i
]
[
j
]
[
0
]
f[i][j][0]
f[i][j][0]:第
j
j
j列从上到下、从左到右到达
(
i
,
j
)
(i, j)
(i,j)的最大值。
f
[
i
]
[
j
]
[
1
]
f[i][j][1]
f[i][j][1]:第
j
j
j列从下到上、从左到右到达
(
i
,
j
)
(i, j)
(i,j)的最大值。
f
[
i
]
[
j
]
[
2
]
f[i][j][2]
f[i][j][2]:合并以上两种方式,到达
(
i
,
j
)
(i, j)
(i,j)的最大值。 需要开
l
o
n
g
l
o
n
g
long \, long
longlong。 算法拓展 记忆化搜索。
f
[
i
]
[
j
]
[
0
]
f[i][j][0]
f[i][j][0]表示从上到下、从左到右到达
(
i
,
j
)
(i, j)
(i,j)的最大值,
f
[
i
]
[
j
]
[
1
]
f[i][j][1]
f[i][j][1]表示从下到上、从左到右到达
(
i
,
j
)
(i, j)
(i,j)的最大值。 目标值是
f
[
n
]
[
m
]
[
0
]
f[n][m][0]
f[n][m][0]。 倒序组织记忆化dfs代码。 核心代码: 其实记忆化搜索就是dp的一种组织形式,也是dfs中优化的利器。 欢迎分享,转载请注明来源:内存溢出#include
#include
#include
struct node
{
int par, lchild, rchild, data;
char c;
}stree[1000010];
#include
2.全都是
&
\&
&或大部分是。
3.全都是
∣
|
∣或大部分是。
在上述过程中,我们可以发现,某些点的值无论怎么变,都不会影响最终的结果。#include
#include
ll dfs(int x, int y, int t)
{
if (x < 1 || x > n || y < 1 || y > m) return mininf;
if (f[x][y][t] != mininf) return f[x][y][t];
if (t == 0) f[x][y][t] = max(dfs(x-1, y, 0), max(dfs(x, y-1, 0), dfs(x, y-1, 1))) + a[x][y];
else f[x][y][t] = max(dfs(x+1, y, 1), max(dfs(x, y-1, 0), dfs(x, y-1, 1))) + a[x][y];
return f[x][y][t];
}
printf("%lld\n", dfs(n, m, 0));
评论列表(0条)