24年-3月-第一组

P1047 ★★

校门外的树：指定轴上树的数量，指定地铁区域数目，输入区间收尾，返回剩余的数目

思路

循环遍历三遍

第一遍，给所有树打上未砍伐标记0
第二遍，从各个区间首位开始循环，打上已砍伐的标记1
第三遍，从头顺序访问所有的树，若未砍伐，则计数+1。

总结

多维数组的定义不够熟练，没有标记+遍历计数的思维；
定义双重循环数组一定不要重复使用i；

P1085★★★

不高兴的津津：七天，每行（天）两个数据（校内课程时间+妈妈安排时间），每天上课时间超过八小时会不高兴，输出最不高兴的一天（排序要有稳定性）

思路1

得到每天的上课总时长；
用排序算法进行排序；
输出排序最高的数的下标，即周几？怎么实现？？

思路2

使用day和max两个变量，day的初始值全部为0，若sum>8,则更改day的值为i；

总结

理解上仍然不到位

    for(int i=1;i<=7;i++){
        cin>>a>>b;
        sum=a+b;
        if(sum>max&&sum>8) {
                max=sum;day=i;  //选出最不高兴的一天
        }
    }

这段代码很精简的得到了最不高兴的一天。

P1089★★★

津津的储蓄计划：津津每月有零花钱三百，如果估计花完当月预算还剩有整百的钱，要判断会哪个月首次出现预算不够的情况；若没有，则计算年末津津加上利息的余额；

思路1

我的思路（错解）

int main(){
    int a[12];  //存放每个月的预算
    int sum=0; //记录津津手中的钱
    int deposit=0;  //记录津津储蓄的钱
    for(int i=1;i<=12;i++){
        sum+=300;  //月初妈妈给300
        cin>>a[i];  //读入每个月的预算
        sum-=a[i];
        if(sum<0)   {cout<<"-"<<i;break;}
        if(sum>100) {sum-=100;deposit+=100;}
        if(sum>200) {sum-=200;deposit+=200;}
        if(sum>300) {sum-=300;deposit+=300;}
    }
    if(sum>0){
    sum=sum+deposit*1.2;
    cout<<sum;}
    return 0;
}

