笔试练习day3

目录

• BC149 简写单词
• • 题目解析
  • • 代码
• dd爱框框
• • 题目解析
  • • 解析
    • 代码
    • • 方法一暴力解法
      • 方法二同向双指针(滑动窗口)
• 除2!
• • 题目解析
  • • 解法
    • • 模拟+贪心+堆

感谢各位大佬对我的支持,如果我的文章对你有用,欢迎点击以下链接
🐒🐒🐒 个人主页
🥸🥸🥸 C语言
🐿️🐿️🐿️ C语言例题
🐣🐣🐣 python
🐓🐓🐓 数据结构C语言
🐔🐔🐔 C++
🐿️🐿️🐿️ 文章链接目录
🏀🏀🏀 笔试练习题

BC149 简写单词

链接添加链接描述

题目解析

这道题就是提取一句话中每个单词的首字母,并且将他们的首字母用大写的形式输出,这里的难点就在于每个单词是通过空格分隔开的,在输入的时候如果用scanf和cin直接输入的话会因为有空格而丢失后面的数据
解决这个难点的第一个方法是用getline输入,getline输入是遇到’\n’才停止,也就是遇到回车键才结束,这样就不会因为有空格而丢失数据了,后面过程就是通过循环去找空格出现的位置,然后空格的下一个位置就是单词的首字母
第二个方法就是用string去解决(这个解法就是通过循环直接往string中输入字符串,然后每次循环输出输入的字符串首字母)

代码

int main() { string s; while(cin>>s) {     if(s[0]<='z'&&s[0]>='a')     {         s[0]=s[0]-32;     }     cout<<s[0]; }     return 0; } 

dd爱框框

链接dd爱框框

题目解析

这道题的意思是在1到n的区间里我们要求出里面的最小区间,使得区间里的所有数加起来大于或等于x,比如区间[1,5]意思就是从arr[1]开始一直到arr[5]的所有数据,[5,8]就表示从arr[5]到arr[8],需要注意这里的n个数是从1开始的,所以用数组的时候我们要先从1开始输入

解析

我们以图中示例为例

输出3 5表示区间[3,5]中的所有数据加起来大于等于x,且这个区间的长度相比于后面的区间长度来说是最小的

代码

方法一暴力解法

暴力解法就是给一个left和right让right和left相加,当结果大于等于x的时候就记录下来

这里的范围是[1,5],然后left往后移动,之后right=left,然后right往后走

方法二同向双指针(滑动窗口)

这个方法是在方法一的基础上进行优化
比如left在1的时候,范围是[1,5],在这个范围的总和为27,之后left++
但是right是没有必要重新会到left位置再往后去确定范围,因为left在a[1]的时候right在a[5]是刚好满足条件的,那么left++后来到a[2]时[2,5]的所以数总和只会比[1,5]少一个a[1],所以只需要在[1,5]总和减去一个a[1]就可以了

然后判断减去a[1]后[2,5]是否满足>=x的条件
这个方法的流程如下

#include<iostream> using namespace std; const int N=1e7+10; int arr[N]; int n,x; int main() {     cin>>n>>x;     for(int i=1;i<=n;i++)          cin>>arr[i];     int left=0,right=0,sum=0;     int retLen=N,retLeft=-1,retRight=-1;     while(right<=n)     {         sum+=arr[right];         while(sum>=x)         {             if(right-left+1<retLen)             {                 retLeft=left;                 retRight=right;                 retLen=right-left+1;             }             sum-=arr[left++];         }         right++;     }     cout<<retLeft<<" "<<retRight<<endl;     return 0; } 

这里有一些细节就是我们将N arr[N] n x都定义成全局变量,这样做的好处是有些题可能会封装一些函数,需要传入这些数据,当我们把他定义成全局变量的时候,就可以不用传参了

此外N=1e7+10让N有足够大

内部的while循环是为了让retLen足够小,让减去一次arr[left]的时候,如果sum仍然大于x,那么就继续减,直到刚好小于x

除2!

链接除2!

题目解析

这道题就是每次操作选取最大的偶数进行砍半,使所以数相加最小

解法

模拟+贪心+堆

#include<iostream> #include<queue> using namespace std;     typedef long long LL; LL n,k; priority_queue<LL> heap; int main() {     cin>>n>>k;     LL sum=0,x;     while(n--)     {         cin>>x;         sum+=x;         if(x%2==0)             heap.push(x);     }     while(heap.size()&&k--)     {         LL t=heap.top()/2;         heap.pop();         sum-=t;         if(t%2==0)             heap.push(t);     }     cout<<sum;     return 0; } 

需要注意这里k和ai的范围都是[1,10^9],并且n的范围是[1,10 ^5],因为要让n个数累加,最后的结果肯定是超过int的最大值的,所以我们用int类型显然是不行的,因此要用longlont,代码中用typedef将longlong命名为LL

priority_queue heap是一个队优先级队列(堆)

第一个while循环是为了让sum将所以的数都加起来,然后如果有偶数,那么就进入堆中

第二个while循环需要先判断堆中是否有元素,当堆里面什么都没有的时候就没有必要继续进行下去了,并且每次循环要让k–,表示操作次数减1

因为是优先级队列,堆顶元素是最大的数,我们用t保留最大数的一半,然后让堆顶元素出堆,之后让sum减去一半这个最大的数,但是我们并不知道t是否还是偶数(t如果一开始是2,2/2=1就变成了奇数,而t如果是4…这些偶数,4/2=2),所以需要再对t进行判断,如果还是偶数那么就继续入堆,然后重复操作