CCF-CSP202303-3 LDAPC++

CCF-CSP【202303-3 LDAP】C++

CCF real test website

The first submission timed out and only 20 minutes

topic ideas

My idea is relatively simple, that is, for each matching expression, traverse N users and verify whether it matches.
For each expression there are two cases:

1. atomic expression
2. complex expression

For atomic expressions, we use the written function atomic_expression() to solve. Since the number of digits of the attribute and attribute value is not sure, directly find() asserts the operator : or ~, and then puts the left side of the assertion operator extracts as attributes, and extracts the right-hand side of the assertion operator as an attribute value.
For complex expressions, we need to consider & amp;(1:2)(2:3) and & amp;(|(1:2)(3~4))(555 :666) and more complex nested expressions. We naturally choose to recurse.
So how to recurse, since the syntax of the expression is: (expression 1)(expression 2), our task is to find the ( and ), then ( and ) of expression 2 is naturally obtained.
If expression 1 contains nested expressions, how to find the ) of expression 1?
My idea is to find the first ) so that the ( in the preceding string (including it) equal to the number of ).
The recursive terminating condition is that the string is an atomic expression, and the first character of the string is not a given operator.
Knowing how to recurse and the termination conditions of recursion, you can naturally complete the code writing!
The main function mainly deals with input and output.

Basic knowledge supplement

Usage of s.find() and s.rfind() in C++
Forward lookup find()

1. s.find(str)
   The return value of find() in string is the subscript position of the first occurrence of the letter in the parent string. If not found, -1 is returned.
2. s.find(str, pos)
find(str, pos) is used to find the position starting from pos **(including characters at pos)** matching str.

C++ code

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <map>
#include <string>
#include <stack>

using namespace std;


bool atomic_expression(int dn, string s, map<int, map<int, int>> m_dn_at){<!-- -->
//1:2
//3~1
if(s.find(':') != -1){<!-- -->
int index = s.find(':');
string s_a = s. substr(0, index);
string s_b = s.substr(index + 1);
int i_a = stoi(s_a);
int i_b = stoi(s_b);
return m_dn_at[dn].count(i_a) > 0 and m_dn_at[dn][i_a] == i_b;
}
else if(s.find('~') != -1){<!-- -->
int index = s.find('~');
string s_a = s. substr(0, index);
string s_b = s.substr(index + 1);
int i_a = stoi(s_a);
int i_b = stoi(s_b);
return m_dn_at[dn].count(i_a) > 0 and m_dn_at[dn][i_a] != i_b;
}
}


bool resolve(int dn, string s, map<int, map<int, int>> m_dn_at){<!-- -->
// &(|(1:2)(3~4))(555:666)
if(s[0] == ' & amp;' or s[0] == '|'){<!-- -->
int l_l = s.find('(');
int l_r = s.find(')');
while(count(s.begin() + l_l, s.begin() + l_r + 1, '(') != count(s.begin() + l_l, s.begin() + l_r + 1, ')')){<!-- -->
l_r = s.find(')', l_r + 1);
}
string s_l = s.substr(l_l + 1, l_r-l_l - 1);
\t\t
int r_l = l_r + 1;
int r_r = s.rfind(')');
string s_r = s.substr(r_l + 1, r_r-r_l-1);
if(s[0]==' &')
return resolve(dn, s_l, m_dn_at) and resolve(dn, s_r, m_dn_at);
else
return resolve(dn, s_l, m_dn_at) or resolve(dn, s_r, m_dn_at);
}
else
return atomic_expression(dn, s, m_dn_at);
}


int main(){<!-- -->
// input processing
    int n,m;
    cin >> n;
map<int, map<int, int>> m_dn_at;
vector<int>v_dn;
    for(int i = 0; i < n; i ++ ){<!-- -->
    int dn;
cin >> dn;
v_dn.push_back(dn);
    int num;
cin >> num;
map<int, int> m_at;
for(int j = 0; j < num; j ++ ){<!-- -->
int a, b;
cin >> a >> b;
m_at[a] = b;
}
m_dn_at[dn] = m_at;
}
\t
    cin >> m;
vector<string> v_s;
    for(int i = 0; i < m; i ++ ){<!-- -->
string s;
    cin >> s;
    v_s.push_back(s);
}
\t
for(int i = 0; i < m; i ++ ){<!-- -->
string s = v_s[i];
\t\t
vector<int>r_dn;
for(int j = 0; j < n; j ++ ){<!-- -->
if(resolve(v_dn[j], s, m_dn_at))
r_dn.push_back(v_dn[j]);
}
sort(r_dn.begin(), r_dn.end());
for(int k=0; k<r_dn. size(); k ++ )
cout << r_dn[k] << " ";
cout << endl;
}
}

The second submission result timed out by 40 minutes

topic ideas

