寒假开始，最近一段时间开始了寒假训练。这段时间如果没有别的事情，争取每天多刷题。每天都抽点空写写题解，写写刷题收获。
POJ - 2387 Dijkstra
题意
一个无向图，起点为1，终点为N的最短路，保证有解。
一个最短路的裸题。。。直接上熟悉的Dijkstra代码，堆优化复杂度。
AC代码
//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <set>
#include <stack>
#include <sstream>
#include <list>
//#include <array>
#include <vector>
#include <queue>
#include <map>
#include <memory>
#include <iterator>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;
int const maxn = 2000 + 10;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
inline int lc(int x) {return x << 1;}
inline int rc(int x) {return x << 1 | 1;}
int dis[maxn];
struct node {
int v, w, next;
}e[maxn << 1];
int head[maxn], cnt, vis[maxn];
void init() {
cnt = 0;
memset(head, -1, sizeof(head));
memset(vis, 0, sizeof(vis));
}
void add(int u, int v, int w) {
e[cnt].v = v;
e[cnt].w = w;
e[cnt].next = head[u];
head[u] = cnt++;
}
int dijkstra(int s, int ed) {
memset(dis, 0x3f, sizeof(dis));
priority_queue<pair<int, int> > q;
dis[s] = 0;
q.push({0, s});
while (!q.empty()) {
int u = q.top().second;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].v, w = e[i].w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push({-dis[v], v});
}
}
}
return dis[ed];
}
int main(void) {
FAST_IO;
init();
int t, n;
cin >> t >> n;
for (int i = 0; i < t; i++) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
add(v, u, w);
}
cout << dijkstra(1, n) << endl;
return 0;
} POJ - 3660 Floyd
题意
有n个牛打架，已经知道了m条打架结果，求出可以得到具体名称牛的个数。
分析
当看到确定排名的时候，第一个想到的就是拓扑排序。虽然感觉并查集找连通个数，然后拓扑排序也可以AC。但这题在最短路专题里，就去想了想最短路的方法。
若是已知 a与b有关系，b与c有关系，则可以推出a与c有关系。例如 a//b b//c 则 a//c 。这就是一种传递的关系，离散数学上的传递闭包。
根据Floyd公式，则设
表示
，则可以推出闭包公式
void Floyd()
{
for(int k=0; k<=n; ++k)
for(int i=0; i<=n; ++i)
for(int j=0; j<=n; ++j)
a[i][j] = a[i][j] || (a[i][k] && a[k][j]);
} 而当对象确定关系的个数总和，及
,则表示
的结果可以确定。
AC代码
//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <set>
#include <stack>
#include <sstream>
#include <list>
//#include <array>
#include <vector>
#include <queue>
#include <map>
#include <memory>
#include <iterator>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;
int const maxn = 100 + 10;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
inline int lc(int x) {return x << 1;}
inline int rc(int x) {return x << 1 | 1;}
int a[maxn][maxn];
int main(void) {
FAST_IO;
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
a[u][v] = 1;
}
// 求传递闭包
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (a[i][k] && a[k][j]) {
a[i][j] = 1;
}
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
int temp = 0;
for (int j = 1; j <= n; j++) {
if (a[i][j] || a[j][i]) temp++;
}
// 若确定关系个数为n-1个，则排名确定
if (temp == n - 1) ans++;
}
cout << ans << endl;
return 0;
} HDU - 2612 两次BFS
题意
Y和M要去同一家KFC见面。要去求出Y和M到KFC最少的总时间。
分析
一个二维平面最短路问题。其实就是个有点麻(s)烦(b)的。方法有很多，可以跑两次BFS，找出Y和M都可以到达的KFC中总用时最短的。
我的解法类似，但不想写2个函数，就用一个标记表示是Y还是M的路径。使用一个队列完成两次BFS。
AC代码
//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <set>
#include <stack>
#include <sstream>
#include <list>
//#include <array>
#include <vector>
#include <queue>
#include <map>
#include <memory>
#include <iterator>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;
int const maxn = 200 + 10;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
inline int lc(int x) {return x << 1;}
inline int rc(int x) {return x << 1 | 1;}
int n, m;
int vis1[maxn][maxn];
int vis2[maxn][maxn];
int mp2[maxn][maxn];
char mp[maxn][maxn];
int dis1[maxn][maxn], dis2[maxn][maxn];
struct node {
int x, y, step, v;
node(int x = 0, int y = 0, int step = 0, int v = 0) : x(x), y(y), step(step), v(v) { }
};
int const dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
int x1, x2, y1, y2;
void bfs() {
queue<node> q;
q.push(node(x1, y1, 0, 1));
q.push(node(x2, y2, 0, 2));
while (!q.empty()) {
node tq = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int tx = tq.x + dir[i][0];
int ty = tq.y + dir[i][1];
if (tx >= 0 && tx < n && ty >= 0 && ty < m && mp[tx][ty] != '#') {
if (tq.v == 1) {
if (vis1[tx][ty]) continue;
q.push(node(tx, ty, tq.step + 1, 1));
vis1[tx][ty] = 1;
dis1[tx][ty] = tq.step + 1;
} else {
if (vis2[tx][ty]) continue;
q.push(node(tx, ty, tq.step + 1, 2));
vis2[tx][ty] = 1;
dis2[tx][ty] = tq.step + 1;
}
}
}
}
}
int main(void) {
FAST_IO;
while (cin >> n >> m) {
memset(dis1, 0x3f, sizeof(dis1));
memset(dis2, 0x3f, sizeof(dis2));
memset(vis1, 0, sizeof(vis1));
memset(vis2, 0, sizeof(vis2));
for (int i = 0; i < n; i++) {
cin >> mp[i];
for (int j = 0; j < m; j++) {
if (mp[i][j] == 'Y') {
x1 = i, y1 = j;
}
if (mp[i][j] == 'M') {
x2 = i, y2 = j;
}
}
}
vis1[x1][y1] = vis1[x2][y2] = 1;
vis2[x1][y1] = vis2[x2][y2] = 1;
dis1[x1][y1] = 0;
dis2[x2][y2] = 0;
bfs();
int ans = INF;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mp[i][j] == '@' && dis1[i][j] != INF && dis2[i][j] != INF && dis1[i][j] + dis2[i][j] <= ans) {
ans = dis1[i][j] + dis2[i][j];
}
}
}
cout << ans * 11 << endl;
}
return 0;
} HDU - 1875 MST
题意
有N个岛屿，现在需要施工，要求让N个岛屿全都连通，并且2个小岛之间的距离不能小于10米，也不能大于1000米，并且花费最小。若是无法实现，则输出"oh!"。
分析
还是最小生成树的裸题，是需要判断岛的距离大于等于10小于等于1000就行了。
AC代码
//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <set>
#include <stack>
#include <sstream>
#include <list>
//#include <array>
#include <vector>
#include <queue>
#include <map>
#include <memory>
#include <iterator>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;
int const maxn = 100 * 100 + 10;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
inline int lc(int x) {return x << 1;}
inline int rc(int x) {return x << 1 | 1;}
struct point {
int x, y;
point(const int &x = 0, const int &y = 0) : x(x), y(y) { }
}p[maxn];
double dis(point &x, point &y) {
return sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y));
}
struct node {
int u, v;
double w;
bool operator<(const node &x) const {
return w < x.w;
}
}e[maxn];
int fa[maxn];
int cnt, setnum;
bool check(const double &w1) {
if (w1 < 10 || w1 > 1000) return false;
return true;
}
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
bool unio(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) {
fa[fx] = fy;
return false;
}
return true;
}
void init(int n) {
cnt = 0;
setnum = n;
for (int i = 0; i <= n; i++) {
fa[i] = i;
}
}
double kruskal() {
sort(e, e + cnt);
double ans = 0;
for (int i = 0; i < cnt; i++) {
if (!unio(e[i].u, e[i].v)) {
setnum--;
ans += e[i].w;
}
}
return ans;
}
int main(void) {
FAST_IO;
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
init(n);
for (int i = 0; i < n; i++) {
cin >> p[i].x >> p[i].y;
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
double w = dis(p[i], p[j]);
if (check(w)) {
e[cnt++] = {i, j, w};
}
}
}
double ans = kruskal();
if (setnum != 1) cout << "oh!" << endl;
else cout << fixed << setprecision(1) << ans * 100 << endl;
}
return 0;
} POJ - 2018 二分
题意
给定一个正整数数列，求一个平均数最大的，长度不小于L的子段。
分析
蓝书上经典二分答案判定。
若二分的值域为长度>=L子段的平均值，则可以把数组中的每个数字减去这个值，就转换成了"是否存在一个长度不小L的子段和>=0"的问题。
而对于这个问题的判断，可以在的时间复杂度内实现。使用前缀和的性质，子段和可以转换成前缀和减法。即：
随着i的增长，j的取值范围都没增大，所以只需要每次枚举j，记录最小的
就行了。
总复杂度：check函数，二分
，总共为
AC代码
//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <set>
#include <stack>
#include <sstream>
#include <list>
// #include <array>
#include <vector>
#include <queue>
#include <map>
#include <memory>
#include <iterator>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;
int const maxn = 1e5 + 10;
inline int lc(int x) {return x << 1;}
inline int rc(int x) {return x << 1 | 1;}
double a[maxn], b[maxn], sum[maxn];
int main(void) {
// FAST_IO;
int n, L;
// cin >> n >> L;
scanf("%d %d", &n, &L);
for (int i = 1; i <= n; i++) {
// cin >> a[i];
scanf("%lf", &a[i]);
}
double eps = 1e-5;
double l = -1e6, r = 1e6;
while (r - l > eps) {
double mid = (l + r) / 2;
for (int i = 1; i <= n; i++) {
b[i] = a[i] - mid;
}
for (int i = 1; i <= n; i++) {
sum[i] = (sum[i - 1] + b[i]);
}
double ans = -1e10;
double min_val = 1e10;
for (int i = L; i <= n; i++) {
min_val = min(min_val, sum[i - L]);
ans = max(ans, sum[i] - min_val);
}
if (ans >= 0) l = mid;
else r = mid;
}
// cout << (int)(r * 1000) << endl;
printf("%d\n", (int)(r * 1000));
return 0;
} 总结
今天寒假开始第一天，写了一些题。但大多还是都是水题、裸题。。。就当状态康复吧。
今天这些题中，比较的经典的：floyd求传递闭包、二分答案求子段和，这两题还是挺具有代表性，比较增长视野的。
京公网安备 11010502036488号