题解 – CSP-J2020 T3/T4

题目链接

[T3]表达式
[T4]方格取数

为什么写这个题解呢，因为当年打的时候对题目不是很理解，今天突然看到自己“尝试过的题目”，忍不住去写一下，结果又花了好多时间……我还不够强啊！

T3

题目描述

给出一个后缀表达式，包含 x_{1 – n} , \And 符号 , | 符号与 ! 符号。求出当删去每个 x_i 时，表达式的值（以询问的样式给出）。

题解

题目看起来还是比较简单的，首先建树：建立一个栈读入，每次读到 \And 或者 | 时，退栈两个，入栈一个。
我们发现，解决问题必须只访问一次元素，正好，dfs一遍可以解决。我们想在dfs的时候会有什么性质。首先这是一颗二叉树，一开始我们会遍历一些运算符，数字往往是在最后访问到。那么在访问运算符的时候，是否有方法将数字的答案都算出来呢。我们发现，当前的 \And 运算符，其中一个儿子为 0 ，则另一支子树完全失效；同样，当前的 | ，其中一个儿子为 1 时，则另一支子树完全失效，我们用 fw 数组去标记这个状态。当然标记完这个状态就可以马上将这个状态传递到儿子。
现在来考虑为什么没有被标记的节点会对答案造成影响。是这样的，每次操作完都要回退——每次只求只更改一个数字的答案，并不是多个数字；所以在这个数字到根的路径上，任何人的父亲的另一条子树的结果都是确定的，那么自己的支路是否会被标记就成了答案的关键。自上向下传递成立！
于是每次查询只需要 \mathcal{O}(1) 的复杂度。
总时间复杂度：\mathcal{O}(n + q)

