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

zhangjinxuan

题目链接：https://www.luogu.com.cn/problem/P7073
我的代码：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. struct Node {
   
5.         bool type; // 0 -> operator, 1 -> value
   
6.         char c; // if type == 0, it means operator (&, |)
   
7.         bool noted; // not -> !
   
8.         bool ok; // If this change, result can change
   
9.         int id; // number id
   
10.         int l, r; //left, right sons
    
11.         int value; //eval_value
    
12. } a[500001];
    
13. 
    
14. int nodtot, nums[1000001], numtot;
    
15. int stak[1000001], top, root;
    
16. int n, na[1000001], rootvalue, q, x;
    
17. 
    
18. void get_ans(int r) {
    
19.         if (a[r].type == 1) {
    
20.                 a[r].value = na[a[r].id];
    
21.                 if (a[r].noted) a[r].value = !a[r].value;
    
22.                 return;
    
23.         }
    
24.         get_ans(a[r].l);
    
25.         get_ans(a[r].r);
    
26.         if (a[r].c == '&') {
    
27.                 a[r].value = a[a[r].l].value & a[a[r].r].value;
    
28.                 if (a[r].noted) a[r].value = !a[r].value;
    
29.         } else {
    
30.                 a[r].value = a[a[r].l].value | a[a[r].r].value;
    
31.                 if (a[r].noted) a[r].value = !a[r].value;
    
32.         }
    
33. }
    
34. 
    
35. void get_dp_value(int r) {
    
36.         if (!a[r].ok) return;
    
37.         if (a[r].type == 1) return; // no left, right sons
    
38.         if (a[r].c == '&') {
    
39.                 if (a[a[r].r].value != 0) a[a[r].l].ok = 1;
    
40.                 if (a[a[r].l].value != 0) a[a[r].r].ok = 1;
    
41.         } else {
    
42.                 if (a[a[r].r].value != 1) a[a[r].l].ok = 1;
    
43.                 if (a[a[r].l].value != 1) a[a[r].r].ok = 1;       
    
44.         }
    
45.         get_dp_value(a[r].l);
    
46.         get_dp_value(a[r].r);
    
47. }
    
48. 
    
49. int main() {
    
50.         char c;
    
51.         int id = 0, lasttype = -1; //0 means operator, 1 means number
    
52.         while ((c = getchar()) != '\n') { // LN
    
53.                 if (c == '\r') continue; // CR
    
54.                 if (c == ' ') { // space
    
55.                         if (lasttype == 1) {
    
56.                                 a[++nodtot] = {1,  0, 0,   0, id, -1, -1};
    
57.                                         /*Tip:Type,c,noted,ok,id, l, r*/
    
58.                                 nums[++numtot] = nodtot;
    
59.                                 stak[++top] = nodtot;
    
60.                                 id = 0;
    
61.                         }
    
62.                 } else if (c == '&' || c == '|' || c == '!') { // operator
    
63.                         lasttype = 0;
    
64.                         if (c == '!') {
    
65.                                 a[stak[top]].noted = 1;
    
66.                         } else {
    
67.                                 int r = stak[top--];
    
68.                                 int l = stak[top--];
    
69.                                 a[++nodtot] = {0, c, 0, 0, 0, l, r};
    
70.                                 stak[++top] = nodtot;
    
71.                         }
    
72.                 } else if (c == 'x') { // number first
    
73.                         lasttype = 1;
    
74.                         id = 0;
    
75.                 } else if (c >= '0' && c <= '9') { // number
    
76.                         lasttype = 1;
    
77.                         id = id * 10 + c - '0';
    
78.                 } else assert(0);
    
79.         }
    
80.         root = stak[top]; // root id
    
81.         scanf("%d", &n);
    
82.         for (int i = 1; i <= n; ++i) {
    
83.                 scanf("%d", &na[i]);
    
84.         }
    
85.         get_ans(root); // get value
    
86.         rootvalue = a[root].value; // root value
    
87.         a[root].ok = 1; //first, root change result will change, its right
    
88.         get_dp_value(root);
    
89.         scanf("%d", &q);
    
90.         while (q--) {
    
91.                 scanf("%d", &x);
    
92.                 if (a[nums[x]].ok) printf("%d\n", !rootvalue); // Can change, change result
    
93.                 else printf("%d\n", rootvalue); // Else, it cannot change result
    
94.         }
    
95.         return 0;
    
96. }