参考题解

    for(int i=1;i<=12;i++){
        sum+=300;  //月初妈妈给300
        cin>>budget;  //读入每个月的预算
        sum-=budget;
            if(sum<0)
            {
                flag=1;
                monthofdeath = i;
                break;
            }
        deposit+=sum/100;   //取整
        sum%=100;  //取余

总结

对取整和取余的效果理解不到位，这道题目的输出部分有小问题，如果出现了透支，就会结束输入。为了得到能存的整百的张数，直接用余额对100取整：sum/100；为了得到拿掉整百剩余的钱，直接用余额对100取余数: sum%100；

P1150★

peter的烟：设定peter初始拥有的烟的数量，设定k个烟蒂能换一根新烟，计算peter最终能吸到烟的总数。

思路1

用n对k取整数：n/k，表示能用烟蒂换到的新烟的数量；
用n对k取余数，n%k，表示换完烟后剩余的数目；
换完一次新烟，重新计算拥有的烟，再重复上面的步骤，直到不能继续换新烟；

思路2

实际上我的做法是使用while循环：

    while(n>k)
    {
        count+=k;
        n=n-k+1;
    }
    count=count+n;
    cout<<count;

只要拥有的烟数量大于k，就抽k根烟，换1根烟；不用考虑烟蒂的问题；OJ之判定了90分，有一个点没有通过测试；后发现有可能是忘记了等号，n=k也可以换新烟；

总结

还算简单，代码逻辑基本都是自己想出来的；

P1151★

子数整数：输入一个正整数K，找出10000到30000之间所有满足条件的五位数：该数的三个子数都能够被k整除（12345的子数为123 234 345），无解输出No;

思路

通过for循环遍历区间内所有的数，遍历每个数时将其拆分成三个子数
对该数的每个子数进行条件判断，若三个都满足则输出该五位数

总结

整体不难，思路没有太大问题，难点在于对整型与字符串的转换生疏了；还有划分字符串的函数；

引用string库
整型与字符串相互转换：

int a;
string str=to_string(a);	//整型转字符串
int a1=stoi(str);     //字符串转整型

字符串的划分：

string a=str.substr(0,2);   //划分字符串；substr(pos,len)

P1152★★★

欢乐的跳：一个 n个元素的整数数组，如果数组两个连续元素之间差的绝对值包括了 [1,n-1]之间的所有整数，则称之符合“欢乐的跳”，如数组 {1,4,2,3}符合“欢乐的跳”，因为差的绝对值分别为：3,2,1。给定一个数组，你的任务是判断该数组是否符合“欢乐的跳”。

思路

先要解决数组的输入；
循环判断两个元素之间的差值是否为区间内元素；
给区间增加一个标记，默认为0，被标记过为1；若全部被标记则认为该数组符合欢乐的跳；

60分解法

int main()
{
    int n;
    int judge=0;
    cin>>n;
    int flag[n];
    for(int i=0;i<n;i++){   //存放数组内元素的标记
        flag[i]=0;
    }
    int num[n];
    for(int i=0;i<n;i++)  //输入数组
    {
        cin>>num[i];
    }
    for(int i=0;i<n-1;i++)    //判断差值是否在数组内
    {
        int diff=abs(num[i+1]-num[i]);
        flag[diff]=1;   //在数组内，标记为1
    }
    for(int i=1;i<n;i++)
    {
        if(flag[i]==0)    //若有一个不在，则数组不是欢乐的跳
        {
            judge=1;
            break;
        }
    }
    if(judge==1)
    {
        cout<<"Not jolly";
    }
    else
    {
        cout<<"Jolly";
    }
    return 0;
}

修改|总结

问题1：我的上面代码中使用了静态数组来存放num和flag，但是数组的大小n仍然是由用户决定的，如果测试点使用的n非常大，就会造成段访问错误；改用vector动态数组可以有效地避免这方面的错误；
问题2：对flag的访问考虑不周，访问flag使用的数组下标是diff，而diff的值可能会超出flag数组的索引大小范围n，因此要使用diff>n来避免这种行为；
修改的部分如下：

//用动态数组初始化num和flag数组：
Vector<int> flag(n,0);
Vector<int> num(n,0);
//防止访问超出flag数组的索引
if(diff>n)
	{
	cout<<"Not jolly";
	return 0;
	}

P1161★

开灯：对一排无限长的灯进行操作，对a,2xa,3xa,..txa的灯开关各按一次，求开着的那盏灯的编号

思路

初始化灯的标记数组，设定值为0；
取实数的整数部分，在for循环中完成对灯的操作；
每对灯做一次操作，该灯的标记就+1；
最后遍历灯的标记数组，找出做了奇数次操作的那个灯；

总结

通过自己的思路解出来了，先定义了初始值大小，用vector数组num存放灯的状态信息（开启或者关闭，初值为0），每次对灯做出操作后，灯的状态信息就加1，如果最后是偶数次，则灯为关闭的状态；在for循环中直接完成了对灯的所有操作；关键是用操作次数巧妙地表示出灯的状态；技巧总结

向下取整|向上取整|强制换整型|

#include<cmath>
int a=floor(1.68193); //向下取整
int a=ceil(1.120983); //向上取整
int a=static_cast<int> (1.210938); //强制转换成整型

P1179★

数字统计：给定一个指定范围，统计数字2出现的次数，每一位上的2都算；

思路

遍历范围内的所有元素，整型转字符型
对每一位字符型拆分成单个的元素；再进行遍历一次；

总结

又是独立解决的一道题，关键点在于合理的使用string库

字符串转整型|找子串|字符串转整型：

#include<string>
string str=to_string(int i); //字符串转整型
string str1=str.substr(position,length); //找子串
int a=stoi(str); //字符串转整型

P1200★

Your ride is here: 通过一种算法判断小组名是否与彗星的名字匹配，匹配则GO，否则STAY;

思路

读入小组和彗星的字符串
将对应字母转换成数字
算各自字母的积
判断模数是否相等

总结

题目的逻辑还算简单，有几个细节问题需要注意：

拆分字符串的两种方法：

#include<string>
string a="COMETQ";
char b=a.at(0);   //得到char型字符
string c=a.substr(0,a); //得到string型字符串

通过ASCII码计算字母的序号

int num1='Z'-'A'+1;  //大写字母
int num2='v'-'a'+1;  //小写字母

P1304★

哥德巴赫猜想：验证区间内的所有偶数是否符合哥德巴赫猜想；

思路1 10分

关键是要拆分成两质数之和；

for 循环中嵌套for循环
内层for循环判断是否是质数

    for(int i=4;i<=n;i++)
    {
        if(i%2==0)
        {
            for(int j=2;j<=i;j++)
            {
                if(isPrime(j)==true&&isPrime(i-j)==true)
                {
                cout<<i<<"="<<j<<"+"<<i-j<<endl;
                break;
                }
            }
        }
    }

这样做的逻辑很简单，结果应该是正确的，但是缺点特别明显，嵌套的双重for循环中一直在执行判定函数，使得时间复杂度过高，在oj中有多个测试点超时；

思路2

优化时间复杂度：问题可能出在了质数的判断函数上：我做的判断函数,过于啰嗦冗长：

bool isPrime(int n)   //素数的判定
{
    if(n<=1)
        return false;
    if(n==2)
        return true;
    if(n%2==0)
        return false;
    for(int i=3;i*i<=n;i+2)
    {
        if(n%i == 0)
            return false;
    }
    return true;
}

修改后：

bool isPrime(int n)   //素数的判定
{
	for(int i = 2;i * i <= n;i++)//只用枚举到sqrt(n),应该会快一点
	{
		if(n % i == 0)
			return false;
	}
	return true;
}

时间复杂度大大降低

总结

整体思路问题不大，通过不了OJ的主要原因是部分测试点超时，优化的关键是降低素数判定函数的时间复杂度，第二种算法的思路需要重点学习，优化幅度大的可能的原因是精简了很多不必要的条件判断函数。

刷题笔记-24年3月第一组 Created at 2024-03-07 14:57 Updated at 2024-09-14 12:35