2024春算法训练4——函数与递归题解

news/2024/5/3 0:22:14/文章来源:https://blog.csdn.net/wy3441415563/article/details/137442083

一、前言

        感觉这次的题目都很好，但是E题....（我太菜了想不到），别人的题解都上百行了，晕；

二、题解

 A-[NOIP2010]数字统计_2024春算法训练4——函数与递归 (nowcoder.com)

这种题目有两种做法：1、计数dp，2、暴力(时间复杂度为0(n))

1、先讲暴力：直接枚举就行了，注意循环内要用一个变量代替i求i的数位上出现过的数字。

#include<iostream>
using namespace std;
int target=2;
int main(){int l,r;cin>>l>>r;int ans=0;for(int i=l;i<=r;i++){int s=i;while(s){int yu=s%10;if(yu==target){ans++;}s/=10;}}cout<<ans;
}

2、记数类dp

这里主要是分情况讨论，假设我们要求一个数字在从一到R中出现的次数，那么就等于求这个数字在每个数出现的次数。问题就转换成了求这个数字在这个数出现的次数，进一步转换成求这个数在要求的数的每一位出现的次数之和。假设我们一直一个数abcdef，要求数字1在第三位出现的次数：

（1）前三位是0~abc-1时，数字是xxx100~xxx199，所以有abc*100种取法

（2）前三位是abc（此时讨论d）

          （2.1）d<1 数字是abc000~abc099  此时有0种取法

          （2.2）d=1  数字是abc100~abc1ef 此时有ef+1种取法

          （2.3） d>1  数字可以取到abc100~abc199（实际范围是abc000~abcdef）  此时有100取法

如果是求区间l到r的个数的话就是用r的减去l的就可以了。特判0，但是这道题都是正整数，所以不用。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath> 
#include<map>
#define pre(i,l,r)for(int i=l;i<=r;i++)
#define pr(i,r,l)for(int i=r;i>=l;i--)
using namespace std;
typedef long long ll;
typedef pair<int ,int>pii;const int N=300010;ll gcd(ll x,ll y)
{return !y?x:gcd(y,x%y);
} /*struct node
{char ch;int num;bool operator < (const struct node &A){return num<A.num;}
}a[N];*/int query(int x)
{int ret=0;while(x){x/=10;ret++;}return ret;
}int cnt(int t,int n) 
{int ret=0;int wei=query(n);pre(i,1,wei){int p=pow(10,i-1);int l=n/p/10,r=n%p,d=n/p%10;/*t如果不为0，则按照一般的规则计算*/if(t)ret+=l*p;/*t如果为0，如果l为0,左边就是000..0前导0无效就不算，如果l不为0，因为t为0，所以不存在
00000...0....的情况，要从0000010...的情况开始*/if(!t&&l)ret+=(l-1)*p;/*(t||l)表示如果t为0，那么t就不能出现在最高位*/   if(d==t&&(t||l))ret+=r+1; if(d>t&&(t||l))ret+=p;}return ret;
}void solve()
{	int l,r;cin>>l>>r;cout<<cnt(2,r)-cnt(2,l-1);
} int main()
{int _;//cin>>_;_=1;while(_--){solve();}return 0;
}

B-素数回文_2024春算法训练4——函数与递归 (nowcoder.com)

按照题目意思求出回文数，然后写一个判断质数的函数就可以了,注意一下数据范围要开ll

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath> 
#include<map>
#define pre(i,l,r)for(int i=l;i<=r;i++)
#define pr(i,r,l)for(int i=r;i>=l;i--)
using namespace std;
typedef long long ll;
typedef pair<int ,int>pii;const int N=300010;ll gcd(ll x,ll y)
{return !y?x:gcd(y,x%y);
} /*struct node
{char ch;int num;bool operator < (const struct node &A){return num<A.num;}
}a[N];*/bool isprime(ll a)
{if(a==1||a==0)return false;for(int i=2;i<=a/i;i++)if(a%i==0)return false;return true;
}bool check(string a)
{ll ret=0;pre(i,0,a.size()-1)ret=ret*10+(a[i]-'0');if(isprime(ret))return true;return false;
}void solve()
{	string a;cin>>a;pr(i,a.size()-2,0)a+=a[i];if(check(a))cout<<"prime";else cout<<"noprime";
} int main()
{int _;//cin>>_;_=1;while(_--){solve();}return 0;
}

C-[NOIP1999]回文数_2024春算法训练4——函数与递归 (nowcoder.com)

