广州市建设企业网站哪家好,wordpress固定连接重,中国最近重大新闻,石家庄热搜题目链接如下#xff1a;
Online Judge
这道题我一开始的思路大方向其实是对的#xff0c;但细节怎么实现set到int的哈希没能想清楚#xff08;没想到这都能用map#xff09;。用setstring的做法来做#xff0c;测试数据小的话答案是对的#xff0c;但大数据时…题目链接如下
Online Judge
这道题我一开始的思路大方向其实是对的但细节怎么实现set到int的哈希没能想清楚没想到这都能用map。用setstring的做法来做测试数据小的话答案是对的但大数据时间超时。
其实就是把所有set一一映射到int, 所以stack里每个元素就是int.
按照刘汝佳思路写的代码如下按理每个case里stack应该先清空但因为题目保证了没有无效操作只需要最上面set的元素个数不清空也没问题
#include cstdio
#include set
#include stack
#include map
#include vector
// #define debugint T, N, a, b;
std::mapstd::setint, int mp;
char op[10];
std::stackint s;
std::setint empty;
std::vectorstd::setint vec;void _push(std::setint st){if(!mp.count(st)){vec.push_back(st);mp[st] vec.size() - 1;}s.push(mp[st]);
}int main(){#ifdef debugfreopen(0.txt, r, stdin);freopen(1.txt, w, stdout);#endifscanf(%d, T);while(T--){scanf(%d, N);vec.clear();mp.clear();while(N--){scanf(%s, op);if(op[0] P){_push(empty);} else{a s.top();s.pop();if(op[0] D){s.push(a);s.push(a);} else{b s.top();s.pop();std::setint tmp;if(op[0] A){tmp vec[b];tmp.insert(a);} else{if(op[0] U){tmp vec[a];for(auto it vec[b].begin(); it ! vec[b].end(); it){tmp.insert(*it);}} else if(op[0] I){for(auto it vec[a].begin(); it ! vec[a].end(); it){if(vec[b].find(*it) ! vec[b].end()){tmp.insert(*it);}}}}_push(tmp);}}printf(%d\n, vec[s.top()].size());}printf(***\n);}#ifdef debugfclose(stdin);fclose(stdout);#endifreturn 0;
}
原先的代码如下超时
#include cstdio
#include set
#include stack
#include string
// #define debugint T, N;
char op[10];
std::stackstd::setstd::string s, empStack;
std::setstd::string a, b, empty;std::string toString(std::setstd::string st){std::string str {;for(auto it st.begin(); it ! st.end(); it){str (it st.begin() ? : ,);str *it;}return str };
}int main(){#ifdef debugfreopen(0.txt, r, stdin);freopen(1.txt, w, stdout);#endifscanf(%d, T);while(T--){scanf(%d, N);s.swap(empStack);while(N--){scanf(%s, op);if(op[0] P){s.push(empty);} else{a s.top();s.pop();if(op[0] D){s.push(a);s.push(a);} else{b s.top();s.pop();if(op[0] A){b.insert(toString(a));s.push(b);} else{if(op[0] U){for(auto it a.begin(); it ! a.end(); it){b.insert(*it);}s.push(b);} else if(op[0] I){std::setstd::string intersect;for(auto it a.begin(); it ! a.end(); it){if(b.find(*it) ! b.end()){intersect.insert(*it);}}s.push(intersect);}}}}printf(%d\n, s.top().size());}printf(***\n);}#ifdef debugfclose(stdin);fclose(stdout);#endifreturn 0;
}
