「2019纪中集训Day10」解题报告

阳光穿透心脏的1/2处 2021-10-19 03:44 280阅读 0赞

# T1、数学题 #

给出两个向量 \\(\\vec \{a\}，\\vec \{b\}\\)。求出一组整数 x, y，使得 \\(|x \\vec a + y \\vec b|\\) 最小，输出 \\(|x \\vec a + y \\vec b|^2\\) 的最小值。

## \\(Sol\\)： ##

一道论文题。  
[金斌《欧几里得算法的应用][Link 1]  
时间复杂度 \\(O(很快)\\)。

## \\(Source\\)： ##

#include <cstdio> #include <cstring> #include <algorithm> void exgcd(long long x_1, long long y_1, long long x_2, long long y_2, long long &a, long long &b) { long long dp = x_1 * x_2 + y_1 * y_2, mod_a = x_1 * x_1 + y_1 * y_1, mod_b = x_2 * x_2 + y_2 * y_2; if (dp < 0) { exgcd(-x_1, -y_1, x_2, y_2, a, b); a = -a; return ; } if (4 * dp * dp <= mod_a * mod_b || dp == 0) { if (mod_a < mod_b) a = 1, b = 0; else b = 1, a = 0; return ; } bool flag = 0; if (mod_a > mod_b) { std::swap(x_1, x_2); std::swap(y_1, y_2); std::swap(mod_a, mod_b); flag = 1; } long long k = dp / mod_a; if (dp - k * mod_a > (k + 1) * mod_a - dp || !k) ++k; exgcd(x_1, y_1, x_2 - k * x_1, y_2 - k * y_1, a, b); a -= k * b; if (flag) std::swap(a, b); } int main() { //freopen("in", "r", stdin); freopen("math.in", "r", stdin); freopen("math.out", "w", stdout); long long x_1, y_1, x_2, y_2, a, b; while (~scanf("%lld %lld %lld %lld", &x_1, &y_1, &x_2, &y_2)) { a = b = 0; exgcd(x_1, y_1, x_2, y_2, a, b); printf("%lld\n", (a * x_1 + b * x_2) * (a * x_1 + b * x_2) + (a * y_1 + b * y_2) * (a * y_1 + b * y_2)); } return 0; }

# T2、挖宝藏 #

给出一个 \\(h \\times n \\times m \\ (1 \\leq h, n, m \\leq 10)\\) 的立方体，每层有 \\(k\_i\\) 个宝藏，到达宝藏所在位置可以获得该宝藏。移动到一个格子里要花费 \\(a\_\{i, j, k\}\\) 的代价，移动到一个格子后该格子代价变为 \\(0\\)，只能在同一层移动或到下一层。初始时在地面 (在地面移动没有代价)，要获得所有宝藏，求最小代价。

## \\(Sol\\)： ##

记 \\(f\_\{i, j, st\}\\) 表示挖到 \\((i, j)\\)，包含宝藏状态为 \\(st\\) 的最小值。  
求最小斯坦纳树，层之间转移时多加一个在 \\((i,j)\\) 的宝藏，代价加上上一层的 \\(f\_\{i,j,u\}\\) 即可，\\(u\\) 表示全集。  
时间复杂度 \\(O(h \\ 3^k (nm + G(nm)))\\)，其中 \\(G(nm)\\) 表示最短路的复杂度。

## \\(Source\\)： ##

#include <cstdio> #include <cstring> #include <algorithm> #include <queue> int in() { int x = 0; char c = getchar(); bool f = 0; while (c < '0' || c > '9') f |= c == '-', c = getchar(); while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); return f ? -x : x; } template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __; } template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __; } const int N = 11, inf = 0x3f3f3f3f; int h, n, m, a[N][N][N], f[N][N][(1 << N) + 1], res; typedef std::pair<int, int> pii; std::vector<pii> s[N]; bool vis[N][N]; struct node { int x, y; } ; int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; std::queue<node> q; int main() { //freopen("in", "r", stdin); freopen("treasure.in", "r", stdin); freopen("treasure.out", "w", stdout); h = in(), n = in(), m = in(); for (int i = 1; i <= h; ++i) for (int j = 1; j <= n; ++j) for (int k = 1; k <= m; ++k) a[i][j][k] = in(); for (int i = 1; i <= h; ++i) for (int k = in(), x, y; k; k--) { x = in(), y = in(); s[i].push_back(pii(x, y)); } for (int now = 1; now <= h; ++now) { for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) { f[i][j][1] = f[i][j][(1 << (s[now - 1].size() + 1)) - 1] + a[now][i][j]; for (int st = 2; st < (1 << (s[now].size() + 1)); ++st) f[i][j][st] = inf; } for (unsigned i = 0; i < s[now].size(); ++i) { f[s[now][i].first][s[now][i].second][1 << (i + 1)] = a[now][s[now][i].first][s[now][i].second]; } for (int st = 1; st < (1 << (s[now].size() + 1)); ++st) { for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) { for (int s1 = (st - 1) & st; s1; s1 = (s1 - 1) & st) chk_min(f[i][j][st], f[i][j][s1] + f[i][j][st ^ s1] - a[now][i][j]); if (f[i][j][st] < inf) q.push((node){i, j}), vis[i][j] = 1; } while (!q.empty()) { node u = q.front(); q.pop(); vis[u.x][u.y] = 0; for (int i = 0; i < 4; ++i) { node v = u; v.x += dx[i], v.y += dy[i]; if (v.x < 0 || v.x > n || v.y < 0 || v.y > m) continue; if (f[u.x][u.y][st] + a[now][v.x][v.y] < f[v.x][v.y][st]) f[v.x][v.y][st] = f[u.x][u.y][st] + a[now][v.x][v.y], q.push(v), vis[v.x][v.y] = 1; } } } } res = inf; for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) chk_min(res, f[i][j][(1 << (s[h].size() + 1)) - 1]); printf("%d\n", res); return 0; }

