题目描述有形如ax3bx2cxd0 这样的一个一元三次方程。给出该方程中各项的系数a,b,c,d 均为实数并约定该方程存在三个不同实根根的范围在 −100 至 100 之间且根与根之差的绝对值 ≥1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)并精确到小数点后 2 位。提示记方程 f(x)0若存在 2 个数 x1 和 x2且 x1x2f(x1)×f(x2)0则在 (x1,x2) 之间一定有一个根。对于这个题我是想到了两种解法一个是暴力解决我直接求根的表达式嘎嘎算但是对于竞赛来说特别费时间很不建议这也是考了你一定的数学能力另一种方法我是采用的二分查找和零点定理的运用你想想如果我能确定两个根的数值使它的函数值相乘小于零证明在这两个根之间肯定有一个值会使函数值等于零这个值就是我们要找的我还怎么找呢用到了二分我利用二分不断地找最终确定近似值就是x因为它有一定的精度所以可能不是整数但近似于整数就行#include bits/stdc.husing namespace std;double a,b,c,d;double f(double x)//我定义了fx的函数{return a*x*x*xb*x*xc*xd;}int main(){cinabcd;for(int i-100;i99;i){double li,ri1;if(fabs(f(l))1e-6)确保他的近似值的绝对值无限趋于0就可以看成是0了这一块主播写成等于0也出现了失误这样写的精度更加准确{printf(%.2f ,l);continue;}if(fabs(f(r))1e-6){printf(%.2f ,r);i;//这个是让i的值自加避免输出重复的值主播也是在这里掉坑里了没有考虑到会重复出现continue;}if(f(l)*f(r)0){for(int t0;t100;t){double mid(lr)/2;if(f(mid)*f(l)0)rmid;elselmid;}printf(%.2f ,l);}}return 0;}题目描述一年一度的“跳石头”比赛又要开始了这项比赛将在一条笔直的河道中进行河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间有 N 块岩石不含起点和终点的岩石。在比赛过程中选手们将从起点出发每一步跳向相邻的岩石直至到达终点。为了提高比赛难度组委会计划移走一些岩石使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制组委会至多从起点和终点之间移走 M 块岩石不能移走起点和终点的岩石。输入格式第一行包含三个整数 L,N,M分别表示起点到终点的距离起点和终点之间的岩石数以及组委会至多移走的岩石数。保证 L≥1 且 N≥M≥0。接下来 N 行每行一个整数第 i 行的整数 Di(0DiL) 表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出且不会有两个岩石出现在同一个位置。输出格式一个整数即最短跳跃距离的最大值。这道题我也是力竭了因为大部分样例都通过了就一个没通过主播也是没想出来后来看了题解这道题是典型的二分答案题整体思路很简单二分最短跳跃距离用check函数判断这个距离能不能通过移走不超过M块石头实现。我的二分模板是对的从头到尾没出错WA完全是因为check函数的边界处理没写明白。我最开始的错误特别典型只把题目给的中间石头放进循环判断河道终点L单独拿出来手写判断。这种写法看着没问题但很容易出边界bug尤其是测试点没有石头、或者把所有石头都移光的情况直接判断出错导致一直WA。单独处理特殊情况是做题最容易翻车的地方。后来我改对的核心方法特别简单直接把终点L当成最后一块石头存进数组末尾让终点和普通石头一起参与循环判断。不用额外写任何特判代码所有间隔统一遍历检查。只要统计出需要移走的石头数量不超过M就说明当前距离合法。最后不断二分找最大合法距离即可。这道题让我明白做题尽量统一逻辑能放进循环处理的千万别单独写判断边界问题基本都是这么来的。#includebits/stdc.husing namespace std;const int MAXN50010;int L,N,M;int a[MAXN];bool check(int d){int cnt0;int last0;for(int i1;iN1;i){if(a[i]-last d){cnt;}else{lasta[i];}}return cnt M;}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cinLNM;for(int i1;iN;i){cina[i];}a[N1]L;int l1,rL;int ans0;while(lr){int midl(r-l)/2;if(check(mid)){ansmid;lmid1;}else{rmid-1;}}coutansendl;return 0;}题目描述现在政府决定在公路上增设一些路标使得公路的“空旷指数”最小。他们请求你设计一个程序计算能达到的最小值是多少。请注意公路的起点和终点保证已设有路标公路的长度为整数并且原有路标和新设路标都必须距起点整数个单位距离。输入格式第 1 行包括三个数 L,N,K分别表示公路的长度原有路标的数量以及最多可增设的路标数量。第 2 行包括递增排列的 N 个整数分别表示原有的 N 个路标的位置。路标的位置用距起点的距离表示且一定位于区间 [0,L] 内。输出格式输出 1 行包含一个整数表示增设路标后能达到的最小“空旷指数”值。这道题也是典型的运用到了二分查找思路大体上跟昨天发的砍木头啥的很像但是处理方式不一样跟跳石头属于同一类把感觉题目要求最多新增 K 个路标让公路上相邻路标之间的最大距离尽可能小。二分的思路就是猜一个空旷指数 mid写 check 函数判断如果要求所有相邻路标间隔不能超过 mid一共需要新增多少路标。如果需要新增的路标数不超过 K说明这个 mid 是可行的我们还可以尝试找更小的答案如果需要的路标超出 K说明 mid 太小得把间隔放大。我再运行的时候出现了错误是数组越界得注意啊证明我的范围有错最后也是找出来ac了#include bits/stdc.husing namespace std;int a[100005];int main(){int r, n, k;cin r n k;for (int i 0; i n; i ){cin a[i];}int ans -1, l 1;while (l r){int M (l r)/2 ;int m 0;for (int i 0; i n; i ){int tmp a[i] - a[i - 1];if (tmp M) m (tmp - 1) / M;}if (m k){ans M;r M - 1;}elsel M 1;}cout ans;}
题目描述有形如ax3bx2cxd0 这样的一个一元三次方程。给出该方程中各项的系数a,b,c,d 均为实数并约定该方程存在三个不同实根根的范围在 −100 至 100 之间且根与根之差的绝对值 ≥1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)并精确到小数点后 2 位。提示记方程 f(x)0若存在 2 个数 x1 和 x2且 x1x2f(x1)×f(x2)0则在 (x1,x2) 之间一定有一个根。对于这个题我是想到了两种解法一个是暴力解决我直接求根的表达式嘎嘎算但是对于竞赛来说特别费时间很不建议这也是考了你一定的数学能力另一种方法我是采用的二分查找和零点定理的运用你想想如果我能确定两个根的数值使它的函数值相乘小于零证明在这两个根之间肯定有一个值会使函数值等于零这个值就是我们要找的我还怎么找呢用到了二分我利用二分不断地找最终确定近似值就是x因为它有一定的精度所以可能不是整数但近似于整数就行#include bits/stdc.husing namespace std;double a,b,c,d;double f(double x)//我定义了fx的函数{return a*x*x*xb*x*xc*xd;}int main(){cinabcd;for(int i-100;i99;i){double li,ri1;if(fabs(f(l))1e-6)确保他的近似值的绝对值无限趋于0就可以看成是0了这一块主播写成等于0也出现了失误这样写的精度更加准确{printf(%.2f ,l);continue;}if(fabs(f(r))1e-6){printf(%.2f ,r);i;//这个是让i的值自加避免输出重复的值主播也是在这里掉坑里了没有考虑到会重复出现continue;}if(f(l)*f(r)0){for(int t0;t100;t){double mid(lr)/2;if(f(mid)*f(l)0)rmid;elselmid;}printf(%.2f ,l);}}return 0;}题目描述一年一度的“跳石头”比赛又要开始了这项比赛将在一条笔直的河道中进行河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间有 N 块岩石不含起点和终点的岩石。在比赛过程中选手们将从起点出发每一步跳向相邻的岩石直至到达终点。为了提高比赛难度组委会计划移走一些岩石使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制组委会至多从起点和终点之间移走 M 块岩石不能移走起点和终点的岩石。输入格式第一行包含三个整数 L,N,M分别表示起点到终点的距离起点和终点之间的岩石数以及组委会至多移走的岩石数。保证 L≥1 且 N≥M≥0。接下来 N 行每行一个整数第 i 行的整数 Di(0DiL) 表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出且不会有两个岩石出现在同一个位置。输出格式一个整数即最短跳跃距离的最大值。这道题我也是力竭了因为大部分样例都通过了就一个没通过主播也是没想出来后来看了题解这道题是典型的二分答案题整体思路很简单二分最短跳跃距离用check函数判断这个距离能不能通过移走不超过M块石头实现。我的二分模板是对的从头到尾没出错WA完全是因为check函数的边界处理没写明白。我最开始的错误特别典型只把题目给的中间石头放进循环判断河道终点L单独拿出来手写判断。这种写法看着没问题但很容易出边界bug尤其是测试点没有石头、或者把所有石头都移光的情况直接判断出错导致一直WA。单独处理特殊情况是做题最容易翻车的地方。后来我改对的核心方法特别简单直接把终点L当成最后一块石头存进数组末尾让终点和普通石头一起参与循环判断。不用额外写任何特判代码所有间隔统一遍历检查。只要统计出需要移走的石头数量不超过M就说明当前距离合法。最后不断二分找最大合法距离即可。这道题让我明白做题尽量统一逻辑能放进循环处理的千万别单独写判断边界问题基本都是这么来的。#includebits/stdc.husing namespace std;const int MAXN50010;int L,N,M;int a[MAXN];bool check(int d){int cnt0;int last0;for(int i1;iN1;i){if(a[i]-last d){cnt;}else{lasta[i];}}return cnt M;}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cinLNM;for(int i1;iN;i){cina[i];}a[N1]L;int l1,rL;int ans0;while(lr){int midl(r-l)/2;if(check(mid)){ansmid;lmid1;}else{rmid-1;}}coutansendl;return 0;}题目描述现在政府决定在公路上增设一些路标使得公路的“空旷指数”最小。他们请求你设计一个程序计算能达到的最小值是多少。请注意公路的起点和终点保证已设有路标公路的长度为整数并且原有路标和新设路标都必须距起点整数个单位距离。输入格式第 1 行包括三个数 L,N,K分别表示公路的长度原有路标的数量以及最多可增设的路标数量。第 2 行包括递增排列的 N 个整数分别表示原有的 N 个路标的位置。路标的位置用距起点的距离表示且一定位于区间 [0,L] 内。输出格式输出 1 行包含一个整数表示增设路标后能达到的最小“空旷指数”值。这道题也是典型的运用到了二分查找思路大体上跟昨天发的砍木头啥的很像但是处理方式不一样跟跳石头属于同一类把感觉题目要求最多新增 K 个路标让公路上相邻路标之间的最大距离尽可能小。二分的思路就是猜一个空旷指数 mid写 check 函数判断如果要求所有相邻路标间隔不能超过 mid一共需要新增多少路标。如果需要新增的路标数不超过 K说明这个 mid 是可行的我们还可以尝试找更小的答案如果需要的路标超出 K说明 mid 太小得把间隔放大。我再运行的时候出现了错误是数组越界得注意啊证明我的范围有错最后也是找出来ac了#include bits/stdc.husing namespace std;int a[100005];int main(){int r, n, k;cin r n k;for (int i 0; i n; i ){cin a[i];}int ans -1, l 1;while (l r){int M (l r)/2 ;int m 0;for (int i 0; i n; i ){int tmp a[i] - a[i - 1];if (tmp M) m (tmp - 1) / M;}if (m k){ans M;r M - 1;}elsel M 1;}cout ans;}
