A U193219 混乱的小镇
题目大意:
E小镇是个混乱的地方,一开始每个人自成帮派(即每个人是自己的老大),有时候会发生团体与团体的混战,胜利一方的老大会成为两个帮派的所有人的老大,并将两个帮派合并。
负责治安的警官Eden会记录下每次混战中不同团体的两个人以及胜利者。但需要注意有时候两个人可能属于同一个帮会,此时属于帮会内战,老大是不会发生任何变化的。有时Eden还需要回答来自上司的检查,即询问某个人的老大是谁,Eden想请你写个程序帮帮他。
题解:
并查集模板,数据强度好像比洛谷官方的要大,之前写模板题的路径压缩在这会超时
代码:
#include<bits/stdc++.h> #define N 100100 using namespace std; int a[N]; int find(int x) { return x == a[x] ? a[x] : a[x] = find(a[x]); } int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { a[i] = i; } while (m--) { int o; scanf("%d", &o); if (o == 0) { int x, y; scanf("%d%d", &x, &y); int c = find(x); int d = find(y); a[d] = c; } if (o == 1) { int x; scanf("%d", &x); printf("%d\n", find(x)); } } return 0; }
B P1706 全排列问题
题目大意:
按照字典序输出自然数 1 到 n 所有不重复的排列,即 n 的全排列,要求所产生的任一数字序列中不允许出现重复的数字。
题解:
DFS+回溯直接扫就行了,n的范围很小很小。
也可以用STL内置的全排列函数(std::next_permutation)。
关于std::next_permutation的介绍可以参考这里:
https://en.cppreference.com/w/cpp/algorithm/next_permutation
代码:
DFS+回溯:
#include<bits/stdc++.h> #define N 100100 using namespace std; vector<int> v; int vis[20]; void dfs(int begin, int n) { if (begin == n) { for (int i = 0; i < n; i++) { printf("%5d", v[i]); } printf("\n"); return; } int l = v.size(); for (int i = 1; i <= n; i++) { int flag = 1; for(int j = 0; j < l; j++){ if(v[j] == i){ flag = 0; } } if(flag){ v.push_back(i); dfs(begin + 1, n); v.pop_back(); } } return; } int main() { int n; cin >> n; dfs(0, n); return 0; }
STL:
#include<bits/stdc++.h> using namespace std; vector<int> nums; int main() { int n; cin>>n; for(int i = 1; i <= n; i++){ nums.push_back(i); } do { for(int i = 0; i < n; i++){ printf("%5d", nums[i]); } printf("\n"); } while(std::next_permutation(nums.begin(), nums.end())); return 0; }
C P1102 A-B 数对
题目大意:
给出一串数以及一个数字 C,要求计算出所有 A−B=C 的数对的个数
题解:
先移一下,变成 A - C = B,然后排序之后二分上下界找B的个数就好了。
代码:
#include<bits/stdc++.h> using namespace std; long long nums[200010]; int main(){ int n,c; cin>>n>>c; for(int i = 0; i < n; i++){ scanf("%lld", &nums[i]); } long long ans = 0; sort(nums, nums + n); for(int i = 0; i < n; i++){ int k = nums[i] - c; ans += upper_bound(nums, nums + n, k) - lower_bound(nums, nums + n, k); } printf("%lld", ans); }
D U193113 子串和
题目大意:
给一个长度为n的序列,问有多少子串的和为0?
题解:
先算了前缀和。
最开始算完之后双层for遍历,果断超时,毕竟n^2
已经十个零了= =
然后转用map去记前缀和相同的个数,因为子串和为0等同于两个前缀和相等
$$b{c} = a{1} + a{2} + ... + a{c}$$
$$b{d} = a{1} + a{2} + ... + a{d}$$
$$b{c} - b{d} = a{d+1} + ... + a{c} = 0$$
$$b{c} - b{d} = 0$$ 等同于 $$b{c} = b{d}$$
然后还要算个排列组合,因为任意两个相同的前缀和都可以代表一段相加为0的子段。
代码:
#include<bits/stdc++.h> #define N 200100 using namespace std; long long a[N]; long long b[N]; long long C(int d, int n){ long long u = 1; for(int i = n - d + 1; i <= n; i++){ u *= i; } for(int i = 1; i <= d; i++){ u /= i; } return u; } map<int, int> m; int main() { int n; cin>>n; for(int i = 1; i <= n; i++){ scanf("%lld", &a[i]); } for(int i = 1; i <= n; i++){ b[i] = b[i - 1] + a[i]; } long long ans = 0; for(int i = 0; i <= n; i++){ auto it = m.find(b[i]); int x = 0; if(it != m.end()){ x = it->second; m.erase(it); } m.insert(make_pair(b[i], x + 1)); } for(auto it = m.rbegin(); it != m.rend(); it++){ if(it->second > 1){ ans += C(2, it->second); } } printf("%lld", ans); return 0; }
E U193234 矩形覆盖
题目大意:
给出二维平面上的n个边与坐标轴平行的矩形,求被它们覆盖过的地方总面积。
0<=x1,y1,x2,y2<=100000
题解:
还不会做,看标签好像是离散化,等会了再来填坑。
之前好像有遇见过类似的但是是求最后一次覆盖的是第几个矩形....应该不太一样。顺便一说好像Leetcode上喜欢出这种,没记错有好几道= =
F P1824 进击的奶牛
题意:
x轴上N个点中选择c个点,问每两个点的最小距离最大时候的值(= =反正就是最小情况的最大值)
题解:
易得具有单调性,考虑二分答案。
代码:
#include<bits/stdc++.h> using namespace std; int nums[100010]; int m, l, r; int main() { int n, c; cin>>n>>c; for (int i = 0; i < n; i++) { scanf("%d", &nums[i]); } sort(nums, nums + n); l = 0; r = nums[n - 1] - nums[0] + 10; for (int i = 0; i < 100; i++) { m = l + ((r - l) >> 1); int les = nums[0] + m, ct = 1; for (int i = 1; i < n; i++) { if (nums[i] >= les) { les = nums[i] + m; ct++; } } if (ct >= c) { l = m + 1; } else { r = m - 1; } } printf("%d", r); }
G P1396 营救
题意:
一个无向图,要求求出s点到t点的路径中每一个线段的最大值最小的情况是多少。
题解:
emmmmm
开始想的是最短路径魔改,写了个dijk发现好像不是很好改,然后又写了个最小生成树,生成完之后再dfs从起点沿着树的路径到扫到终点就好了。
最开始偷懒用二维数组来标记数是否经过某个线段,然后果断MEL了,然后又改了用vector存才过的...
代码:
#include<bits/stdc++.h> using namespace std; int n, m, s, t, u, v, total; struct edge { int start, to; int val; bool operator<(edge b) { return val < b.val; } } bian[20010]; int f[20010]; int x[20010]; long long ans = 0; vector<int> vis[20010]; int find(int x) { return x == f[x] ? f[x] : f[x] = find(f[x]); } inline void kruskal() { for (int i = 1; i <= m; i++) { u = find(bian[i].start); v = find(bian[i].to); if (u == v) continue; vis[bian[i].start].push_back(bian[i].to); vis[bian[i].to].push_back(bian[i].start); f[u] = v; total++; if (total == n - 1) break; } } void dfs(int q, int mx, int from) { if (q == t) { ans = mx; return; } if (ans != 0) { return; } while (!vis[q].empty()) { int v = vis[q].back(); if (v != from) { for (int j = 1; j <= m; j++) { if ((bian[j].start == q && bian[j].to == v) || (bian[j].to == q && bian[j].start == v)) { dfs(v, max(mx, bian[j].val), q); break; } } } vis[q].pop_back(); } } int main() { scanf("%d%d%d%d", &n, &m, &s, &t); for (int i = 1; i <= n; i++) f[i] = i; for (int i = 1; i <= m; i++) { scanf("%d%d%d", &bian[i].start, &bian[i].to, &bian[i].val); } sort(bian + 1, bian + m + 1); kruskal(); dfs(s, -1, s); printf("%lld", ans); }
H P1144 最短路计数
题目大意:
给出一个N个顶点M条边的无向无权图,顶点编号为1到N。问从顶点1开始,到其他每个点的最短路有几条。
题解:
其实写个dijk就好了,如果d[e.to] > d[v] + 1那么e.to的路径数就等于v的路径数,如果d[e.to] == d[v] + 1那么e.to的路径数就要加上v的路径数。(此时已确定要进行松弛操作)
代码:
#include<bits/stdc++.h> #define MAXV 2000010 #define INF 0x3f3f3f3f using namespace std; struct edge{ int to,cost; }; int n; vector<edge> G[MAXV]; int d[1000010]; int nums[1000010]; typedef pair<int, int> P; const int mod = 100003; void dijk(int s){ priority_queue<P, vector<P>, greater<P> > que; memset(d, INF, sizeof(d)); d[s] = 0; nums[s] = 1; que.push(P(0, s)); while(!que.empty()){ P p = que.top(); que.pop(); int v = p.second; if(d[v] < p.first) continue; for(int i = 0; i < G[v].size(); i++){ edge e = G[v][i]; if(d[e.to] > d[v] + e.cost){ d[e.to] = d[v] + e.cost; nums[e.to] = nums[v]; que.push(P(d[e.to], e.to)); } else if(d[e.to] == d[v] + e.cost){ nums[e.to] += nums[v]; nums[e.to] %= mod; } } } } int main(){ int n,m; scanf("%d %d", &n, &m); for(int i = 0; i < m; i++){ int u,v; scanf("%d%d", &u, &v); G[u].push_back({v,1}); G[v].push_back({u,1}); } dijk(1); for(int i = 1; i <= n; i++){ printf("%d\n", nums[i]); } return 0; }
后面还有两题暂时都不会做,摆烂