细节真的很多，一开始就写出来，调了40分钟

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
/*
结论1：两个1或 - 恒为1
结论2：两个0与 - 恒为0
结论3：1和0与、或结果一样，1的答案是0，0的答案是1
结论4：两个0或 - 恒为1
结论5：两个1与 - 恒为0
我们只要统计这个东西对原序列是否有用，如果不是没用，那一定有用。。
当 0 & x 或者 1 | x时，x的值对表达式无影响
*/
char s[1000010];
bool a[300010];
int son[300010][2];
int cls[100010];
bool fw[300010];
int cnt;
int n;
inline void dfs(int pos) {//第一遍遍历，查找那种fw节点，下一遍dfs，标记fw
  if(cls[pos] == 0) return;
  if(cls[pos] == 1) {
    int s1 = son[pos][0];
    int s2 = son[pos][1];
    if(a[s1] == 0 && a[s2] == 0) {fw[s1] = fw[s2] = 1; return;}
    if(a[s1] == 0) {fw[s2] = 1; dfs(s1); return;}
    if(a[s2] == 0) {fw[s1] = 1; dfs(s2); return;}
    dfs(s1);
    dfs(s2);
  }
  if(cls[pos] == 2) {
    int s1 = son[pos][0];
    int s2 = son[pos][1];
    if(a[s1] == 1 && a[s2] == 1) {fw[s1] = fw[s2] = 1; return;}
    if(a[s1] == 1) {fw[s2] = 1; dfs(s1); return;}
    if(a[s2] == 1) {fw[s1] = 1; dfs(s2); return;}
    dfs(s1);
    dfs(s2);
  }
}
//这个也可以用dfs序，本质一样
void cd(int pos, int stat) {
  if(pos == 0) return;
  if(cls[pos] == 0) {fw[pos] = stat; return;}
  // printf("%d\n", pos);
  int s1 = son[pos][0];
  int s2 = son[pos][1];
  if(stat == 0) {
    cd(s1, fw[s1]);
    cd(s2, fw[s2]);
  }
  if(stat == 1) {
    cd(s1, 1);
    cd(s2, 1);
  }
  return;
}
int main()
{
  // freopen(".in", "r", stdin);
  // freopen(".out", "w", stdout);
  gets(s);
  stack<int> st;
  scanf("%d", &n);
  for(int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  cnt = n + 1;
  int l = strlen(s);//读入
  for(int i = 0; i < l; i++) {
    // printf("%c", s[i]);
    if(s[i] == 'x') {
      i++;
      int val = 0;
      while(isdigit(s[i])) {
        val = val * 10 + s[i] - '0';
        i++;
      }
      // printf("%d ", val);
      cls[val] = 0;
      st.push(val);
    }
    else if(s[i] == '&') {
      auto s1 = st.top(); st.pop();
      auto s2 = st.top(); st.pop();
      st.push(cnt);
      son[cnt][0] = s1;
      son[cnt][1] = s2;
      a[cnt] = a[s1] & a[s2];
      // printf("%d\n", cnt);
      cls[cnt++] = 1;
    }
    else if(s[i] == '|') {
      auto s1 = st.top(); st.pop();
      auto s2 = st.top(); st.pop();
      st.push(cnt);
      son[cnt][0] = s1;
      son[cnt][1] = s2;
      a[cnt] = a[s1] | a[s2];
      cls[cnt++] = 2;
    }
    else if(s[i] == '!') {
      auto tmp = st.top();
      a[tmp] = !a[tmp];
    }
  }
  int s = cnt - 1;
  dfs(s);
  // cout << 114514;
  cd(s, 0);
  int q, k;
  scanf("%d", &q);
  // for(int i = 1; i < cnt; i++) {
  //   printf("%d %d %d %d %d\n", a[i], fw[i], cls[i], son[i][0], son[i][1]);
  // }
  while(q--) {
    scanf("%d", &k);
    printf("%d\n", fw[k] ? a[s] : !a[s]);
  }
  return 0;
}

T4

妹想出来怎么做啊，但是黄题。

题目描述

一张 n \times m 的方格图，从左上角走到右下角，只能往右、往上、往下走，求经过路径的最大贡献。

题解

我还没仔细分析过复杂度，这题还是很微妙的。
首先，正搜跟反搜应该是一样的，毕竟图倒转过来也是从左上走到右下角。比较关键的部分是 vis ，即有没有访问过，以及衍生的该访问过的点是不是最优解问题。这方便我们进行记忆化搜索，以达到题目允许的 \mathcal{O}(nm) 复杂度。
这个时候考虑一下走的方向的特殊性，假设现在在终点，只能通过左边或上面而来，而如果现在在终点上面一格，同样也只能通过左边或上面走来。推广一下，在某一列只能向上走或者向下走，其实就是普通的记忆化搜索，如果可能有更优解，从前面转移过来就行，最后前面回溯完了，当前的位置可以保证是最优的。
所以转移的时候考虑两种状态就可以了，分别是在这一列上从下走来，或者从上走来，这其中每个状态都可以从上一列转移过来。

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const ll Min = -(1LL << 55);
const int MAXN = 1e3 + 10;
ll mp[MAXN][MAXN];
ll ans[MAXN][MAXN][2];
int n, m;
int dx[] = {0, 1, -1};
int dy[] = {1, 0, 0};
//虽然说是记忆化搜索，但是基本思想是从右搜到左，优先上下搜()
inline ll dfs(int x, int y, int from) {
  //from  0从下面来 1从上面来
  if(x < 1 || y < 1 || x > n || y > m) return Min;
  if(ans[x][y][from] != Min) return ans[x][y][from];
  if(from == 0) ans[x][y][from] = max(max(dfs(x + 1, y, 0), dfs(x, y - 1, 0)), dfs(x, y - 1, 1)) + mp[x][y];
  else ans[x][y][from] = max(max(dfs(x - 1, y, 1), dfs(x, y - 1, 0)), dfs(x, y - 1, 1)) + mp[x][y];
  return ans[x][y][from];
}
int main()
{
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      scanf("%lld", &mp[i][j]);
      ans[i][j][0] = ans[i][j][1] = Min;
    }
  }
  ans[1][1][1] = ans[1][1][0] = mp[1][1];
  printf("%lld\n", dfs(n, m, 1));
  return 0;
}