用一个数组求回文数，与原数组相加，最后判断是否为回文数，重复以上步骤最多30次，

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath> 
#include<map>
#define pre(i,l,r)for(int i=l;i<=r;i++)
#define pr(i,r,l)for(int i=r;i>=l;i--)
using namespace std;
typedef long long ll;
typedef pair<int ,int>pii;const int N=300010;ll gcd(ll x,ll y)
{return !y?x:gcd(y,x%y);
} /*struct node
{char ch;int num;bool operator < (const struct node &A){return num<A.num;}
}a[N];*/int n;//将字符转换成数字
int tr(char ch)
{return ch<='9'?(ch-'0'):(ch+10-'A');
}//将数字转换成字符
char rt(int tt)
{return tt<=9?(tt+'0'):(tt-10+'A');
}//判断当前的数是否回文
bool check(vector<char>x)
{int l=0,r=x.size()-1;while(l<r){if(x[l]!=x[r])return false;l++;r--;}return true;
}void solve()
{	cin>>n;string ss;cin>>ss;vector<char>a;pre(i,0,ss.size()-1)a.push_back(ss[i]);//a存储数int cnt=30;bool flag=1;if(check(a)){cout<<"STEP=0";return ;}while(cnt){cnt--;int t=0;vector<char>temp,ans;//temp存储a的翻转数，ans临时存储计算结果pr(i,a.size()-1,0)temp.push_back(a[i]);//模拟不同进制的加法pr(i,a.size()-1,0){int x=tr(a[i]),y=tr(temp[i]);int tt=(t+x+y)%n;t=(x+y+t)/n;char s=rt(tt);ans.push_back(s);}if(t)ans.push_back(rt(t));/*reverse(ans.begin(),ans.end());*/ //ans如果是回文数不会对结果有影响，但是如果不是也没有影响，这一步是多余的/*pre(i,0,ans.size()-1)cout<<ans[i];cout<<endl;*/if(check(ans)){cout<<"STEP="<<30-cnt;flag=0;break;}else a=ans;}if(flag) cout<<"Impossible!";
} int main()
{int _;//cin>>_;_=1;while(_--){solve();}return 0;
}

D-素数中的等差数列_2024春算法训练4——函数与递归 (nowcoder.com)

先求质数，然后用一个数组将质数存储起来，（此时是有序的不用排序），然后从小到大枚举等差数列，每组等差数列最少有三个，还有可能多于三个，可以先保留最后两个然后枚举前面的。

#include<iostream>
#include<algorithm>
using namespace std;
int f[100010];
int  prime(int ans){if(ans==1)return 0;if(ans==2)return 1;for(int i=2;i<=ans/i;i++){if(ans%i==0)return 0;}return 1;
}
int main(){int k=0,p=0;int l,r;scanf("%d%d",&l,&r);for(int i=l;i<=r;i++){if(prime(i))f[k++]=i;}for(int i=0;i<k-3;i++){if(f[i+2]-f[i+1]==f[i+1]-f[i]){while(f[i+2]-f[i+1]==f[i+1]-f[i]){printf("%d ",f[i]);i++;}i--;printf("%d %d\n",f[i+1],f[i+2]);i+=2;}}return 0;
}

F-日历中的数字_2024春算法训练4——函数与递归 (nowcoder.com)

每个月的话年份和月份都不会变，这两者可以直接处理，但是日的话就要一个一个的枚举。

