洛谷P1449(栈和逆序表达式)
水题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include <cstdio> #include <cstring> #include <stack> using namespace std;int main () { char str[10001 ]; scanf ("%s" , str); int len = strlen (str); int num = 0 ; stack<int > s; for (int i = 0 ; i < len; ++i) { if (str[i] >= '0' && str[i] <= '9' ) { num *= 10 ; num += str[i] - '0' ; } else if (str[i] == '.' ) { s.push (num); num = 0 ; } else if (str[i] == '@' ) { printf ("%d\n" , s.top ()); s.pop (); } else { int a = s.top (); s.pop (); int b = s.top (); s.pop (); if (str[i] == '-' ) s.push (b - a); else if (str[i] == '+' ) s.push (b + a); else if (str[i] == '*' ) s.push (b * a); else if (str[i] == '/' ) s.push (b / a); } } return 0 ; }
洛谷P1739(栈)
水题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include <cstdio> #include <cstring> #include <stack> using namespace std;int main () { int flag = 1 ; stack<char > s; char str[300 ]; scanf ("%s" , str); int len = strlen (str); for (int i = 0 ; i < len; ++i) { if (str[i] == '(' ) s.push (str[i]); if (str[i] == ')' ) { if (s.empty ()) flag = 0 ; else s.pop (); } } if (!s.empty ()) flag = 0 ; if (flag) printf ("YES\n" ); else printf ("NO\n" ); return 0 ; }
洛谷P1115(?)
分在洛谷的线性数据结构里,但我好像不是这么做的
ai 表示第i个数,a[i]表示前i项和
ai ……aj 和最大的话,那么这段长度为a[j]-a[i]
即a[i]最小的时候,以aj 结尾的最长序列和可以一步算出
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include <cstdio> const int MAX_N = 2e5 + 1 ;const int INF = 1e9 ;int a[MAX_N];int main () { int n; scanf ("%d" , &n); for (int i = 0 ; i < n; ++i) { scanf ("%d" , &a[i]); a[i] = a[i] + a[i-1 ]; } int min = 0 ; int ans = a[0 ]; for (int i = 1 ; i < n; ++i) { min = min > a[i-1 ] ? a[i-1 ] : min; ans = ans < a[i] - min ? a[i] - min : ans; } printf ("%d\n" , ans); return 0 ; }
洛谷P1160(双向链表)
简单题,初学可练手
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 #include <cstdio> #include <cstdlib> typedef struct Node { int data; Node *left; Node *right; } Node; Node *book[100001 ]; Node *head = (Node *)malloc (sizeof (Node)); Node *q = (Node *)malloc (sizeof (Node)); Node *find (int num) { if (book[num]) return book[num]; return NULL ; } void insert (int num1, int d, int num2) { Node *p = find (num1); Node *t = (Node *)malloc (sizeof (Node)); t->data = num2; if (!d && p->left == head) { t->left = head; t->right = p; head->right = t; p->left = t; } else if (!d) { t->left = p->left; t->right = p; p->left->right = t; p->left = t; } else if (d && p->right == NULL ) { t->right = NULL ; t->left = p; p->right = t; } else if (d) { t->right = p->right; t->left = p; p->right->left = t; p->right = t; } book[num2] = t; } void del (int num) { Node *p = find (num); if (!p) return ; if (p->left ==NULL && p->right == NULL ) { ; } else if (p->left == NULL ) { p->right->left = NULL ; } else if (p->right == NULL ) { p->left->right = NULL ; } else { p->left->right = p->right; p->right->left = p->left; } free (p); book[num] = NULL ; } int main () { for (int i = 0 ; i < 100001 ; ++i) book[i] = NULL ; head->left = NULL ; head->right = q; q->data = 1 ; q->left = head; q->right = NULL ; book[1 ] = q; int n; scanf ("%d" , &n); for (int i = 2 ; i < n + 1 ; ++i) { int num1, num2, d; num2 = i; scanf ("%d%d" , &num1, &d); insert (num1, d, num2); } int m; scanf ("%d" , &m); for (int i = 0 ; i < m; ++i) { int num; scanf ("%d" , &num); del (num); } Node *p = head->right; while (p) { printf ("%d " , p->data); p = p->right; } printf ("\n" ); return 0 ; }
洛谷P1996(单向链表)
初学练手的简单题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 #include <cstdio> #include <cstdlib> using namespace std;typedef struct Node { int data; struct Node * next; } Node; int n, m;int size = 1 ;Node *init () { Node *q, *head; head = (Node *)malloc (sizeof (Node)); head->data = 1 ; q = head; for (int i = 2 ; i <= n; ++i) { Node *p = (Node *)malloc (sizeof (Node)); p->data = i; q->next = p; if (i == n) p->next = head; else q = p; size++; } return head; } void solve (Node *head) { Node *q; Node *p = (Node *)malloc (sizeof (Node)); p = head; while (size > 0 ) { for (int i = 1 ; i < m - 1 ; ++i) { q = p->next; p = q; } Node *t = q->next; q->next = q->next->next; printf ("%d " , t->data); free (t); size--; if (size) p = q->next; } } int main () { scanf ("%d%d" , &n, &m); if (!n) return 0 ; else { Node *head = init (); solve (head); } return 0 ; }
洛谷P2661(图论+并查集,最小环问题)
简单题,但是要思考一下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 #include <cstdio> #include <algorithm> using namespace std;const int MAX_N = 2e5 + 2 ;int par[MAX_N];int d[MAX_N];int n;int ans = 2e9 ;void init () { for (int i = 0 ; i <= n; ++i) { par[i] = i; d[i] = 0 ; } } int find (int x) { if (x == par[x]) return x; else { int last= par[x]; par[x] = find (par[x]); d[x] += d[last]; } return par[x]; } bool same (int x, int y) { return find (x) == find (y); } void unite (int x, int y) { x = find (x); y = find (y); if (x == y) return ; else par[x] = y; } void solve (int a, int b) { int x = find (a); int y = find (b); if (x == y) ans = min (ans, d[a] + d[b] + 1 ); else { unite (x, y); d[a] = d[b] + 1 ; } } int main () { scanf ("%d" , &n); init (); for (int i = 1 ; i <= n; ++i) { int t; scanf ("%d" , &t); solve (i, t); } printf ("%d\n" , ans); return 0 ; }
洛谷P1111(并查集求连通块数量)
简单题, 想到套模板即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 #include <cstdio> #include <algorithm> using namespace std;const int MAX_N = 1e5 + 1 ;struct Node { int a; int b; int n; }; bool cmp (Node a, Node b) { return a.n < b.n; }; int par[MAX_N];int rank1[MAX_N];void init (int n) { for (int i = 0 ; i < n; ++i) { par[i] = i; rank1[i] = 0 ; } } int find (int x) { if (par[x] == x) return x; else return par[x] = find (par[x]); } void unite (int x, int y) { x = find (x); y = find (y); if (x == y) return ; if (rank1[x] < rank1[y]) par[x] = y; else { par[y] = x; if (rank1[x] == rank1[y]) rank1[x]++; } } bool same (int x, int y) { return (find (x) == find (y)); } int main () { int n, m; scanf ("%d%d" , &n, &m); Node a[MAX_N]; for (int i = 0 ; i < m; ++i) { scanf ("%d%d%d" , &a[i].a, &a[i].b, &a[i].n); } sort (a, a+m, cmp); int t = n; init (n); for (int i = 0 ; i < m; ++i) { if (!same (a[i].a, a[i].b)) { unite (a[i].a, a[i].b); t--; } if (t == 1 ) { printf ("%d\n" , a[i].n); return 0 ; } } printf ("-1\n" ); return 0 ; }
洛谷P1197(并查集+逆向思考+邻接表+栈)
中等题,搞了我好久
并查集只加边不减边,所以从所有星球被毁开始计算联通数
由于数据太大,邻接矩阵开不下,只能邻接表(这是我第一次用邻接表)
为了输出简单,我用了栈存储答案
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 #include <cstdio> #include <cstdlib> #include <stack> #include <cstring> using namespace std;const int MAX_N = 4e5 + 1 ;int par[MAX_N]; int rankk[MAX_N]; void init (int n) { for (int i = 0 ; i < n; ++i) { par[i] = i; rankk[i] = 0 ; } } int find (int x) { if (par[x] == x) return x; else return par[x] = find (par[x]); } void unite (int x, int y) { x = find (x); y = find (y); if (x == y) return ; if (rankk[x] < rankk[y]) par[x] = y; else { par[y] = x; if (rankk[x] == rankk[y]) rankk[x]++; } } bool same (int x, int y) { return find (x) == find (y); } struct Node { int data; Node *next; }; Node v[MAX_N]; void initl (int n) { for (int i = 0 ; i < n; ++i) { v[i].data = i; v[i].next = NULL ; } } void InsertNode (int a, int b) { Node *NewNode = (Node *)malloc (sizeof (Node)); NewNode->data = b; NewNode->next = v[a].next; v[a].next = NewNode; return ; } int n, m, ans;int book[MAX_N];stack<int > s; int main () { scanf ("%d%d" , &n, &m); initl (n); for (int i = 0 ; i < m; ++i) { int a, b; scanf ("%d%d" , &a, &b); InsertNode (a, b); InsertNode (b, a); } int k; scanf ("%d" , &k); int deletek[k+1 ]; memset (deletek, 0 , sizeof (deletek)); for (int i = 0 ; i < k; ++i) { scanf ("%d" , &deletek[i]); book[deletek[i]] = 1 ; } init (n); int ans = n - k; for (int i = 0 ; i < n; ++i) { Node *p = v[i].next; if (!book[i]) { while (p) { if (!book[p->data] && !same (i, p->data)) { unite (i, p->data); ans--; } p = p->next; } } } s.push (ans); for (int i = k - 1 ; i >= 0 ; --i) { int a = deletek[i]; Node *p = &v[a]; book[a] = 0 ; ans++; while (p) { if (!book[p->data]) { if (!same (a, p->data)) { ans--; unite (a, p->data); } } p = p->next; } s.push (ans); } while (!s.empty ()) { printf ("%d\n" , s.top ()); s.pop (); } return 0 ; }
洛谷P2024(并查集+思维)
想到其实还好做
不知道每种动物属于哪种,于是开三倍长度的并查集,存储a,a 的天敌,a的天敌的天敌
每次输入a及其天敌及其天敌的天敌都要更新
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 #include <cstdio> const int MAX_N = 1e4 * 5 ;int par[MAX_N * 4 ]; int rank[MAX_N * 4 ]; void init (int N) { for (int i = 0 ; i < N; ++i) { par[i] = i; rank[i] = 0 ; } } int find (int x) { if (par[x] == x) return x; else return par[x] = find (par[x]); } void unite (int x, int y) { x = find (x); y = find (y); if (x == y) return ; if (rank[x] < rank[y]) par[x] = y; else { par[y] = x; if (rank[x] == rank[y]) rank[x]++; } } bool same (int x, int y) { return find (x) == find (y); } int ans = 0 ;int N, k;void solve (int T, int X, int Y) { if (X > N || Y > N) { ans++; return ; } if (T == 1 ) { if (same (X, Y+N) || same (X, Y+2 *N)) { ans++; return ; } else { unite (X, Y); unite (X+N, Y+N); unite (X+2 *N, Y+2 *N); } } else { if (same (X, Y) || same (X, Y+2 *N)) { ans++; return ; } else { unite (X, Y+N); unite (X+N, Y+N*2 ); unite (X+N*2 , Y); } } } int main () { scanf ("%d%d" , &N, &k); int T, X, Y; init (3 * N + 3 ); for (int i = 0 ; i < k; ++i) { scanf ("%d%d%d" , &T, &X, &Y); solve (T, X, Y); } printf ("%d\n" , ans); return 0 ; }
洛谷P1197(带权并查集)
tle了2个点,只有61分,待更
结语 没什么好说的,做得要死要活的,才这么几道简单题,菜是原罪,继续加油吧~