复制代码

链接：https://www.luogu.com.cn/record/106777888
总体思路：

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

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

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

最佳答案与问题无关！

最佳答案

月排行榜 / 总排行榜

歌者文明清理员

2023-4-2 17:56:39

代码的问题可能在于输入数字时没有正确处理完毕。具体来说，当读入一个数字时，应该将 lasttype 设置为 1，而不是等到空格时再设置，因为只有在读入数字时才能确定一个节点的类型。因此，可以改成以下代码：

1. 
   
2. while ((c = getchar()) != '\n') {
   
3.     if (c == '\r') continue;
   
4.     if (c == ' ') {
   
5.         if (lasttype == 1) {
   
6.             a[++nodtot] = {1, 0, 0, 0, id, -1, -1};
   
7.             nums[++numtot] = nodtot;
   
8.             stak[++top] = nodtot;
   
9.             id = 0;
   
10.         }
    
11.         lasttype = -1;
    
12.     } else if (c == '&' || c == '|' || c == '!') {
    
13.         lasttype = 0;
    
14.         if (c == '!') {
    
15.             a[stak[top]].noted = 1;
    
16.         } else {
    
17.             int r = stak[top--];
    
18.             int l = stak[top--];
    
19.             a[++nodtot] = {0, c, 0, 0, 0, l, r};
    
20.             stak[++top] = nodtot;
    
21.         }
    
22.     } else if (c == 'x') {
    
23.         lasttype = 1;
    
24.         id = 0;
    
25.     } else if (c >= '0' && c <= '9') {
    
26.         lasttype = 1;
    
27.         id = id * 10 + c - '0';
    
28.     } else assert(0);
    
29. }
    

复制代码

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

跳转到最佳答案楼层

zhangjinxuan

@tommyyu @ExiaGN001 @额外减小

额外减小

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

歌者文明清理员

代码的问题可能在于输入数字时没有正确处理完毕。具体来说，当读入一个数字时，应该将 lasttype 设置为 1，而不是等到空格时再设置，因为只有在读入数字时才能确定一个节点的类型。因此，可以改成以下代码：

1. 
   
2. while ((c = getchar()) != '\n') {
   
3.     if (c == '\r') continue;
   
4.     if (c == ' ') {
   
5.         if (lasttype == 1) {
   
6.             a[++nodtot] = {1, 0, 0, 0, id, -1, -1};
   
7.             nums[++numtot] = nodtot;
   
8.             stak[++top] = nodtot;
   
9.             id = 0;
   
10.         }
    
11.         lasttype = -1;
    
12.     } else if (c == '&' || c == '|' || c == '!') {
    
13.         lasttype = 0;
    
14.         if (c == '!') {
    
15.             a[stak[top]].noted = 1;
    
16.         } else {
    
17.             int r = stak[top--];
    
18.             int l = stak[top--];
    
19.             a[++nodtot] = {0, c, 0, 0, 0, l, r};
    
20.             stak[++top] = nodtot;
    
21.         }
    
22.     } else if (c == 'x') {
    
23.         lasttype = 1;
    
24.         id = 0;
    
25.     } else if (c >= '0' && c <= '9') {
    
26.         lasttype = 1;
    
27.         id = id * 10 + c - '0';
    
28.     } else assert(0);
    
29. }
    

复制代码

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

zhangjinxuan

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

az

zhangjinxuan

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

还是25分：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. struct Node {
   
5.         bool type; // 0 -> operator, 1 -> value
   
6.         char c; // if type == 0, it means operator (&, |)
   
7.         bool noted; // not -> !
   
8.         bool ok; // If this change, result can change
   
9.         int id; // number id
   
10.         int l, r; //left, right sons
    
11.         int value; //eval_value
    
12. } a[500001];
    
