CSP-J 2020表达式题目求助，代码看不出问题，求高人指导（本人自己想出来了）,C\C++交流,技术交流,鱼C论坛

zhangjinxuan 发表于 2023-4-2 17:44:11

CSP-J 2020表达式题目求助，代码看不出问题，求高人指导（本人自己想出来了）

本帖最后由 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;

int nodtot, nums, numtot;
int stak, top, root;
int n, na, rootvalue, q, x;

void get_ans(int r) {
if (a.type == 1) {
a.value = na.id];
if (a.noted) a.value = !a.value;
return;
}
get_ans(a.l);
get_ans(a.r);
if (a.c == '&') {
a.value = a.l].value & a.r].value;
if (a.noted) a.value = !a.value;
} else {
a.value = a.l].value | a.r].value;
if (a.noted) a.value = !a.value;
}
}

void get_dp_value(int r) {
if (!a.ok) return;
if (a.type == 1) return; // no left, right sons
if (a.c == '&') {
if (a.r].value != 0) a.l].ok = 1;
if (a.l].value != 0) a.r].ok = 1;
} else {
if (a.r].value != 1) a.l].ok = 1;
if (a.l].value != 1) a.r].ok = 1;
}
get_dp_value(a.l);
get_dp_value(a.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].noted = 1;
} else {
int r = stak;
int l = stak;
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; // root id
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &na);
}
get_ans(root); // get value
rootvalue = a.value; // root value
a.ok = 1; //first, root change result will change, its right
get_dp_value(root);
scanf("%d", &q);
while (q--) {
scanf("%d", &x);
if (a].ok) printf("%d\n", !rootvalue); // Can change, change result
else printf("%d\n", rootvalue); // Else, it cannot change result
}
return 0;
}
链接：https://www.luogu.com.cn/record/106777888
总体思路：

先输入字符串，处理成为表达式树，在计算一下整个表达式的结果，接着来处理出如果一个节点发生改变，结果会不会改变，然后，就来回答，能改变就输出相反值，否则输出原结果

只不过，这是错的，因为在 nums[++numtot] 这一行不对，应该是 nums = nodtot, numtot 也就不要了，悲，我就因为这个调了一整天{:10_266:}

现在第一个回复，奖 2 鱼币，因为你缓解了我悲痛的心情！{:10_256:}

最佳答案与问题无关！

zhangjinxuan 发表于 2023-4-2 17:53:03

@tommyyu @ExiaGN001 @额外减小

额外减小 发表于 2023-4-2 17:55:23

呵呵。以后超过普及/提高-的题目都不要叫我。
我不是信竞的，我是物竞（悲）

歌者文明清理员 发表于 2023-4-2 17:56:39

代码的问题可能在于输入数字时没有正确处理完毕。具体来说，当读入一个数字时，应该将 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].noted = 1;
   } else {
         int r = stak;
         int l = stak;
         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);
}

另外，也许需要检查一下其他部分是否存在问题，比如变量名和数组下标是否对应等等。

zhangjinxuan 发表于 2023-4-2 18:07:07

额外减小发表于 2023-4-2 17:55
呵呵。以后超过普及/提高-的题目都不要叫我。
我不是信竞的，我是物竞（悲）

az

zhangjinxuan 发表于 2023-4-2 18:09:39

歌者文明清理员发表于 2023-4-2 17:56
代码的问题可能在于输入数字时没有正确处理完毕。具体来说，当读入一个数字时，应该将 lasttype 设置为 1， ...

还是25分：
#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;

int nodtot, nums, numtot;
int stak, top, root;
int n, na, rootvalue, q, x;

void get_ans(int r) {
if (a.type == 1) {
a.value = na.id];
if (a.noted) a.value = !a.value;
return;
}
get_ans(a.l);
get_ans(a.r);
if (a.c == '&') {
a.value = a.l].value & a.r].value;
if (a.noted) a.value = !a.value;
} else {
a.value = a.l].value | a.r].value;
if (a.noted) a.value = !a.value;
}
}

void get_dp_value(int r) {
if (!a.ok) return;
if (a.type == 1) return; // no left, right sons
if (a.c == '&') {
if (a.r].value != 0) a.l].ok = 1;
if (a.l].value != 0) a.r].ok = 1;
} else {
if (a.r].value != 1) a.l].ok = 1;
if (a.l].value != 1) a.r].ok = 1;
}
get_dp_value(a.l);
get_dp_value(a.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;
}
lasttype = -1;
} else if (c == '&' || c == '|' || c == '!') { // operator
lasttype = 0;
if (c == '!') {
a].noted = 1;
} else {
int r = stak;
int l = stak;
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; // root id
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &na);
}
get_ans(root); // get value
rootvalue = a.value; // root value
a.ok = 1; //first, root change result will change, its right
get_dp_value(root);
scanf("%d", &q);
while (q--) {
scanf("%d", &x);
if (a].ok) printf("%d\n", !rootvalue); // Can change, change result
else printf("%d\n", rootvalue); // Else, it cannot change result
}
return 0;
}

ExiaGN001 发表于 2023-4-2 21:28:55

zhangjinxuan 发表于 2023-4-2 17:53
@tommyyu @ExiaGN001 @额外减小

最近不在线，勿at

zhangjinxuan 发表于 2023-4-3 07:17:50

ExiaGN001 发表于 2023-4-2 21:28
最近不在线，勿at

{:10_291:}

myd0313 发表于 2023-4-3 18:37:25

{:10_266:}

页: [1]

鱼C论坛's Archiver

CSP-J 2020表达式 题目求助，代码看不出问题，求高人指导（本人自己想出来了）

CSP-J 2020表达式题目求助，代码看不出问题，求高人指导（本人自己想出来了）