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条）