当前位置：首页 > news >正文

【C++】 —— 笔试刷题day_17

news 2026/6/1 12:29:58

一、小乐乐改数字

题目解析

这道题，它们给定一个数，我们要对它进行修改；如果某一位是奇数，就把它变成1,；如果是偶数，就把它变成0；
让我们输出最后得到的数。

算法思路

这道题，总体来说是非常简单的啦，解法呢，就是模拟整个过程。

当然呢这里模拟，也不是去一次去这个数的某一位去操作，那太麻烦了。

我们可以直接按照字符串进行输出，然后遍历字符串，判断这一个数是奇数还是偶数，然后进行操作。
这里我们通过查看ASSIC码可以发现，字符0到9数字0到9它的奇偶性是一样的，所以我们进行判断时就不用去-'0'了

最后呢我们需要取出前缀0，这里可以使用stoi函数，也可以自己实现去除前缀0。

代码实现

#include<iostream>#include<string>usingnamespacestd;string str;intmain(){cin>>str;for(inti=0;i<str.size();i++){if(str[i]%2==0)str[i]='0';elsestr[i]='1';}cout<<stoi(str)<<endl;return0;}

二、十字爆破

题目解析

OK啊，这道题输入一个n*m的二维数组，让我们求它每一个位置方格的得分情况，最后输出。
得分规则：arr[i][j]位置的得分等于第i行和第j列所有数的和。

算法思路

题目描述很简单，现在我们来看如何去解决这道问题；

首先暴力解法，当我们求某一个位置的得分时，去遍历它这一行和这一列所有的数，然后求和。（这里肯定会超时）

暴力解法不行，那我们来想一想有没有什么可以优化的：

我们在求(i,j)位置时，要用到第i行所有数的和；在求(i,j-1)位置时，也要用到第i行所有数的和；
那我们是不是可以预先将每一行/每一列所有数的和求出来，这样我们在求某一个位置的得分时就不用去遍历了。
**OK啊，这里我们的思路就出来了：**就是先将每一行/每一列所有数的和求出来，然后求(i,j)位置的和直接用第i行的和加上第j列的和，再减去i,j位置的数就可以了。（这里第i行会计算一遍(i,j)位置，第j列也会计算(i,j)位置，所有要减去一个(i,j)位置的值）。

代码实现

#include<iostream>usingnamespacestd;constintN=1e6+10;intn,m;longlongrow[N];longlongcol[N];intmain(){scanf("%ld %ld",&n,&m);longlongarr[n][m];for(inti=0;i<n;i++){for(intj=0;j<m;j++){scanf("%ld",&arr[i][j]);row[i]+=arr[i][j];col[j]+=arr[i][j];}}//记录完成以后输出for(inti=0;i<n;i++){for(intj=0;j<m;j++){printf("%ld ",row[i]+col[j]-arr[i][j]);}printf("\n");}return0;}

三、比那名居的桃子

题目解析

题目描述：小红想要吃桃子，吃完桃子以后每天可以获得ai的快乐值，获得bi个羞耻值，桃子效果可以持续k天。
现在我们要求，小红在哪一天吃桃子可以获得尽可能多的快乐值；（如果快乐值相等，就让羞耻值尽可能小）。

算法思路

对于这道题，我们可以使用暴力解法，遍历数组，遍历到i位置时，求一下从i位置开始k天的快乐值和羞耻值。

对于暴力解法，我们就要进行优化：

滑动窗口：

我们在求从i位置开始和从i+1位置开始时，这两个区间的差别就是i位置和i+k位置；
所以我们在处理求i+1位置开始时，只需要让i位置开始求出的值减去i位置，加上i+k位置即可。
这里我们需要记录区间内快乐值的和hSum，也要记录区间内羞耻值的和sSum；还要记录一下当前快乐值的最大值hMax和当前羞耻值的最小值sMin。
入窗口：让hSum加上right位置的快乐值，sSum加上right位置的羞耻值。
判断：当区间的长度大于k时，进行出窗口操作（进行一次即可，这里我们要维持区间长度为k）
出窗口：让hSum减去left位置的快乐值，sSum减去left位置的羞耻值；left++即可。
更新结果：，当区间长度等于k时，进行更新结果操作，这里我们更新不止是hSum > hMax时进行更新，当hSum == hMax && sSum < sMin时，我们也要更新结果。

当然对于这道题，我们还可以使用前缀和来解决：

通过暴力解法和优化的滑动窗口，我们可能发现，我们需要从i位置开始，k个数据的和；

那我们能不能先求出来这个和呢？

我们对于h和s数组，分别创建一个对应的hSum和sSum数组，这两个数组中存放的就是每一个位置之前所有数的和。
hSum[i]：i位置之前h中所有数的和；
sSum[i]：i位置之前s中所有数的和；
这里我们在遍历i位置时，我们可以直接拿到从i位置开始k个数据的和numh（numh = hSum[i+k-1] - hSum[i-1]）和nums（nums = sSum[i+k-1] - sSum[i-1]）。
这样我们遍历是时候，取到numh和nums然后判断更新结果就好了。

这需要注意，我们在遍历i位置时，需要用到i-1位置和i+k-1位置，所以我们从1开始遍历，直到n-k（[1 , n-k+1])

这样对于大于n-k+1小于等于n的位置的数据，从这些位置开始，后面是没有k个数据的。

代码实现

滑动窗口：

#include<iostream>usingnamespacestd;constintN=1e5+10;longlongn,k;longlongh[N+1],s[N+1];longlonghSum[N+1],sSum[N+1];intmain(){//滑动窗口cin>>n>>k;for(inti=1;i<=n;i++)cin>>h[i];for(inti=1;i<=n;i++)cin>>s[i];intleft=1,right=1;longlonghSum=0,sSum=0,hMax=0,sMin=0;intret=0;while(right<=n){hSum+=h[right];sSum+=s[right];while(right-left+1>k){hSum-=h[left];sSum-=s[left];left++;}if(right-left+1==k){//更新结果if((hSum>hMax)||(hSum==hMax&&sSum<sMin)){ret=left;hMax=hSum;sMin=sSum;}}right++;}cout<<ret<<endl;return0;}

前缀和：

#include<iostream>usingnamespacestd;constintN=1e5+10;longlongn,k;longlongh[N+1],s[N+1];longlonghSum[N+1],sSum[N+1];intmain(){//前缀和cin>>n>>k;for(inti=1;i<=n;i++){cin>>h[i];hSum[i]=hSum[i-1]+h[i];}for(inti=1;i<=n;i++){cin>>s[i];sSum[i]=sSum[i-1]+s[i];}intret=0;longlonghMax=0,sMin=0;for(inti=1;i<=n-k+1;i++){longlongnumh=hSum[i+k-1]-hSum[i-1];longlongnums=sSum[i+k-1]-sSum[i-1];if((numh>hMax)||(numh==hMax&&nums<sMin)){ret=i;hMax=numh;sMin=nums;}}cout<<ret<<endl;return0;}