13. 
    
14. int nodtot, nums[1000001], numtot;
    
15. int stak[1000001], top, root;
    
16. int n, na[1000001], rootvalue, q, x;
    
17. 
    
18. void get_ans(int r) {
    
19.         if (a[r].type == 1) {
    
20.                 a[r].value = na[a[r].id];
    
21.                 if (a[r].noted) a[r].value = !a[r].value;
    
22.                 return;
    
23.         }
    
24.         get_ans(a[r].l);
    
25.         get_ans(a[r].r);
    
26.         if (a[r].c == '&') {
    
27.                 a[r].value = a[a[r].l].value & a[a[r].r].value;
    
28.                 if (a[r].noted) a[r].value = !a[r].value;
    
29.         } else {
    
30.                 a[r].value = a[a[r].l].value | a[a[r].r].value;
    
31.                 if (a[r].noted) a[r].value = !a[r].value;
    
32.         }
    
33. }
    
34. 
    
35. void get_dp_value(int r) {
    
36.         if (!a[r].ok) return;
    
37.         if (a[r].type == 1) return; // no left, right sons
    
38.         if (a[r].c == '&') {
    
39.                 if (a[a[r].r].value != 0) a[a[r].l].ok = 1;
    
40.                 if (a[a[r].l].value != 0) a[a[r].r].ok = 1;
    
41.         } else {
    
42.                 if (a[a[r].r].value != 1) a[a[r].l].ok = 1;
    
43.                 if (a[a[r].l].value != 1) a[a[r].r].ok = 1;       
    
44.         }
    
45.         get_dp_value(a[r].l);
    
46.         get_dp_value(a[r].r);
    
47. }
    
48. 
    
49. int main() {
    
50.         char c;
    
51.         int id = 0, lasttype = -1; //0 means operator, 1 means number
    
52.         while ((c = getchar()) != '\n') { // LN
    
53.                 if (c == '\r') continue; // CR
    
54.                 if (c == ' ') { // space
    
55.                         if (lasttype == 1) {
    
56.                                 a[++nodtot] = {1,  0, 0,   0, id, -1, -1};
    
57.                                         /*Tip:Type,c,noted,ok,id, l, r*/
    
58.                                 nums[++numtot] = nodtot;
    
59.                                 stak[++top] = nodtot;
    
60.                                 id = 0;
    
61.                         }
    
62.                         lasttype = -1;
    
63.                 } else if (c == '&' || c == '|' || c == '!') { // operator
    
64.                         lasttype = 0;
    
65.                         if (c == '!') {
    
66.                                 a[stak[top]].noted = 1;
    
67.                         } else {
    
68.                                 int r = stak[top--];
    
69.                                 int l = stak[top--];
    
70.                                 a[++nodtot] = {0, c, 0, 0, 0, l, r};
    
71.                                 stak[++top] = nodtot;
    
72.                         }
    
73.                 } else if (c == 'x') { // number first
    
74.                         lasttype = 1;
    
75.                         id = 0;
    
76.                 } else if (c >= '0' && c <= '9') { // number
    
77.                         lasttype = 1;
    
78.                         id = id * 10 + c - '0';
    
79.                 } else assert(0);
    
80.         }
    
81.         root = stak[top]; // root id
    
82.         scanf("%d", &n);
    
83.         for (int i = 1; i <= n; ++i) {
    
84.                 scanf("%d", &na[i]);
    
85.         }
    
86.         get_ans(root); // get value
    
87.         rootvalue = a[root].value; // root value
    
88.         a[root].ok = 1; //first, root change result will change, its right
    
89.         get_dp_value(root);
    
90.         scanf("%d", &q);
    
91.         while (q--) {
    
92.                 scanf("%d", &x);
    
93.                 if (a[nums[x]].ok) printf("%d\n", !rootvalue); // Can change, change result
    
94.                 else printf("%d\n", rootvalue); // Else, it cannot change result
    
95.         }
    
96.         return 0;
    
97. }

复制代码

ExiaGN001

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

最近不在线，勿at

zhangjinxuan

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

myd0313