公司网站设计与实现的英文文献,中国外协加工网最新订单,工业设计软件上市公司,万家灯火网站建设文章目录 前言试题 A: 子 2023作者思考题解答案 试题 B: 双子数作者思考题解 试题 C: 班级活动作者思考题解 试题 D: 合并数列作者思考题解 试题 E: 数三角作者思考题解 试题 F: 删边问题作者思考题解 试题 G: AB 路线作者思考题解 试题 H: 抓娃娃作者思考题解 试题 I: 拼数字试… 文章目录 前言试题 A: 子 2023作者思考题解答案 试题 B: 双子数作者思考题解 试题 C: 班级活动作者思考题解 试题 D: 合并数列作者思考题解 试题 E: 数三角作者思考题解 试题 F: 删边问题作者思考题解 试题 G: AB 路线作者思考题解 试题 H: 抓娃娃作者思考题解 试题 I: 拼数字试题 J: 逃跑 前言
第一次接触写国赛的题在下才疏学浅题解如有错误请指正。 A ~ H有题解其中E题作者打的暴力。 如果能帮助你的话点点赞吧谢谢
试题 A: 子 2023
本题总分5 分
【问题描述】 小蓝在黑板上连续写下从 1 到 2023 之间所有的整数得到了一个数字序列 S 12345678910111213 . . . 20222023。 小蓝想知道 S 中有多少种子序列恰好等于 2023 提示以下是 3 种满足条件的子序列用中括号标识出的数字是子序列包含的数字 1[2]34567891[0]111[2]1[3]14151617181920212223… 1[2]34567891[0]111[2]131415161718192021222[3]… 1[2]34567891[0]111213141516171819[2]021222[3]… 注意以下是不满足条件的子序列虽然包含了 2、0、2、3 四个数字但是顺序不对 1[2]345678910111[2]131415161718192[0]21222[3]…
【答案提交】 这是一道结果填空的题你只需要算出结果后提交即可。本题的结果为一个整数在提交答案时只填写这个整数填写多余的内容将无法得分
作者思考
作完省赛的就知道这不就是省赛E题的接龙数列嘛。简单的dp就可以。分别以2 0 2 3要转化因为有两个2结尾dp就可以了。 虽然正解是dp但是暴力 剪枝也可以做就是跑的有些慢。作者本地跑差不多50s。 还一个坑就是如果你不开long long就会得到错的答案1189693313
题解
#includebits/stdc.h
using namespace std;
#define int long long // 开long long string s; int f1() {int cnt 0;for (int a 0; a s.size(); a) {if (s[a] ! 2) continue;for (int b a 1; b s.size(); b) {if (s[b] ! 0) continue;for (int c b 1; c s.size(); c) {if (s[c] ! 2) continue;for (int d c 1; d s.size(); d) {if (s[d] ! 3) continue;cnt;}}}}return cnt;
}int f2() {int dp[4] {0}; // 分别代表2、20、202、2023的数量for (char ch : s) {if (ch 2) {dp[0];dp[2] dp[1];}if (ch 0) dp[1] dp[0];if (ch 3) dp[3] dp[2];}return dp[3];
}signed main(){for (int i 1; i 2023; i) { // 剪枝 string tmp to_string(i);for (char ch : tmp) {if (ch 2) s 2;if (ch 0) s 0;if (ch 3) s 3;}}
// cout f1() endl; // 暴力 cout f2() endl; // dpreturn 0;
}
答案
5484660609试题 B: 双子数
本题总分5 分
【问题描述】 若一个正整数 x 可以被表示为 p 2 ^2 2 × q 2 ^2 2其中 p、q 为质数且 p , q则 x 是一个 “双子数”。请计算区间 [2333, 23333333333333] 内有多少个 “双子数”
【答案提交】 这是一道结果填空的题你只需要算出结果后提交即可。本题的结果为一个整数在提交答案时只填写这个整数填写多余的内容将无法得分。
作者思考
首先第一眼看到质数那么直接就是质数筛嘛。筛多少质数呢看区间数量级是10 14 ^{14} 14 ,难道筛10 14 ^{14} 14 不用 p、q 的最大值 23333333333333 \sqrt{23333333333333} 23333333333333 ≈ \approx ≈ 4830459。 所以大约筛5 x 10 6 ^6 6就可以了。 还有一个坑 计算p 2 ^2 2 × q 2 ^2 2 时遍历到最大的p、q ,大约是10 24 ^{24} 24 ,那么数量级会爆long long。解决办法1、用int128 2、缩小数据范围开根号转化成 p x q 在范围 [ 2333 \sqrt{2333} 2333 , 23333333333333 \sqrt{23333333333333} 23333333333333 ] 这样就完美解决了
题解
#include bits/stdc.h
using namespace std;
#define int long long
const int maxl 1e7 7;int l 2333, r 23333333333333;
int ans;
vectorint prime;
int flag[maxl];void euler_prime(int n) {for (int i 2; i n; i) {if (!flag[i]) prime.push_back(i);for (int p : prime) {flag[p * i] 1;if (i % p 0 || p * i n) break;}}
}signed main () {euler_prime(5e6 7);for (int i 0; i prime.size(); i) {for (int j i 1; j prime.size(); j) {int x prime[i] * prime[j]; // 这里的x是题目中的x开根号if (x pow(l, 0.5)) continue; if (x pow(r, 0.5)) break; // 太大后面的数都不用看了都大于范围ans; }}cout ans endl;return 0;
}试题 C: 班级活动
时间限制: 1.0s 内存限制: 256.0MB 本题总分10 分
【问题描述】 小明的老师准备组织一次班级活动。班上一共有 n 名n 为偶数同学老师想把所有的同学进行分组每两名同学一组。为了公平老师给每名同学随机分配了一个 n 以内的正整数作为 id第 i 名同学的 id 为 a i _i i。 老师希望通过更改若干名同学的 id 使得对于任意一名同学 i有且仅有另一名同学 j 的 id 与其相同a i _i i a j _j j。请问老师最少需要更改多少名同学的 id
【输入格式】 输入共 2 行。 第一行为一个正整数 n。 第二行为 n 个由空格隔开的整数 a 1 _1 1, a 2 _2 2, …, a i _i i。
【输出格式】 输出共 1 行一个整数。
【样例输入】
4
1 2 2 3【样例输出】
1【样例说明】 仅需要把 a 1 _1 1 改为 a 3 _3 3 或者把 a 3 _3 3改为 a 1 _1 1 即可。
【评测用例规模与约定】 对于 20% 的数据保证 n ≤ 10 3 ^3 3。 对于 100% 的数据保证 n ≤ 10 5 ^5 5。
作者思考
这里看两组样例就能明白规律了
输入
1 2 2 2 2 2 3
输出
3这里很显然就是3个2要变成1, 3和一个其他数字。 输入
1 2 2 2 3 4
输出
2这里很显然就是1个2要变成1或者3 4剩下两个数字再合并。 结论 配对超过2个同学的数字总和设为cnt1 没有完成配对的同学的数字总和设为cnt2 当cnt1 cnt2时,输出cnt1 当cnt1 cnt2时输出cnt1 (cnt2 - cnt1) / 2 时间复杂度O(n) 题解
#include bits/stdc.h
using namespace std;
const int maxl 1e5 7;int n, cnt1, cnt2;
int a[maxl];
mapint,int mp;
bool flag[maxl];int main() {cin n;for (int i 1; i n; i) {cin a[i];mp[a[i]];}for (int i 1; i n; i) {if (!flag[a[i]]) {if (mp[a[i]] 1) cnt2;else if (mp[a[i]] 2) cnt1 (mp[a[i]] - 2);flag[a[i]] 1;} }if (cnt1 cnt2) cout cnt1 endl;else cout cnt1 (cnt2 - cnt1) / 2 endl;return 0;
}试题 D: 合并数列
时间限制: 1.0s 内存限制: 256.0MB 本题总分10 分
【问题描述】 小明发现有很多方案可以把一个很大的正整数拆成若干正整数的和。他采取了其中两种方案分别将他们列为两个数组 {a 1 _1 1, a 2 _2 2, …, a n _n n} 和 {b 1 _1 1, b 2 _2 2, …, b m _m m}。两个数组的和相同。
定义一次合并操作可以将某数组内相邻的两个数合并为一个新数新数的值是原来两个数的和。小明想通过若干次合并操作将两个数组变成一模一样即 n m 且对于任意下标 i 满足 a i _i i b i _i i。请计算至少需要多少次合并操作可以完成小明的目标。
【输入格式】 输入共 3 行。 第一行为两个正整数 n, m。 第二行为 n 个由空格隔开的整数 a 1 _1 1, a 2 _2 2, …, a n _n n。 第三行为 m 个由空格隔开的整数 b 1 _1 1, b 2 _2 2, …, b m _m m。
【输出格式】 输出共 1 行一个整数。
【样例输入】
4 3
1 2 3 4
1 5 4【样例输出】
1【样例说明】 只需要将 a 2 _2 2 和 a 3 _3 3 合并数组 a 变为 {1, 5, 4}即和 b 相同。
【评测用例规模与约定】 对于 20% 的数据保证 n, m ≤ 10 3 ^3 3。 对于 100% 的数据保证 n, m ≤ 10 5 ^5 50 a i _i i , b i _i i ≤ 10 5 ^5 5。
作者思考
作者个人觉得不会这道题的人大概率是没看到题目中的相邻的两个数 。这里我给的大家标出来了。 看到这就应该是迎刃而解了贪心就可以了。直接放代码了我觉得你一定看的懂的 时间复杂度O(n)
题解
#includebits/stdc.h
using namespace std;int n, m, ans;
int tp1, tp2;
queueint q1, q2;int main(){cin n m;for (int i 1, x; i n; i) cin x, q1.push(x);for (int i 1, x; i m; i) cin x, q2.push(x);while (!q1.empty()) {tp1 q1.front();tp2 q2.front();if (tp1 tp2) q1.pop(), q2.pop();else if (tp1 tp2) q1.pop(), q1.front() tp1, ans;else q2.pop(), q2.front() tp2, ans;}cout ans endl;return 0;
}试题 E: 数三角
时间限制: 1.0s 内存限制: 256.0MB 本题总分15 分
【问题描述】 小明在二维坐标系中放置了 n 个点他想在其中选出一个包含三个点的子集这三个点能组成三角形。然而这样的方案太多了他决定只选择那些可以组成等腰三角形的方案。请帮他计算出一共有多少种选法可以组成等腰三角形
【输入格式】 输入共 n 1 行。 第一行为一个正整数 n。 后面 n 行每行两个整数 x i _i i, y i _i i 表示第 i 个点的坐标。
【输出格式】 输出共 1 行一个整数。
【样例输入】
5
1 4
1 0
2 1
1 2
0 1【样例输出】
5【样例说明】 一共有 4 种选法{2, 3, 4}、{3, 4, 5}、{4, 5, 2}、{5, 2, 3}、{1, 3, 5}。
【评测用例规模与约定】 对于 20% 的数据保证 n ≤ 200。 对于 100% 的数据保证 n ≤ 20000 ≤ x i _i i, y i _i i ≤ 10 9 ^9 9。
作者思考
作者思考不了了作者不会 直接打暴力了。 时间复杂度O(n 3 ^3 3)
题解
#includebits/stdc.h
using namespace std;
const int maxl 1e6 7;
struct point {int x;int y;
};int n, ans;
point p[maxl];double dis(int a, int b) {return sqrt((p[a].x - p[b].x) * (p[a].x - p[b].x) (p[a].y - p[b].y) * (p[a].y - p[b].y)) * 1.00;
}signed main(){cin n;for (int i 1; i n; i) cin p[i].x p[i].y;// 遍历所有点并且要避免重复 for (int i 1; i n; i) {for (int j 1; j i; j) {for (int k 1; k j; k) {double a dis(i, j);double b dis(i, k);double c dis(j, k);if (a b c a c b b c a)if ((a b) || (a c) || (b c)) ans;}}}cout ans endl;return 0;
}试题 F: 删边问题
时间限制: 1.0s 内存限制: 256.0MB 本题总分15 分
【问题描述】 给定一个包含 N 个结点 M 条边的无向图 G结点编号 1 . . . N。其中每个 结点都有一个点权 W i _i i。 你可以从 M 条边中任选恰好一条边删除如果剩下的图恰好包含 2 个连通 分量就称这是一种合法的删除方案。 对于一种合法的删除方案我们假设 2 个连通分量包含的点的权值之和分 别为 X 和 Y请你找出一种使得 X 与 Y 的差值最小的方案。输出 X 与 Y 的差 值。
【输入格式】 第一行包含两个整数 N 和 M。 第二行包含 N 个整数W 1 _1 1, W 2 _2 2. . . . W N _N N。 以下 M 行每行包含 2 个整数 U 和 V代表结点 U 和 V 之间有一条边。
【输出格式】 一个整数代表最小的差值。如果不存在合法的删除方案输出 −1。
【样例输入】
4 4
10 20 30 40
1 2
2 1
2 3
4 3【样例输出】
20【样例说明】 由于 1 和 2 之间实际有 2 条边所以合法的删除方案有 2 种分别是删除(2, 3) 之间的边和删除 (3, 4) 之间的边。 删除 (2, 3) 之间的边剩下的图包含 2 个连通分量{1, 2} 和 {3, 4}点权和分别是 30、70差为 40。 删除 (3, 4) 之间的边剩下的图包含 2 个连通分量{1, 2, 3} 和 {4}点权和分别是 60、40差为 20。
【评测用例规模与约定】 对于 20% 的数据1 ≤ N, M ≤ 10000。 对于另外 20% 的数据每个结点的度数不超过 2。 对于 100% 的数据1 ≤ N, M ≤ 2000000 ≤ W i _i i ≤ 1091 ≤ U, V ≤ N。
作者思考
这个15分是真不好拿呀真比后面两道20分的题还难真无语 考察知识点Tarjan 算法 缩点、Tarjan 算法 求割边、拓扑序 暴力点的解法就是求完割边遍历每个割边求差值。时间复杂度是O(M(u v)) ≈ O(n 3 ^3 3)超时 优化把他当有向图然后进行缩点缩点后会出现拓扑序根据拓扑序求节点值和。差值所有节点值之和 - 2 * 其中一半连通节点和
题解
#includebits/stdc.h
using namespace std;
const int MaxN 0x3f3f3f3f;
const int maxl 1e6 7;
struct edge{int u;int v;bool operator (edge b) const { // map 需要给出排序规则 if (u ! b.u) return u b.u;else return v b.v;}
};int n, m, W, w[maxl], ans MaxN;
/*
W ——所以节点值总和
w ——每个节点值
ans ——最小差值
*/// 无向图求割边
vectorint G1[maxl];
vectoredge e; // 求割边
mapedge, int mp1; // 记录边数标记掉重边又可能是割边的边
int cnt1 1;
int dfn1[maxl], low1[maxl];
int flag1[maxl];// 有向图缩点建新图。目的利用新图拓扑序求节点值 和
vectorint G2[maxl], nG[maxl]; // G2 ——有向图缩点nG ——缩点后的新图
mapedge, int mp2; // 新图建立会有重边
int tp;
stackint st;
int cnt2 1, sc;
int scc[maxl];
int flag2[maxl];
int dfn2[maxl], low2[maxl];
int nw[maxl], dp[maxl]; // nw ——缩点后的新权值dp ——后i个点的权值和 void targan_bridge(int u, int fa) { // 求割边 dfn1[u] low1[u] cnt1;for (int v : G1[u]) {if (!dfn1[v]) {targan_bridge(v, u);low1[u] min(low1[u], low1[v]);if (low1[v] dfn1[u]) e.push_back({min(u, v), max(u, v)});} else if (dfn1[v] dfn1[u v ! fa]) low1[u] min(low1[u], dfn1[v]);}
}void targan_point(int u) { // 缩点 st.push(u);flag2[u] 1;dfn2[u] low2[u] cnt2;for (int v : G2[u]) {if (!dfn2[v]) {targan_point(v);low2[u] min(low2[u], low2[v]);} else if (flag2[v]) low2[u] min(low2[u], dfn2[v]);}if (low2[u] dfn2[u]) {sc;do {tp st.top();st.pop();scc[tp] sc;flag2[tp] 0;}while (tp ! u);}
}signed main() {cin n m;for (int i 1; i n; i) {cin w[i];W w[i]; }for (int i 1, u, v; i m; i) {cin u v;G1[u].push_back(v);G1[v].push_back(u);mp1[{min(u, v), max(u, v)}];G2[u].push_back(v);}int d 0; // 判断给的图是否是个连通图for (int i 1; i n; i) {if (!dfn1[i]) {targan_bridge(i, i);d;}if (!dfn2[i]) targan_point(i);} if (d 1 || !e.size()) { // 不是连通图 或者 没有割边直接返回 cout -1 endl;return 0;}// 缩点建新图for (int u 1; u n; u) {nw[scc[u]] w[u];for (int v : G2[u]) {if (scc[v] ! scc[u] !mp2[{min(u, v), max(u, v)}]) {nG[scc[u]].push_back(scc[v]);mp2[{min(u, v), max(u, v)}]; }}} // 根据拓扑序求节点权值和 for (int u sc; u; u--) {dp[u] nw[u];for (int v : nG[u]) dp[v] dp[u];}for (edge birdge : e) {if (mp1[birdge] 1) continue; // 重边不用更新 ans的值int p max(scc[birdge.u], scc[birdge.v]); // 割边中序号较大的点int t dp[p];ans min(ans, abs(W - t - t)); // 计算差值 }cout ans endl; return 0;
}试题 G: AB 路线
时间限制: 1.0s 内存限制: 256.0MB 本题总分20 分
【问题描述】 有一个由 N × M 个方格组成的迷宫每个方格写有一个字母 A 或者 B。小蓝站在迷宫左上角的方格目标是走到右下角的方格。他每一步可以移动到上下左右相邻的方格去。 由于特殊的原因小蓝的路线必须先走 K 个 A 格子、再走 K 个 B 格子、再走 K 个 A 格子、再走 K 个 B 格子……如此反复交替。 请你计算小蓝最少需要走多少步才能到达右下角方格 注意路线经过的格子数不必一定是 K 的倍数即最后一段 A 或 B 的格子可以不满 K 个。起点保证是 A 格子。
例如 K 3 时以下 3 种路线是合法的 AA AAAB AAABBBAAABBB 以下 3 种路线不合法 ABABAB ABBBAAABBB AAABBBBBBAAA
【输入格式】 第一行包含三个整数 N、M 和 K。 以下 N 行每行包含 M 个字符A 或 B代表格子类型。
【输出格式】 一个整数代表最少步数。如果无法到达右下角输出 −1。
【样例输入】
4 4 2
AAAB
ABAB
BBAB
BAAA【样例输出】
8【样例说明】 每一步方向如下下右下右上右下下路线序列AABBAABBA。
【评测用例规模与约定】 对于 20% 的数据1 ≤ N, M ≤ 4。 对于另 20% 的数据K 1。 对于 100% 的数据1 ≤ N, M ≤ 10001 ≤ K ≤ 10。
作者思考
这题其实不难就是走迷宫加强版。让在下给您分析一下。 最短路 两种方法
bfs、堆优化步数最小dp[i][j] —— 当前步最小 附加条件 AB交错走且A先走每次走k步最后一步可以走少于k不 这个很好实现嘛比如bfs中节点结构体中加一个flag代表是谁走cnt代表现在走了多少步d代表方向。就直接可以实现了。 这里给出比较巧妙的解决办法不用设这么多变量。利用步数直接看代码吧不难的就是很巧妙。 思路有很多我就给出我的吧
题解
#includebits/stdc.h
using namespace std;
const int MaxN 0x3f3f3f3f;
const int maxl 1e3 7;
struct node {int x, y;int step;
};
int dx[] {0, 1, -1, 0, 0};
int dy[] {0, 0, 0, 1, -1};int n, m, k;
char mp[maxl][maxl];
int dp[maxl][maxl];
node tp;
queuenode q;int main(){memset(dp, 0x3f, sizeof(dp)); // 赋最大值cin n m k;for (int i 1; i n; i) {for (int j 1; j m; j) {cin mp[i][j];}} if (mp[1][1] ! A) {cout -1 endl;return 0;}dp[1][1] 0;q.push({1, 1, 0});while (!q.empty()) {tp q.front();q.pop();int x tp.x;int y tp.y;int step tp.step;for (int i 1; i 4; i) {int nx x dx[i];int ny y dy[i];int nstep (step 1) % (2 * k);if (nx 1 || ny 1 || nx n || ny m) continue;if (mp[nx][ny] A nstep k) continue;if (mp[nx][ny] B nstep k) continue;if (dp[nx][ny] dp[x][y] 1) {dp[nx][ny] dp[x][y] 1;q.push({nx, ny, nstep});}}}if (dp[n][m] MaxN) cout -1 endl;else cout dp[n][m] endl;return 0;
}试题 H: 抓娃娃
时间限制: 1.0s 内存限制: 256.0MB 本题总分20 分
【问题描述】 小明拿了 n 条线段练习抓娃娃。他将所有线段铺在数轴上第 i 条线段的左端点在 l i _i i右端点在 r i _i i。小明用 m 个区间去框这些线段第 i 个区间的范围是 [L i _i i, R i _i i]。如果一个线段有 至少一半 的长度被包含在某个区间内则将其视为被这个区间框住。请计算出每个区间框住了多少个线段
【输入格式】 输入共 n m 1 行。 第一行为两个正整数 n, m。 后面 n 行每行两个整数 l i _i i,r i _i i。 后面 m 行每行两个整数 L i _i i, R i _i i。
【输出格式】 输出共 m 行每行一个整数。
【样例输入】
3 2
1 2
1 3
3 4
1 4
2 3【样例输出】
3
2【评测用例规模与约定】 对于 20% 的数据保证 n, m ≤ 10 3 ^3 3。 对于 100% 的数据保证 n, m ≤ 10 5 ^5 5l i _i i r i _i i0 l i _i i,r i _i i, L i _i i, R i _i i ≤ 10 6 ^6 6max{r i _i i − l i _i i} ≤ min{R i _i i − L i _i i}
作者思考
我只能说这道题是真的简单。而且是20分啊为啥不放到最前面10分啊真服了 不就是最基础的前缀和与差分嘛 抓住以下几个点
框住区间中间就算抓住会有精度问题。乘2防止
题解
#includebits/stdc.h
using namespace std;
const int maxl 2e6 7;int n, m;
int sum[maxl]; int main(){cin n m;for (int i 1, l, r; i n; i) {cin l r;sum[l r];}for (int i 1; i maxl; i) sum[i] sum[i - 1];for (int i 1, l, r; i m; i) {cin l r;l * 2;r * 2;cout sum[r] - sum[l - 1] endl;}return 0;
}后面两道题作者能力有限不会。如果你们能会的话。记得留言告诉我。在下把题目放在这里了。 试题 I: 拼数字
时间限制: 1.0s 内存限制: 256.0MB 本题总分25 分
【问题描述】 小蓝要用 N 个数字 2 和 M 个数字 3 拼出一个 N M 位的整数。请你计算 小蓝能拼出的最大的 2023 的倍数是多少
【输入格式】 两个整数 N 和 M。
【输出格式】 一个 N M 位的整数代表答案。如果拼不出 2023 的倍数输出 −1。
【样例输入】
2 8【样例输出】
2233333333【评测用例规模与约定】 对于 20% 的数据1 ≤ N, M ≤ 12。 对于 40% 的数据1 ≤ N, M ≤ 100。 对于 60% 的数据1 ≤ N, M ≤ 10000。 对于 100% 的数据1 ≤ N, M ≤ 1000000。
试题 J: 逃跑
时间限制: 1.0s 内存限制: 256.0MB 本题总分25 分
【问题描述】 小明所在星系有 n 颗星球编号为 1 到 n。这些星球通过 n − 1 条无向边连成一棵树。根结点为编号为 1 的星球。 为了在星际战争到来时逃到其他星系小明在根结点设置了逃离用的传送门。每个星球的人只需要一直往父结点星球移动就可以抵达根结点。为了方便各个星球的人去往根结点小明将其中 m 个星球设置为了跳板星球。在从某个星球去往根结点的路径上当一个人经过任意星球包括起点星球时他可以尝试直接跳跃到 其前往根结点路径上的除当前星球以外的第一个跳板星球其时间花费和走到父结点星球的时间花费相同都是 1 单位时间。 然而因为技术问题向跳板星球的跳跃并不一定成功每一次跳跃都有p 的概率失败并转而跳跃到当前星球的父结点星球相当于直接走到父结点星球同时此跳板星球失效将 不再视为跳板星球。 为了衡量移动效率小明想知道如果一个人在这 n 颗星球中随机选择一颗出发前往根结点其花费的最短时间的期望是多少单位时间
【输入格式】 输入共 n 1 行第一行为两个正整数 n、m 和一个浮点数 p。 后面 n − 1 行每行两个正整数 xi , y i _i i 表示第 i 条边的两个端点。 最后一行共 m 个正整数表示所有跳板星球的编号。
【输出格式】 一行一个浮点数表示答案请保留两位小数。
【样例输入】
4 1 0.2
1 2
2 3
3 4
2【样例输出】
1.30【样例说明】 从 1 号星球出发的时间花费为 0 从 2 号星球出发的时间花费为 1 从 3 号星球出发的时间花费为 2 从 4 号星球出发的时间花费为 0.8 × 2 0.2 × 3 2.2。 所以期望时间为 (0122.2)/4 1.3。
【评测用例规模与约定】 对于 30% 的数据保证 1 ≤ n ≤ 2000。 对于 100% 的数据保证 1 ≤ n ≤ 10 6 ^6 6 1 ≤ m ≤ n0 p 1。