注意小于10的月份和日是要补0的；

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath> 
#include<map>
#define pre(i,l,r)for(int i=l;i<=r;i++)
using namespace std;
typedef long long ll;
typedef pair<int ,int>pii;const int N=300010;ll gcd(ll x,ll y)
{return !y?x:gcd(y,x%y);
} /*struct node
{char ch;int num;bool operator < (const struct node &A){return num<A.num;}
}a[N];*/int n;int m1[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int m2[]={0,31,29,31,30,31,30,31,31,30,31,30,31};
map<int ,int>q;bool check(int a)
{return((a%400==0)||(a%4==0&&a%100!=0))?true:false;
}void solve1(int a,int b)
{if(a<10)q[0]+=b;while(a){q[a%10]+=b;a/=10;}
}void solve2(int x)
{pre(i,1,x){if(i<10)q[0]++;int a=i;while(a){q[a%10]++;a/=10;}}
}void solve()
{	int year,month,target;while(cin>>year>>month>>target){if(check(year)){solve1(year,m2[month]);solve1(month,m2[month]);solve2(m2[month]);}else{solve1(year,m1[month]);solve1(month,m1[month]);solve2(m1[month]);}cout<<q[target]<<endl;q.clear();}
} int main()
{int _;//cin>>_;_=1;while(_--){solve();}return 0;
}

G-兔子的序列_2024春算法训练4——函数与递归 (nowcoder.com)

sqrt返回的是浮点数，因此如果要用其判断完全平方数就要将其转化为整形

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath> 
#include<map>
#define pre(i,l,r)for(int i=l;i<=r;i++)
#define pr(i,r,l)for(int i=r;i>=l;i--)
using namespace std;
typedef long long ll;
typedef pair<int ,int>pii;const int N=300010;ll gcd(ll x,ll y)
{return !y?x:gcd(y,x%y);
}bool cmp(int a,int b)
{return a<b;
}/*struct node
{char ch;int num;bool operator < (const struct node &A){return num<A.num;}
}a[N];*/int a[1010];
void solve()
{	int n;cin>>n;pre(i,1,n)cin>>a[i];sort(a+1,a+1+n,cmp);pr(i,n,1)if((int)sqrt(a[i])*(int)sqrt(a[i])!=a[i]){cout<<a[i];break;}
} int main()
{int _;//cin>>_;_=1;while(_--){solve();}return 0;
}

H-小X的多边形_2024春算法训练4——函数与递归 (nowcoder.com)

这题是一道数学题，就是将多边形分割成三角形，然后将三角形面积计算转换成向量叉乘，刚好转换成一个点和其相邻点的向量叉乘，详细证明可以看下这个大牛的博客：

计算任意多边形的面积 - tenos - 博客园 (cnblogs.com)icon-default.png?t=N7T8https://www.cnblogs.com/TenosDoIt/p/4047211.html代码如下：

include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int main()
{int n;cin>>n;vector<int>a,b;while(n--){int x,y;cin>>x>>y;a.push_back(x);b.push_back(y);}int s=0;for(int i=0,j=1;i<a.size();i++,j++){if(j==a.size())j=0;s+=a[i]*b[j];s-=a[j]*b[i];}int ans;if(s%2==0)ans=abs(s/2);else ans=abs(s/2)+1;cout<<ans;return 0;
}

I-The Biggest Water Problem_2024春算法训练4——函数与递归 (nowcoder.com)

对于任意一个十进制数x,x=a*10^n+b*10^(n-1)+......+c*10^0;如果每次只取其位数上的数，可以发现数会越变越小，所以一定有解。按照题意模拟即可

#include<iostream>
using namespace std;
int sum=0;
void solve(int n){int s=n;sum=0;while(s){sum+=s%10;s/=10;}
}
int main(){string c;cin>>c;for(unsigned int i=0;i<c.size();i++){sum+=c[i]-'0';}while(sum>=10){solve(sum);}cout<<sum;
}

J-小q的数列_2024春算法训练4——函数与递归 (nowcoder.com)

求值的话直接递归就行，但是求第一次出现的数的话要观察规律，发现是2的n次方减一

K-大吉大利，今晚吃鸡_2024春算法训练4——函数与递归 (nowcoder.com)、

此题有限制只能移动到相邻的柱子上面去我们可以将n个圆盘看成两部分，一部分是上面n-1个圆盘，另外一部分就是第n个圆盘，可以得出递归的步骤有如下几步：

如果n==1要跳两下

1、将（n-1）从A拿到C

2、将n从A拿到B；

3、将（n-1）从C拿到A

4、将n从B拿到C

5、将（n-1）从A拿到C；

当然事实上A，B，C不是固定的，固定的是A，B，C分别代表的起始柱，工具柱，目的柱,反正n被拿到目的柱后就可以忽略了，每次解决的都是n，当n-1递归到1时结束；记得特判0。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath> 
#include<map>
#define pre(i,l,r)for(int i=l;i<=r;i++)
#define pr(i,r,l)for(int i=r;i>=l;i--)
using namespace std;
typedef long long ll;
typedef pair<int ,int>pii;const int N=300010;ll gcd(ll x,ll y)
{return !y?x:gcd(y,x%y);
} /*struct node
{char ch;int num;bool operator < (const struct node &A){return num<A.num;}
}a[N];*/ll ans=0;void hanoi(int x)
{if(x==1){ans+=2;return ;}hanoi(x-1);ans++;hanoi(x-1);ans++;hanoi(x-1);}void solve()
{	int x;while(scanf("%d",&x)!=EOF){ans=0;if(x)hanoi(x);cout<<ans<<endl;}
} int main()
{int _;//cin>>_;_=1;while(_--){solve();}return 0;
}

L-[NOIP2001]数的计算_2024春算法训练4——函数与递归 (nowcoder.com)

这题的题目描述有点问题建议去看原题。思路是如果一个数可以得到一个数那么他就可以得到这一个数的所有集合。P1028 [NOIP2001 普及组] 数的计算 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)icon-default.png?t=N7T8https://www.luogu.com.cn/problem/P1028

