北航2018级算法期末上机部分题解

北航2018级算法期末第二次上机考试部分题解

• C题 三角形
• • 题目描述
  • 数据大小
  • 输入
  • 输出
  • 解题思路
  • 题解代码
• D 魔术
• • 题目描述
  • 数据描述
  • 输入
  • 输出
  • 解题思路
  • 题解代码
• E 乘法
• • 题目描述
  • 输入
  • 输出
  • 解题思路
  • 题解代码
• F 图
• • 题目描述
  • 数据描述
  • 输出格式
  • 输入
  • 输出
  • 解题思路
  • 题解代码

C题 三角形

题目描述

给定 根木棍的长度，然后有 个询问，每一次询问给定 , 表示询问从第 根木棍到第 根木棍中是否存在可以组成三角形的木棍。如果存在输出 ，否则输出 。

数据大小

多组输入

每组数据第一行两个正整数 。

第二行包含 个正整数 , 表示第 个木棍的长度。

接下来 行。每行包含两个正整数 和 表示查询 区间内是否存在能够组成三角形的三条木棍。

输入

输出

解题思路

我们首先思考什么情况是可以构成三角形的。任取三根长度已知的木棍，长度分别为：, , ，那么如果可以构成三角形，这三个长度应该满足：

即应该满足，反之，就不存在三角形。

通过上面的分析，我们可以很自然地想到通过暴力枚举的方式来对一个区间里的每种木棍组成方式进行测验。但是 的取值很大，如果使用三层循环的暴力枚举就会 TLE。这样我们接着想到去降低暴力枚举的区间长度，来降低运行时间。

为了减小搜索区间，我们再次回到三角形组成的条件：。

从而我们可以得到三根木棍不可以组成三角形的条件：

那么我们思考，如果在长度为 的查询序列中没有可以生成三角形的木棍组合，那么将这 个数从小到大排序后也依旧无法组成三角形。那么此时我们可以得到：。

此我们可以联想到斐波那契数列，如果考虑最小增长情况 ，那么 就会持续增长，当 等于 50 的时候， 就会超过 , 就不符合题目的输入要求了。

通过上面的分析我们可以发现：当检查区间的长度大于等于 50 时，就可以直接认定存在了可以生成三角形的木棍。而剩下的情况我们就可以用暴力枚举的方式来进行检查。

代码如下

题解代码

D 魔术

题目描述

魔术师的桌子上有 个杯子排成一行，编 为，其中某些杯子底下藏有一个小球，如果你准确地猜出是哪些杯子，你就可以获得奖品。花费元，魔术师就会告诉你杯子底下藏有球的总数的奇偶性。

采取最优的询问策略，你至少需要花费多少元，才能保证猜出哪些杯子底下藏着球/p>

数据描述

第一行一个整数。

第行有个整数，表示每一种询问所需的花费。其中（对区间[i,j]进行询问的费用，）为第行第个数。

输入

输出

解题思路

知道了第 个杯子的奇偶性，就相当于知道了 和 之间的缝到 和
之间的缝的奇偶性，知道了缝 到缝 的奇偶性和缝 到缝 的奇偶性，我们就知道了缝 到缝 的奇偶性。

所以如果我们要知道所有杯子底下有没有球，我们就要知道每个杯子左右两端的缝之间的奇偶性，也就相当于要知道任意两个缝之间的奇偶性。

所以我们利用 个空隙来代表是否知道了一个区间，对于每一个， 我们在 和 之间建立一条权值为 的无向边，然后利用Prim算法来跑一遍最小生成树，最后输出最小生成树的权值就是最后的答案。

题解代码

#include #include #define MAX 2005#define INF 0x3f3f3f3fusing namespace std;int n;bool vis[MAX];//判断节点是否已经访问过了int dis[MAX];//记录现在到某一节点的最小距离 int G[MAX][MAX];int C;//查询费用 long long ans;//最后结果 bool judge(){    for(int i = 0; i  n; i++)if(!vis[i]) return 1;    return 0;}void Prim(){    memset(dis, INF, sizeof(dis));    dis[0] = 0;    while(judge())    {int u = -1, min = INF;for(int j = 0; j  n; j++){    if(!vis[j] && dis[j]  min)    { u = j; min = dis[j];    }}vis[u] = true;ans += dis[u];for(int v = 0; v  n; v++){    if(!vis[v] && G[u][v]  dis[v]) dis[v] = G[u][v];}    }    return;}int main(void){    scanf("%d", &n);    for(int i = 0; i  n; i++)for(int j = 0; j  n; j++)    G[i][j] = INF;//初始化图    ans = 0;//初始化 ans 为 0    for(int i = 1; i  n; i++)    {for(int j = i; j  n; j++){    scanf("%d", &C);    G[i - 1][j] = C;//建边     G[j][i - 1] = C;//注意是无向图，所以要建立双向边 }    }    Prim();//因为是稠密图，所以使用Prim算法跑最小生成树     printf("%lldn", ans);    return 0
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！