题目传送门
排行榜
一个人做了12年北大出的题，自己还是太弱了，图论的知识忘光光，最小生成树裸题写不来，Dijkstra TLE不知道用SPFA。
简单几何(点到线段的距离) + 三分 B Stealing a Cake
题意：圆外一个点先到圆再到矩形的最短距离。
分析：由于圆在[0, PI]和[PI, PI*2]上是单峰函数，用三分求极值，应该在[0，PI*2]上也算单峰函数吧。
/************************************************
* Author :Running_Time
* Created Time :2015/11/7 星期六 17:24:32
* File Name :B_2.cpp************************************************/#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = acos (-1.0);
int dcmp(double x) { //三态函数，减少精度问题if (fabs (x) < EPS) return 0;else return x < 0 ? -1 : 1;
}
struct Point { //点的定义double x, y;Point () {}Point (double x, double y) : x (x), y (y) {}Point operator + (const Point &r) const { //向量加法return Point (x + r.x, y + r.y);}Point operator - (const Point &r) const { //向量减法return Point (x - r.x, y - r.y);}Point operator * (double p) const { //向量乘以标量return Point (x * p, y * p);}Point operator / (double p) const { //向量除以标量return Point (x / p, y / p);}bool operator < (const Point &r) const { //点的坐标排序return x < r.x || (x == r.x && y < r.y);}bool operator == (const Point &r) const { //判断同一个点return dcmp (x - r.x) == 0 && dcmp (y - r.y) == 0;}
};
typedef Point Vector; //向量的定义
Point read_point(void) { //点的读入double x, y;scanf ("%lf%lf", &x, &y);return Point (x, y);
}
double dot(Vector A, Vector B) { //向量点积return A.x * B.x + A.y * B.y;
}
double cross(Vector A, Vector B) { //向量叉积return A.x * B.y - A.y * B.x;
}
Vector rotate(Vector A, double rad) {return Vector (A.x * cos (rad) - A.y * sin (rad), A.x * sin (rad) + A.y * cos (rad));
}
double length(Vector A) {return sqrt (dot (A, A));
}
double angle(Vector A, Vector B) { //向量转角，逆时针，点积return acos (dot (A, B) / length (A) / length (B));
}
double point_to_seg(Point p, Point a, Point b) {if (a == b) return length (p - a);Vector V1 = b - a, V2 = p - a, V3 = p - b;if (dcmp (dot (V1, V2)) < 0) return length (V2);else if (dcmp (dot (V1, V3)) > 0) return length (V3);else return fabs (cross (V1, V2)) / length (V1);
}struct Circle {Point c;double r;Circle () {}Circle (Point c, double r) : c (c), r (r) {}Point point(double a) {return Point (c.x + cos (a) * r, c.y + sin (a) * r);}
};Point s, a, b, c, d;
Circle C;double cal_dis(double rad) {Point p = C.point (rad);double dis1 = length (s - p);double dis2 = 1e9;dis2 = min (dis2, point_to_seg (p, a, b));dis2 = min (dis2, point_to_seg (p, b, c));dis2 = min (dis2, point_to_seg (p, c, d));dis2 = min (dis2, point_to_seg (p, d, a));return dis1 + dis2;
}int main(void) {double x, y, r, x2, y2;while (scanf ("%lf%lf", &x, &y) == 2) {if (dcmp (x) == 0 && dcmp (y) == 0) break;s = Point (x, y);scanf ("%lf%lf%lf", &x, &y, &r);C = Circle (Circle (Point (x, y), r));scanf ("%lf%lf%lf%lf", &x, &y, &x2, &y2);a = Point (min (x, x2), max (y, y2));b = Point (min (x, x2), min (y, y2));c = Point (max (x, x2), min (y, y2));d = Point (max (x, x2), max (y, y2));Vector V[2];int cnt = point_cir_tan (s, C, V);double l = angle (Vector (1, 0), V[0]), r = angle (Vector (1, 0), V[1]);if (l > r) swap (l, r);while (r - l > EPS) {double mid = (l + r) / 2;double lmid = (l + mid) / 2;double rmid = (r + mid) / 2;double res1 = cal_dis (lmid),res2 = cal_dis (rmid);if (res1 < res2) {r = rmid;}else l = lmid;}printf ("%.2f\n", cal_dis (l));}return 0;
}
预处理+递推DP C Substrings
题意：给n个数字，q次询问，每次回答所有长度为w的子串不同数字个数的和
分析：先想状态，dp[w]表示长度为w的不同数字总和，有个递推关系，dp[i] = dp[i-1] - last[i-1] + sum[i]。last[i]表示后缀长度为i的不同个数，从i-1到i时能发现少了最后一个长度i-1的子串，当然还要加上新的权值，sum[i]表示两个相同数字距离大于等于i的所有个数，那么先求c[i] 等于i的所有个数，后缀累加就行了。这题充分使用了预处理的技巧求解问题，复杂度 O (n)
/************************************************
* Author :Running_Time
* Created Time :2015/11/9 星期一 10:23:58
* File Name :C.cpp************************************************/#include <bits/stdc++.h>
using namespace std;#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = acos (-1.0);
ll dp[N];
int a[N], pre[N], sum[N], last[N], c[N];int main(void) {int n, q;while (scanf ("%d", &n) == 1) {if (!n) break;for (int i=1; i<=n; ++i) scanf ("%d", &a[i]);memset (c, 0, sizeof (c));memset (pre, 0, sizeof (pre));for (int i=1; i<=n; ++i) {c[i-pre[a[i]]]++;pre[a[i]] = i;}sum[n] = c[n];for (int i=n-1; i>=1; --i) {sum[i] = sum[i+1] + c[i];}memset (c, 0, sizeof (c));last[1] = 1; c[a[n]]++;for (int i=2; i<=n; ++i) { //lengthif (c[a[n-i+1]] == 0) {last[i] = last[i-1] + 1;c[a[n-i+1]] = 1;}else last[i] = last[i-1];}dp[1] = n;for (int i=2; i<=n; ++i) {dp[i] = dp[i-1] - last[i-1] + sum[i];}scanf ("%d", &q);while (q--) {int w; scanf ("%d", &w);printf ("%I64d\n", dp[w]);}}//cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";return 0;
}
SPFA/BFS H Friend Chains
题意：就是求任意两点的最短路的最大值
分析：Floyd O(n^3)绝对超时，我想了Dijkstra，O (V * (VlogE + V)，后来用了SPFA倒是勉勉强强过了，对Dijkstra无爱了。杭电discuss里有人写了最快的解法，类似于求树的直径，两边BFS。问题是第一次找最远的点可能有多个，要选择度数最小的，否则度数多了，从那个点出发到某些点并不是最远的，也就不是直径。
SPFA
#include <bits/stdc++.h>
using namespace std;const int N = 1e3 + 10;
const int E = 2e4 + 10;
const int INF = 0x3f3f3f3f;
struct Edge {int v, w, nex;Edge () {}Edge (int v, double w, int nex) : v (v), w (w), nex (nex) {}
}edge[E];
int head[N];
bool vis[N];
int d[N];
int n, m, e;void init(void) {memset (head, -1, sizeof (head));e = 0;
}
void add_edge(int u, int v, int w) {edge[e] = Edge (v, w, head[u]);head[u] = e++;
}void SPFA(int s) {for (int i=1; i<=n; ++i) {vis[i] = false; d[i] = INF;}vis[s] = true; d[s] = 0;queue<int> Q; Q.push (s);while (!Q.empty ()) {int u = Q.front (); Q.pop ();vis[u] = false;for (int i=head[u]; ~i; i=edge[i].nex) {int v = edge[i].v, w = edge[i].w;if (d[v] > d[u] + w) {d[v] = d[u] + w;if (!vis[v]) {vis[v] = true; Q.push (v);}}}}
}map<string, int> id;
char str1[11], str2[11];int main(void) {while (scanf ("%d", &n) == 1) {if (!n) break;id.clear ();for (int i=1; i<=n; ++i) {scanf ("%s", &str1);id[str1] = i;}init ();scanf ("%d", &m);for (int i=1; i<=m; ++i) {scanf ("%s%s", &str1, &str2);if (id[str1] == id[str2]) continue;add_edge (id[str1], id[str2], 1);add_edge (id[str2], id[str1], 1);}int ans = 0;for (int i=1; i<=n; ++i) {SPFA (i);for (int j=1; j<=n; ++j) {if (d[j] == INF) {ans = -1; break;}if (ans < d[j]) ans = d[j];}if (ans == -1) break;}printf ("%d\n", ans);}return 0;
}
BFS
/************************************************
* Author :Running_Time
* Created Time :2015/11/7 星期六 16:16:25
* File Name :H_2.cpp************************************************/#include <bits/stdc++.h>
using namespace std;#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e3 + 10;
const int E = 2e4 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = acos (-1.0);
struct Edge {int v, w, nex;Edge () {}Edge (int v, int w, int nex) : v (v), w (w), nex (nex) {}
}edge[E];
int head[N], d[N], deg[N];
bool vis[N];
int n, m, e;void init(void) {memset (head, -1, sizeof (head));memset (deg, 0, sizeof (deg));e = 0;
}
void add_edge(int u, int v, int w) {edge[e] = Edge (v, w, head[u]);head[u] = e++;
}int BFS(int s) {for (int i=1; i<=n; ++i) {d[i] = (i == s) ? 0 : INF;vis[i] = (i == s) ? true : false;}queue<int> Q; Q.push (s);int idx = 0, mx = 0;while (!Q.empty ()) {int u = Q.front (); Q.pop ();for (int i=head[u]; ~i; i=edge[i].nex) {int v = edge[i].v, w = edge[i].w;if (vis[v]) continue;if (d[v] > d[u] + w) {d[v] = d[u] + w;vis[v] = true; Q.push (v);}if (d[v] > mx || (d[v] == mx && deg[v] < deg[idx])) {mx = d[v]; idx = v;}}}return idx;
}
map<string, int> id;
char str1[11], str2[11];int main(void) {while (scanf ("%d", &n) == 1) {if (!n) break;id.clear ();for (int i=1; i<=n; ++i) {scanf ("%s", &str1);id[str1] = i;}init ();scanf ("%d", &m);for (int i=1; i<=m; ++i) {scanf ("%s%s", &str1, &str2);if (id[str1] == id[str2]) continue;add_edge (id[str1], id[str2], 1);add_edge (id[str2], id[str1], 1);deg[id[str1]]++; deg[id[str2]]++;}int ans = 0;int idx = BFS (1);ans = d[BFS (idx)];for (int i=1; i<=n; ++i) {if (d[i] == INF) {ans = -1; break;}}printf ("%d\n", ans);}return 0;
}
水 I The Power of Xiangqi
比赛前走了一盘象棋，竟然就碰到了关于象棋的题目。
状态压缩+枚举 J Scaring the Birds
题意：有几个点可以放稻草人，问最少放几个稻草人才能保护所以稻草
分析：没什么陷阱吧，主要看样例的R的范围有些纠结，放稻草人的点没有稻草的。只要状压枚举要放的数量和位置就可以了。
#include <bits/stdc++.h>
using namespace std;const int N = 55;
const int INF = 0x3f3f3f3f;
struct Point {int x, y, r, step;Point () {}Point (int x, int y, int step) : x (x), y (y), step (step) {}
}p[11];
int n, m;
int a[N][N];
bool vis[N][N];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};void map_init(void) {for (int i=1; i<=n; ++i) {for (int j=1; j<=n; ++j) a[i][j] = 0;}for (int i=0; i<m; ++i) {a[p[i].x][p[i].y] = 1;}
}bool judge(void) {for (int i=1; i<=n; ++i) {for (int j=1; j<=n; ++j) {if (!a[i][j]) return false;}}return true;
}bool check(int x, int y) {if (x < 1 || x > n || y < 1 || y > n || vis[x][y]) return false;else return true;
}void BFS(int u) {int R = p[u].r; vis[p[u].x][p[u].y] = true;queue<Point> Q; Q.push (Point (p[u].x, p[u].y, 0));while (!Q.empty ()) {Point r = Q.front (); Q.pop ();if (r.step > R) continue;a[r.x][r.y] = 1;for (int i=0; i<4; ++i) {int tx = r.x + dx[i], ty = r.y + dy[i];if (!check (tx, ty)) continue;vis[tx][ty] = true;Q.push (Point (tx, ty, r.step + 1));}}
}int main(void) {while (scanf ("%d", &n) == 1) {if (!n) break;scanf ("%d", &m);for (int i=0; i<m; ++i) {scanf ("%d%d", &p[i].x, &p[i].y);}for (int i=0; i<m; ++i) {scanf ("%d", &p[i].r);}int S = 1 << m;int ans = INF;for (int i=0; i<S; ++i) {int num = __builtin_popcount (i);map_init ();for (int j=0; j<m; ++j) {if (i & (1 << j)) {memset (vis, false, sizeof (vis));BFS (j);}}if (!judge ()) continue;ans = min (ans, num);}if (ans == INF) puts ("-1");else printf ("%d\n", ans);}return 0;
}
最小生成树 K Outlets
题意：求最小生成树，限制是p和q一定要有边连
分析：作为第二水的题目我竟然不会写，kruskal的方法前先将p和q连上边就行了，或者Prim在p到q的距离变为0(优先出队列)，然后再加回去。
Kruskal
#include <bits/stdc++.h>
using namespace std;const int N = 55;
const int E = N * N;
const double INF = 1e9;
struct Edge {int u, v;double w;Edge () {}Edge (int u, int v, double w) : u (u), v (v), w (w) {}bool operator < (const Edge &r) const {return w < r.w;}
}edge[E];
struct UF {int rt[N], rk[N];void init(void) {memset (rt, -1, sizeof (rt));memset (rk, 0, sizeof (rk));}int Find(int x) {return rt[x] == -1 ? x : rt[x] = Find (rt[x]);}void Union(int x, int y) {x = Find (x); y = Find (y);if (x == y) return ;if (rk[x] > rk[y]) {rt[y] = x; rk[x] += rk[y];}else {rt[x] = y; rk[y] += rk[x];}}
}uf;
int x[N], y[N];
int tot;double sqr(int x, int y) {return (double) (x * x + y * y);
}
double cal_dis(int i, int j) {return sqrt (sqr (x[i] - x[j], y[i] - y[j]));
}void add_edge(int u, int v, double w) {edge[tot++] = Edge (u, v, w);
}int p, q;int main(void) {int n;while (scanf ("%d", &n) == 1) {if (!n) break;scanf ("%d%d", &p, &q);if (p > q) swap (p, q);for (int i=1; i<=n; ++i) {scanf ("%d%d", &x[i], &y[i]);}uf.init (); tot = 0;double ans = cal_dis (p, q);uf.rt[p] = q;for (int i=1; i<=n; ++i) {for (int j=i+1; j<=n; ++j) {add_edge (i, j, cal_dis (i, j));}}sort (edge, edge+tot);for (int i=0; i<tot; ++i) {int u = edge[i].u, v = edge[i].v;double w = edge[i].w;u = uf.Find (u); v = uf.Find (v);if (u == v) continue;ans += w;uf.Union (u, v);}printf ("%.2f\n", ans);}return 0;
}
Prim
#include <bits/stdc++.h>
using namespace std;const int N = 55;
const int E = N * N;
const double INF = 1e9;
struct Edge {int v, nex;double w;Edge () {}Edge (int v, double w, int nex) : v (v), w (w), nex (nex) {}bool operator < (const Edge &r) const {return w > r.w;}
}edge[E];
int head[N];
bool vis[N];
double d[N];
int x[N], y[N];
int p, q, e;void init(void) {memset (head, -1, sizeof (head));e = 0;
}void add_edge(int u, int v, double w) {edge[e] = Edge (v, w, head[u]);head[u] = e++;
}double sqr(int x, int y) {return (double) (x * x + y * y);
}
double cal_dis(int i, int j) {return sqrt (sqr (x[i] - x[j], y[i] - y[j]));
}double Prim(int s) {memset (vis, false, sizeof (vis));for (int i=0; i<55; ++i) d[i] = INF;priority_queue<Edge> Q;double ret = 0;for (int i=head[s]; ~i; i=edge[i].nex) {int v = edge[i].v; double w = edge[i].w;if (d[v] > w) {d[v] = w;if (v == q) {ret += d[v];d[v] = 0;}Q.push (Edge (v, d[v], 0));}}vis[s] = true; d[s] = 0;while (!Q.empty ()) {int u = Q.top ().v; Q.pop ();if (vis[u]) continue;vis[u] = true; ret += d[u];for (int i=head[u]; ~i; i=edge[i].nex) {int v = edge[i].v; double w = edge[i].w;if (v == q) continue;if (!vis[v] && d[v] > w) {d[v] = w; Q.push (Edge (v, d[v], 0));}}}return ret;
}int main(void) {int n;while (scanf ("%d", &n) == 1) {if (!n) break;scanf ("%d%d", &p, &q);if (p > q) swap (p, q);for (int i=1; i<=n; ++i) {scanf ("%d%d", &x[i], &y[i]);}init ();for (int i=1; i<=n; ++i) {for (int j=i+1; j<=n; ++j) {add_edge (i, j, cal_dis (i, j));add_edge (j, i, cal_dis (i, j));}}printf ("%.2f\n", Prim (p));}return 0;
}