代码如下:

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath> 
#include<map>
#define pre(i,l,r)for(int i=l;i<=r;i++)
#define pr(i,r,l)for(int i=r;i>=l;i--)
using namespace std;
typedef long long ll;
typedef pair<int ,int>pii;const int N=300010;ll gcd(ll x,ll y)
{return !y?x:gcd(y,x%y);
} /*struct node
{char ch;int num;bool operator < (const struct node &A){return num<A.num;}
}a[N];*/int dp[N];void init()
{pre(i,1,1010)dp[i]=1;pre(i,1,1010)pre(j,1,i/2)dp[i]+=dp[j];
}void solve()
{	init();int n;cin>>n;cout<<dp[n]<<endl;
} int main()
{int _;//cin>>_;_=1;while(_--){solve();}return 0;
}

M-[CSP2019]格雷码（code)_2024春算法训练4——函数与递归 (nowcoder.com)

非常适合递归的一道题：又题可知每次在前面要么加1，要么加0，那么我们可以通过判断

n位数第k位数是由（n-1）位第几个数变来的，如果k在前一半，那么加一个0，否则加一个1

如果k在前一半那么它在加0之前的那个数的位置一定是在（n-1）位的第k个，因为前半段是顺序，

反之k是（n-1）位数的第（2^n-k+1）个，因为后半段是逆序。一直递归到0,1，结束即可

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath> 
#include<map>
#define pre(i,l,r)for(int i=l;i<=r;i++)
#define pr(i,r,l)for(int i=r;i>=l;i--)
using namespace std;
typedef long long ll;
typedef pair<int ,int>pii;const int N=300010;ll gcd(ll x,ll y)
{return !y?x:gcd(y,x%y);
} /*struct node
{char ch;int num;bool operator < (const struct node &A){return num<A.num;}
}a[N];*/string t[2]={"0","1"};void finds(int x,ll k)
{if(x==1&&k==0){cout<<"0";return;}if(x==1&&k==1){cout<<"1";return;}if(k>=(ll)pow(2,x-1)){cout<<"1";k=(ll)pow(2,x)-k-1;finds(x-1,k);}else {cout<<"0";finds(x-1,k);}
}void solve()
{	ll n,k;cin>>n>>k;finds(n,k);
} int main()
{int _;//cin>>_;_=1;while(_--){solve();}return 0;
}

N-[NOIP2011]瑞士轮_2024春算法训练4——函数与递归 (nowcoder.com)

这题用sort就逃不了tle的命运，所以再看了大佬的题解后发现这题目的每一轮的排序时间复杂度可以用归并排序控制在O(n),从而逃脱tle的魔爪。

每一轮从前往后将所有人分为胜者组和败者组，因为胜者组和败者组是默认有序的，因为一开始就是按分数大小排序的，所以前一组的胜者的分数一定大于后一组的胜者的分数。然后这时候用归并排序其时间复杂度稳定是O(n)。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath> 
#include<map>
#define pre(i,l,r)for(int i=l;i<=r;i++)
#define pr(i,r,l)for(int i=r;i>=l;i--)
using namespace std;
typedef long long ll;
typedef pair<int ,int>pii;const int N=1000010;ll gcd(ll x,ll y)
{return !y?x:gcd(y,x%y);
} struct node
{int score,ability,h;bool operator < (const struct node &A){if(score!=A.score)return score>A.score;return h<A.h;}
}a[N],A[N],B[N];int n,r,q,cnt=1;void merge_sort()
{int i=1,j=1,k=1;while(i<=n/2&&j<=n/2){if(A[i].score>B[j].score || (A[i].score == B[j].score && A[i].h<B[j].h)){a[k].score=A[i].score;a[k].h=A[i].h;a[k++].ability=A[i++].ability;}else{a[k].score=B[j].score;a[k].h=B[j].h;a[k++].ability=B[j++].ability;}}while(i<=n/2){a[k].score=A[i].score;a[k].h=A[i].h;a[k++].ability=A[i++].ability;}while(j<=n/2){a[k].score=B[j].score;a[k].h=B[j].h;a[k++].ability=B[j++].ability;}
}void solve()
{	cin>>n>>r>>q;n*=2;pre(i,1,n)cin>>a[i].score,a[i].h=i;pre(i,1,n)cin>>a[i].ability;sort(a+1,a+1+n);for(int j=1;j<=r;j++){cnt=1;for(int i=1;i<=n;i+=2){if(a[i].ability>a[i+1].ability){A[cnt].ability=a[i].ability;B[cnt].ability=a[i+1].ability;A[cnt].score=a[i].score+1;B[cnt].score=a[i+1].score;A[cnt].h=a[i].h;B[cnt++].h=a[i+1].h;}else{A[cnt].ability=a[i+1].ability;B[cnt].ability=a[i].ability;A[cnt].score=a[i+1].score+1;B[cnt].score=a[i].score;A[cnt].h=a[i+1].h;B[cnt++].h=a[i].h;}}merge_sort();}cout<<a[q].h<<endl;
} int main()
{int _;//cin>>_;_=1;while(_--){solve();}return 0;
}

