气泡图
两两判断关系，dfs。
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> double x[1005], y[1005], r[1005]; int f[1005][1005]; const double eps = 1e-10; #include<vector> using namespace std; vector<int> G[1005]; int p[1005], father[1005]; void dfs(int x, int fa) { father[x] = fa; for (int i = 0; i < G[x].size(); i++) { p[G[x][i]]--; } for (int i = 0; i < G[x].size(); i++) { int v = G[x][i]; if (p[v] == 0 && father[v]==0) { dfs(v, x); } } } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%lf%lf%lf", &x[i], &y[i], &r[i]); } memset(f, 0, sizeof(f)); memset(p, 0, sizeof(p)); memset(father, 0, sizeof(father)); for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { if (i != j) { double d = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])); if (r[i] - r[j] >= d) { f[i][j] = 1; G[i].push_back(j); f[j][i] = -1; p[j]++; } if (r[j] - r[i] >= d) { f[i][j] = -1; f[j][i] = 1; G[j].push_back(i); p[i]++; } } } } for (int i = 1; i <= n; i++) { if (p[i] == 0) { dfs(i, 0); break; } } for (int i = 1; i <= n; i++) { printf("%d ", father[i]); } return 0; }
候选人追踪
维护S集合中的最小值和其余候选人中的最大值
#include<stdio.h> #include<string.h> #include<stdlib.h> template <class T> class SegmentTree { public: T dat, lazy; int leftBorder, rightBorder, mid; SegmentTree * leftSon, * rightSon; T(* lazyfunc)(T, T); T(* mergefunc)(T, T); SegmentTree() { leftBorder = rightBorder = -1; leftSon = rightSon = NULL; } void pushdown(); void pushup(); void Build(T *, int, int, T(*)(T, T), T(*)(T, T)); void Modify(int, int, T); T Query(int, int); void Free(); }; template<class T> void SegmentTree<T>::pushdown() { if (lazy && leftBorder != rightBorder) { leftSon->dat = lazyfunc(leftSon->dat, lazy); rightSon->dat = lazyfunc(rightSon->dat, lazy); leftSon->lazy = lazyfunc(leftSon->lazy, lazy); rightSon->lazy = lazyfunc(rightSon->lazy, lazy); } lazy = (T)0; } template<class T> void SegmentTree<T>::pushup() { dat = mergefunc(leftSon->dat, rightSon->dat); } template<class T> void SegmentTree<T>::Build(T * S, int l, int r, T(* lfunc)(T, T), T(* mfunc)(T, T)) { if (l > r) { return; } lazy = (T)0; leftBorder = l; rightBorder = r; mid = (leftBorder + rightBorder) >> 1; lazyfunc = lfunc; mergefunc = mfunc; if (l == r) { dat = S[l]; return; } leftSon = new SegmentTree; leftSon->Build(S, l, mid, lfunc, mfunc); rightSon = new SegmentTree; rightSon->Build(S, mid + 1, r, lfunc, mfunc); pushup(); } template<class T> void SegmentTree<T>::Modify(int l, int r, T NewDat) { if (l > r || l < leftBorder || rightBorder < r) { return; } if (leftBorder == l && rightBorder == r) { dat = lazyfunc(dat, NewDat); lazy = lazyfunc(lazy, NewDat); return; } pushdown(); if (r <= mid) { leftSon->Modify(l, r, NewDat); } else if (mid < l) { rightSon->Modify(l, r, NewDat); } else { leftSon->Modify(l, mid, NewDat); rightSon->Modify(mid + 1, r, NewDat); } pushup(); } template<class T> T SegmentTree<T>::Query(int l, int r) { if (l > r || l < leftBorder || rightBorder < r) { return dat; } pushdown(); if (l == leftBorder && r == rightBorder) { return dat; } if (r <= mid) { return leftSon->Query(l, r); } else if (mid < l) { return rightSon->Query(l, r); } else { return mergefunc(leftSon->Query(l, mid), rightSon->Query(mid + 1, r)); } } template<class T> void SegmentTree<T>::Free() { if (leftSon != NULL) { leftSon->Free(); } if (rightSon != NULL) { rightSon->Free(); } delete leftSon; delete rightSon; } int lazyfunc(int a, int b) { return a + b; } int mergefunc(int a, int b) { return a > b ? b : a; } int n, k; bool f[320000]; class tick { public: int t, c; }; int cmp(const void *x, const void *y) { tick * tx = (tick *)x; tick * ty = (tick *)y; return tx->t > ty->t ? 1 : -1; } tick p[320000]; int index_____[320000], a[320000]; SegmentTree<int> st; int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif memset(a, 0, sizeof(a)); scanf("%d%d", &n, &k); for (int i = 0; i < n; i++) { scanf("%d%d", &p[i].t, &p[i].c); } memset(f, false, sizeof(f)); for (int i = 0; i < k; i++) { int s; scanf("%d", &s); f[s] = true; } int cnt = 0; for (int i = 0; i < 315159; i++) { if (f[i]) { index_____[i] = cnt++; } } qsort(p, n, sizeof(tick), cmp); int ptr = 0, ans = 0, max = 0, time = p[0].t, s = -1; st.Build(a, 0, k - 1, lazyfunc, mergefunc); while (ptr < n) { do { if (f[p[ptr].c]) { st.Modify(index_____[p[ptr].c], index_____[p[ptr].c], 1); } else { a[p[ptr].c]++; if (a[p[ptr].c] > max) { max = a[p[ptr].c]; } } ptr++; } while (p[ptr].t == p[ptr - 1].t && ptr < n); int q = st.Query(0, k - 1); if (s == 1) { ans += p[ptr - 1].t - time; } time = p[ptr - 1].t; if (q > max) { s = 1; } else { s = -1; } } printf("%d ", ans); return 0; }
墨水滴
bfs，优先扩展队列中颜色最深的点。
#include<stdio.h> #include<string.h> #include<stdlib.h> class ink { public: int x, y; }; int n, k; int a[1005][1005]; bool f[1005][1005]; const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; ink heap[2100000]; int len; void adjust_down(int p) { if (p * 2 <= len && a[heap[p].x][heap[p].y] < a[heap[p * 2].x][heap[p * 2].y]) { ink tmp = heap[p]; heap[p] = heap[p * 2]; heap[p * 2] = tmp; adjust_down(p * 2); } if (p * 2 + 1 <= len && a[heap[p].x][heap[p].y] < a[heap[p * 2 + 1].x][heap[p * 2 + 1].y]) { ink tmp = heap[p]; heap[p] = heap[p * 2 + 1]; heap[p * 2 + 1] = tmp; adjust_down(p * 2 + 1); } } void adjust_up(int p) { if (p <= 1) { return; } if (a[heap[p].x][heap[p].y] > a[heap[p / 2].x][heap[p / 2].y]) { ink tmp = heap[p]; heap[p] = heap[p / 2]; heap[p / 2] = tmp; adjust_up(p / 2); } } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif scanf("%d%d", &n, &k); memset(f, false, sizeof(f)); memset(a, 0, sizeof(a)); len = 0; for (int i = 0; i < k; i++) { ink t; int g; scanf("%d%d%d", &t.x, &t.y, &g); if (g > a[t.x][t.y]) { a[t.x][t.y] = g; if (!f[t.x][t.y]) { heap[++len] = t; adjust_up(len); f[t.x][t.y] = true; } } } while (len > 0) { ink head = heap[1]; heap[1] = heap[len]; len--; adjust_down(1); f[head.x][head.y] = false; for (int i = 0; i < 4; i++) { int x = head.x + dx[i], y = head.y + dy[i]; if (x < 0 || x >= n || y < 0 || y >= n) { continue; } if (a[x][y] < a[head.x][head.y] - 1) { a[x][y] = a[head.x][head.y] - 1; if (!f[x][y]) { f[x][y] = true; ink p; p.x = x, p.y = y; heap[++len] = p; adjust_up(len); } } } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { printf("%d ", a[i][j]); } printf(" "); } return 0; }
鱼形子图计数
先枚举A点，再从A点能到的点中枚举D点，计算AD都能到的点的数量tmp，则鱼身部分p1=tmp*(tmp-1)种构造；D点度数减3为鱼尾的可选集合，共p2=(d(D)-3)*(d(D)-4)/2种构造；则以A点为鱼头的子图个数为p1*p2。
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<vector> #include<algorithm> using namespace std; const long long M = 1000000007; vector<int> G[100005]; int n, m; long long common(int u, int v) { int iu = 0, iv = 0; long long ret = 0; while (iu < G[u].size() && iv < G[v].size()) { if (G[u][iu] == G[v][iv]) { iu++, iv++, ret++; } else if (G[u][iu] < G[v][iv]) { iu++; } else { iv++; } } return ret; } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif long long ans; while (scanf("%d%d", &n, &m) != EOF) { ans = 0; for (int i = 1; i <= n; i++) { G[i].clear(); } for (int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } for (int i = 1; i <= n; i++) { sort(G[i].begin(), G[i].end()); } int A, B, C, D, E, F; for (A = 1; A <= n; A++) { if (G[A].size() < 3) { continue; } for (int i = 0; i < G[A].size(); i++) { long long p1 = 0, p2 = 0, tmp; D = G[A][i]; if (G[D].size() < 5) { continue; } tmp = common(A, D); if (tmp >= 2) { p1 = tmp * (tmp - 1) / 2 % M; } tmp = G[D].size() - 3; if (tmp >= 2) { p2 = tmp * (tmp - 1) / 2 % M; } ans = (ans + p1 * p2) % M; } } printf("%lld ", ans); } return 0; }