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