太弱小了。。。
ABC 水水水题略过。
D. Unnatural Language Processing
找规律，如果出现CVCC的形式划分为CVC其余情况都划分为CV
|
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 |
#include <iostream> #include <cstring> #include <vector> #include <unordered_map> #include <algorithm> using namespace std; void solve() { int n; string s; cin >> n >> s; unordered_map<char, bool> h; h['a'] = h['e'] = 1; h['b'] = h['c'] = h['d'] = 0; for (int i = 0; i < n;) { if (i + 3 < n && !h[s[i + 2]] && !h[s[i + 3]] || i + 3 == n) { cout << s[i] << s[i + 1] << s[i + 2]; i += 3; if (i < n) cout << '.'; } else { cout << s[i] << s[i + 1]; i += 2; if (i < n) cout << '.'; } } cout << '\n'; } int main() { cin.tie(0)->sync_with_stdio(0); int T; cin >> T; while (T --) { solve(); } } |
E. Romantic Glasses
stl unordered_map被hack了，长知识了
|
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 <iostream> #include <cstring> #include <vector> #include <algorithm> #include <map> using namespace std; using LL = long long; void solve() { int n; cin >> n; vector<int> a(n + 1); vector<LL> b(n + 1); map<LL, int> h; a[0] = b[0] = 0; h[0] = 1; for (int i = 1; i <= n; ++ i) { cin >> a[i]; if (i & 1) { b[i] = b[i - 1] + a[i]; } else { b[i] = b[i - 1] - a[i]; } h[b[i]] ++; } for(auto [key, val]: h) { if (val > 1) { cout << "YES\n"; return; } } cout << "NO\n"; } int main() { cin.tie(0)->sync_with_stdio(0); int T; cin >> T; while (T --) { solve(); } } |
F. Greetings
只有一个线段包含另外一个线段才有可能相遇
按左端点排序，然后对每一个线段都找右端点比它小的个数
用树状数组维护右端点就可以做到O(nlogn)
|
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 <cstring> #include <algorithm> #include <unordered_map> #include <vector> using namespace std; using PII = pair<int, int>; using LL = long long; const int N = 2e5 + 10; int c[N]; int lowbit(int x) { return x & -x; } void add(int x, int v) { for (int i = x; i < N; i += lowbit(i)) c[i] += v; } int query(int x) { int res = 0; for (int i = x; i; i -= lowbit(i)) res += c[i]; return res; } void solve() { int n; cin >> n; vector<PII> a(n); vector<int> b; for (int i = 0; i < n; ++ i) { cin >> a[i].first >> a[i].second; b.push_back(a[i].second); } sort(b.begin(), b.end()); unordered_map<int, int> h; for (int i = 0; i < n; ++ i) { h[b[i]] = i + 1; } for (int i = 0; i < n; ++ i) { a[i].second = h[a[i].second]; } sort(a.begin(), a.end()); for (int i = 0; i < n; ++ i) { add(a[i].second, 1); } LL ans = 0; for (int i = 0; i < n; ++ i) { ans += query(a[i].second) - 1; add(a[i].second, -1); } cout << ans << '\n'; } int main() { cin.tie(0)->sync_with_stdio(0); int T; cin >> T; while (T --) { solve(); } } |
G. Bicycles
学了一个新的算法——分层图
看一个板子题
P4568 [JLOI2011] 飞行路线
|
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 |
#include <iostream> #include <cstring> #include <queue> #include <algorithm> #define toMin(a, b) (a > b ? a = b: 0) #define toMax(a, b) (a < b ? a = b: 0) using namespace std; using PII = pair<int, int>; const int N = 1e4 + 10, M = 1e5 + 10, K = 15; const int INF = 0x3f3f3f3f; int h[N], e[M], ne[M], w[M], idx; int dist[N][K]; bool vis[N][K]; int n, m, k; int s, t; /* dist[i,j]表示从起点走到i点用了j次免费机会的最短路 for each edge to point v [u,v,cost] 来说有两种可能 1.不用免费机会 dist[v,j]=MIN(dist[u,j]) 2.使用免费机会 dist[v,j]=MIN(dist[u,j+1]) */ void add(int a, int b, int c) { e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++; } void dijkstra(int s, int t) { memset(dist, 0x3f, sizeof dist); priority_queue<PII, vector<PII>, greater<PII>> heap; dist[s][0] = 0; heap.push({0, s}); while (heap.size()) { int t = heap.top().second; int d = heap.top().first; int u = t % n; int f = t / n; heap.pop(); if (vis[u][f]) continue; vis[u][f] = true; for (int i = h[u]; ~i; i = ne[i]) { int to = e[i]; int c = w[i]; if (dist[to][f] > d + c) { dist[to][f] = d + c; heap.push({d + c, f * n + to}); } if (f < k && dist[to][f + 1] > d) { dist[to][f + 1] = d; heap.push({d, (f + 1) * n + to}); } } } } int main() { cin.tie(0)->sync_with_stdio(0); memset(h, -1, sizeof h); cin >> n >> m >> k; cin >> s >> t; while (m --) { int a, b, c; cin >> a >> b >> c; add(a, b, c), add(b, a, c); } dijkstra(s, t); int ans = INF; for (int i = 0; i <= k; ++ i) toMin(ans, dist[t][i]); cout << ans << '\n'; } |
本题的代码
|
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 |
#include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <queue> #define toMin(a, b) (a > b ? a = b: 0) #define toMax(a, b) (a < b ? a = b: 0) using namespace std; using LL = long long; using PLI = pair<LL, int>; const int N = 1e3 + 10, M = N << 1; const LL INF = 0x3f3f3f3f3f3f3f3f; int h[N], e[M], ne[M], w[M], idx; int n, m, s[N]; bool st[N][N]; LL dist[N][N]; /* dist[i,j]表示从起点到i点最后一次用j车的最小值 for each edge from v to u: let dist = c and use Bicycle j 1. dist[u,j]=MIN(dist[v,j]+c*s[j]) 2. dist[u,v]=MIN(dist[v,v]+c*s[u]) */ void add(int a, int b, int c) { e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++; } void dijkstra(int start, int end) { memset(dist, 0x3f, sizeof dist); memset(st, false, sizeof st); priority_queue<PLI, vector<PLI>, greater<PLI>> heap; heap.push({0, start * n + start}); dist[start][start] = 0; while (heap.size()) { int point = heap.top().second; LL d = heap.top().first; int u = point % n, f = point / n; heap.pop(); if (st[u][f]) continue; st[u][f] = true; for (int i = h[u]; ~i; i = ne[i]) { int to = e[i], c = w[i]; if (dist[to][f] > d + (LL)c * s[f]) { // 不换车 dist[to][f] = d + (LL)c * s[f]; heap.push({dist[to][f], f * n + to}); } if (dist[to][u] > d + (LL)c * s[u]) { // 换车 dist[to][u] = d + (LL)c * s[u]; heap.push({dist[to][u], u * n + to}); } } } } void solve() { idx = 0; memset(h, -1, sizeof h); cin >> n >> m; while (m --) { int a, b, c; cin >> a >> b >> c; add(a, b, c), add(b, a, c); } for (int i = 1; i <= n; ++ i) cin >> s[i]; dijkstra(1, n); LL res = INF; for (int i = 1; i <= n; ++ i) toMin(res, dist[n][i]); cout << res << '\n'; } int main() { cin.tie(0)->sync_with_stdio(0); int T; cin >> T; while (T --) { solve(); } } |
发表回复