PKU2019数据结构与算法实习期末考试
http://dapractise.openjudge.cn/2019finalexam2/
排队
|
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 |
#include<map> #include<set> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<stack> #define ll long long #define inf 1000000000 #define N 100005 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n, m; int fa[30005]; int getfa(int x) { return x == fa[x]? x: fa[x] = getfa(fa[x]); } int main() { int T = read(); while(T--) { n = read(); m = read(); for(int i = 1; i <= n; i++) fa[i] = i; for(int i = 1; i <= m; i++) { int x = read(), y = read(); int fx = getfa(x), fy = getfa(y); fa[fx] = fy; } for(int i = 1; i <= n; i++) printf("%d ", getfa(i)); cout << endl; } return 0; } |
树状数组过线段树不过
|
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 |
#include<map> #include<set> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<stack> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int nextRand(int num) { return (num * 199 + 666) % 9875321; } int m, n; int t[3000005]; int main() { m = read(); n = read(); int num = 0; ll ans = 0; for(int i = 1; i <= n; i++) { num = nextRand(num); int x = num % m + 1; for(int i = x - 1; i; i -= i & -i) ans += t[i]; for(int i = x; i <= m; i += i & -i) t[i]++; } cout << ans << endl; return 0; } |
线段树求最大数
|
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 |
#include<map> #include<set> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<stack> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int m, n; int L[800005], R[800005], mx[800005]; void build(int k, int l, int r) { L[k] = l; R[k] = r; mx[k] = 0; if(l == r)return; int mid = (l + r) >> 1; build(k << 1, l, mid); build(k << 1 | 1, mid + 1, r); } void modify(int k, int x, int y) { int l = L[k], r = R[k], mid = (l + r) >> 1; if(l == r) { mx[k] = y; return; } if(x <= mid)modify(k << 1, x, y); else modify(k << 1 | 1, x, y); mx[k] = max(mx[k << 1], mx[k << 1 | 1]); } int query(int k, int x, int y) { int l = L[k], r = R[k], mid = (l + r) >> 1; if(l == x && y == r) return mx[k]; int ans = 0; if(x <= mid)ans = max(ans, query(k << 1, x, min(y, mid))); if(y > mid)ans = max(ans, query(k << 1 | 1, max(x, mid + 1), y)); return ans; } int main() { int T = read(); while(T--) { m = read(); build(1, 1, 200000); n = 0; for(int i = 1; i <= m; i++) { char ch[2]; scanf("%s", ch); int t = read(); if(ch[0] == 'A') { n++; modify(1, n, t); } else { int ans = query(1, n - t + 1, n); printf("%d\n", ans); } } } return 0; } |
关键词搜索
|
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 |
#include<map> #include<set> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<stack> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n, cnt; char str[100005]; int t[500005][26]; int danger[500005], fail[500005], q[500005], vis[500005]; void insert(int l) { int now = 1; for(int i = 0; i < l; i++) { int y = str[i] - 'a'; if(!t[now][y]) t[now][y] = ++cnt; now = t[now][y]; } danger[now]++; } void buildfail() { for(int i = 0; i < 26; i++) t[0][i] = 1; int head = 0, tail = 1; q[0] = 1; fail[1] = 0; while(head != tail) { int x = q[head]; head++; for(int i = 0; i < 26; i++) { if(!t[x][i])continue; int y = t[x][i], k = fail[x]; while(!t[k][i]) k = fail[k]; fail[y] = t[k][i]; // danger[y] += danger[t[k][i]]; q[tail++] = y; } } } int query(int l) { int ans = 0, now = 1; for(int i = 0; i < l; i++) { int y = str[i] - 'a'; while(!t[now][y]) now = fail[now]; now = t[now][y]; int k = now; while(!vis[k] && k) { ans += danger[k]; vis[k] = 1; k = fail[k]; } } return ans; } int main() { int T = read(); while(T--) { n = read(); cnt = 1; for(int i = 1; i <= n; i++) { scanf("%s", str); insert(strlen(str)); } // for(int i = 1; i <= cnt; i++) // cout << danger[i] <<' '; buildfail(); scanf("%s", str); cout << query(strlen(str)) << endl; for(int i = 1; i <= cnt; i++) { for(int j = 0; j < 26; j++) t[i][j] = 0; danger[i] = vis[i] = 0; } } return 0; } |
旅行最短路
|
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<map> #include<set> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<stack> #define ll long long #define inf 100000000 #define pa pair<int, int> using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n, m, cnt; int dis[2][2005], last[2005], vis[2005]; struct data{ int to, next, v; }e[10005]; void insert(int u, int v, int w) { e[++cnt] = (data){v, last[u], w}; last[u] = cnt; e[++cnt] = (data){u, last[v], w}; last[v] = cnt; } priority_queue<pa, vector<pa>, greater<pa> >q; void dijkstra(int x, int f) { memset(vis, 0, sizeof(vis)); dis[f][x] = 0; q.push(make_pair(0, x)); while(!q.empty()) { int now = q.top().second; q.pop(); if(vis[now])continue; vis[now] = 1; for(int i = last[now]; i; i = e[i].next) if(dis[f][now] + e[i].v < dis[f][e[i].to]) { dis[f][e[i].to] = dis[f][now] + e[i].v; q.push(make_pair(dis[f][e[i].to], e[i].to)); } } } int main() { int T = read(); while(T--) { memset(last, 0, sizeof(last)); memset(dis, 127/3, sizeof(dis)); cnt = 0; n = read(); m = read(); for(int i = 1; i <= m; i++) { int u = read(), v = read(), w = read(); insert(u, v, w); } dijkstra(1, 0); dijkstra(n, 1); for(int i = 1; i <= n; i++) { int ans = dis[0][i] + dis[1][i]; if(ans > inf)ans = -1; printf("%d ", ans); } cout << endl; } return 0; } |
强连通分量
|
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 |
#include<map> #include<set> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<stack> #define ll long long #define inf 100000000 #define N 100005 #define M 200005 #define pa pair<int, int> using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n, m, scc, ind, top; int bl[N], inq[N], low[N], dfn[N], size[N], q[N]; vector<int> e[N]; void tarjan(int x) { dfn[x] = low[x] = ++ind; q[++top] = x; inq[x] = 1; for(int i = 0; i < e[x].size(); i++) if(!dfn[e[x][i]]) { tarjan(e[x][i]); low[x] = min(low[x], low[e[x][i]]); } else if(inq[e[x][i]]) low[x] = min(low[x], dfn[e[x][i]]); if(low[x] == dfn[x]) { int now = -1; scc++; while(now != x) { now = q[top]; top--; inq[now] = 0; size[scc]++; bl[now]=scc; } } } int main() { int T = read(); while(T--) { n = read(); m = read(); scc = ind = top = 0; for(int i = 1; i <= n; i++) { e[i].clear(); dfn[i] = low[i] = size[i] = 0; } for(int i = 1; i <= m; i++) { int u = read(), v = read(); e[u].push_back(v); } for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i); printf("%d\n", scc); sort(size + 1, size + scc + 1); for(int i = 1; i <= scc; i++) printf("%d ", size[i]); cout << endl; } return 0; } |
统计不同子串
|
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 |
#include<map> #include<set> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<stack> #define ll long long #define inf 100000000 #define N 100005 #define M 200005 #define pa pair<int, int> using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int MAXN = 100010; int wa[MAXN], wb[MAXN], wv[MAXN], Ws[MAXN]; //辅助数组 int height[MAXN], Rank[MAXN]; int s[MAXN]; char str[MAXN]; int n, m; //注意，wv和Ws的元素个数应该同时超过字符串的字符种类数和字符串长度 int sa[MAXN]; //sa[i]是名次为i的后缀的位置，即后缀数组 void buildSA(const int * s, int * sa) { //n: 字符串s的长度 //m: 开始是字符串s中字符的种类数，后来变成不同j-后缀的个数 //调用方法： buildSA("banana",sa,6，127); int i, j, p, *pm = wa, *k2sa = wb, *t; for (i = 0; i<m; i++) Ws[i] = 0; for (i = 0; i<n; i++) Ws[pm[i] = s[i]]++; //(1) //此时Ws[i]是字符i(编码为i的字符)出现的次数 ，pm是原字符串s的复制品 //字符的编码就是字符的排名，此处排名可不连续，相对大小正确即可 //Ws[i]也可以看作排名为i的1-后缀的出现次数 for (i = 1; i<m; i++) Ws[i] += Ws[i - 1]; //此时Ws[i]是编码不大于i的字符出现的次数, //也可以说是排名不大于 i 的字符出现的次数 for (i = n - 1; i >= 0; i--) sa[--Ws[pm[i]]] = i; //(2) for (j = p = 1; p < n; j <<= 1, m = p) { //烧脑循环 //在一次循环中,已知j-后缀相关信息,要求 2j-后缀相关信息 //此时，sa[i]是名次为i的j-后缀的位置,pm[i]是位置为i的j-后缀的排名 // j > 1时，m 是不同j-后缀的个数 for (p = 0, i = n - j; i < n; i++) k2sa[p++] = i; //k2sa[i]是所有2j-后缀按照第二关键字（第二个j-后缀）排序后，名次为i的 2j-后缀的位置 //从位置 n-j开始的2j-后缀，第二关键字为NULL，NULL的排名最小, //共j个2j-后缀的第二关键字是NULL //执行完此循环后，p = j, k2sa[0] - k2sa[j-1]值确定 for (i = 0; i < n; i++) //按名次从小到大遍历n个j-后缀 if (sa[i] >= j) k2sa[p++] = sa[i] - j; for (i = 0; i < m; i++) Ws[i] = 0; for (i = 0; i < n; i++) //按第二关键字名次遍历2j-后缀的第一关键字 Ws[ wv[i] = pm[k2sa[i]] ]++; //此时Ws[i]表示排名为i的j-后缀的个数 //j = 1时，Ws和 （1）处的 Ws是一样的 //pm[k2sa[i]]: 位置为k2sa[i]的j-后缀的排名 //Ws[i], 排名为 i 的 j-后缀的个数(j>1时，i从0到m-1) //wv[i]: 位置为k2sa[i]的j-后缀的排名,第一次执行的时候，和s[k2sa[i]]的编码一样 for (i = 1; i < m; i++) Ws[i] += Ws[i - 1]; //此时 Ws[i]是排名不大于i的j-后缀的个数 for (i = n - 1; i >= 0; i--) //按第二关键字的名次从大到小遍历所有2j-后缀 sa[--Ws[wv[i]]] = k2sa[i];//求位置为k2sa[i]的2j-后缀的名次 for (t = pm, pm = k2sa, k2sa = t, pm[sa[0]] = 0, p = i = 1; i<n; i++) {//按名次遍历2j-后缀 //p为目前发现的，不同的 2j-后缀的个数 int a = sa[i - 1], b = sa[i]; //a,b是名次相邻的两个2j-后缀的位置 //pm,k2sa换了，所以此时k2sa[i]是位置为i的j-后缀的排名 if (k2sa[a] == k2sa[b] && a + j < n && b + j < n && k2sa[a + j] == k2sa[b + j]) //看名次为i的那个2j-后缀是不是新的，即和名次为i-1的那个2j-后缀是否一样 //如果两个2j-后缀，他们的第一关键字排名相同（即第一关键字相同） //且第二关键字排名也相同（即第二关键字相同），则这俩个2j-后缀相同 pm[sa[i]] = p - 1; //未发现新的2j-后缀 //位置为sa[i](即排名为i的那个2j-后缀的位置)的2j-后缀的排名是 p - 1 else pm[sa[i]] = p++; //发现新的2j-后缀 } //当p达到n时，说明已经有了n个不同的2j-后缀，并且都在sa里排好了序。 //因此p达到n时，循环即可终止。 } //烧脑循环结束 return; } void BuildHeight(int * str,int * sa,int * Rank) { int i, j, k; for(int i = 0;i < n; ++i) //i 是名次,n是字符串长度 Rank[sa[i]] = i; height[0] = 0; for (i = k = 0; i < n - 1; height[Rank[i++]] = k)//i是位置 for (k ? k-- : 0, j = sa[Rank[i] - 1]; //Rank[0]>0才不越界 str[i+k]==str[j+k]; k++); //k相当于是 H[i]; height[Rank[i]] = H[i] ; } int main() { int T = read(); while(T--) { n = read(); m = 27; scanf("%s", str); for(int j = 0; j < n; j++) s[j] = str[j] - 'a' + 1; n++; buildSA(s, sa); BuildHeight(s, sa, Rank); ll ans = 0; for(int i = 1; i < n; i++) { // cout << sa[i] << endl; ans += n - sa[i] - 1 - height[i]; } cout << ans << endl; } return 0; } |
匹配 网络流模板
|
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 |
#include<map> #include<set> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<stack> #define ll long long #define inf 100000000 #define N 100005 #define M 200005 #define pa pair<int, int> using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n, m, k, T, ans, cnt; int h[405], q[405], last[405]; struct data{ int to, next, v; }e[100005]; void insert(int u, int v, int w) { e[++cnt] = (data){v, last[u], w}; last[u] = cnt; e[++cnt] = (data){u, last[v], 0}; last[v] = cnt; } bool bfs() { memset(h, 0, sizeof(h)); h[0] = 1; q[0] = 0; int head = 0, tail = 1; while(head != tail) { int x = q[head]; head++; for(int i = last[x]; i; i = e[i].next) if(!h[e[i].to] && e[i].v) { h[e[i].to] = h[x] + 1; q[tail++] = e[i].to; } } return h[T]; } int dfs(int x, int f) { if(x == T)return f; int w, used = 0; for(int i = last[x]; i; i = e[i].next) if(h[e[i].to] == h[x] + 1 && e[i].v) { w = dfs(e[i].to, min(f - used, e[i].v)); e[i].v -= w; e[i ^ 1].v += w; used += w; if(used == f)return f; } if(!used)h[x] = 0; return used; } int main() { int test = read(); while(test--) { ans = 0; n = read(); m = read(); k = read(); T = n + m + 2 * k + 1; cnt = 1; memset(last, 0, sizeof(last)); for(int i = 1; i <= k; i++) for(int j = 1; j <= n; j++) { int x = read(); if(x) insert(j, i + n, 1); } for(int i = 1; i <= k; i++) for(int j = 1; j <= m; j++) { int x = read(); if(x) insert(i + k + n, n + 2 * k + j, 1); } T = n + m + 2 * k + 1; for(int i = 1; i <= k; i++) insert(n + i, n + i + k, 1); for(int i = 1; i <= n; i++) insert(0, i, 1); for(int i = 1; i <= m; i++) insert(n + 2 * k + i, T, 1); while(bfs()) ans += dfs(0, inf); cout << ans << endl; } return 0; } |
线性表出
|
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 |
#include<map> #include<set> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<stack> #define ll long long #define inf 100000000 #define N 100005 #define M 200005 #define pa pair<int, int> using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct P{ int x, y; friend bool operator<(P a, P b) { if(a.y == b.y)return a.x < b.x; return a.y < b.y; } friend int operator*(P a, P b) { return a.x * b.y - a.y * b.x; } friend P operator-(P a, P b) { return (P){a.x - b.x, a.y - b.y}; } }p[10005], q[10005]; int dis2(P a) { return a.x * a.x + a.y * a.y; } int n, top; ll ans; bool cmp(P a, P b) { if((a - p[1]) * (b - p[1]) == 0) return dis2(a - p[1]) < dis2(b - p[1]); return (a - p[1]) * (b - p[1]) > 0; } void graham() { top = 0; for(int i = 2; i <= n; i++) if(p[i] < p[1]) swap(p[i], p[1]); sort(p + 2, p + n + 1, cmp); for(int i = 1; i <= n; i++) { while(top > 1 && (q[top] - q[top - 1]) * (p[i] - q[top]) <= 0) top--; q[++top] = p[i]; } // for(int i = 1; i <= top; i++) q[++top] = p[1]; for(int i = 2; i <= top; i++) ans += (q[i] - q[1]) * (q[i + 1] - q[1]); if(ans < 0)ans = -ans; } int main() { int T = read(); while(T--) { n = read(); ans = 0; for(int i = 1; i <= n; i++) p[i].x = read(), p[i].y = read(); graham(); if(ans & 1) printf("%lld.50\n", ans / 2); else printf("%lld.00\n", ans / 2); } return 0; } |
Subscribe
计数器 9850901
OI 课件=>
OI 课件=>