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

一、前言

        感觉这次的题目都很好,但是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.rhkb.cn/news/300741.html

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

相关文章

Flask Python Flask-SQLAlchemy中数据库的数据类型、flask中数据可的列约束配置

Flask Python Flask-SQLAlchemy中数据库的数据类型、flask中数据可的列约束配置 SQLAlchemy官方文档地址实战的代码分享数据类型列约束配置自定义方法 SQLAlchemy官方文档地址 SQLAlchemy官方文档地址 实战的代码分享 Flask-SQLAlchemy框架为创建数据库的实例提供了一个基类…

蓝桥杯—PCF8951

1.整个系统靠SDA和SCL实现完善的全双工数据传输 2.引脚图 AN1为光明电阻 AN3为滑动变阻 A0-A2均接地 时钟线连P20 地址线连P21 实物图 iic总线 谁控制时钟线谁是主设备 时序相关 官方提供的底层驱动代码 /* # I2C代码片段说明1. 本文件夹中提供的驱动代码供参赛选手完成…

Docker容器(五)Docker Compose

一、概述 1.1介绍 Docker Compose是Docker官方的开源项目&#xff0c;负责实现对Docker容器集群的快速编排。Compose 是 Docker 公司推出的一个工具软件&#xff0c;可以管理多个 Docker 容器组成一个应用。你需要定义一个 YAML 格式的配置文件docker-compose.yml&#xff0c;…

STC89C51学习笔记(五)

STC89C51学习笔记&#xff08;五&#xff09; 综述&#xff1a;文本讲述了代码中速写模板的创建、如何将矩阵键盘的按键与数字一一对应以及如何创建一个矩阵键盘密码锁。 一、速写模板 点击“templates”&#xff0c;再鼠标右键选择配置&#xff0c;按照以下方式即可修改一些…

4.7 IO day6

1&#xff1a;有一个隧道&#xff0c;全长5公里&#xff0c;有2列火车&#xff0c;全长200米&#xff0c; 火车A时速 100公里每小时 火车B时速 50公里每小时 现在要求模拟火车反复通过隧道的场景(不可能2列火车都在隧道内运行) #include <stdio.h> #include <string.…

Mac安装配置Appium

一、安装 nodejs 与 npm 安装方式与 windows 类似 &#xff0c;官网下载对应的 mac 版本的安装包&#xff0c;双击即可安装&#xff0c;无须配置环境变量。官方下载地址&#xff1a;https://nodejs.org/en/download/ 二、安装 appium Appium 分为两个版本&#xff0c;一个是…

【iOS】UITableView性能优化

文章目录 前言一、优化的本质二、卡顿产生原因三、CPU层面优化1.使用轻量级对象2.cellForRowAtIndexPath方法中不要做耗时操作3.UITableView的复用机制4.提前计算好布局了解tableView代理方法执行顺序cell高度计算rowHeightestimatedRowHeight 高度计算进行时机rowHeight计算时…

阿里云服务器可以干嘛?阿里云服务器八大用途介绍

阿里云服务器可以干嘛&#xff1f;能干啥你还不知道么&#xff01;简单来讲可用来搭建网站、个人博客、企业官网、论坛、电子商务、AI、LLM大语言模型、测试环境等&#xff0c;阿里云百科aliyunbaike.com整理阿里云服务器的用途&#xff1a; 阿里云服务器活动 aliyunbaike.com…

XML HTTP传输 小结

what’s XML XML 指可扩展标记语言&#xff08;eXtensible Markup Language&#xff09;。 XML 被设计用来传输和存储数据&#xff0c;不用于表现和展示数据&#xff0c;HTML 则用来表现数据。 XML 是独立于软件和硬件的信息传输工具。 应该掌握的基础知识 HTMLJavaScript…

视听杂志知网收录期刊投稿发表论文

《视听》是由国家新闻出版总署批准的正规的&#xff0c;兼有新闻传播、新媒体理论探索的当代学术性省级综合期刊。坚持正确的理论导向&#xff0c;全面展示广播影视事业发展中出现的新情况、新事物&#xff0c;探索现代传媒基础理论&#xff0c;研究网络传播、通讯传播等新媒体…

【SCI绘图】【小提琴系列1 python】绘制按分类变量分组的垂直小提琴图

SCI&#xff0c;CCF&#xff0c;EI及核心期刊绘图宝典&#xff0c;爆款持续更新&#xff0c;助力科研&#xff01; 本期分享&#xff1a; 【SCI绘图】【小提琴系列1 python】绘制按分类变量分组的垂直小提琴图&#xff0c;文末附完整代码 小提琴图是一种常用的数据可视化工具…

ES入门十四:分词器

我们存储到ES中数据大致分为以下两种&#xff1a; 全文本&#xff0c;例如文章内容、通知内容精确值&#xff0c;如实体Id 在对这两类值进行查询的时候&#xff0c;精确值类型会比较它们的二进制&#xff0c;其结果只有相等或者不想等。而对全文本类型进行等值比较是不太实现…

顺序统计量

一、顺序统计量 定义&#xff1a;将长度为 n 的数组按升序排序后&#xff0c;第 i 个位置的数字是该数组的第 i 小的量&#xff0c;称之为第 i 顺序统计量。 则一个数组中的最小值是第1顺序统计量&#xff0c;最大值是第n顺序统计量&#xff0c;中位数是第 (n1)/2 顺序统计量 …

C-结构体对齐

结构体对齐&#xff08;Struct Alignment&#xff09;&#xff1a;是计算机编程中的一个概念&#xff0c;通常用于描述编译器如何安排结构体的成员在内存中的存储方式。 在很多计算机体系结构中&#xff0c;访问未对齐的数据可能会导致性能下降&#xff0c;甚至是程序崩溃。为了…

rsync 远程同步----------安全高效的异地备份策略

目录 一、rsync介绍 rsync和cp的区别 rsync和scp的区别 二、rsync同步方式 rsync备份的方式 三、配置rsync源服务器 ①本地复制 ②下行同步 ③上行同步 四、常用Rsync命令 五、配置源的两种表达方法 六、部署rsync下行同步 ①环境准备 ②配置rsync源服务器-------…

Spring源码解析-容器基本实现

spring源码解析 整体架构 defaultListableBeanFactory xmlBeanDefinitionReader 创建XmlBeanFactory 对资源文件进行加载–Resource 利用LoadBeandefinitions(resource)方法加载配置中的bean loadBeandefinitions加载步骤 doLoadBeanDefinition xml配置模式 validationMode 获…

HTTP 常见的状态码以及其适用场景

是什么 HTTP状态码&#xff08;英语&#xff1a;HTTP Status Code&#xff09;&#xff0c;用以表示网页服务器超文本传输协议响应状态的3位数字代码 它由 RFC 2616规范定义的&#xff0c;并得到 RFC 2518、RFC 2817、RFC 2295、RFC 2774与 RFC 4918等规范扩展 简单来讲&#…

FPGA + 图像处理(三)生成3x3像素矩阵

前言 生成NxN的像素矩阵是对图像进行各类滤波操作的基本前提&#xff0c;本文介绍一种通过bram生成3x3矩阵的方法。 程序 生成bram核 因为本文介绍的是基于bram生成的3x3像素矩阵&#xff0c;所以要先生成两个bram核&#xff0c;用于缓存前两行图像数据 在 IP catalog中选…

【LeetCode热题100】74. 搜索二维矩阵(二分)

一.题目要求 给你一个满足下述两条属性的 m x n 整数矩阵&#xff1a; 每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target &#xff0c;如果 target 在矩阵中&#xff0c;返回 true &#xff1b;否则&#xff0c;…

特别详细的Spring Cloud 系列教程1:服务注册中心Eureka的启动

Eureka已经被Spring Cloud继承在其子项目spring-cloud-netflix中&#xff0c;搭建Eureka Server的方式还是非常简单的。只需要通过一个独立的maven工程即可搭建Eureka Server。 我们引入spring cloud的依赖和eureka的依赖。 <dependencyManagement><!-- spring clo…