AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

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

2023-05-12 175
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 前言：每天练习五道题，炼气篇大概会练习200道题左右，题目有C语言网上的题，也有洛谷上面的题，题目简单适合新手入门。（代码都是命运之光自己写的，练完这200多道题就考了今年第十四届的B组蓝桥杯C/C++获得了省一，后面还会更新“算法修炼之筑基篇”里面包括了省赛到国赛这一个月训练的刷奖计划，大概有40道左右，感兴趣的话可以关注一下命运之光）

博主：命运之光

专栏：算法修炼之练气篇

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

题目描述

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

输入格式

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

输出格式

输出一个整数代表天数。

样例输入

10 20 99

样例输出

8

提示

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

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

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

#include <stdio.h>inta,b,n,sum=0,cout1=0,day=1;
intmain()
{
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);
return0;
}

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

#include <stdio.h>longlonga,b,n,cout1=0,day=1;
intmain()
{
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);
return0;
}

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

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

改进算法如下：
longlongtemp=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>longlonga,b,n,cout1=0,day=1,flag,temp,sum=0;
intmain()
{
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);
return0;
}

无奈~进行调试

输入

10 20 30

正确输出应该是

3

我的输出是

4

错误点分析

改错

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

最终代码+运行结果

#include <stdio.h>longlonga,b,n,cout1=0,day=1,flag,temp,sum=0;
intmain()
{
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);
return0;
}

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

题目描述

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

输入格式

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

输出格式

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

样例输入

3

样例输出

4 2 4

提示

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

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

解题思路：

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

注：

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

#include<bits/stdc++.h>usingnamespacestd;
intmain()
{
intn,i;
cin>>n;
i=2*n-2;
if(n==1)//如果输入是1    {
printf("1\n");//直接输出1return0;
    }
while(i>n)//循环打印从高到低    {
printf("%d\n",i);//例如：n=5时，输出8，6i=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，8i=i+2;
    }
return0;
}

题目 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>usingnamespacestd;
intmain()
{
strings;
cin>>s;//读一个字符串boolans=true;
inti=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;
    }
return0;
}

题目 1200: 回文串

题目描述

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

输入格式

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

输出格式

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

样例输入

abcba

样例输出

Y

反向扫描——尺取法

反向扫描：i、j 方向相反，i 从头到尾，j 从尾到头，在中间相会。也可以把反向扫描的 i、j 指针称为「左右指针」
注意：用尺取法的最关键之处在于，两个指针 i、j在总体上只能有一个循环，例如：i 循环一遍，对应的 j 只能跟随 i 循环一遍。这样才能实现计算复杂度从 O(n^2)到 O(n)的优化。
解题思路：设反向扫描双指针为i和j,如果s[i]和s[j]相同，则执行i++和j—;如果s[i]和s[j]不同，那么或者删除s[i],或者删除s[j],看剩下的字符串是否是回文串。
#include<bits/stdc++.h>usingnamespacestd;
intmain()
{
strings;
cin>>s;//读一个字符串boolans=true;
inti=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;
    }
return0;
}

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

题目描述

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

输入格式

仅有一个数：N  ≤  26。

输出格式

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

样例输入

3

样例输出

ABACABA

#include<bits/stdc++.h>usingnamespacestd;
intmain()
{
strings1="A",s2;
intn,k=1;
scanf("%d",&n);
for(inti=2;i<=n;i++)
    {
s2=65+k;
s1=s1+s2+s1;
k++;
    }
printf("%s",s1.c_str());/*string类型用printf输出时%s，后用.c_str()否则会报错*/return0;
}

🍓🍓今日份修炼结束，再接再厉！！！

