首页 > 代码库 > [题解]某模拟题题解
[题解]某模拟题题解
第一道题还是比较简单,只不过做的时候手贱写错了一个字母，然后活活RE掉了40分
先处理处最终的图，然后从后往前用并查集完成询问。至于之前的删边可以排个序，
然后建一个长度和它一样的boolean数组标志这条边又没被删，删除的时候就lower_bound
就可以了，只不过注意重复的边。如果这一位上为false（这条边被删掉了）应该往后找到
第一个为true的地方，然后将它改为false
Code:
1 #include<iostream> 2 #include<cstdio> 3 #include<fstream> 4 #include<cstdlib> 5 #include<queue> 6 #include<set> 7 #include<map> 8 #include<cctype> 9 #include<algorithm> 10 #include<cstring> 11 #include<string> 12 #include<stack> 13 using namespace std; 14 typedef bool boolean; 15 #define smin(a, b) a = min(a, b) 16 #define smax(a, b) b = max(a, b) 17 template<typename T> 18 inline void readInteger(T& u) { 19 char x; 20 while(!isdigit(x = getchar())); 21 for(u = x - ‘0‘; isdigit((x = getchar())); u = (u << 3) + (u << 1) + x - ‘0‘); 22 ungetc(x, stdin); 23 } 24 25 typedef class union_found{ 26 public: 27 int *f; 28 union_found():f(NULL) {} 29 union_found(int points) { 30 f = new int[(const int)(points + 1)]; 31 for(int i = 0; i <= points; i++) 32 f[i] = i; 33 } 34 int find(int x) { 35 if(f[x] != x) return f[x] = find(f[x]); 36 return f[x]; 37 } 38 void unit(int fa, int so) { 39 int ffa = find(fa); 40 int fso = find(so); 41 f[fso] = ffa; 42 } 43 boolean connected(int a, int b) { 44 return find(a) == find(b); 45 } 46 }union_found; 47 48 typedef class _edge{ 49 public: 50 int from; 51 int end; 52 _edge(const int a = 0, const int b = 0) { 53 from = min(a, b); 54 end = max(a, b); 55 } 56 boolean operator <(_edge another) const { 57 if(this->from != another.from) return this->from < another.from; 58 return this->end < another.end; 59 } 60 }_edge; 61 62 typedef class _question{ 63 public: 64 boolean isCut; 65 int a; 66 int b; 67 }_question; 68 69 inline void readQues(_question& que){ 70 int c; 71 readInteger(c); 72 if(c == 1) que.isCut = true; 73 else que.isCut = false; 74 readInteger(que.a); 75 readInteger(que.b); 76 } 77 78 int n, m, q; 79 union_found uf; 80 _edge* es; 81 boolean* enable; 82 _question *ques; 83 stack<int> s; 84 85 #define MAP_IT multiset<_edge>::iterator 86 87 inline void init() { 88 int lastEdge; 89 readInteger(n); 90 readInteger(m); 91 readInteger(q); 92 es = new _edge[(const int)(m + 1)]; 93 uf = union_found(n); 94 ques = new _question[(const int)(q + 1)]; 95 enable = new boolean[(const int)(m + 1)]; 96 lastEdge = m; 97 memset(enable, true, sizeof(boolean) * (m + 1)); 98 for(int i = 1, a, b; i <= m; i++){ 99 readInteger(a);100 readInteger(b);101 es[i] = _edge(a, b);102 }103 sort(es + 1, es + m + 1);104 for(int i = 1; i <= q; i++){105 readQues(ques[i]);106 ques[i].a ^= lastEdge;107 ques[i].b ^= lastEdge;108 if(ques[i].isCut){109 // es.erase(es.lower_bound(_edge(ques[i].a, ques[i].b)));110 int rank = lower_bound(es + 1, es + m + 1, _edge(ques[i].a, ques[i].b)) - es;111 while(!enable[rank]) rank++;112 enable[rank] = false;113 lastEdge--;114 }115 }116 for(int i = 1; i <= m; i++){117 if(enable[i])118 uf.unit(es[i].from, es[i].end);119 }120 }121 122 void solve() {123 for(int i = q; i > 0; i--){124 if(ques[i].isCut){125 uf.unit(ques[i].a, ques[i].b);126 }else{127 boolean result = uf.connected(ques[i].a, ques[i].b);128 if(result) s.push(1);129 else s.push(0);130 }131 }132 while(!s.empty()){133 printf("%d\n", s.top());134 s.pop();135 }136 }137 138 int main(){139 freopen("graph.in", "r", stdin);140 freopen("graph.out", "w", stdout);141 init();142 solve();143 fclose(stdin);144 fclose(stdout);145 return 0;146 }
第二道相对于第一道题就没有那么友好了，这次真的只能用在线算法，于是我决定用暴力碰碰运气
结果真的AC了。。。（这数据太水，没办法）
思路很简单，这道题是树，所以，两点之间的连线断开后，就成了两个联通块，然后我给每个连通块
一个编号，然后每次删边就去dfs一遍修改这个值。
Code
1 #include<iostream> 2 #include<cstdio> 3 #include<fstream> 4 #include<cstdlib> 5 #include<queue> 6 #include<set> 7 #include<map> 8 #include<cctype> 9 #include<algorithm> 10 #include<cstring> 11 #include<string> 12 using namespace std; 13 typedef bool boolean; 14 #define smin(a, b) a = min(a, b) 15 #define smax(a, b) b = max(a, b) 16 template<typename T> 17 inline void readInteger(T& u) { 18 char x; 19 while(!isdigit(x = getchar())); 20 for(u = x - ‘0‘; isdigit((x = getchar())); u = (u << 3) + (u << 1) + x - ‘0‘); 21 ungetc(x, stdin); 22 } 23 24 ///Linked Map Template Starts 25 typedef class Edge{ 26 public: 27 int next; 28 int end; 29 Edge(const int next = 0, const int end = 0):next(next), end(end){ } 30 }Edge; 31 typedef class MapManager{ 32 public: 33 int *h; 34 Edge* edge; 35 int ce; 36 MapManager():h(NULL), edge(NULL), ce(0) { } 37 MapManager(int point, int edges):ce(0){ 38 h = new int[(const int)(point + 1)]; 39 edge = new Edge[(const int)(edges + 1)]; 40 memset(h, 0, sizeof(int) * (point + 1)); 41 } 42 inline void addEdge(int from, int end) { 43 edge[++ce] = Edge(h[from], end); 44 h[from] = ce; 45 } 46 }MapManager; 47 ///Linked Map Template Ends 48 49 int n, q; 50 MapManager tree; 51 int* fa; 52 int* value; 53 int* types; 54 int ct; 55 56 inline void init() { 57 ct = 1; 58 readInteger(n); 59 readInteger(q); 60 value = http://www.mamicode.com/new int[(const int)(n + 1)]; 61 fa = new int[(const int)(n + 1)]; 62 tree = MapManager(n, 2 * n); 63 types = new int[(const int)(n + 1)]; 64 fill(types + 1, types + n + 1, 1); 65 for(int i = 1; i <= n; i++) readInteger(value[i]); 66 for(int i = 1, a, b; i < n; i++){ 67 readInteger(a); 68 readInteger(b); 69 tree.addEdge(a, b); 70 tree.addEdge(b, a); 71 } 72 } 73 74 void buildTree(int node, int lastNode){ 75 fa[node] = lastNode; 76 for(int i = tree.h[node]; i != 0; i = tree.edge[i].next){ 77 int& end = tree.edge[i].end; 78 if(end == lastNode) continue; 79 buildTree(end, node); 80 } 81 } 82 83 void update(int node, int lastNode, const int newType){ 84 if(fa[node] != lastNode) return; 85 types[node] = newType; 86 for(int i = tree.h[node]; i != 0; i = tree.edge[i].next){ 87 int& end = tree.edge[i].end; 88 if(end == lastNode) continue; 89 update(end, node, newType); 90 } 91 } 92 93 int lastans; 94 95 inline void solve() { 96 buildTree(1, 0); 97 for(int i = 1, c, a, b; i <= q; i++){ 98 readInteger(c); 99 readInteger(a);100 readInteger(b);101 a ^= lastans;102 b ^= lastans;103 int s;104 switch(c){105 case 1:106 if(fa[a] == b){107 s = a;108 }else{109 s = b;110 }111 fa[s] = 0;112 update(s, 0, ++ct);113 break;114 case 2:115 if(types[a] == types[b]){116 lastans = value[a] * value[b];117 } else {118 lastans = value[a] + value[b];119 }120 printf("%d\n", lastans);121 break;122 case 3:123 value[a] = b;124 break;125 default:126 // throw c;127 break;128 }129 }130 }131 132 int main(){133 freopen("tree.in", "r", stdin);134 freopen("tree.out", "w", stdout);135 init();136 solve();137 return 0;138 }
第三题，也是最简单的一道，直接Tarjan搜强连通分量不解释
Code
1 #include<iostream> 2 #include<cstdio> 3 #include<fstream> 4 #include<cstdlib> 5 #include<queue> 6 #include<set> 7 #include<map> 8 #include<stack> 9 #include<cctype> 10 #include<algorithm> 11 #include<cstring> 12 #include<string> 13 using namespace std; 14 typedef bool boolean; 15 #define smin(a, b) a = min(a, b) 16 #define smax(a, b) b = max(a, b) 17 template<typename T> 18 inline void readInteger(T& u) { 19 char x; 20 while(!isdigit(x = getchar())); 21 for(u = x - ‘0‘; isdigit((x = getchar())); u = (u << 3) + (u << 1) + x - ‘0‘); 22 ungetc(x, stdin); 23 } 24 ///Linked Map Template Starts 25 typedef class Edge{ 26 public: 27 int next; 28 int end; 29 Edge(const int next = 0, const int end = 0):next(next), end(end){ } 30 }Edge; 31 typedef class MapManager{ 32 public: 33 int *h; 34 Edge* edge; 35 int ce; 36 MapManager():h(NULL), edge(NULL), ce(0) { } 37 MapManager(int point, int edges):ce(0){ 38 h = new int[(const int)(point + 1)]; 39 edge = new Edge[(const int)(edges + 1)]; 40 memset(h, 0, sizeof(int) * (point + 1)); 41 } 42 inline void addEdge(int from, int end) { 43 edge[++ce] = Edge(h[from], end); 44 h[from] = ce; 45 } 46 }MapManager; 47 ///Linked Map Template Ends 48 49 MapManager g; 50 long long result; 51 52 stack<int> s; 53 boolean* visited; 54 boolean* inStack; 55 int counter; 56 int *visitID; 57 int *exitID; 58 59 inline void getMap(int end){ 60 int c_m = 0; 61 int node; 62 do{ 63 node = s.top(); 64 s.pop(); 65 inStack[node] = false; 66 c_m++; 67 }while(node != end); 68 result += c_m * 1LL * (c_m - 1) / 2; 69 } 70 71 void Tarjan(int node){ 72 visited[node] = true; 73 visitID[node] = exitID[node] = ++counter; 74 s.push(node); 75 inStack[node] = true; 76 for(int i = g.h[node]; i != 0; i = g.edge[i].next){ 77 int e = g.edge[i].end; 78 if(!visited[e]) { 79 Tarjan(e); 80 smin(exitID[node], exitID[e]); 81 } else if(inStack[e]) { 82 smin(exitID[node], visitID[e]); 83 } 84 } 85 if(visitID[node] == exitID[node]) 86 getMap(node); 87 } 88 89 int n; 90 int m; 91 92 inline void init() { 93 readInteger(n); 94 readInteger(m); 95 g = MapManager(n, m); 96 visited = new boolean[(const int)(n + 1)]; 97 inStack = new boolean[(const int)(n + 1)]; 98 visitID = new int[(const int)(n + 1)]; 99 exitID = new int[(const int)(n + 1)];100 memset(visited, false, sizeof(boolean) * (n + 1));101 memset(inStack, false, sizeof(boolean) * (n + 1));102 for(int i = 1, a, b; i <= m; i++) {103 readInteger(a);104 readInteger(b);105 g.addEdge(a, b);106 }107 }108 109 inline void solve() {110 for(int i = 1; i <= n; i++) {111 if(!visited[i])112 Tarjan(i);113 }114 cout<<result;115 }116 117 int main(){118 freopen("logic.in", "r", stdin);119 freopen("logic.out", "w", stdout);120 init();121 solve();122 return 0;123 }
[题解]某模拟题题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。