Tsinghua 2018 DSA PA3简要题解

CST2018 3-1-1 Sum (15%)

简单的线段树，单点修改，区间求和。

很简单。

CST2018 3-1-2 Max (20%)

高级的线段树。

维护区间最大和，区间和，左边最大和，右边最大和。

单点修改的时候一路吧区间都改了就好了。

求子段最大值也就判断一下左右就好了。

略微复杂。

  1 #include <cstdio>
  2 
  3 using namespace std;
  4 const int N = 5e5 + 5;
  5 const int inf = 1e9;
  6 int n, m;
  7 int a[N];
  8 
  9 inline int max(int x, int y) {
 10     return x > y ? x : y;
 11 }
 12 
 13 struct seg {
 14     seg *ls, *rs;
 15     int sum, mx, mxl, mxr;
 16     
 17     void* operator new(size_t) {
 18         static seg* c;
 19         c = new seg[1];
 20         c -> ls = c -> rs = NULL;
 21         c -> mxl = c -> mxr = c -> mx = c -> sum = 0;
 22         return c;
 23     }
 24     
 25     inline void change_point(int x) { //change the value of a single point
 26         if (x > 0) {
 27             sum = mx = mxl = mxr = x;
 28         } else {
 29             sum = x;
 30             mx = mxl = mxr = 0;
 31         }
 32     }
 33     
 34     inline void update() {
 35         if (ls == NULL || rs == NULL) return;
 36         sum = ls -> sum + rs -> sum;
 37         mx = max(max(ls -> mx, rs -> mx), ls -> mxr + rs -> mxl);
 38         mxl = max(ls -> mxl, ls -> sum + rs -> mxl);
 39         mxr = max(rs -> mxr, rs -> sum + ls -> mxr);
 40     }
 41     
 42     #define mid (l + r >> 1)
 43     void build(int l, int r) {
 44         if (l == r) {
 45             change_point(a[l]);
 46             return;
 47         }
 48         ls = new()seg, ls -> build(l, mid);
 49         rs = new()seg, rs -> build(mid + 1, r);
 50         update();
 51     }
 52     
 53     void modify(int l, int r, int pos, int x) {
 54         if (pos < l || r < pos) return;
 55         if (l == r) {
 56             change_point(x);
 57             return;
 58         }
 59         if (pos <= mid) ls -> modify(l, mid, pos, x);
 60         if (mid < pos) rs -> modify(mid + 1 , r, pos, x);
 61         update();
 62     }
 63     
 64     seg* query(int l, int r, int L, int R) {
 65         seg* ret = new()seg;
 66         if (l == L && R == r) {
 67             *ret = *this;
 68             return ret;
 69         }
 70         if (R <= mid) return ls -> query(l, mid, L, R);
 71         if (L > mid) return rs -> query(mid + 1, r, L, R);
 72         
 73         ret -> ls = ls -> query(l, mid, L, mid);
 74         ret -> rs = rs -> query(mid + 1, r, mid + 1, R);
 75         ret -> update();
 76         delete ret -> ls;
 77         delete ret -> rs;
 78         return ret;
 79     }
 80     #undef mid
 81 } *segment, *ans;
 82 
 83 int main() {
 84     int op, x, y;
 85     scanf("%d%d", &n, &m);
 86     for (int i = 1; i <= n; ++i)
 87         scanf("%d", a + i);
 88     segment = new()seg;
 89     segment -> build(1, n);    
 90     for (int i = 1; i <= m; ++i) {
 91         scanf("%d%d%d", &op, &x, &y);
 92         if (op == 0) {
 93             segment -> modify(1, n, x, y);
 94         } else {
 95             ans = segment -> query(1, n, x, y);
 96             printf("%d
", ans -> mx);
 97             delete ans;
 98         }
 99     }
100     return 0;
101 }

View Code

CST2018 3-2 Not Found (20%)

内存有点小，在考虑按层建立trie树？

不太会。

CST2018 3-3 Hacker (20%)

$18^5$其实并不大，直接预处理hash一下就好了。

冲突的话直接记录输出duplicate。

比较简单。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include "crc.h"
  4 
  5 using namespace std;
  6 const char charset[] = "0123456789tsinghua";
  7 const char setlen = 18;
  8 const int P2 = 38734667;
  9 const char LEN = 20;
 10 int hashTable[P2], flag[P2];
 11 
 12 char code[LEN];
 13 char pwd[LEN];
 14 
 15 int n;
 16 char salt[LEN];
 17 int saltlen;
 18 
 19 int test_cnt;
 20 
 21 inline int encode_char(char ch) {
 22     switch(ch) {
 23         case '0' : return 1;
 24         case '1' : return 2;
 25         case '2' : return 3;
 26         case '3' : return 4;
 27         case '4' : return 5;
 28         case '5' : return 6;
 29         case '6' : return 7;
 30         case '7' : return 8;
 31         case '8' : return 9;
 32         case '9' : return 10;
 33         case 't' : return 11;
 34         case 's' : return 12;
 35         case 'i' : return 13;
 36         case 'n' : return 14;
 37         case 'g' : return 15;
 38         case 'h' : return 16;
 39         case 'u' : return 17;
 40         case 'a' : return 18;
 41     }
 42 }
 43 
 44 inline char decode_char(int x) {
 45     switch(x) {
 46         case 1 : return '0';
 47         case 2 : return '1';
 48         case 3 : return '2';
 49         case 4 : return '3';
 50         case 5 : return '4';
 51         case 6 : return '5';
 52         case 7 : return '6';
 53         case 8 : return '7';
 54         case 9 : return '8';
 55         case 10 : return '9';
 56         case 11 : return 't';
 57         case 12 : return 's';
 58         case 13 : return 'i';
 59         case 14 : return 'n';
 60         case 15 : return 'g';
 61         case 16 : return 'h';
 62         case 17 : return 'u';
 63         case 18 : return 'a';
 64     }
 65 }
 66 
 67 inline int encode(char* str) {
 68     int len = strlen(str);
 69     int encodeNumber = 0;
 70     for (int i = 0; i < len; ++i)
 71         encodeNumber = 19 * encodeNumber + encode_char(str[i]);
 72     return encodeNumber;
 73 }
 74 
 75 inline void swap(char &x, char &y) {
 76     char t;
 77     t = x;
 78     x = y;
 79     y = t;
 80 }
 81 
 82 inline void decode(char* str, int x) {
 83     int t = 0;
 84     while (x) {
 85         str[t] = decode_char(x % 19);
 86         x = x / 19;
 87         t += 1;
 88     }
 89     for (int i = 0; i * 2 < t; ++i) {
 90         swap(str[i], str[t - i - 1]);
 91     }
 92     str[t] = 0;
 93 }
 94 
 95 int _union(char *str, unsigned char *input) {
 96     int i = 0;
 97     for (; str[i]; ++i) input[i] = str[i];
 98     for (int j = 0; salt[j]; ++j) input[i++] = salt[j];
 99     input[i] = 0;
100     return i;
101 }
102 
103 inline bool check_eq(int x, int y) {
104     char str[10];
105     decode(str, x);
106     unsigned char input[20];
107     int i = _union(str, input);
108     int CRC32Value1 = crc32(input, i);
109     if (CRC32Value1 == y) return 1;
110     return 0;
111 }
112 
113 void insert_hash(int x, int y) {
114     int hash = ((x % P2) + P2) % P2;
115     while (hashTable[hash] != -1) {
116         if (check_eq(hashTable[hash], x)) {
117             flag[hash] = 1;
118             return;
119         }
120         hash += 1;
121     }
122     hashTable[hash] = y;
123 }
124 
125 void update_pwd(char x) {
126     for (int i = 0; i <= 5; ++i)
127         pwd[i] = pwd[i + 1];
128     pwd[6] = x;
129     pwd[7] = 0;
130 }
131 
132 void get_hash(int x) {
133     int hash = ((x % P2) + P2) % P2;
134     while (hashTable[hash] != -1) {
135         if (check_eq(hashTable[hash], x)) {
136             if (flag[hash] == 1) {
137                 puts("duplicate");
138                 return;
139             }
140             char ans[10];
141             decode(ans, hashTable[hash]);
142             printf("%s
", ans);
143             update_pwd(ans[0]);
144             return;
145         }
146         hash += 1;
147     }
148     puts("No");
149 }
150 
151 void make_hash(char* str) {
152     unsigned char input[20];
153     int i = _union(str, input);
154     int CRC32Value = crc32(input, i); //calculate CRC32
155     insert_hash(CRC32Value, encode(str));
156 }
157 
158 void dfs(int len) {
159     for (int i = 0; i < setlen; ++i) {
160         code[len] = charset[i];
161         code[len + 1] = 0;
162         make_hash(code);
163         if (len < 4) dfs(len + 1);
164     }
165 }
166 
167 void find_hash() {
168     int CRC32Value;
169     scanf("%d", &CRC32Value);
170     get_hash(CRC32Value);
171 }
172 
173 int main() {
174     int len;
175     int oper;
176     scanf("%d
", &n);
177     scanf("%s
", salt);
178     saltlen = strlen(salt);
179     for (int i = 0; i < P2; ++i)
180         hashTable[i] = -1, flag[i] = 0;
181     
182     dfs(0);
183     while (n--) {
184         scanf("%d
", &oper);
185         if (oper == 0) {
186             find_hash();
187         }
188         if (oper == 1) {
189             make_hash(pwd);
190         }
191     }
192     return 0;
193 }

View Code

CST2018 3-4 kth (20%)

可以先通过3n次比较进行排序。

一个数组的话直接二分就好了。

要是两个数组可以丢堆里面。

三个不会【摊手

  1 #include "kth.h"
  2 #include <cstdio>
  3 
  4 using namespace std;
  5 const int N = 5e5 + 5;
  6 const int K = 26e5 + 5;
  7 
  8 int X[N], Y[N], Z[N];
  9 
 10 template<class T> inline void swap(T &x, T &y) {
 11     register T tmp;
 12     tmp = x, x = y, y = tmp;
 13 }
 14 
 15 struct heap {
 16     heap *ls, *rs;
 17     int _X, _Y, _Z;
 18     int dep;
 19     
 20     void *operator new(size_t, int __X, int __Y, int __Z) {
 21         static heap mempool[K], *c = mempool;
 22         c -> ls = c -> rs = NULL;
 23         c -> dep = 1;
 24         c -> _X = __X, c -> _Y = __Y, c -> _Z = __Z;
 25         return c++;
 26     }
 27     
 28     friend inline bool compare_greater(heap *x, heap *y) {
 29         return compare(X[y -> _X], Y[y -> _Y], Z[y -> _Z], X[x -> _X], Y[x -> _Y], Z[x -> _Z]);
 30     }
 31     
 32     #define Dep(p) (p ? p -> dep : 0)
 33     friend heap* merge(heap *x, heap *y) {
 34         if (!x) return y;
 35         if (!y) return x;
 36         if (compare_greater(x, y)) swap(x, y);
 37         x -> rs = merge(x -> rs, y);
 38         if (Dep(x -> rs) > Dep(x -> ls)) swap(x -> ls, x -> rs);
 39         x -> dep = Dep(x -> rs) + 1;
 40         return x;
 41     }
 42     #undef Dep
 43     
 44     inline heap* pop() {
 45         return merge(ls, rs);
 46     }
 47 } *root;
 48 
 49 
 50 inline bool check_less(int flag, int x, int y) {
 51     if (flag == 1) return compare(x, 1, 1, y, 1, 1);
 52     if (flag == 2) return compare(1, x, 1, 1, y, 1);
 53     if (flag == 3) return compare(1, 1, x, 1, 1, y);
 54 }
 55 
 56 inline void swap(int *a, int x, int y) {
 57     int t;
 58     t = a[x];
 59     a[x] = a[y];
 60     a[y] = t;
 61 }
 62 
 63 void sort(int l, int r, int flag, int *A) {
 64     if (l >= r) return;
 65     swap(A[(l + r >> 1)], A[r]);
 66     int x = A[r], i = l - 1;
 67     for (int j = l; j <= r; ++j) {
 68         if (check_less(flag, A[j], x)) {
 69             i++;
 70             swap(A, i, j);
 71         }
 72     }
 73     i += 1;
 74     A[r] = A[i];
 75     A[i] = x;
 76     sort(l, i - 1, flag, A);
 77     sort(i + 1, r, flag, A);
 78 }
 79 
 80 void init(int n) {
 81     for (int i = 1; i <= n; ++i)
 82         X[i] = Y[i] = Z[i] = i;
 83     sort(1, n, 1, X);
 84     sort(1, n, 2, Y);
 85     sort(1, n, 3, Z);
 86 }
 87 
 88 inline void insert(int _X, int _Y, int _Z) {
 89     root = merge(root, new(_X, _Y, _Z)heap);
 90 }
 91 
 92 void get_kth(int n, int k, int *x, int *y, int *z) {
 93     init(n); //sort for x, y and z
 94     root = new(1, 1, 1)heap;
 95     int _X, _Y, _Z;
 96     while (--k) {
 97         _X = root -> _X, _Y = root -> _Y, _Z = root -> _Z;
 98         if (_Z != n) insert(_X, _Y, _Z + 1);
 99         if (_Z == 1) {
100             if (_Y == 1 && _X != n) insert(_X + 1, _Y, _Z);
101             if (_Y != n) insert(_X, _Y + 1, _Z);
102         }
103         root = root -> pop();
104     }
105     *x = X[root -> _X], *y = Y[root -> _Y], *z = Z[root -> _Z];
106 }

View Code

CST2018 3-5 Prefix (20%)

一道简单的KMP，就是考虑每个节点为结尾多出来多少重复的。

比较简单。

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 using namespace std;
 5 typedef long long ll;
 6 const int N = 2e7 + 5;
 7 
 8 int f[N];
 9 int cnt[N];
10 char str[N];
11 int len;
12 
13 void KMP(int len) {
14     int i = 0, j = -1;
15     f[0] = -1;
16     while (i < len) {
17         if (j == -1 || str[i] == str[j]) {
18             i += 1;
19             j += 1;
20             f[i] = j;
21         }
22         else j = f[j];
23     }
24     f[0] = 0;
25 }
26 
27 int main() {
28     gets(str);
29     len = strlen(str);
30     KMP(len);
31     ll ans = 0;
32     memset(cnt, 0, sizeof(cnt));
33     for (int i = 1; i <= len; ++i) {
34         cnt[i] = cnt[f[i]];
35         cnt[i]++;
36         ans += cnt[i];
37     }
38     printf("%lld
", ans);
39     return 0;
40 }

View Code

CST2018 3-6 Match (20%)

Treap的应用：

插入：基本操作。

删除：基本操作。

翻转：基本操作。

比较大小：用hash比较。

所以要记录两个值：以某个节点为根的顺序的hash和逆序的hash。

写起来比较麻烦。

  1 #include <cstdio>
  2 
  3 using namespace std;
  4 const int N = 4e5 + 5;
  5 const int LEN = 10e5 + 5;
  6 const int P1 = 951413;
  7 const int P2 = 1e9 + 7;
  8 
  9 int n, m;
 10 
 11 template<class T> inline void swap(T &x, T &y) {
 12     register T tmp;
 13     tmp = x, x = y, y = tmp;
 14 }
 15 
 16 
 17 namespace treap {
 18     struct node;
 19     node *root, *null;
 20     int base[LEN];
 21     
 22     inline int cal_hash(int hash1, int sz1, int ch, int hash2, int sz2) {
 23         int ret = (hash2 + 1ll * ch * base[sz2] % P2) % P2;
 24         ret = (ret + 1ll * hash1 * base[sz2 + 1] % P2) % P2;
 25         return ret;
 26     }
 27     
 28     struct node {
 29         node *ls, *rs;
 30         int sz, rev, hashl, hashr;
 31         int ch;
 32         
 33         #define Len (1 << 16)
 34         inline void* operator new(size_t, int _v = 0) {
 35             static node *mempool, *c;
 36             if (mempool == c)
 37                 mempool = (c = new node[Len]) + Len;
 38             c -> ls = c -> rs = null;
 39             c -> sz = 1;
 40             c -> rev = 0;
 41             c -> hashl = c -> hashr = c -> ch = _v;
 42             return c++;
 43         }
 44         #undef Len
 45         
 46         inline void reverse() {
 47             rev ^= 1;
 48             swap(ls, rs);
 49             swap(hashl, hashr);
 50         }
 51         
 52         inline node* push() {
 53             if (rev) {
 54                 ls -> reverse(), rs -> reverse();
 55                 rev = 0;
 56             }
 57             return this;
 58         }
 59         
 60         inline node* update() {
 61             sz = ls -> sz + rs -> sz + 1;
 62             ls -> push(), rs -> push();
 63             hashl = cal_hash(ls -> hashl, ls -> sz, ch, rs -> hashl, rs -> sz);
 64             hashr = cal_hash(rs -> hashr, rs -> sz, ch, ls -> hashr, ls -> sz);
 65             return this;
 66         }
 67     };
 68         
 69     inline void init() {
 70         null = new()node;
 71         null -> ls = null -> rs = null;
 72         null -> sz = null -> hashl = null -> hashr = 0;
 73         
 74         base[0] = 1;
 75         for (int i = 1; i < LEN; ++i)
 76             base[i] = 1ll * base[i - 1] * P1 % P2;
 77     }
 78     
 79     inline unsigned int Rand() {
 80         static unsigned int res = 2333;
 81         return res += res << 2 | 1;
 82     }
 83     inline int random(int x, int y) {
 84         return Rand() % (x + y) < x;
 85     }
 86     
 87     void build(node *&p, int l, int r, int *a) {
 88         if (l > r) {
 89             p = null;
 90             return;
 91         }
 92         p = new(a[l + r >> 1])node;
 93         if (l == r) {
 94             p -> update();
 95             return;
 96         }
 97         build(p -> ls, l, (l + r >> 1) - 1, a);
 98         build(p -> rs, (l + r >> 1) + 1, r, a);
 99         p -> update();
100     }
101     
102     void merge(node *&p, node *x, node *y) {
103         if (x == null || y == null)
104             p = x == null ? y -> push() : x -> push();
105         else if (random(x -> sz, y -> sz)) {
106             p = x -> push();
107             merge(p -> rs, x -> rs, y);
108         } else {
109             p = y -> push();
110             merge(p -> ls, x, y -> ls);
111         }
112         p -> update();
113     }
114      
115     void split(node *p, node *&x, node *&y, int k) {
116         if (!k) {
117             x = null, y = p -> push();
118             return;
119         }
120         if (k == p -> sz) {
121             x = p -> push(), y = null;
122             return;
123         }
124         if (p -> ls -> sz >= k) {
125             y = p -> push();
126             split(p -> ls, x, y -> ls, k);
127             y -> update();
128         } else {
129             x = p -> push();
130             split(p -> rs, x -> rs, y, k - p -> ls -> sz - 1);
131             x -> update();
132         }
133     }
134 }
135 using namespace treap;
136 
137 int a[N];
138 
139 int main() {
140     char ch;
141     int op;
142     int pos, tmp;
143     int pos1, pos2, len;
144     node *x, *y, *z;
145     int hash1, hash2, ans = 0;
146     scanf("%d %d
", &n, &m);
147     for (int i = 1; i <= n; ++i) {
148         ch = getchar();
149         while (!('a' <= ch && ch <= 'z')) ch = getchar();
150         a[i] = ch - 'a' + 1;
151     }
152     
153     init();
154     build(root, 1, n, a);
155     while (m--) {
156         scanf("%d", &op);
157         if (op == 1) {
158             scanf("%d", &pos);
159             ch = getchar();
160             while (!('a' <= ch && ch <= 'z')) ch = getchar();
161             tmp = ch - 'a' + 1;
162             split(root, x, y, pos);
163             z = new(tmp)node;
164             merge(root, x, z); merge(root, root, y);
165             //root = x + y, new_root = x + z + y
166         }
167         if (op == 2) {
168             scanf("%d", &pos);
169             split(root, x, y, pos - 1); split(y, y, z, 1);
170             merge(root, x, z);
171             //root = x + y + z, new_root = x + z
172         }
173         if (op == 3) {
174             scanf("%d %d", &pos1, &pos2);
175             split(root, x, y, pos1 - 1), split(y, y, z, pos2 - pos1 + 1);
176             y -> reverse();
177             merge(root, x, y -> push()), merge(root, root, z);
178             //root = x + y + z, y -> rev
179         }
180         if (op == 4) {
181             scanf("%d %d %d", &pos1, &pos2, &len);
182             split(root, x, y, pos1 - 1), split(y, y, z, len);
183             hash1 = y -> hashl;
184             merge(root, x, y), merge(root, root, z);
185             
186             split(root, x, y, pos2 - 1), split(y, y, z, len);
187             hash2 = y -> hashl;
188             merge(root, x, y), merge(root, root, z);
189             ans += (hash1 == hash2);
190         }
191     }
192     printf("%d
", ans);
193     return 0;
194 }

View Code

CST2018 3-7 History (15%)

强制在线。

简单hash。

CST2018 3-8 Shortest (15%)

堆优化Dijkstra。

其实我觉得spfa加SLF还是能过。。。