O-[NOIP2007]Hanoi双塔问题_2024春算法训练4——函数与递归 (nowcoder.com)

这题应该跟上面那题差不多，特点是没有条件限制，但是它的数据范围有点大。

思路参考上面，可以得出递归的步骤是：

n==1时走一步

1、将（n-1）从A拿到B

2、将（n）从A拿到C

3、将（n-1）从B拿到B

但是这题用递归会炸、、范围原因，只要改一改这其实是一道简单的dp题

递推公式如下：

考虑到结果会很大，于是我们可以采用高精度乘法：

（关于高精度可以看看这里：高精度运算-CSDN博客）

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath> 
#include<map>
#define pre(i,l,r)for(int i=l;i<=r;i++)
#define pr(i,r,l)for(int i=r;i>=l;i--)
using namespace std;
typedef long long ll;
typedef pair<int ,int>pii;const int N=300010;ll gcd(ll x,ll y)
{return !y?x:gcd(y,x%y);
} /*struct node
{char ch;int num;bool operator < (const struct node &A){return num<A.num;}
}a[N];*/int dp[201][201];void init()
{dp[1][1]=1;pre(i,2,201){pre(j,1,201)dp[i][j]=dp[i-1][j]*2;int t=0;dp[i][1]++;pre(j,1,201)if(dp[i][j]>=10)dp[i][j+1]+=dp[i][j]/10,dp[i][j]%=10;}
}void solve()
{	init();int n;cin>>n;int flag=201;pre(j,1,201)dp[n][j]*=2;pre(j,1,201)if(dp[n][j]>=10)dp[n][j+1]+=dp[n][j]/10,dp[n][j]%=10;pr(i,201,1)if(dp[n][i]){flag=i;break;}pr(i,flag,1)cout<<dp[n][i];
} int main()
{int _;//cin>>_;_=1;while(_--){solve();}return 0;
}

P-[NOIP1998]幂次方_2024春算法训练4——函数与递归 (nowcoder.com)

这里的子任务就是如何将一个数表示成2的幂次方的问题，对于任意一个数，如果它大于等于2^n，那么他就一定可以分解成2^n+..........的形式，那么我们的一个任务就是表示2^n,然后进一步表示n,n也一定可以表示成2^m+.....的形式。（n,m均为常数）。直到其中有一个环节能够用2或者1表示，那么递归结束。至于加号，从上面的表示来看，只要递归没结束，即x不为0，就有加号。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath> 
#include<map>
#define pre(i,l,r)for(int i=l;i<=r;i++)
#define pr(i,r,l)for(int i=r;i>=l;i--)
using namespace std;
typedef long long ll;
typedef pair<int ,int>pii;const int N=300010;ll gcd(ll x,ll y)
{return !y?x:gcd(y,x%y);
} /*struct node
{char ch;int num;bool operator < (const struct node &A){return num<A.num;}
}a[N];*/void gui(int x)
{pr(i,14,0){if(pow(2,i)<=x){if(i==1)cout<<2;else if(i==0)cout<<"2(0)";else {cout<<"2(";gui(i);cout<<")";}x-=pow(2,i);if(x)cout<<"+";}}}void solve()
{	int n;cin>>n;gui(n);
} int main()
{int _;//cin>>_;_=1;while(_--){solve();}return 0;
}

Q-[NOIP2001]一元三次方程求解_2024春算法训练4——函数与递归 (nowcoder.com)

这题有两个解法：1、暴力 2、二分，3、盛金公式。

1、暴力感觉有点勉强（能做出来就是win）直接枚举所有的可能解，注意要时间复杂度和eps的取值

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath> 
#include<map>
#define pre(i,l,r)for(int i=l;i<=r;i++)
#define pr(i,r,l)for(int i=r;i>=l;i--)
using namespace std;
typedef long long ll;
typedef pair<int ,int>pii;const int N=300010;ll gcd(ll x,ll y)
{return !y?x:gcd(y,x%y);
} /*struct node
{char ch;int num;bool operator < (const struct node &A){return num<A.num;}
}a[N];*/double a,b,c,d;double f(double x){double ret=a*x*x*x+b*x*x+c*x+d;return ret;
}
double eps=1e-2;void solve()
{	cin>>a>>b>>c>>d;int cnt=0;double i=-100.0;while(cnt<3&&i<=100){if(fabs(f(i))<eps){printf("%.2f ",i);cnt++;i+=1;}	i+=0.001;}
} int main()
{int _;//cin>>_;_=1;while(_--){solve();}return 0;
}

 2、二分：题目说如果两端点值异号那么区间至少有一个解，而且两个解的距离大于等于1，所以我们对每个长度为一两端点异号的区间进行二分的话，不考虑两端点都是解的情况下，一定可以二分出一个正解。同时要特判端点值，因为区间为闭区间。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath> 
