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<<i 1<<i。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main()
{
int n; scanf("%d", &n);
if (n % 2) printf("-1\n");
else
{
for (int i = 24; i >= 1; --i)
{
if (n / (1 << i) == 1)
{
n -= (1 << i);
printf("%d ", 1 << i);
}
}
}
return 0;
}
算法拓展
打表。预处理出 2 i 2^i 2i次方的值，用数组存起来。对每个预处理的值进行标记。倒序枚举 n n n，如果枚举的值被标记了，说明他是 2 i 2^i 2i。可以直接输出，相应的 n n n的值也要减去 2 i 2^i 2i。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int b[30] ={0,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216};
int v[18000000];
int main()
{
int n; scanf("%d", &n);
if (n % 2)
{
printf("-1"); return 0;
}
for (int i = 1; i <= 24; ++i) v[b[i]] = 1;
int x = n;
while (x)
{
if (v[x])
{
printf("%d ", x);
x = n - x;
n = x;
}else --x;
}
return 0;
}
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。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int f[610];
int main()
{
int n, w, cnt, d;
scanf("%d%d", &n, &w);
for (register int t = 1; t <= n; ++t)
{
scanf("%d", &d);
++f[d]; // 记录该成绩的人数有多少个
cnt = t * w / 100;
if (cnt < 1) cnt = 1;
// 找排名第cnt的分数
int s = 0, k;
for (k = 600; k >= 0; --k)
{
s += f[k];
if (s >= cnt) break;
}
printf("%d ", k);
}
return 0;
}
算法拓展
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，从栈中依次弹出两个数字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。结点开结构体，存父节点、左右儿子、值、字符。
struct node
{
int par, lchild, rchild, data;
char c;
}stree[1000010];
字符串用 g e t c h a r getchar getchar读入。当读入 x x x的时候，后面跟的就是数字，把数字处理出来，然后建立结点并入栈。当读入 ! ! !的时候，建立结点，栈顶的结点作为该结点的左儿子。当读入 & \& &和 ∣ | ∣时，建立结点，栈顶的结点分别作为他们的右儿子和左儿子。这样就建成了表达式树。根结点的值就是整体结果。
查询时。取反的结点都是叶结点。只需要改变该叶结点到根结点之间的结点的值就可以了。如果数据是随机的，每次查询的平均复杂度就是 l o g log log级别的。一个很重要的优化：当某个结点的值和原先的值相同时，则直接返回根节点的值。本题有特殊数据，以下代码官方数据能得95分。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char s[1000010];
int a[100010], n, cnt, sstack[1000010], stop;
struct node
{
int par, lchild, rchild, data;
char c;
}stree[1000010];
int main()
{
int len = 0;
while ((s[++len] = getchar()) != '\n'); s[len] = 32;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
cnt = n;
for (int i = 1; i <= len; ++i)
{
if (s[i] == 'x')
{
int snum = 0, t = i + 1;
while (s[t] != 32)
{
snum = snum * 10 + s[t] - '0';
++t;
}
i = t;
sstack[++stop] = snum;
stree[snum].data = a[snum]; stree[snum].c = a[snum] + '0';
}else if (s[i] == '!')
{
stree[++cnt].lchild = sstack[stop]; --stop;
stree[stree[cnt].lchild].par = cnt;
stree[cnt].data = !stree[stree[cnt].lchild].data;
stree[cnt].c = '!';
sstack[++stop] = cnt;
}else if (s[i] == '&')
{
stree[++cnt].rchild = sstack[stop]; --stop;
stree[cnt].lchild = sstack[stop]; --stop;
stree[stree[cnt].lchild].par = cnt;
stree[stree[cnt].rchild].par = cnt;
stree[cnt].data = stree[stree[cnt].lchild].data & stree[stree[cnt].rchild].data;
stree[cnt].c = '&';
sstack[++stop] = cnt;
}else if (s[i] == '|')
{
stree[++cnt].rchild = sstack[stop]; --stop;
stree[cnt].lchild = sstack[stop]; --stop;
stree[stree[cnt].lchild].par = cnt;
stree[stree[cnt].rchild].par = cnt;
stree[cnt].data = stree[stree[cnt].lchild].data | stree[stree[cnt].rchild].data;
stree[cnt].c = '|';
sstack[++stop] = cnt;
}
}
int q; scanf("%d", &q);
while (q--)
{
int t; scanf("%d", &t);
int p, sres = !a[t];
while (1)
{
p = stree[t].par;
if (stree[p].c == '!') sres = !sres;
else if (stree[p].c == '&')
{
if (stree[p].lchild == t) sres = sres & stree[stree[p].rchild].data;
else sres = sres & stree[stree[p].lchild].data;
}else if (stree[p].c == '|')
{
if (stree[p].lchild == t) sres = sres | stree[stree[p].rchild].data;
else sres = sres | stree[stree[p].lchild].data;
}
if (sres == stree[p].data)
{
sres = stree[cnt].data; break;
}
t = p;
if (stree[t].par == 0) break;
}
printf("%d\n", sres);
}
return 0;
}
以上表达式树不是平衡树，有3种特殊情况会过不了。
1.全都是
!
!
!或大部分是。树退化成了链。
2.全都是
&
\&
&或大部分是。树几乎退化成了链。
3.全都是
∣
|
∣或大部分是。树几乎退化成了链。
如下图：
在上述过程中，我们可以发现，某些点的值无论怎么变，都不会影响最终的结果。比如
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)。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
using namespace std;
char s[1000010];
int a[100010], n, cnt, sstack[1000010], stop;
struct node
{
int lchild, rchild, data, tag;
char c;
}stree[1000010];
void print_tag(int t)
{
if (stree[t].lchild == 0 && stree[t].rchild == 0) return; // 叶结点
if (stree[t].tag == 1)
{
stree[stree[t].lchild].tag = stree[stree[t].rchild].tag = 1;
}else if (stree[t].c == '&')
{
if (stree[stree[t].lchild].data == 0) stree[stree[t].rchild].tag = 1;
if (stree[stree[t].rchild].data == 0) stree[stree[t].lchild].tag = 1;
}else if (stree[t].c == '|')
{
if (stree[stree[t].lchild].data == 1) stree[stree[t].rchild].tag = 1;
if (stree[stree[t].rchild].data == 1) stree[stree[t].lchild].tag = 1;
}
print_tag(stree[t].lchild);
print_tag(stree[t].rchild);
}
int main()
{
int len = 0;
while ((s[++len] = getchar()) != '\n'); s[len] = 32;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
cnt = n;
for (int i = 1; i <= len; ++i)
{
if (s[i] == 'x')
{
int snum = 0, t = i + 1;
while (s[t] != 32)
{
snum = snum * 10 + s[t] - '0';
++t;
}
i = t;
sstack[++stop] = snum;
stree[snum].data = a[snum]; stree[snum].c = a[snum] + '0';
}else if (s[i] == '!')
{
stree[++cnt].lchild = sstack[stop]; --stop;
stree[cnt].data = !stree[stree[cnt].lchild].data;
stree[cnt].c = '!';
sstack[++stop] = cnt;
}else if (s[i] == '&')
{
stree[++cnt].rchild = sstack[stop]; --stop;
stree[cnt].lchild = sstack[stop]; --stop;
stree[cnt].data = stree[stree[cnt].lchild].data & stree[stree[cnt].rchild].data;
stree[cnt].c = '&';
sstack[++stop] = cnt;
}else if (s[i] == '|')
{
stree[++cnt].rchild = sstack[stop]; --stop;
stree[cnt].lchild = sstack[stop]; --stop;
stree[cnt].data = stree[stree[cnt].lchild].data | stree[stree[cnt].rchild].data;
stree[cnt].c = '|';
sstack[++stop] = cnt;
}
}
print_tag(cnt); // 打标记，打上标记的结点，值是否改变，对结果不影响
int ans = stree[cnt].data;
int q; scanf("%d", &q);
while (q--)
{
int t; scanf("%d", &t);
if (stree[t].tag == 0) printf("%d\n", !ans); else printf("%d\n", ans);
}
return 0;
}
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。
#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
int n, m, a[1010][1010];
ll f[1010][1010][3];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) scanf("%d", &a[i][j]);
for (int i = 1; i <= n; ++i) f[i][1][1] = f[i][1][0] = f[i][1][2] = f[i-1][1][0] + a[i][1];
for (int j = 2; j <= m; ++j)
{
// f[i][j][0]
f[1][j][0] = f[1][j-1][2] + a[1][j];
for (int i = 2; i <= n; ++i)
f[i][j][0] = max(f[i][j-1][2], f[i-1][j][0]) + a[i][j];
// f[i][j][1]
f[n][j][1] = f[n][j-1][2] + a[n][j];
for (int i = n - 1; i >= 1; --i)
f[i][j][1] = max(f[i][j-1][2], f[i+1][j][1]) + a[i][j];
// f[i][j][2]
for (int i = 1; i <= n; ++i)
f[i][j][2] = max(f[i][j][0], f[i][j][1]);
}
printf("%lld\n", f[n][m][2]);
return 0;
}
算法拓展
记忆化搜索。 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代码。
核心代码：
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));
其实记忆化搜索就是dp的一种组织形式，也是dfs中优化的利器。