【数据结构1-1】线性表
P3156 【深基15.例1】询问学号
#include <stdio.h> int main() { int n, m, a[2000000]; scanf("%d %d", &n, &m); for (int i = 0; i < n; ++i) scanf("%d", &a[i]); for (int i = 0; i < m; ++i) { int j; scanf("%d", &j); printf("%d\n", a[j - 1]); } return 0; }P3613 【深基15.例2】寄包柜
// #include <stdio.h> // 这道题显然不能模拟，因为会浪费很多空间 // 考虑稀疏矩阵的三元表（虽然依然会有一个TLE） // int main() { // int n, q, a[100000][3] = {0}, index = 0; // 跟踪操作 // scanf("%d %d", &n, &q); // for (int i1 = 0; i1 < q; ++i1) { // int p, i, j, k; // scanf("%d", &p); // if (p == 1) { // scanf("%d %d %d", &i, &j, &k); // a[index][0] = i; a[index][1] = j; a[index][2] = k; // index++; // continue; // } // scanf("%d %d", &i, &j); // // 查找，一定是之前操作过的 // // 考虑重复存，所以从后往前找 // for (int j1 = index - 1; j1 >= 0; --j1) { // if (a[j1][0] == i && a[j1][1] == j) { printf("%d\n", a[j1][2]); break; } // } // } // return 0; // } #include <stdio.h> #include <string.h> #define N 2000003 // 用静态数组 + 开放寻址 int key1[N], key2[N], val[N]; // key1=柜子, key2=格子 int cnt = 0; // 找位置，返回数组下标 int find(int i, int j) { int h = (i * 100003L + j) % N; // 乘大质数，把i j拉开，减少碰撞 while (key1[h]) { if (key1[h] == i && key2[h] == j) return h; h = (h + 1) % N; // 线性探测 } return h; } int main() { int n, q; scanf("%d %d", &n, &q); while (q--) { int p, i, j, k; scanf("%d", &p); if (p == 1) { scanf("%d %d %d", &i, &j, &k); int pos = find(i, j); key1[pos] = i; key2[pos] = j; val[pos] = k; continue; } scanf("%d %d", &i, &j); int pos = find(i, j); printf("%d\n", val[pos]); } return 0; }P1449 后缀表达式
#include <stdio.h> // 后缀表达式，栈的经典应用 int main() { int nums[50] = {0}, top = 0, num = 0; char temp; while ((temp = getchar()) != '@') { if (temp >= '0' && temp <= '9') { num = num * 10 + temp - '0'; continue; } else if (temp == '.') { nums[top++] = num; num = 0; continue; } // 遇到操作符时，取出两根操作数，压入计算后的结果 int num1 = nums[--top], num2 = nums[--top]; switch(temp) { case '+': num = num2 + num1; break; case '-': num = num2 - num1; break; case '*': num = num2 * num1; break; case '/': num = num2 / num1; break; } nums[top++] = num; num = 0; } printf("%d", nums[0]); return 0; }P1996 约瑟夫问题
#include <stdio.h> int main() { int p[101] = {0}, n, m, out = 0; scanf("%d %d", &n, &m); int i = 0, cnt = 1; while (out != n) { if (i == n) i = 0; // 循环 if (p[i] == 1) { // 已出圈 ++i; continue; } if (cnt == m) { printf("%d ", i + 1); out++; cnt = 0; p[i] = 1; } ++i; ++cnt; } return 0; }P1160 队列安排
用数组存关系，而非模拟，因为操作都只改关系，而并不关心节点本身。
#include <stdio.h> int pre[100005], nxt[100005]; // i号左/右是谁 int removed[100005] = {0}; void insert(int i, int k, int p) { if (p == 0) { // i 插入到 k 左边 pre[i] = pre[k]; pre[k] = i; nxt[i] = k; nxt[pre[i]] = i; } else { nxt[i] = nxt[k]; nxt[k] = i; pre[i] = k; pre[nxt[i]] = i; } } int main() { int n; scanf("%d", &n); // 初始只有 1 号 pre[1] = 0; nxt[1] = 0; for (int i = 2; i <= n; i++) { int k, p; scanf("%d %d", &k, &p); insert(i, k, p); } int m; scanf("%d", &m); while (m--) { int x; scanf("%d", &x); removed[x] = 1; } // 找队头 int cur = 1; while (pre[cur] != 0) cur = pre[cur]; // 从左到右输出 while (cur != 0) { if (!removed[cur]) printf("%d ", cur); cur = nxt[cur]; } return 0; }P1540 [NOIP 2010 提高组] 机器翻译
#include <stdio.h> // 先进先出，循环队列 int a[101] = {0}, size = 0; int m, res = 0; int find(int word) { for (int i = 0; i < size; ++i) { int index = i % m; if (a[index] == word) return index; } return -1; } int main() { int n; scanf("%d %d", &m, &n); for (int i = 0; i < n; ++i) { int word; scanf("%d", &word); if (find(word) == -1) { res++; a[size % m] = word; size++; } } printf("%d", res); return 0; }P2058 [NOIP 2016 普及组] 海港
#include <stdio.h> #define MAXSIZE 300001 #define DIFF 86400 // 只需记录当前24h内的乘客国籍 int main() { int n, t, k, x, res = 0; int q[MAXSIZE][2], front = 0, rear = 0; // 到达时间，国籍 int nation[100001] = {0}; scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%d %d", &t, &k); // 出队 for (; front != rear && q[front][0] <= t - DIFF; front++) { nation[q[front][1]]--; if (nation[q[front][1]] == 0) res--; } // 入队 while (k--) { scanf("%d", &x); q[rear][0] = t; q[rear++][1] = x; if (nation[x] == 0) res++; nation[x]++; } printf("%d\n", res); } return 0; }P1241 括号序列
#include <stdio.h> // 栈 + 标记数组 int main() { char s[105]; int stack[105], top = 0; int matched[105] = {0}; // 标记哪些位置已经配对 scanf("%s", s); for (int i = 0; s[i]; i++) { if (s[i] == '(' || s[i] == '[') { stack[top++] = i; // 存下标，不是存字符 continue; } if (top > 0) { int last = stack[top - 1]; if ((s[last] == '(' && s[i] == ')') || (s[last] == '[' && s[i] == ']')) { matched[last] = 1; matched[i] = 1; top--; } // 不匹配就不管，留着后面补 } } // 输出：遍历原串，没配对的位置前后补括号 for (int i = 0; s[i]; i++) { if (!matched[i]) { // 前面补对应的左括号 if (s[i] == ')' || s[i] == ']') { printf("%c", s[i] == ')' ? '(' : '['); } } putchar(s[i]); if (!matched[i]) { // 后面补对应的右括号 if (s[i] == '(' || s[i] == '[') { printf("%c", s[i] == '(' ? ')' : ']'); } } } return 0; }P2234 [HNOI2002] 营业额统计
这道题链表会比数组慢，因为链表花大量时间在“从头遍历找插入位置”上，而数组用二分查找 + 连续内存移动，反而总耗时更少。
// 链表版 #include <stdio.h> #include <stdlib.h> typedef struct Node{ int data; struct Node *next; }Node; int insert(Node *head, int x) { Node *cur = head->next, *prev = head; while (cur && x > cur->data) { cur = cur->next; prev = prev->next; } // 此时 prev < x < cur if (cur && x == cur->data) return 0; Node *newNode = (Node*)malloc(sizeof(Node)); newNode->data = x; newNode->next = cur; prev->next = newNode; if (cur == NULL) return x - prev->data; if (prev == head) return cur->data - x; return cur->data - x < x - prev->data ? cur->data - x : x - prev->data; } // 需要找到前i天中最接近第i天营业额的值 -> 插入排序，链表 int main() { int n, res = 0; scanf("%d", &n); Node *head = (Node*)malloc(sizeof(Node)); head->next = NULL; head->data = 0; while (n--) { int temp; scanf("%d", &temp); res += insert(head, temp); } printf("%d", res); return 0; }// 数组版 #include <stdio.h> #include <stdlib.h> int a[40000], cnt = 0; // 二分找插入位置 int insert(int x) { if (cnt == 0) { a[0] = x; cnt = 1; return x; } int l = 0, r = cnt - 1, pos = cnt; while (l <= r) { int m = (l + r) >> 1; if (a[m] < x) l = m + 1; else r = m - 1; } pos = l; int min = 1 << 30; if (pos > 0 && x - a[pos - 1] < min) min = x - a[pos - 1]; if (pos < cnt && a[pos] - x < min) min = a[pos] - x; // 插入（往后移） for (int i = cnt; i > pos; i--) a[i] = a[i - 1]; a[pos] = x; cnt++; return min; } int main() { int n, x, res = 0; scanf("%d", &n); while (n--) { scanf("%d", &x); res += insert(x); } printf("%d", res); return 0; }P4387 【深基15.习9】验证栈序列
#include <stdio.h> int sq[100001] = {0}, s[100001] = {0}; int main() { int q, n; scanf("%d", &q); while (q--) { scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &sq[i]); // 第i个数出栈时，前i-1个数一定都已入栈 int temp, begin = 0, top = 0, flag = 1; for (int i = 0; i < n; ++i) { scanf("%d", &temp); if (top > 0 && s[top - 1] == temp) { top--; continue; } while (begin < n && sq[begin] != temp) s[top++] = sq[begin++]; if (begin == n) { flag = 0; } // 这里注意千万不要break！！因为还需要把这一串的输入读完...在这卡了好久orz begin++; } if (flag && top == 0) printf("Yes\n"); else printf("No\n"); } return 0; }