# T3、理想城市 #

给出无限网格上的一些黑色格子 (其余为白色格子)，保证黑色格子四连通，白色格子四连通。求无序不同黑色格子点对之间的最短路径格子数之和 (路径为四连通的黑格子)。

## \\(Sol\\)： ##

一棵树上所有简单路径的边数之和 \\(\\sum\_\{(u,v) \\in E\} size\_u \\times size\_v\\) (即计算每条边的贡献)。  
本题中保证同色格子四连通，考虑转化成树上问题，把相邻格子之间看成一条边。  
将一行中连续的格子压成一个点，与上一行或下一行中与它左右区间交集不为空的点连边。  
列与行同样处理，由于白色格子四连通，这样处理后的图不会有环，所以按树上处理。

时间复杂度 \\(O(n \\log\_2 n + n)\\)。

## \\(Source\\)： ##

//#pragma GCC optimize(2) #include <cstdio> #include <cstring> #include <algorithm> #include <queue> int in() { int x = 0; char c = getchar(); bool f = 0; while (c < '0' || c > '9') f |= c == '-', c = getchar(); while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); return f ? -x : x; } template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __; } template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __; } const int N = 1e5 + 5, mod = 1e9; int n, res; struct node { int x, y; } a[N], b[N]; inline bool cmpx(const node &i, const node &j) { return i.x == j.x ? i.y < j.y : i.x < j.x; } inline bool cmpy(const node &i, const node &j) { return i.y == j.y ? i.x < j.x : i.y < j.y; } struct edge { int next, to; } e[N]; int ecnt, head[N], siz[N], node_tot; inline void jb(const int u, const int v) { e[++ecnt] = (edge){head[u], v}, head[u] = ecnt; e[++ecnt] = (edge){head[v], u}, head[v] = ecnt; } void dfs(const int u, const int fa) { siz[u] = b[u].y - b[u].x + 1; for (int i = head[u]; i; i = e[i].next) { int v = e[i].to; if (v == fa) continue; dfs(v, u); siz[u] += siz[v]; res += 1ll * siz[v] * (n - siz[v]) % mod; if (res >= mod) res -= mod; } } int main() { //freopen("in", "r", stdin); freopen("city.in", "r", stdin); freopen("city.out", "w", stdout); n = in(); for (int i = 1; i <= n; ++i) a[i] = (node){in(), in()}; ecnt = 1, node_tot = 0; std::sort(a + 1, a + 1 + n, cmpx); for (int i = 1, j = 1, p = 0, t = 1; i <= n; i = ++j) { while (a[j + 1].x == a[j].x && a[j + 1].y == a[j].y + 1) ++j; b[++node_tot] = (node){a[i].y, a[j].y}; if (p) { for (; p < t && b[p].y < b[node_tot].x; ++p); for (; p < t && b[p].y <= b[node_tot].y; ++p) jb (p, node_tot); if (p < t && b[p].x <= b[node_tot].y) jb (p, node_tot); } if (a[j + 1].x != a[j].x) p = t, t = node_tot + 1; } dfs(1, -1); ecnt = 1, node_tot = 0; memset(head, 0, sizeof(head)); std::sort(a + 1, a + 1 + n, cmpy); for (int i = 1, j = 1, p = 0, t = 1; i <= n; i = ++j) { while (a[j + 1].y == a[j].y && a[j + 1].x == a[j].x + 1) ++j; b[++node_tot] = (node){a[i].x, a[j].x}; if (p) { for (; p < t && b[p].y < b[node_tot].x; ++p); for (; p < t && b[p].y <= b[node_tot].y; ++p) jb (p, node_tot); if (p < t && b[p].x <= b[node_tot].y) jb (p, node_tot); } if (a[j + 1].y != a[j].y) p = t, t = node_tot + 1; } dfs(1, -1); printf("%d\n", res); return 0; }

转载于:https://www.cnblogs.com/15owzLy1-yiylcy/p/11334079.html

[Link 1]: https://wenku.baidu.com/view/d5e0e018964bcf84b9d57ba8.html