题目链接

[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;
}