First move the topic from the valley of Los Angeles
Title Description
Little C is keen on learning mathematical logic. One day, he found a special logical expression. In this logical expression, all operands are variables, and their values can only be ， 0 ， or ， 1. The operation is carried out from left to right. If there are parentheses in the expression, the value of the subexpression in parentheses is evaluated first. In particular, this expression has and only has the following operations:
- And operation: A & b. If and only if the values of # a # and # b # are # 1 # the value of this expression is # 1. In other cases, the value of the expression is 0.
- Or operation: a | b. If and only if the values of # a # and # b # are # 0 # the value of the expression is # 0. In other cases, the value of the expression is 1.
- Inverse operation:! a. If and only if the value of # a # is # 0 # the value of the expression is # 1. In other cases, the value of the expression is 0.
Little C wants to know what the value of the original expression is when a logical expression and the initial value of each operand are given, and then the value of an operand is reversed.
In order to simplify the processing of expressions, we have the following conventions:
The expression will be entered as a suffix expression.
The definition of suffix expression is as follows:
- If ， E ， is an operand, the suffix expression of ， E ， is itself.
- If {e} is an expression in the form of E1} op} E2}, where op} is any binary operator and the priority is not higher than the operators outside the brackets of E1 and E2 ， the suffix of {e} is E1 E2 op, where E1 ， E2 ， is the suffix of E1 and E2 ， respectively.
- If ， e ， is an expression in the form of E1 ， the suffix of E1 ， is the suffix of ， e ，.
Meanwhile, for convenience, input:
- And operator (&), or operator (|), negate operator (!) There is a space on the left and right of the expression, but there is no space at the end of the expression.
- Operands are formed by splicing the lowercase letter ， x ， with a positive integer, which represents the subscript of the variable. For example: x10 indicates the variable x10 with subscript 10. The data guarantees that each variable appears exactly once in the expression.
Input format
The first line contains a string, {s, representing the expression described above.
The second line contains a positive integer n, which represents the number of variables in the expression. The subscript of the variable in the expression is 1,2,..., n.
The third line contains n # integers, and the # i # integer represents the initial value of the variable xi #.
The fourth line contains a positive integer q, which indicates the number of queries.
Next, line # q # with a positive integer for each line, indicating the subscript of the variable to be inverted. Note that the modification of each inquiry is temporary, that is, the modification in the previous inquiry will not affect the subsequent inquiry.
The data ensures that the input expression is legal. The initial value of the variable is 0 or 1.
Output format
The output has a total of # q # lines, with # 0 # or # 1 in each line, indicating the value of the expression under the query.
Sample input and output
Enter #1 copy
x1 x2 & x3 | 3 1 0 1 3 1 2 3
Output #1 copy
1
1
0
This question is true and a little difficult. I passed it directly in the examination room. Looking back, I found that it is still skilled
Problem solution
For data storage, I use the following forms:
First define a structure:
struct node{
char op;
int value;
int dp[2];
vector<node*>son;
node(){
dp[0]=0;
dp[1]=0;
value=0;
op='F'; //F indicates no, leaf nodes can be marked
vector<node*>son(); //Initialization without
}
};dp array will be explained later. Value stores the value of the node subtree. A vector array represents its child nodes. It is easy to find that the number of child nodes depends on the symbol of the node, which is! When there is only one; When it is & or |, it is two. Leaf nodes are stored values without symbols, rather than leaf nodes with no values but symbols in the initial state.
You can use the stack container to handle suffix expressions
Create a date array to record the node type with subscript x, which is associated with stack
We define various data in the form of pointers, because in this way, we can dynamically allocate memory and reduce the consumption. But more importantly, this allows us to establish various data structures and establish connections. When a value changes, other types of its corresponding pointer also change.
There are two methods to deal with the core algorithm of this problem
First kind
Is to enter the value to be changed each time, and then traverse the whole tree to give the answer. But obviously, in the case of a large number of queries, this method will definitely timeout.
Second
Before entering the value to be changed, we print the table:
How to make a table? First, we need Dfs to traverse the whole tree from bottom to top to find the default value of each node.
Let's define a function DFS later_ dp traverses the whole tree from top to bottom to find the dp value of each node.
The meaning of dp [] array is that when the value of this node is x and the operation result of the whole tree is dp[x],dp obviously has only two states, so we define int dp[2] as enough.
From top to bottom, for the root node, it is obvious that its dp value is the value of the whole tree.
For each child node, we consider two cases:
1. The symbol corresponding to the parent node is! When, its dp value is the opposite dp value of its parent node.
2. When the symbol corresponding to the parent node is & or |, first find the result z of corresponding symbol operation with another child node of its parent node when its value is x, and then the value of dp[z] corresponding to its parent node
The reason for this is that we can get the values of all cases after traversing the tree. Compared with scheme 1, we don't have to traverse many times.
Finally, when inputting each node to be changed, we can output the dp value of the changed result.
AC code is here
#include<cstdio>
#include<stack>
#include<vector>
#include<cstring>
using namespace std;
struct node{
char op;
int value;
int dp[2];
vector<node*>son;
node(){
dp[0]=0;
dp[1]=0;
value=0;
op='F';
vector<node*>son();
}
};
stack<node*>fuel;
node* date[100000];
char str[100000];
int tot=0,quenum,que;
using namespace std;
int Dfs_solve(node* x){
if(x->op=='F'){
return 0;
}
for(int i=0;i<x->son.size();i++){
Dfs_solve(x->son[i]);
}
if(x->op=='!'){
x->value=(!x->son[0]->value);
}
else if(x->op=='&'){
x->value=(x->son[0]->value & x->son[1]->value);
}
else if(x->op=='|'){
x->value=(x->son[0]->value | x->son[1]->value);
}
return 0;
}
void Dfs_dp(node* x,node* father){
if(father==NULL){
x->dp[0]=0;
x->dp[1]=1;
}
else{
if(father->op=='!'){
x->dp[0]=father->dp[1];
x->dp[1]=father->dp[0];
}
else if(father->op=='&' || father->op=='|'){
node *other;
if(father->son[0]==x){
other=father->son[1];
}
else{
other=father->son[0];
}
if(father->op=='&'){
x->dp[0]=father->dp[0];
x->dp[1]=father->dp[other->value];
}
else{
x->dp[1]=father->dp[1];
x->dp[0]=father->dp[other->value];
}
}
}
for(int i=0;i<x->son.size();i++){
Dfs_dp(x->son[i],x);
}
return;
}
int main(){
while(scanf("%s",str)){
if(str[0]=='x'){
int num=0;
for(int i=1;i<strlen(str);i++){
num=(num<<3)+(num<<1)+(str[i]^48);
}
date[num]=new node;
fuel.push(date[num]);
}
else if(str[0]=='&' || str[0]=='|'){
node* a;
node* b;
node* c=new node;
a=fuel.top();
fuel.pop();
b=fuel.top();
fuel.pop();
c->op=str[0];
c->son.push_back(a);
c->son.push_back(b);
fuel.push(c);
}
else if(str[0]=='!'){
node* a;
node* b=new node;
a=fuel.top();
fuel.pop();
b->son.push_back(a);
b->op='!';
fuel.push(b);
}
else{
for(int i=0;i<strlen(str);i++){
tot=(tot<<3)+(tot<<1)+(str[i]^48);
}
for(int i=1;i<=tot;i++){
scanf("%d",&date[i]->value);
}
break;
}
}
node* root=fuel.top();
Dfs_solve(root);
Dfs_dp(root,NULL);
scanf("%d",&quenum);
for(int i=0;i<quenum;i++){
scanf("%d",&que);
printf("%d\n",date[que]->dp[!date[que]->value]);
}
return 0;
}