|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 zhangjinxuan 于 2023-7-10 20:43 编辑
题目链接：https://www.luogu.com.cn/problem/P7073
我的代码：#include <bits/stdc++.h>
using namespace std;
struct Node {
bool type; // 0 -> operator, 1 -> value
char c; // if type == 0, it means operator (&, |)
bool noted; // not -> !
bool ok; // If this change, result can change
int id; // number id
int l, r; //left, right sons
int value; //eval_value
} a[500001];
int nodtot, nums[1000001], numtot;
int stak[1000001], top, root;
int n, na[1000001], rootvalue, q, x;
void get_ans(int r) {
if (a[r].type == 1) {
a[r].value = na[a[r].id];
if (a[r].noted) a[r].value = !a[r].value;
return;
}
get_ans(a[r].l);
get_ans(a[r].r);
if (a[r].c == '&') {
a[r].value = a[a[r].l].value & a[a[r].r].value;
if (a[r].noted) a[r].value = !a[r].value;
} else {
a[r].value = a[a[r].l].value | a[a[r].r].value;
if (a[r].noted) a[r].value = !a[r].value;
}
}
void get_dp_value(int r) {
if (!a[r].ok) return;
if (a[r].type == 1) return; // no left, right sons
if (a[r].c == '&') {
if (a[a[r].r].value != 0) a[a[r].l].ok = 1;
if (a[a[r].l].value != 0) a[a[r].r].ok = 1;
} else {
if (a[a[r].r].value != 1) a[a[r].l].ok = 1;
if (a[a[r].l].value != 1) a[a[r].r].ok = 1;
}
get_dp_value(a[r].l);
get_dp_value(a[r].r);
}
int main() {
char c;
int id = 0, lasttype = -1; //0 means operator, 1 means number
while ((c = getchar()) != '\n') { // LN
if (c == '\r') continue; // CR
if (c == ' ') { // space
if (lasttype == 1) {
a[++nodtot] = {1, 0, 0, 0, id, -1, -1};
/*Tip:Type,c,noted,ok,id, l, r*/
nums[++numtot] = nodtot;
stak[++top] = nodtot;
id = 0;
}
} else if (c == '&' || c == '|' || c == '!') { // operator
lasttype = 0;
if (c == '!') {
a[stak[top]].noted = 1;
} else {
int r = stak[top--];
int l = stak[top--];
a[++nodtot] = {0, c, 0, 0, 0, l, r};
stak[++top] = nodtot;
}
} else if (c == 'x') { // number first
lasttype = 1;
id = 0;
} else if (c >= '0' && c <= '9') { // number
lasttype = 1;
id = id * 10 + c - '0';
} else assert(0);
}
root = stak[top]; // root id
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &na[i]);
}
get_ans(root); // get value
rootvalue = a[root].value; // root value
a[root].ok = 1; //first, root change result will change, its right
get_dp_value(root);
scanf("%d", &q);
while (q--) {
scanf("%d", &x);
if (a[nums[x]].ok) printf("%d\n", !rootvalue); // Can change, change result
else printf("%d\n", rootvalue); // Else, it cannot change result
}
return 0;
}
总体思路：
先输入字符串，处理成为表达式树，在计算一下整个表达式的结果，接着来处理出如果一个节点发生改变，结果会不会改变，然后，就来回答，能改变就输出相反值，否则输出原结果
只不过，这是错的，因为在 nums[++numtot] 这一行不对，应该是 nums[id] = nodtot, numtot 也就不要了，悲，我就因为这个调了 一整天
现在第一个回复，奖 2 鱼币，因为你缓解了我悲痛的心情！
最佳答案与问题无关！
代码的问题可能在于输入数字时没有正确处理完毕。具体来说，当读入一个数字时，应该将 lasttype 设置为 1，而不是等到空格时再设置，因为只有在读入数字时才能确定一个节点的类型。因此，可以改成以下代码： while ((c = getchar()) != '\n') {
if (c == '\r') continue;
if (c == ' ') {
if (lasttype == 1) {
a[++nodtot] = {1, 0, 0, 0, id, -1, -1};
nums[++numtot] = nodtot;
stak[++top] = nodtot;
id = 0;
}
lasttype = -1;
} else if (c == '&' || c == '|' || c == '!') {
lasttype = 0;
if (c == '!') {
a[stak[top]].noted = 1;
} else {
int r = stak[top--];
int l = stak[top--];
a[++nodtot] = {0, c, 0, 0, 0, l, r};
stak[++top] = nodtot;
}
} else if (c == 'x') {
lasttype = 1;
id = 0;
} else if (c >= '0' && c <= '9') {
lasttype = 1;
id = id * 10 + c - '0';
} else assert(0);
}
另外，也许需要检查一下其他部分是否存在问题，比如变量名和数组下标是否对应等等。
|
评分
-
查看全部评分
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2023-4-2 17:44:11
置顶卡
千斤顶
显身卡
楼主
发表于 2023-4-2 17:56:39
