1.链接:https://ac.nowcoder.com/acm/contest/11228/A
你可以选择一个奇数和一个偶数,使他们的和尽可能的大,但是要小于nn。 请问他们的和最大为多少。 奇数:不是二的倍数。 偶数:二的倍数。 输入描述: 输入一个正整数nn,4\leq n\leq 10^94≤n≤10 9 输出描述: 输出一个整数代表答案。 示例1 输入4 输出3 说明: 可以选择11和22 他们的和为33并且3<43<4。
分析:(这道题很是简单,有两种理解方法)
1.题目要求之和最大,并且要求小于当前的这个数,分析一下,偶数只能分成两个偶数或 者两个奇数,而技术只能分成一个奇数,一个偶数,而题目又有要求分成的两个数,一个奇数一个偶数,那 答案不就直接出来了,如果输入的是偶数,则答案直接是此数减一;如果输入的是奇数,则答案是次数减 二; 2.可以让这个数直接除以二,得到的那个数就是答案中的偶数,奇数就是偶数减一,因为要是加一个话得到 的值就会大于原来的那个数。
源码:(1)
#include <iostream> using namespace std; int main() { int a; cin>>a; if(a%2==0) { cout<<a-1<<endl; } if(a%2!=0) { cout<<a-2<<endl; } return 0; }
(2)
#include <iostream> using namespace std; int main() { int a; cin>>a; int b=a/2; int c=b+b-1; cout<<c<<endl; return 0; }
2.https://ac.nowcoder.com/acm/contest/11228/B
直接放网址吧。
分析:
首先分析题目,数组中有0,要把零变成任意正整数,并且保证,最后数组的和最小。 所以我们只需要遍历一遍,碰见0,就把0变成比前一项大一就行了,这样就能保证,它最后的和是最小的 要注意的是,当第一项为0时,要手动变为1。 如果碰见前一项大于后一项的就返回-1,如果没有就加上它; 最后输出就可以了。
源码:
#include <iostream> using namespace std; int arr[101]; int n; int main() { int count=0; cin>>n; for(int i=0;i<n;i++) { cin>>arr[i]; } if(arr[0]==0) { arr[0]=1; } count+=arr[0]; for(int i=1;i<n;i++) { if(arr[i]==0) { arr[i]=arr[i-1]+1; }else{ if(arr[i]<=arr[i-1]) { cout<<-1<<endl; return 0; } } count+=arr[i]; } cout<<count<<endl; return 0; }
3.https://ac.nowcoder.com/acm/contest/11228/C
分析:
这道题呢,有一点点“小南”,题目说最后x是偶数,并且x的值是输入进去的,注意一下,第一,他们一次 消去的是相同的两个数,并且是相邻的,如果原本长度是奇数,那么就不可能到最后是偶数;第二,如果 给定的0、1个数还没有最后指定留下来的多,那么也不可能;第三,如果前两个满足的话,你还要判断一 下,他们的长度减去要求留下的x/2之后,他们是不是偶数,如果不是那么同时不可能经过n次消除,能消 除完,剩要保留的个数。
源码:
#include <iostream> using namespace std; int main() { int a,b,x; cin>>a>>b>>x; x=x/2; if((a+b)&1||a<x||b<x) { cout<<-1<<endl; return 0; } a=a-x; b=b-x; if(a&1||b&1) { cout<<-1<<endl; return 0; } for(int i=0;i<a;i++)cout<<"0"; for(int i=0;i<b;i++)cout<<"1"; for(int i=0;i<x;i++)cout<<"01"; return 0; }
4.https://www.acwing.com/problem/content/4431/
分析:
这道题不难,但是我还是花了很长时间,思路很简单,第一步判断输入的长度是不是大于等于26,小于的 话直接输出NO;第二步就是大小写统一;第三步用map函数存值,key为字母,value为出现的次数,map函数的特点就是,碰见map中没有的直接存进去,并且value+1,如果有 value直接+1;难点就在于我这些函数不熟悉。
源码:
#include <bits/stdc++.h> using namespace std; int main() { int n; cin>>n; if(n<26&&n>0) { cout<<"NO"<<endl; return 0; } string s; cin>>s; map<char , int> mp; for(int i=0;i<n;i++) { if(s[i]>=65&&s[i]<=90) { s[i]=tolower(s[i]); } } for(int i=0;i<n;i++) { mp[s[i]]++; } if(mp.size()==26) { cout<<"YES"<<endl; }else{ cout<<"NO"<<endl; } return 0; }
分析:
这道题是很简单的,题目已经把规律给得很清楚了,创建一个新的数组,这个数组的长度是原数组的一半,每次你处理的时候乘以2就可以了,再判断一下,当前是第几个数对分一下是求最小值还是最大值,最后把这个数组赋值给原数组,再次进入循环,直到长度为1时,退出循环即可。最后输出为一个一个元素,即是答案。
源码:(我最大的坑就是while那里写成了if,最后还是调试的时候看出来的,cao!废了很长时间)
#include <bits/stdc++.h> using namespace std; int main() { vector<int> nums={1,3,5,2,4,8,2,2}; (这个是我在本地调试的时候直接放数据了) while(nums.size()>1)(判断条件) { vector<int> num(nums.size()/2,0);(每次创建一个新数组) for(int i=0;i<nums.size()/2;i++) { if(i%2==0) { num[i]=min(nums[i*2],nums[i*2+1]); }else{ num[i]=max(nums[i*2],nums[i*2+1]); } } nums=num; } cout<<nums[0]<<endl; return 0; }
分析:
这道题就有点小绕脑子了,这道题的简单之处在于没有让你那最后的结果输出出来,只用输出有几个数组满足条件就行了。简单分析一下,它说了那么多,无非就是,求这个数组可以分为几个长度为k的子数组,本人再看这道题时,想复杂了,用来map函数,但其实不用这么复杂, 很显然,一眼贪心。因为能凑成一组的尽可能地都塞进一组中,这样是更优的。 从最大值来看,对于全局最大值 max,我一定会让所有在 [max−k,max] 之间的值分为一组。
源码:
class Solution { public: int partitionArray(vector<int>& nums, int k) { sort(nums.begin(),nums.end()); int n=nums.size(); int count=1; int a=nums[0],b=0;(记录一下最小值,另外定义一个中间变量) for(int i=0;i<n;i++) { if(nums[i]-a<=k) continue;(差值在k之间的不用管) else{ (如果不在,则要变一下当前最小值,记录一下值) a=nums[i]; count++; } } return count; } };