算法修炼之练气篇——练气九层

命运之光

发布于 2024-03-20 10:15:49

960

发布于 2024-03-20 10:15:49

博主：命运之光专栏：算法修炼之练气篇前言：每天练习五道题，炼气篇大概会练习200道题左右，题目有C语言网上的题，也有洛谷上面的题，题目简单适合新手入门。（代码都是命运之光自己写的，练完这200多道题就考了今年第十四届的B组蓝桥杯C/C++获得了省一，后面还会更新“算法修炼之筑基篇”里面包括了省赛到国赛这一个月训练的刷奖计划，大概有40道左右，感兴趣的话可以关注一下命运之光）

题目 2656: 蓝桥杯2022年第十三届省赛真题-刷题统计

题目描述

小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做 a 道题目，周六和周日每天做 b 道题目。请你帮小明计算，按照计划他将在第几天实现做题数大于等于 n 题？

输入格式

输入一行包含三个整数 a, b 和 n.

输出格式

输出一个整数代表天数。

样例输入

10 20 99

样例输出

提示

对于 50% 的评测用例，1 ≤ a, b, n ≤ 106 . 对于 100% 的评测用例，1 ≤ a, b, n ≤ 1018 .

从错误到正确详细带你走一遍！

思路一：暴力破解（时间超限71）

#include <stdio.h>
int a,b,n,sum=0,cout1=0,day=1;
int main()
{
    scanf("%d %d %d",&a,&b,&n);
    while(sum<n)
    {
        cout1++;
        if(day==8)
        {
            day=1;
        }
        if(day<=5)
        {
            sum=sum+a;
        }
        else
        {
            sum=sum+b;
        }
        day++;
    }
    printf("%d\n",cout1);
    return 0;
}

思路二：在以上算法上进行优化降低算法复杂度（时间超限80）

#include <stdio.h>
long long a,b,n,cout1=0,day=1;
int main()
{
    scanf("%lld %lld %lld",&a,&b,&n);
    while(n>=0)
    {
        cout1++;
        if(day==8)
        {
            day=1;
        }
        if(day<=5)
        {
            n=n-a;
        }
        else
        {
            n=n-b;
        }
        day++;
    }
    printf("%lld\n",cout1);
    return 0;
}

先总结一下：我发现，通过加减这样改算法复杂度，复杂度能降低但降低的非常非常小，所以下来我将用乘除的方式改进复杂度问题，让时间不会超限。

思路三：依旧暴力破解，但我用乘除的方式降低复杂度

改进算法如下：

  long long temp=n;
    if(temp>=(5*a+2*b))
    {
        while(n>=(5*a+2*b))
        {
            flag=n/(5*a+2*b)*7;
            n=n-flag*(5*a+2*b)/7;
               sum=flag;
        }
    }

运行结果（这就很迷~🍓）

#include<stdio.h>
long long a,b,n,cout1=0,day=1,flag,temp,sum=0;
int main()
{
    scanf("%lld %lld %lld",&a,&b,&n);
    temp=n;
    if(temp>=(5*a+2*b))
    {
        while(n>=(5*a+2*b))
        {
            flag=n/(5*a+2*b)*7;
            n=n-flag*(5*a+2*b)/7;
               sum=flag;
        }
    }
    while(n>=0)
    {
        sum++;
        if(day==8)
        {
            day=1;
        }
        if(day<=5)
        {
            n=n-a;
        }
        else
        {
            n=n-b;
        }
        day++;
    }
    printf("%lld",sum);
    return 0;
}

无奈~进行调试

输入

10 20 30

正确输出应该是

我的输出是

错误点分析

改错

//while(n>=0)错了，将等号去掉
while(n=0)

最终代码+运行结果

#include <stdio.h>
long long a,b,n,cout1=0,day=1,flag,temp,sum=0;
int main()
{
    scanf("%lld %lld %lld",&a,&b,&n);
    temp=n;
    if(temp>=(5*a+2*b))
    {
        while(n>=(5*a+2*b))
        {
            flag=n/(5*a+2*b)*7;
            n=n-flag*(5*a+2*b)/7;
               sum=flag;
        }
    }
    while(n>0)
    {
        sum++;
        if(day==8)
        {
            day=1;
        }
        if(day<=5)
        {
            n=n-a;
        }
        else
        {
            n=n-b;
        }
        day++;
    }
    printf("%lld",sum);
    return 0;
}

题目 2657: 蓝桥杯2022年第十三届省赛真题-修剪灌木

题目描述

