2023大厂真题提交网址(含题解):

www.CodeFun2000.com（http://101.43.147.120/）

最近我们一直在将收集到的机试真题制作数据并搬运到自己的OJ上，供大家免费练习,体会真题难度。现在OJ已录入50+道2023年最新大厂真题，同时在不断的更新。同时，可以关注"塔子哥学算法"公众号获得每道题的题解。
在这里插入图片描述

题目1:[HNOI2013]游走

题目大意

给你一张无向连通图,从第 $1$ 点随机游走到 $n$ 点。花费为经过的边的编号的和.问你如何安排边的编号使得期望花费最小化.

$\leq 500,m \leq n^2$

题目思路:

很容易想到，求出每条边期望经过次数，然后贪心安放即可.

但是 $m$ 太大，无法求解.考虑先求每个点期望经过次数.

考虑到 $n$ 点就停止了，所以不考虑 $n$ 的贡献。
显然有转移:
$f_1=1+\sum_{(1,j)\in E}^{}\frac{f_j}{du_j}$
$f_n=0$
$f_i=\sum_{(i,j)\in E}^{}\frac{f_j}{du_j}, \ i \in [2,n)$

对于一条边 $(i, j)$ ,它期望经过的次数是:

$g_{i,j}=\frac{f_i}{du_i} + \frac{f_j}{du_j}$

所以跑高斯消元后，对边排序计算即可。

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
const int maxn = 505;
const double eps = 1e-8;
vector<int> e[maxn];
int du[maxn];
double a[maxn][maxn];
double res[maxn] , ans[maxn * maxn];
int main()
{ios::sync_with_stdio(false);int n , m; cin >> n >> m;for (int i = 1 ; i <= m ; i++){int x , y; cin >> x >> y;e[x].pb(y);e[y].pb(x);du[x]++;du[y]++;}for (int i = 1 ; i <= n ; i++) a[i][i] = 1;for (int i = 1 ; i < n ; i++){for (auto v : e[i]){a[i][v] = -1.0 / du[v];}}a[1][n + 1] = 1;// guess消元int r , c;for (r = c = 1 ; r <= n && c <= n ; r++ , c++){int p = r;for (int j = r + 1 ; j <= n ; j++){if (a[p][c] < a[j][c]){p = j;break;}}// 不会有自由元swap(a[p] , a[r]);for (int j = 1 ; j <= n ; j++){if (j == r) continue;if (fabs(a[r][c]) < eps) continue;double d = a[j][c] / a[r][c];for (int k = c ; k <= n + 1 ; k++)a[j][k] -= d * a[r][k];}}for (int i = 1 ; i <= n ; i++) res[i] = a[i][n + 1] / a[i][i];int cnt = 0;for (int i = 1 ; i <= n ; i++){for (auto v : e[i]){if (v < i) continue;ans[++cnt] = res[i] / du[i] + res[v] / du[v];}}sort(ans + 1 , ans + 1 + cnt);double gg = 0;// cout << "cnt = " << cnt << endl;for (int i = 1 ; i <= cnt ; i++){gg += (cnt - i + 1.0) * ans[i];}cout << fixed << setprecision(3);cout << gg << endl;return 0;
}