A:(https://ac.nowcoder.com/acm/contest/67865/A)
本题考察判断输入是否结束,注意数据范围
#include <iostream>
using namespace std;
int main() {
long long a, b;
while(cin >> a >> b)
{
cout << a + b << endl;
}
return 0;
}
import sys
while True:
s = sys.stdin.readline()
if not s:
break
a, b = map(int, s.split(" "))
print(a + b)
时间复杂度: 在于题目有多少组输入
空间复杂度: O(1)
E:(https://ac.nowcoder.com/acm/contest/67865/E)
贪心、排序
选任意两个玩具,价格高的玩具一定要买,也就是玩具价格次大的可以免单,因此每次选玩具一定要选价格高但不是最高的玩具x和比它价格高的玩具y,直到玩具都选完了,不妨先按递增排序,从后往前遍历即可
遇事不慌先排序哈(啦啦啦)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int n;
cin >> n;
vector<int>nums(n);
for(int i = 0; i < n; i += 1)
{
cin >> nums[i];
}
sort(nums.begin(),nums.end(),[&](int a, int b){return a > b;});
long long ans = 0;
for(int i = 0; i < n; i += 2)
{
ans += nums[i];
}
cout << ans << endl;
}
n = int(input())
nums = list(map(int, input().split(" ")))
nums.sort()
print(sum(nums[i] for i in range(n - 1, -1, -2)))
时间复杂度: O(nlogn) 排序nlogn
空间复杂度: O(n)
I:(https://ac.nowcoder.com/acm/contest/67865/I)
模拟、排序、哈希
前置知识,哈希计数
用哈希表统计英文字母的出现次数,再按asill值从小到大排序
注意输入可能有空格,可以用getline(cin, s)
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<unordered_map>
using namespace std;
int main()
{
string s;
getline(cin, s);
unordered_map<char, int>mp;
int mx = 0;
for(auto c:s)
{
if(c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z')
{
mp[c] += 1;
mx = max(mp[c], mx);
}
}
vector<char>res;
for(auto x:mp)
{
if(x.second == mx) res.push_back(x.first);
}
sort(res.begin(), res.end());
cout << res[0] << endl;
return 0;
}
from collections import defaultdict
s = input()
mp = defaultdict(int)
for x in s:
if 'a' <= x <= 'z' or 'A' <= x <= 'Z':
mp[x] += 1
mx = max(mp.values())
res = []
for key in mp.keys():
if mp[key] == mx:
res.append(key)
res.sort()
print(res[0])
时间复杂度: O(n)
空间复杂度:O(1) 最有52个字母出现次数都一样
J:(https://ac.nowcoder.com/acm/contest/67865/J)
小丑题
数据范围很大,找质数最快O(n),预处理数组都开不了,从 x mod (x - i) 考虑
x 是质数, 它的因子只有 1 和 x,x - i < x,所以要想输出 YES, 要满足 x = i + 1,质数增长太快了,只有当 i <= 2 时, x = i + 1
#include <iostream>
using namespace std;
int main() {
long long i;
cin >> i;
cout << (i <= 2 ? "YES" : "NO") << endl;
return 0;
}
i = int(input())
print("YES" if i <= 2 else "NO")