文章标签：
C++
C语言
测试技术
算法
命运之光
目录
相关文章
命运之光
|
算法 C语言 C++
算法修炼之练气篇——练气三层
简介： 前言：每天练习五道题，炼气篇大概会练习200道题左右，题目有C语言网上的题，也有洛谷上面的题，题目简单适合新手入门。（代码都是命运之光自己写的，练完这200多道题就考了今年第十四届的B组蓝桥杯C/C++获得了省一，后面还会更新“算法修炼之筑基篇”里面包括了省赛到国赛这一个月训练的刷奖计划，大概有40道左右，感兴趣的话可以关注一下命运之光）
命运之光
165 0
命运之光
|
机器学习/深度学习 算法 C语言
算法修炼之练气篇——练气十六层
每天练习五道题，炼气篇大概会练习200道题左右，题目有C语言网上的题，也有洛谷上面的题，题目简单适合新手入门。（代码都是命运之光自己写的，练完这200多道题就考了今年第十四届的B组蓝桥杯C/C++获得了省一，后面还会更新“算法修炼之筑基篇”里面包括了省赛到国赛这一个月训练的刷奖计划，大概有40道左右，感兴趣的话可以关注一下命运之光）
命运之光
102 0
命运之光
|
算法 C语言 C++
算法修炼之练气篇——练气二十一层
每天练习五道题，炼气篇大概会练习200道题左右，题目有C语言网上的题，也有洛谷上面的题，题目简单适合新手入门。（代码都是命运之光自己写的，练完这200多道题就考了今年第十四届的B组蓝桥杯C/C++获得了省一，后面还会更新“算法修炼之筑基篇”里面包括了省赛到国赛这一个月训练的刷奖计划，大概有40道左右，感兴趣的话可以关注一下命运之光）
命运之光
185 0
算法修炼之练气篇——练气二十一层
命运之光
|
人工智能 算法 Go
算法修炼之练气篇——练气二十二层
每天练习五道题，炼气篇大概会练习200道题左右，题目有C语言网上的题，也有洛谷上面的题，题目简单适合新手入门。（代码都是命运之光自己写的，练完这200多道题就考了今年第十四届的B组蓝桥杯C/C++获得了省一，后面还会更新“算法修炼之筑基篇”里面包括了省赛到国赛这一个月训练的刷奖计划，大概有40道左右，感兴趣的话可以关注一下命运之光）
命运之光
227 0
命运之光
|
算法 C语言 C++
算法修炼之练气篇——练气二十层
每天练习五道题，炼气篇大概会练习200道题左右，题目有C语言网上的题，也有洛谷上面的题，题目简单适合新手入门。（代码都是命运之光自己写的，练完这200多道题就考了今年第十四届的B组蓝桥杯C/C++获得了省一，后面还会更新“算法修炼之筑基篇”里面包括了省赛到国赛这一个月训练的刷奖计划，大概有40道左右，感兴趣的话可以关注一下命运之光）
命运之光
120 0
命运之光
|
算法 C语言 C++
算法修炼之练气篇——练气十九层
每天练习五道题，炼气篇大概会练习200道题左右，题目有C语言网上的题，也有洛谷上面的题，题目简单适合新手入门。（代码都是命运之光自己写的，练完这200多道题就考了今年第十四届的B组蓝桥杯C/C++获得了省一，后面还会更新“算法修炼之筑基篇”里面包括了省赛到国赛这一个月训练的刷奖计划，大概有40道左右，感兴趣的话可以关注一下命运之光）
命运之光
128 0
命运之光
|
机器学习/深度学习 算法 C语言
算法修炼之练气篇——练气十八层
每天练习五道题，炼气篇大概会练习200道题左右，题目有C语言网上的题，也有洛谷上面的题，题目简单适合新手入门。（代码都是命运之光自己写的，练完这200多道题就考了今年第十四届的B组蓝桥杯C/C++获得了省一，后面还会更新“算法修炼之筑基篇”里面包括了省赛到国赛这一个月训练的刷奖计划，大概有40道左右，感兴趣的话可以关注一下命运之光）
命运之光
132 0
命运之光
|
算法 C语言 C++
算法修炼之练气篇——练气十七层
每天练习五道题，炼气篇大概会练习200道题左右，题目有C语言网上的题，也有洛谷上面的题，题目简单适合新手入门。（代码都是命运之光自己写的，练完这200多道题就考了今年第十四届的B组蓝桥杯C/C++获得了省一，后面还会更新“算法修炼之筑基篇”里面包括了省赛到国赛这一个月训练的刷奖计划，大概有40道左右，感兴趣的话可以关注一下命运之光）
命运之光
108 0
命运之光
|
算法 数据安全/隐私保护 C语言
算法修炼之练气篇——练气十五层
每天练习五道题，炼气篇大概会练习200道题左右，题目有C语言网上的题，也有洛谷上面的题，题目简单适合新手入门。（代码都是命运之光自己写的，练完这200多道题就考了今年第十四届的B组蓝桥杯C/C++获得了省一，后面还会更新“算法修炼之筑基篇”里面包括了省赛到国赛这一个月训练的刷奖计划，大概有40道左右，感兴趣的话可以关注一下命运之光）
命运之光
95 0
命运之光
|
算法 C语言 C++
算法修炼之练气篇——练气十四层
每天练习五道题，炼气篇大概会练习200道题左右，题目有C语言网上的题，也有洛谷上面的题，题目简单适合新手入门。（代码都是命运之光自己写的，练完这200多道题就考了今年第十四届的B组蓝桥杯C/C++获得了省一，后面还会更新“算法修炼之筑基篇”里面包括了省赛到国赛这一个月训练的刷奖计划，大概有40道左右，感兴趣的话可以关注一下命运之光）
命运之光
152 0

热门文章

最新文章

  • 1
    【数据结构与算法】一篇文章彻底搞懂二分查找（思路图解+代码优化）两种实现方式，递归与非递归
  • 2
    算法学习之顺序结构
  • 3
    泛型KMP算法
  • 4
    OneMob（一体传媒）：大数据算法 让营销更精准
  • 5
    【算法】算法之美—Fire Net
  • 6
    Node.js使用jsrsasign实现SHA256withRSA加密算法
  • 7
    【编程练习】收集的一些c++代码片，算法排序，读文件，写日志，快速求积分等等
  • 8
    字符串相似度算法 递归与动态规划求解分析
  • 9
    【算法研究】Bresenham画线算法
  • 10
    算法导论第十四章 数据结构的扩张
  • 1
    算法：位运算
    37
  • 2
    算法：双指针
    52
  • 3
    基于harris角点和RANSAC算法的图像拼接matlab仿真
    91
  • 4
    m基于遗传优化的LDPC码NMS译码算法最优归一化参数计算和误码率matlab仿真
    76
  • 5
    深入浅出JVM（十三）之垃圾回收算法细节
    53
  • 6
    深入浅出JVM（十二）之垃圾回收算法
    44
  • 7
    常见的算法排序（2）
    46
  • 8
    数据结构与算法 动态规划(启发式搜索、遗传算法、强化学习待完善)
    98
  • 9
    数据结构与算法 回溯
    36
  • 10
    数据结构与算法 分治
    39

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍

    • 相关电子书

    更多
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台
  • 阿里技术参考图册-算法篇

    • 相关实验场景

    更多
  • 推荐系统入门之使用ALS算法实现打分预测
  • 欧拉图的构造性证明与算法实现
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 使用Swing算法实现商品推荐
    • 下一篇
    阿里云OSS设置跨域访问