#include<map>
#define pre(i,l,r)for(int i=l;i<=r;i++)
#define pr(i,r,l)for(int i=r;i>=l;i--)
using namespace std;
typedef long long ll;
typedef pair<int ,int>pii;const int N=300010;ll gcd(ll x,ll y)
{return !y?x:gcd(y,x%y);
} /*struct node
{char ch;int num;bool operator < (const struct node &A){return num<A.num;}
}a[N];*/double a,b,c,d;double f(double x){return a*x*x*x+b*x*x+c*x+d;
}
double eps=1e-2;void solve()
{	scanf("%lf %lf %lf %lf",&a,&b,&c,&d);int cnt=0;pre(i,-100,100){double y1=f(i*1.0);double y2=f((i+1)*1.0);if(!y1){   cnt++;printf("%.2lf ",i*1.0);}if(y1*y2<0){double l=i,r=i+1;while(r-l>=0.001){    double mid=(l+r)/2;if(f(mid)*f(l)<=0)r=mid;else l=mid;}printf("%.2lf ",l);cnt++;}if(cnt==3)break;}
} int main()
{int _;//cin>>_;_=1;while(_--){solve();}return 0;
}

 3、盛金公式，建议自行搜索。

R-[NOIP2002]过河卒_2024春算法训练4——函数与递归 (nowcoder.com)

这题看起来好有感觉，直接用dp写了。我们可以先忽略马这个元素，如果只用求路径数的话，那么

对于所有第一排和第一列的格子，显然都只有一种走法，然后对于其他格子的路径总数等于其上面格子的路径总数加上左边的格子的路径总数。

加入马之后要考虑其影响，1、如果马可以出现在第一行或者第一列那么第一行或者第一列在那个点后面的格子就不可能到达了；2、如果上面或者左边马可以到达那么那个点的路径数一定为0，

