CSP-J2020第二轮 解题分析

1.优秀的拆分

算法分析

奇数不存在优秀的拆分。偶数一定存在优秀的拆分。从大到小枚举2的$i$次方，从24到1。如果$n$大于$2^i$，说明$2^i$是他的一个拆分项，输出。$2^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$次方的值，用数组存起来。对每个预处理的值进行标记。倒序枚举$n$，如果枚举的值被标记了，说明他是$2^i$。可以直接输出，相应的$n$的值也要减去$2^i$。

#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]$，可以用hash思想。读到一个成绩的时候，就标记一下。然后从600到0倒序枚举分数线统计个数，当个数大于等于获奖人数时退出，此时就是答案。时间复杂度$O(600n)$，$n$最大为10万，可以过。

注意事项：对于$p\ast w\%$的下取整，要注意精度跳变，可以用整除替换：$p\ast 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.对顶堆。对顶堆可以维护单调区间第k大数或第k小数。本题适用于求第k大数。左边的是小根堆q1，右边的是大根堆q2。两者拼接起来就是由大到小。假设该轮的获奖人数为t。第x个选手成绩出来后，如果此时q1的个数小于t，则把x丢进q1。如果q1的个数还是小于t，则q2的堆顶出堆，进入q1，直到q1的个数等于t。此时q1的堆顶分数就是答案。入堆和出堆时间复杂度都是$log$的，整体复杂度$O(nlogn)$。

3.表达式

算法分析

对于后缀表达式的计算，朴素的算法可以借助数字栈。从左到右扫描，遇到数字就入栈，遇到操作符op，从栈中依次弹出两个数字x2和x1，进行运算$x1opx2$，然后将运算结果再入栈。如果是动态取反某个数字q次查询，这个复杂度就高了，为$O(n\ast q)$。对于这种改变的地方很少，但是需要整体结果的，就需要考虑将改变的影响降到最少。

表达式树。建立表达式树的时候还得借助栈。在表达式中，数字都是叶结点，运算符都是非叶结点。叶结点的编号按照1~n进行，运算符按照从左到右的顺序在n的基础上分别加1。结点开结构体，存父节点、左右儿子、值、字符。

struct node
{int par, lchild, rchild,  data;char c;
}stree[1000010];

字符串用$getchar$读入。当读入$x$的时候，后面跟的就是数字，把数字处理出来，然后建立结点并入栈。当读入$!$的时候，建立结点，栈顶的结点作为该结点的左儿子。当读入$\&$和$|$时，建立结点，栈顶的结点分别作为他们的右儿子和左儿子。这样就建成了表达式树。根结点的值就是整体结果。

查询时。取反的结点都是叶结点。只需要改变该叶结点到根结点之间的结点的值就可以了。如果数据是随机的，每次查询的平均复杂度就是$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$，$a$的值无论怎么改变都不会影响结果，此时我们可以给值为$a$的这个点打个标记。相似的还有$1|a$。建立表达式树后，从根结点开始向下$O(n)$的复杂度就可以完成打标记。如果一个叶结点到跟结点的路径上，有一个点被打标记了，那么该结点也要被打标记，即标记可以下传。这样我们最终只要判断取反的叶结点是否打了标记。如果打标记了，则结果为根结点的值。如果没打标记，则结果为根结点的值取反。为什么？假设取反的叶结点没有打标记，则该叶结点到根结点的路径上都没有打标记。则该叶结点的父结点的值就要取反，该父结点的父结点的值也要取反，依次类推，到根结点之间包含根结点的值都要取反。查询的复杂度是$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]$表示从$(1,1)$走到$(i,j)$的最值会有后效性。可以考虑以列作为阶段，从左到右推进。对于每个点$(i,j)$有从上到下、从左到右和从下到上、从左到右两种方式到达。然后再合并两种方式的最值。

$f[i][j][0]$：第$j$列从上到下、从左到右到达$(i,j)$的最大值。

$f[i][j][1]$：第$j$列从下到上、从左到右到达$(i,j)$的最大值。

$f[i][j][2]$：合并以上两种方式，到达$(i,j)$的最大值。

需要开$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]$表示从上到下、从左到右到达$(i,j)$的最大值，$f[i][j][1]$表示从下到上、从左到右到达$(i,j)$的最大值。目标值是$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中优化的利器。