My improvement is mainly based on this article, and my modification of the above code is limited to the return type of atomic_expression and resolve.
For each atomic expression, obtain the LD set that meets the expression, and then perform the intersection and union operation.
For some explanation of the code, in the atomic_expression function index = min(s.find(':'), s.find('~')); Under normal circumstances, s.find(':') and s.find('~') must have a -1 , another >0, we want to get the index of >0, we should choose max instead of min, but -1 corresponds to 18446744073709551615 in this function, so you need to choose min.

Basic knowledge supplement

map operation
Both map and set are traversed through iterators. The difference is that the way map reads elements is it->first and it->second, while set reads elements The method is *iter.
The traversal of the map and set data structures is as follows:

 map<int, map<int, int>>::iterator it = m_dn_at.begin() ;
for(; it != m_dn_at.end(); it ++ ){<!-- -->
if(m_dn_at[it->first].count(i_a) > 0 and m_dn_at[it->first][i_a] == i_b)
s_a.insert(it->first);
if(m_dn_at[it->first].count(i_a) > 0 and m_dn_at[it->first][i_a] != i_b)
s_b.insert(it->first);
}
\t
set<int>::iterator iter;
for(iter = s_r.begin(); iter != s_r.end(); iter ++ ){<!-- -->
cout << *iter << " ";
}

Find intersection and union of sets
Set intersection and union:

 set_intersection(s_a.begin(), s_a.end(), s_b.begin(), s_b.end(), inserter(s_is, s_is.begin()));
set_union(s_a.begin(), s_a.end(), s_b.begin(), s_b.end(), inserter(s_u, s_u.begin()));

C++ code

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <map>
#include <set>
#include <string>
#include <stack>

using namespace std;


set<int> atomic_expression(string s, map<int, map<int, int>> m_dn_at){<!-- -->
//1:2
//3~1
int index = min(s.find(':'), s.find('~'));
string a = s. substr(0, index);
string b = s.substr(index + 1);
int i_a = stoi(a);
int i_b = stoi(b);
\t
set<int> s_a, s_b, s_c;
\t
// https://blog.csdn.net/segegefe/article/details/124164513
    map<int, map<int, int>>::iterator it = m_dn_at. begin() ;

for(; it != m_dn_at.end(); it ++ ){<!-- -->
if(m_dn_at[it->first].count(i_a) > 0 and m_dn_at[it->first][i_a] == i_b)
s_a.insert(it->first);
if(m_dn_at[it->first].count(i_a) > 0 and m_dn_at[it->first][i_a] != i_b)
s_b.insert(it->first);
}
\t
if(s[index] == ':')
return s_a;
else
return s_b;
}


set<int> resolve(string s, map<int, map<int, int>> m_dn_at){<!-- -->
// &(|(1:2)(3~4))(555:666)
if(s[0] == ' & amp;' or s[0] == '|'){<!-- -->
int l_l = s.find('(');
int l_r = s.find(')');
while(count(s.begin() + l_l, s.begin() + l_r + 1, '(') != count(s.begin() + l_l, s.begin() + l_r + 1, ')')){<!-- -->
l_r = s.find(')', l_r + 1);
}
string s_l = s.substr(l_l + 1, l_r-l_l - 1);
\t\t
int r_l = l_r + 1;
int r_r = s.rfind(')');
string s_r = s.substr(r_l + 1, r_r-r_l-1);
\t\t
set<int> s_a, s_b, s_is, s_u;
s_a = resolve(s_l, m_dn_at);
s_b = resolve(s_r, m_dn_at);
set_intersection(s_a.begin(), s_a.end(), s_b.begin(), s_b.end(), inserter(s_is, s_is.begin()));
set_union(s_a.begin(), s_a.end(), s_b.begin(), s_b.end(), inserter(s_u, s_u.begin()));
if(s[0]==' &')
return s_is;
else
return s_u;
}
else
return atomic_expression(s, m_dn_at);
}


int main(){<!-- -->
    int n,m;
    cin >> n;
map<int, map<int, int>> m_dn_at;
vector<int>v_dn;
    for(int i = 0; i < n; i ++ ){<!-- -->
    int dn;
cin >> dn;
v_dn.push_back(dn);
    int num;
cin >> num;
map<int, int> m_at;
for(int j = 0; j < num; j ++ ){<!-- -->
int a, b;
cin >> a >> b;
m_at[a] = b;
}
m_dn_at[dn] = m_at;
}
\t
    cin >> m;
vector<string> v_s;
    for(int i = 0; i < m; i ++ ){<!-- -->
string s;
    cin >> s;
    v_s.push_back(s);
}
for(int i = 0; i < m; i ++ ){<!-- -->
string s = v_s[i];
set<int> s_r;
s_r = resolve(s, m_dn_at);
set<int>::iterator iter;
for(iter = s_r.begin(); iter != s_r.end(); iter ++ ){<!-- -->
cout << *iter << " ";
}
cout << endl;
}
}

Summary

This question got 40 points because of running overtime, just to provide some ideas for students who have no idea, if you have any suggestions for improvement, welcome to comment!
I think it’s good, remember to help me like it!