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;
}

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

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

相关文章

Golang单元测试和压力测试

Golang单元测试和压力测试

一.单元测试 1.1 go test工具 go语言中的测试依赖go test命令。编写测试代码和编写普通的Go代码过程类似&#xff0c;并不需要学习新的语法&#xff0c;规则和工具。 go test命令是一个按照一定约定和组织的测试代码的驱动程序。在包目录内&#xff0c;所有以_test.go为后缀名的…
阅读更多...
自定义gitlog格式

自定义gitlog格式

git log命令非常强大而好用&#xff0c;在复杂系统的版本管理中扮演着重要的角色&#xff0c;但默认的git log命令显示出的东西实在太丑&#xff0c;不好好打扮一下根本没法见人&#xff0c;打扮好了用alias命令拍个照片&#xff0c;就正式出道了&#xff01; 在使用git查看lo…
阅读更多...
物联网可视化平台

物联网可视化平台

随着数字化转型的深入&#xff0c;物联网技术正在成为企业实现智能化、高效化运营的重要工具。物联网可视化平台&#xff0c;作为连接物理世界与数字世界的桥梁&#xff0c;为企业提供了直观、实时的数据展示和监控能力&#xff0c;从而在数字化转型中扮演着关键角色。 一、物…
阅读更多...
链路代价信息、链路状态信息（链路状态通告LSA）

链路代价信息、链路状态信息（链路状态通告LSA）

链路代价信息"link cost information" 通常指的是**在网络中&#xff0c;数据包从一个节点传输到另一个节点所需承担的“成本”或者“开销”&#xff0c;这个概念常用于路由算法和网络设计中**。以下是一些关键要点&#xff1a; 1. **路径开销**&#xff1a;路径开…
阅读更多...
【iOS】UITableView性能优化

【iOS】UITableView性能优化

文章目录 前言一、优化的本质二、卡顿产生原因三、CPU层面优化1.使用轻量级对象2.cellForRowAtIndexPath方法中不要做耗时操作3.UITableView的复用机制4.提前计算好布局了解tableView代理方法执行顺序cell高度计算rowHeightestimatedRowHeight 高度计算进行时机rowHeight计算时…
阅读更多...
如何采集大众点评的商家信息-简数采集器

如何采集大众点评的商家信息-简数采集器

如何使用简数采集器批量采集大众点评的店铺和活动等相关信息呢&#xff1f; 简数采集器目前不支持采集大众点评的店家和活动等信息&#xff0c;不建议采集&#xff0c;请换个采集源采集。 简数采集器采集网站文章特别简单&#xff0c;不需要懂编程写代码&#xff0c;只需填写…
阅读更多...
基于Spring Boot的网上书城系统（带文档）

基于Spring Boot的网上书城系统（带文档）

主要功能 本次设计任务是要设计一个网上书城管理系统&#xff0c;通过这个系统能够满足网上书城的管理及用户的图书信息管理及购物功能。系统的主要功能包括&#xff1a;首页、个人中心、用户管理、图书类型管理、图书分类管理、图书信息管理、我的收藏管理、系统管理、订单管…
阅读更多...
2.接口自动化测试学习-执行excel测试用例

2.接口自动化测试学习-执行excel测试用例

1.接口自动化测试规划 编程语言 编程工具 自动化测试框架&#xff1a;pytest 报告可视化&#xff1a;allure 持续方案&#xff1a;CI持续集成-jenkins 仓库服务器&#xff08;自动化执行&#xff09;&#xff1a;github/gitlab/gitee 测试管理工具&#xff1a;jira 2.项目代码…
阅读更多...
三防笔记本丨工业笔记本电脑丨助力测绘行业的数字化转型

三防笔记本丨工业笔记本电脑丨助力测绘行业的数字化转型

测绘行业测绘行业一直是高度技术化的领域&#xff0c;其重要性在于为建设、规划和资源管理提供准确的地理数据。然而&#xff0c;随着技术的发展&#xff0c;传统的测绘方法已经难以满足对数据精度和实时性的要求。因此&#xff0c;测绘行业正逐渐向数字化转型&#xff0c;采用…
阅读更多...
Node.js进阶——Express

Node.js进阶——Express

文章目录 一、初识Express1、概念2、安装3、使用3、托管静态资源4、nodemon 二、Express路由1、概念2、使用1&#xff09;简单使用2&#xff09;模块化路由 三、Express中间件1、介绍2、语法1&#xff09;基本语法2&#xff09;next函数作用3&#xff09;定义中间件函数4&#…
阅读更多...
成人英语口语学习-生活口语日常商务口语柯桥成人培训学校

