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")

时间复杂度: O(1)

空间复杂度:O(1)

又活一天,略略略