爱丽丝要完成一项修剪灌木的工作。有 N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晚会修剪一棵灌木，让灌木的高度变为 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始，每天向右修剪一棵灌木。当修剪了最右侧的灌木后，她会调转方向，下一天开始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。然后如此循环往复。灌木每天从早上到傍晚会长高 1 厘米，而其余时间不会长高。在第一天的早晨，所有灌木的高度都是 0 厘米。爱丽丝想知道每棵灌木最高长到多高。

输入格式

一个正整数 N ，含义如题面所述。

输出格式

输出 N 行，每行一个整数，第i行表示从左到右第 i 棵树最高能长到多高。

样例输入

样例输出

4 2 4

提示

对于 30% 的数据，N ≤ 10. 对于 100% 的数据，1 < N ≤ 10000.

理解题意！！找到规律！！以下是找到的规律！！（可参考）

解题思路：

这道题主要是找规律，题意读懂后找到规律，把所找的规律用算法表示出来。

注：

找到规律后实现不止一种方法，下面这个是直接打出来的，也可以想一想更简单，代码量更少的实现方法，主要我认为的是最快想到的就是最好的，没必要太过苛求简易。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i;
    cin>>n;
    i=2*n-2;
    if(n==1)//如果输入是1
    {
        printf("1\n");//直接输出1
        return 0;
    }
    while(i>n)//循环打印从高到低
    {
        printf("%d\n",i);//例如：n=5时，输出8，6
        i=i-2;
    }
    if(n%2==0)//判断是否为偶数
    {
        printf("%d\n",i);/*例如：n=6时，多输出一次6，使其满足答案的10 8 6 6 8 10*/
    }
    while(i<=2*n-2)//循环打印从低到高
    {
        printf("%d\n",i);//例如：n=5时，输出4，6，8
        i=i+2;
    }
    return 0;
}

题目 1999: 回文判断

题目描述

若一个正整数从左向右读与从右向左读都一样，我们就将其称之为回文数（例如12321、44、3都是回文数）。输入一个正整数，判断它是否是回文数，是则输出YES，否则输出NO。（提示：以字符串形式读取输入的整数）

输入格式

正整数

输出格式

YES或NO

样例输入

2332

样例输出

YES

解题思路：设反向扫描双指针为i和j,如果s[i]和s[j]相同，则执行i++和j—;如果s[i]和s[j]不同，那么或者删除s[i],或者删除s[j],看剩下的字符串是否是回文串。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;//读一个字符串
    bool ans=true;
    int i=0,j=s.size()-1;//双指针
    while(i<j)
    {
        if(s[i]!=s[j])
        {
            ans=false;
            break;
        }
        i++;
        j--;//移动双指针
    }
    if(ans)
    {
        cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }
    return 0;
}

题目 1200: 回文串

题目描述

回文串是从左到右或者从右到左读起来都一样的字符串，试编程判别一个字符串是否为回文串。

输入格式

输入一个字符串。串长度<255.

输出格式

判别输入的字符串是否为回文串，是输出"Y",否则输出"N"。

样例输入

abcba

样例输出

反向扫描——尺取法

反向扫描：i、j 方向相反，i 从头到尾，j 从尾到头，在中间相会。也可以把反向扫描的 i、j 指针称为「左右指针」

注意：用尺取法的最关键之处在于，两个指针 i、j在总体上只能有一个循环，例如：i 循环一遍，对应的 j 只能跟随 i 循环一遍。这样才能实现计算复杂度从 O(n^2)到 O(n)的优化。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;//读一个字符串
    bool ans=true;
    int i=0,j=s.size()-1;//双指针
    while(i<j)
    {
        if(s[i]!=s[j])
        {
            ans=false;
            break;
        }
        i++;
        j--;//移动双指针
    }
    if(ans)
    {
        cout<<"Y"<<endl;
    }
    else
    {
        cout<<"N"<<endl;
    }
    return 0;
}

题目 1461: 蓝桥杯基础练习VIP-FJ的字符串

题目描述

FJ在沙盘上写了这样一些字符串： A1 = “A” A2 = “ABA” A3 = “ABACABA” A4 = “ABACABADABACABA” … … 你能找出其中的规律并写所有的数列AN吗？

输入格式

仅有一个数：N ≤ 26。

输出格式

请输出相应的字符串AN，以一个换行符结束。输出中不得含有多余的空格或换行、回车符。

样例输入

样例输出

ABACABA

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s1="A",s2;
    int n,k=1;
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
    {
        s2=65+k;
        s1=s1+s2+s1;
        k++;
    }
    printf("%s",s1.c_str());/*string类型用printf输出时%s，后用.c_str()否则会报错*/
    return 0;
}