代码如下：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath> 
#include<map>
#define pre(i,l,r)for(int i=l;i<=r;i++)
#define pr(i,r,l)for(int i=r;i>=l;i--)
using namespace std;
typedef long long ll;
typedef pair<int ,int>pii;const int N=300010;ll gcd(ll x,ll y)
{return !y?x:gcd(y,x%y);
} /*struct node
{char ch;int num;bool operator < (const struct node &A){return num<A.num;}
}a[N];*/
int dx[]={2,2,1,1,-2,-2,-1,-1},dy[]={1,-1,2,-2,1,-1,2,-2};
ll ans[21][21];void solve()
{	int n,m,a,b;cin>>n>>m>>a>>b;ans[a][b]=-1;pre(i,0,7){int x=a+dx[i],y=b+dy[i];if(x>=0&&x<=n&&y>=0&&y<=m)ans[x][y]=-1;}pre(i,0,n){if(ans[i][0]!=-1)ans[i][0]=1;else break;}pre(i,0,m){if(ans[0][i]!=-1)ans[0][i]=1;else break;}pre(i,1,n){pre(j,1,m){if(ans[i][j]==-1)continue;if(ans[i-1][j]!=-1)ans[i][j]+=ans[i-1][j];if(ans[i][j-1]!=-1)ans[i][j]+=ans[i][j-1];}}cout<<ans[n][m];
} int main()
{int _;//cin>>_;_=1;while(_--){solve();}return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.luyixian.cn/news_show_1046009.aspx

如若内容造成侵权/违法违规/事实不符，请联系dt猫网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

网站SEO关键词规划时如何筛选出合适的关键词？

网站SEO关键词规划时如何筛选出合适的关键词？

在网站SEO优化过程中&#xff0c;关键词布局是一个至关重要的环节。首先&#xff0c;我们需要确定核心关键词&#xff0c;然后通过各种策略和方法对关键词进行扩展。完成关键词扩展后&#xff0c;接下来的任务就是对这些扩展后的关键词进行筛选。那么&#xff0c;如何进行有效的…
阅读更多...
pytorch3d、Detectron2编译安装

pytorch3d、Detectron2编译安装

基础环境&#xff1a; python&#xff1a;3.6 ubuntu&#xff1a;18.04 pytorch&#xff1a;1.8 cuda&#xff1a;10.2 一、pytorch3d编译 官方指南 GitCode - 开发者的代码家园 注意&#xff1a;cuda11以下的版本&#xff0c;需要安装CUB libaray&#xff0c;cuda11以上的版…
阅读更多...
开源项目one-api的k8s容器化部署（上）-- 制作镜像及部署准备

开源项目one-api的k8s容器化部署（上）-- 制作镜像及部署准备

一、背景 最近需要对开源项目one-api进行k8s容器化部署&#xff0c;主要分以下几个步骤&#xff1a; 制作docker镜像申请mysql和redis数据库docker-compose部署方式k8s部署方式 整个的篇幅比较长&#xff0c;将会分成上下两篇来阐述。 二、制作docker镜像 开源项目one-api…
阅读更多...
Idea集成Docker的快捷部署

Idea集成Docker的快捷部署

Idea集成Docker的快捷部署 配置Docker远程访问1.1 修改 `/lib/systemd/system/docker.service`1.2 替换`ExecStart`1.3 重启docker服务1.4 监听端口是否被占用1.5 服务器防火墙开启2375端口1.6 测试配置IDEA2.1 下载docker插件2.2 添加docker连接2.3 配置容器镜像加速器2.4 配置…
阅读更多...
Gradle 在 Spring 中的使用ApiHug准备-工具篇-006

Gradle 在 Spring 中的使用ApiHug准备-工具篇-006

&#x1f917; ApiHug {Postman|Swagger|Api...} 快↑ 准√ 省↓ GitHub - apihug/apihug.com: All abou the Apihug apihug.com: 有爱&#xff0c;有温度&#xff0c;有质量&#xff0c;有信任ApiHug - API design Copilot - IntelliJ IDEs Plugin | Marketplace ApiHug …
阅读更多...
Redis Cluster集群模式

Redis Cluster集群模式

目录 一、理论 1.1 概念 1.2 集群的作用 1.3 redis集群的数据分片 1.4 Redis集群的主从复制模型 二、实践 2.1 Redis集群模式的搭建 2.1.1 cluster集群前期工作 2.1.2 开启群集功能 2.1.3 启动redis节点 2.1.4 启动集群 2.2 测试集群 总结 一、理论 1.1 概念 集群&a…
阅读更多...
vulhub之Webmin篇

vulhub之Webmin篇

Webmin是功能最强大的基于Web的Unix系统管理工具。管理员通过浏览器访问Webmin的各种管理功能并完成相应的管理动作。Webmin支持绝大多数的Unix系统&#xff0c;这些系统除了各种版本的linux以外还包括&#xff1a;AIX、HPUX、Solaris、Unixware、Irix和FreeBSD等。 影响版本&…
阅读更多...
JVM、maven、Nexus

JVM、maven、Nexus

一、jvm简介 1.应用程序申请内存时出现的三种情况&#xff1a; ①OOM:内存溢出&#xff0c;是指应用系统中存在无法回收的内存或使用的内存过多&#xff0c;最终使得程序运行要用到的内存大于能提供的最大内存。此时程序就运行不了&#xff0c;系统会提示内存溢出&#xff0c…
阅读更多...
自己动手封装axios通用方法并上传至私有npm仓库：详细步骤与实现指南

自己动手封装axios通用方法并上传至私有npm仓库：详细步骤与实现指南

文章目录 一、构建方法1、api/request.js2、api/requestHandler.js3、api/index.js 二、测试方法1、api/axios.js2、main.js3、app.vue4、vue.config.js5、index.html 三、打包1、配置package.json2、生成库包3、配置发布信息4、发布 四、使用1、安装2、使用 五、维护1、维护和…
阅读更多...
基于FPGA的DDR相关知识导航界面

基于FPGA的DDR相关知识导航界面

个人觉得想要真正理解DDR&#xff0c;那就要从SDRAM入手&#xff0c;SDRAM读写控制器也可以作为入门FPGA的一个判断标准&#xff0c;说实话I2C、UART、SPI这些接口难度太低了&#xff0c;会写这些接口说明不了什么。 很常见的问题&#xff0c;现在DDR3、SDRAM、DDR4官方都有IP&…
阅读更多...
数据结构——二叉树链式结构的实现

数据结构——二叉树链式结构的实现

大家好我是小锋&#xff0c;今天我们来学习的是二叉树链式结构的实现 首先我们来学习一下二叉树的基本操作 在看二叉树基本操作前我们来回顾下二叉树的概念&#xff0c; 二叉树是&#xff1a; 1. 空树 2. 非空&#xff1a;根节点&#xff0c;根节点的左子树、根节点的右…
阅读更多...
【THM】Exploit Vulnerabilities（利用漏洞）-

【THM】Exploit Vulnerabilities（利用漏洞）-

介绍 在这个房间里，我们将讨论一些识别漏洞的方法，并结合我们的研究技能来了解这些漏洞是如何被滥用的。 此外，您还会发现一些公开可用的资源，这些资源是您在执行漏洞研究和利用时的技能和工具的重要补充。然后，您将在房间的最后将所有这些应用到实际挑战中。 自动化与…
阅读更多...
如何监控容器或K8s中的OpenSearch

如何监控容器或K8s中的OpenSearch

概述 当前 OpenSearch 使用的越来越多, 但是 OpenSearch 生态还不尽完善. 针对如下情况: 监控容器化或运行在 K8s 中的 OpenSearch 我查了下, 官方还没有提供完备的方案. 这里如何监控 K8s 中的 OpenSearch, 包括安装 exporter 插件、采集、展示全环节。 OpenSearch 简介…
阅读更多...
红豆Cat 1开源｜项目三： 从0-1设计一款HTTP版本RTU（支持GNSS）产品的软硬件全过程

红豆Cat 1开源｜项目三： 从0-1设计一款HTTP版本RTU（支持GNSS）产品的软硬件全过程

HTTP版RTU&#xff08;支持GNSS&#xff09;项目概述 RTU&#xff08;Remote Terminal Unit&#xff09;&#xff0c;中文即远程终端控制系统&#xff0c;负责对现场信号、工业设备的监测和控制。RTU是构成企业综合自动化系统的核心装置&#xff0c;通常由信号输入/出模块、微…
阅读更多...
蓝桥杯-单片机基础16——利用定时计数中断进行动态数码管的多窗口显示

蓝桥杯-单片机基础16——利用定时计数中断进行动态数码管的多窗口显示

综合查阅了网络上目前能找到的所有关于此技能的代码&#xff0c;最终找到了下述方式比较可靠&#xff0c;且可以自定义任意显示的数值。 传统采用延时函数的方式实现动态数码管扫描&#xff0c;在题目变复杂时效果总是会不佳&#xff0c;因此在省赛中有必要尝试采用定时计数器中…
阅读更多...
洪水预警：如何通过数据可视化提前应对灾害

洪水预警：如何通过数据可视化提前应对灾害

数据可视化在应对洪涝灾害问题中发挥着重要作用。洪涝灾害是一种常见而严重的自然灾害&#xff0c;给人们的生命、财产和生活带来了巨大的威胁和损失。而数据可视化技术通过将海量的数据转化为直观、易懂的图表、图像或地图等形式&#xff0c;帮助人们更好地理解洪涝灾害的发生…
阅读更多...
微服务-2 Eureka

微服务-2 Eureka

Eureka 启动页面&#xff1a; 同理再注册完order-service后&#xff0c;刷新启动页面&#xff1a; userservice 启动多台服务&#xff1a; [ 代码 ]&#xff1a;orderService.java&#xff08;用 RestTemplate 调其他服务&#xff0c;用 userservice 代替 localhost:8081&…
阅读更多...
视频图像的两种表示方式YUV与RGB（4）

视频图像的两种表示方式YUV与RGB（4）

本篇主要讲YUV与RGB之间的转换&#xff0c;包括YUV444 颜色编码格式 转为 RGB 格式 &#xff0c;RGB颜色编码格式转为 YUV444 格式。 一、 YUV与RGB之间的转换 YUV与RGB颜色格式之间进行转换时 , 涉及一系列的数学运算 ; YUV 颜色编码格式转为RGB格式的转换公式 取决于 于 YUV …
阅读更多...
数据结构——线性表（顺序存储结构）

数据结构——线性表（顺序存储结构）

语言&#xff1a;C语言软件&#xff1a;Visual Studio 2022笔记书籍&#xff1a;数据结构——用C语言描述如有错误&#xff0c;感谢指正。若有侵权请联系博主 一、线性表的逻辑结构 线性表是n个类型相同的数据元素的有限序列&#xff0c;对n>0&#xff0c;除第一元素无直接…
阅读更多...
电能质量问题有几类？再怎样进行谐波治理

电能质量问题有几类？再怎样进行谐波治理

一、为什么要进行电能质量的治理 电能质量是指电力系统中电能的质量。理想的电能应该是完美对称的正弦波。一些因素会使波形偏离对称正弦&#xff0c;由此便产生了电能质量问题。一方面我们研究存在哪些影响因素会导致电能质量问题&#xff0c;一方面我们研究这些因素会导致哪…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站 广利置业