成人英语口语学习-生活口语日常商务口语柯桥成人培训学校

如果你听见老外对你说forget-me-not&#xff0c;千万不要想太多。因为&#xff0c;他只是在说一种花的名字。就是长下面这样&#xff1a; forget-me-not的意思是勿忘我&#xff0c;是一种鲜花的名字。 例句&#xff1a;The plant is called forget-me-not. 这种植物叫勿忘我…
阅读更多...
Vscode连接WSL2当中的jupyter

Vscode连接WSL2当中的jupyter

主要解决办法参考自这篇博客 1. 在WSL当中安装jupyter 这个随便找一篇博客即可&#xff0c;比如这篇&#xff0c;也可以根据现有的环境参考其它博客内容 2. 使用jupyter创建一个虚拟环境 首先激活想要添加的虚拟环境后&#xff0c;输入命令安装库: pip install ipykernel …
阅读更多...
JUC：手写实现一个简易的线程池（Java）

JUC：手写实现一个简易的线程池（Java）

目录 ​编辑 先上完整代码&#xff1a; 解析&#xff1a; 任务队列&#xff1a; 线程池类&#xff1a; 拒绝策略&#xff1a; 先上完整代码&#xff1a; public class MyThreadPool {public static void main(String[] args) {ThreadPool threadPool new ThreadPool(2, …
阅读更多...
分布式主键ID生成策略

分布式主键ID生成策略

业务系统对分布式ID的要求 唯一性&#xff1a;在分布式系统中&#xff0c;每个节点都需要生成唯一的标识符来确保数据的唯一性。传统的单点生成ID方式无法满足分布式环境下的需求&#xff0c;而分布式ID能够在整个系统中保证每个节点生成的ID都是唯一的。 顺序性&#xff1a;某…
阅读更多...
Centos7源码方式安装Elasticsearch 7.10.2单机版

Centos7源码方式安装Elasticsearch 7.10.2单机版

下载 任选一种方式下载 官网7.10.2版本下载地址&#xff1a; https://artifacts.elastic.co/downloads/elasticsearch/elasticsearch-7.10.2-linux-x86_64.tar.gz 网盘下载链接 链接&#xff1a;https://pan.baidu.com/s/1EJvUPGVOkosRO2PUaKibaA?pwdbnqi 提取码&#x…
阅读更多...
Lumos学习王佩丰Excel第二讲：单元格格式设置

Lumos学习王佩丰Excel第二讲：单元格格式设置

今天学会GIF录制了&#xff0c;分享知识会更简便一些&#xff0c;话不多说&#xff0c;开始吧~ 一、美化表格 1、设置单元格格式的路径 从菜单栏进入&#xff1a; 选中区域&#xff08;单元格&#xff09;- 右键“设置单元格格式”&#xff1a; 2、合并单元格 合并一行 批量…
阅读更多...
大话设计模式——10.适配器模式（Adapter Pattern）

大话设计模式——10.适配器模式（Adapter Pattern）

简介 将一个类的接口转换成客户希望的另外一个接口。使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。 UML图&#xff1a; 应用场景 系统需要使用现有的类&#xff0c;而这些类的接口不符合系统的需要java中的JDBC、InputStreamReader 示例 翻译员的主要工作也…
阅读更多...
解决Android Studio Loading Devices问题

解决Android Studio Loading Devices问题

目录 一、解决办法&#xff08;普通&#xff09;&#xff1a; 二、解决办法的优化 三、解决办法的进一步优化 问题&#xff1a;windows 11 电脑&#xff0c;每次开机&#xff0c;打开Android Studio,都会显示Loading Devices&#xff0c;连接不上设备。 原因&#xff1a;adb…
阅读更多...
性能优化-如何爽玩多线程来开发

性能优化-如何爽玩多线程来开发

前言 多线程大家肯定都不陌生&#xff0c;理论滚瓜烂熟&#xff0c;八股天花乱坠&#xff0c;但是大家有多少在代码中实践过呢&#xff1f;很多人在实际开发中可能就用用Async&#xff0c;new Thread()。线程池也很少有人会自己去建&#xff0c;默认的随便用用。在工作中大家对…
阅读更多...
STL--list如何实现元素的插入和删除

STL--list如何实现元素的插入和删除

在C标准模板库&#xff08;STL&#xff09;中&#xff0c;std::list 是一个双向链表。由于它的双向链表特性&#xff0c;std::list 支持在任何位置高效地插入和删除元素。 元素插入&#xff1a; ●使用 push_back() 在列表尾部添加元素&#xff1b; ●使用 push_front() 在列表…
阅读更多...
最新文章

Copyright @ 2022~2023