如果你是荣誉课的学生，请你注意以下事项：
这里有两道题没做
C. 公共子串 II 传统题 3000ms 256MB
Description 给定两个字符串 \(s\) 和 \(t\) ，计算字符串 \(s\) 和 \(t\) 公共子串对数量。
假设第一个字符串 \(s = (s_1, s_2, \dots, s_n)\) 和 \(t = (t_1, t_2, \dots, t_m)\) ，统计有多少对 \((i, j, k)\) 使得子串 \(s_i, \dots, s_{i+k-1}\) 和 \(t_j, \dots, t_{j+k-1}\) 相等。（其中 \(k > 0, 1 \leq i + k - 1 \leq n, 1 \leq j + k - 1 \leq m\) ）。
这里我们定义两个字符串 \(s\) 和 \(t\) 是相等当且仅当将两个字符串按照字典序排序之后，每一个位置都对应相等，例如字符串abc和字符串acb在这种定义下认为是相等的。
第一行两个整数 \(n\) 和 \(m\) 表示字符串长度。
第二行为长度为 \(n\) 的字符串 \(s\) 和长度为 \(m\) 的字符串 \(t\) 。
两个字符串之间用空格隔开。
Output 一个整数，表示字符串 \(s\) 和 \(t\) 公共子串对数量。
Samples 输入样例
输出样例
Limitation \(2 \leq n, m \leq 3000\)
思路与题解 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 #include <iostream> #include <vector> #include <map> #include <unordered_map> using namespace std;using ull = unsigned long long ;const ull BASE = 131ULL ;ull gethash (const vector<int >& f) { ull h = 0 ; for (int i = 0 ; i < 26 ; ++i) h = h * BASE + (ull)(f[i] + 1 ); return h; } int main () int n, m; cin >> n >> m; string s, t; cin >> s >> t; int maxK = min (n,m); int ans = 0 ; for (int k = 1 ; k <= maxK; ++k) { unordered_map<ull, int > cnt (max(1 , n-k+1 ) * 2 ) ; vector<int > f (26 ) ; for (int i = 0 ; i < k; ++i) f[s[i] - 'a' ]++; cnt[gethash (f)]++; for (int i = k; i < n; ++i) { f[s[i]-'a' ]++; f[s[i-k]-'a' ]--; cnt[gethash (f)]++; } vector<int > g (26 ) ; for (int i = 0 ; i < k; ++i) g[t[i]-'a' ]++; auto it = cnt.find (gethash (g)); if (it != cnt.end ()) ans += it->second; for (int i = k; i < m; ++i) { g[t[i]-'a' ]++; g[t[i-k]-'a' ]--; auto it2 = cnt.find (gethash (g)); if (it2 != cnt.end ()) ans += it2->second; } } cout << ans; return 0 ; }
D. 嘉然今天切什么 传统题 1500ms 256MB
Description 嘉然家的玻璃被熊孩子打坏了！
在这寒冷的天气中，没有玻璃怎么行？Y很着急，他不想让嘉然着凉！
于是，Y从玻璃制造厂拉了一大块玻璃来，大小恰好为 \(H \times W\) 。当然，他还需要自己动手切割，才能恰好切割出嘉然窗户的形状。
Y有两种切割玻璃的方式：
H a，表示沿着 \(a\) 刻度的位置水平切一刀；W a，表示沿着 \(a\) 刻度的位置垂直切一刀。Y想知道，每次切割以后，最大块的玻璃的面积是多少。
第一行三个整数 \(W\) ，\(H\) 和 \(n\) 分别表示宽、高和切割次数。
接下来 \(n\) 行，每行一个字符（H 或 W）表示水平切割还是垂直切割，和一个整数 \(a\) 表示切割的刻度位置。
Output 对于每次切割，输出当前最大的玻璃的面积。
Samples 输入样例
输出样例
Limitation \(1 \leq n \leq 2 \times 10^5\) ，\(2 \leq W, H \leq 10^9\) 。
保证切割的刻度必定存在，保证不会在同一个地方切割两次。
思路与题解 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 #include <iostream> #include <vector> #include <set> using namespace std;using ll = long long ;int main () ll W,H,n; cin>>W>>H>>n; set<ll> weightP, heightP; multiset<ll> weightL, heightL; weightP.insert (0 ); weightP.insert (W); heightP.insert (0 ); heightP.insert (H); weightL.insert (W); heightL.insert (H); while (n--) { char op; int a; cin >> op >> a; if (op == 'H' ) { auto it = heightP.insert (a).first; auto pre = prev (it); auto nxt = next (it); ll old = *nxt - *pre; auto lenIt = heightL.find (old); if (lenIt != heightL.end ()) heightL.erase (lenIt); heightL.insert (a - *pre); heightL.insert (*nxt - a); } else if (op == 'W' ) { auto it = weightP.insert (a).first; auto pre = prev (it); auto nxt = next (it); ll old = *nxt - *pre; auto lenIt = weightL.find (old); if (lenIt != weightL.end ()) weightL.erase (lenIt); weightL.insert (a - *pre); weightL.insert (*nxt - a); } ll maxH = *prev (heightL.end ()); ll maxW = *prev (weightL.end ()); cout << (maxH * maxW) << "\n" ; } return 0 ; }
E. 最小过路费 题目背景 小思来到了博学园，这里有 \(n\) 个城市。
城市与城市之间有许多道路，具体而言一共有 \(m\) 条双向道路。其中第 \(i\) 条道路连接了城市 \(a_i\) 和 \(b_i\) ，并且这条道路的过路费为 \(c_i\) ，意味着通过这条道路（无论是从哪个方向）将花费 \(c_i\) 个辆云币。因为博学园只修建两种道路，过路费只有两种可能：免费、或 1 个辆云币，即：\(c_i \in \{0,1\}\) 。
博学园的城市是连通的，这意味着从任何一个城市出发都存在路径到达任何一个城市。
我们定义 \(cost(x,y)\) 表示从城市 \(x\) 出发走到城市 \(y\) 所消耗的最小过路费。
接下来，小思有 \(Q\) 次询问，每次询问会给你一个起点 \(S\) ，表示询问 \(\sum_{x=1}^n cost(S,x)\) 的值。
请你回答一下小思的询问吧！
输入格式 第一行包含两个整数 \(n\) ，\(m\) 分别表示城市数量和道路数量。
接下来的 \(m\) 行种，第 \(i\) 行包含 3 个整数 \(a_i, b_i, c_i\) ，表示道路连接的城市和过路费。
接下来一行，一个整数 \(Q\) 表示小思的询问次数。
接下来的 \(Q\) 行，每行一个整数 \(S\) 表示询问的起点。
输出格式 输出 \(Q\) 行，每行一个整数，表示对应的答案。
样例 #1 样例输入 #1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 5 7 1 2 0 1 3 1 1 4 1 1 5 1 2 4 1 2 3 0 3 5 0 5 1 2 3 4 5
样例输出 #1 数据范围与提示 对于 10% 的测试数据满足 \(n, m \leq 10\)
对于 40% 的测试数据满足 \(n \leq 1000\)
对于 70% 的测试数据满足 \(Q \leq 3\)
对于 100% 的测试数据满足 \(1 \leq n \leq 10^5, 1 \leq m \leq 2 \times 10^5, 1 \leq Q \leq 50, 1 \leq a_i, b_i, S \leq n, c_i \in \{0,1\}\)
思路与题解 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 #include <deque> #include <iostream> #include <vector> #include <climits> using namespace std;int main () int n, m; cin >> n >> m; vector<vector<pair<int ,int >>> adj (n+1 ); while (m--) { int a, b, c; cin >> a >> b >> c; adj[a].emplace_back (b, c); adj[b].emplace_back (a, c); } int Q; cin >> Q; vector<int > dist (n+1 , INT_MAX) ; deque<int > q; while (Q--) { int S; cin >> S; fill (dist.begin (), dist.end (), INT_MAX); dist[S] = 0 ; q.clear (); q.push_front (S); while (!q.empty ()) { int u = q.front (); q.pop_front (); int distu = dist[u]; for (auto pairs : adj[u]) { int v = pairs.first; int distv = pairs.second; if (distv + distu < dist[v]) { dist[v] = distv + distu; if (distv == 0 ) q.push_front (v); else q.push_back (v); } } } long long ans = 0 ; for (int i = 1 ; i <= n; i++) ans += dist[i]; cout << ans << "\n" ; } return 0 ; }
SB. L 传统题 2000ms 256MiB
题面 要求在一个 \(n \times m\) 的由小写字符构成的矩阵中找出一个 \(L\) 形的由小写字符构成的字符串的出现次数。\(k\) 的 \(L\) 形字符串宽为 \(k\) ，高为 \(k\) ，粗细为 \(1\) ，按先从上到下，再从左到右 的顺序输入。\(3\) 的 \(L\) 形字符串，其形状形如：
对应的输入格式形如：
输入格式 第 \(1\) 行输入字符矩阵的长 \(n\) ，宽 \(m\) ，\(L\) 形字符串的长度 \(k\) （\(n, m \leq 5000, 2 \leq k \leq \min(n,m)\) ）。\(2\) 行到第 \(n+1\) 行输入 \(n\) 个长为 \(m\) 的小写字母字符串，表示一个 \(n \times m\) 的矩阵。\(n+2\) 行输入一个长为 \(2k-1\) 的小写字母字符串，表示一个长度为 \(k\) 的 \(L\) 形字符串。
输出格式 一个数字，表示该 \(L\) 形字符串在矩阵中的出现次数。
样例 输入数据 1 1 2 3 4 5 6 7 5 4 3 bbbb bbfd dddd rdfg rdfg bbddd
输出数据 1 输入数据 2 1 2 3 4 5 6 4 5 3 aedcf bbbbf cdeaf fffff abcde
输出数据 2 思路与题解 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 #include <iostream> #include <vector> using namespace std;using ll = long long ;const ll BASE = 131 ;int main () int n, m, k; cin >> n >> m >> k; vector<string> g (n) ; for (int i = 0 ; i < n; ++i) cin >> g[i]; string L; cin >> L; string L1, L2; L1 = L.substr (0 , k); L2 = L.substr (k-1 , k); int ans = 0 ; vector<vector<bool >> key (n-k+2 , vector <bool >(m-k+2 , false )); for (int i = k-1 ; i < n; ++i){ for (int j = 0 ; j+k <= m; ++j){ string cur = g[i].substr (j, k); if (cur == L2){ key[i-k+1 ][j] = true ; } } } vector<string> gr (m) ; for (int i = 0 ; i < n; ++i){ for (int j = 0 ; j < m; ++j){ gr[j].push_back (g[i][j]); } } for (int i = 0 ; i+k <= m; ++i){ for (int j = 0 ; j+k <= n; ++j){ if (key[j][i]){ string cur = gr[i].substr (j, k); if (cur == L1){ ans++; } } } } cout << ans; return 0 ; }
SC. 岛屿（island） 传统题 1500ms 512MiB
题目描述 C 国有 \(n\) 个互不连通的岛屿，政府决定修建若干桥梁连接部分岛屿。对于第 \(i\) 号岛屿，修建桥梁的难易度是 \(a_i\) ，如果在难易度分别为 \(x,y\) 的岛屿之间建桥，那么就要花费 \(x+y\) 单位的金钱。由于某些原因，一个岛屿最多修建 \(3\) 座桥。
政府会下达 \(m\) 次指令，每次给出两个岛屿编号 \(x,y\) ，你需要先判断岛屿 \(x,y\) 是否已经联通（联通指：岛屿 \(x\) 可以通过某些桥到达岛屿 \(y\) ）。如果已经联通，则无视这条指令；否则，你可以选择岛屿 \(x\) 或与岛屿 \(x\) 联通的某个岛屿，再选择岛屿 \(y\) 或者与岛屿 \(y\) 联通的某个岛屿，在所选的两个岛屿之间建桥（注意需要满足每个岛屿修桥不超过 \(3\) 次的条件）。请最小化总造桥花费，并在每次指令下达后判断是否需要建桥。
输入格式 输入的第一行包含两个整数 \(n,m\) 。
接下来一行有 \(n\) 个整数，为 \(a_1,a_2,a_3\ldots a_n\) 。
接下来 \(m\) 行，每行两个正整数 \(x,y\) 。
输出格式 输出一共 \(m+1\) 行，对于前 \(m\) 行，每一行输出 yes 或 no，代表需要修桥或者不需要修桥。第 \(m+1\) 行输出最小总花费。
样例 1 输入 1 2 3 4 5 6 7 5 5 1 10 10 10 10 1 2 1 3 1 4 2 3 1 5
样例 1 输出 样例 1 解释 第一条指令，\(1,2\) 没有联通，选择岛屿 \(1,2\) 建桥，花费为 \(1+10=11\) 。
第二条指令，\(1,3\) 没有联通，选择岛屿 \(1,3\) 建桥，花费为 \(1+10=11\) 。
第三条指令，\(1,4\) 没有联通，选择岛屿 \(1,4\) 建桥，花费为 \(1+10=11\) 。
第四条指令，\(2,3\) 已经联通，故不做处理。
第五条指令，\(1,5\) 没有联通，但是岛屿 \(1\) 已经修建三次，可以选择岛屿 \(2,5\) 建桥，花费为 \(10+10=20\) 。
总花费为 \(53\) 。
样例 2 输入 1 2 3 4 5 6 7 8 9 10 11 12 10 10 1 7 9 1 1 1 6 1 1 6 1 6 1 1 3 10 1 9 1 7 2 7 5 7 1 5 3 6 3 9
样例 2 输出 1 2 3 4 5 6 7 8 9 10 11 yes no yes yes yes yes yes no yes no 43
思路与题解 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 #include <iostream> #include <vector> #include <numeric> #include <queue> using namespace std;int n;vector<int > a; vector<int > dsu; vector<int > sz; vector<vector<int >> g; vector<int > rem; long long ans = 0 ;struct cmp { bool operator () (int x, int y) const if (a[x] != a[y]) return a[x] > a[y]; return x > y; } }; vector<priority_queue<int , vector<int >, cmp>> query; int find (int u) if (u == dsu[u]) return u; return dsu[u] = find (dsu[u]); } void connect (int u, int v) u = find (u); v = find (v); if (u == v) return ; if (sz[u] < sz[v]) swap (u, v); dsu[v] = u; sz[u] += sz[v]; while (!query[v].empty ()){ int x = query[v].top (); query[v].pop (); query[u].push (x); } } int available (int u) u = find (u); while (!query[u].empty ()){ int x = query[u].top (); if (rem[x] > 0 ) return x; query[u].pop (); } return -1 ; } void solve (int x, int y) int px = find (x), py = find (y); if (px == py){ cout << "no" << '\n' ; return ; } int cx = available (px); int cy = available (py); if (cx == -1 || cy == -1 ){ cout << "no" << '\n' ; return ; } ans += (long long )a[cx] + (long long )a[cy]; rem[cx]--; rem[cy]--; connect (px, py); cout << "yes" << '\n' ; } int main () int m; if (!(cin >> n >> m)) return 0 ; a.resize (n); g.resize (n); query.clear (); query.resize (n); dsu.resize (n, 0 ); sz.assign (n, 1 ); rem.assign (n, 3 ); iota (dsu.begin (), dsu.end (), 0 ); for (int i = 0 ; i < n; ++i) { cin >> a[i]; query[i].push (i); } while (m--){ int x, y; cin >> x >> y; x--; y--; solve (x, y); } cout << ans; return 0 ; }
