P76009 不同字母奇偶 — 题解

专题： 字符串
适用题目： 新生 OJ 本地题包中的 P76009，不要直接用于外站同名题。

解题思路

开一个大小为 26 的出现标记表，出现过的字母只计一次。

复杂度

时间 $O(n+26)$，额外空间 $O(26)$。

易错点

不是统计字符总个数，而是统计不同字母的个数。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

int main(void) {
    static char s[100005]; int seen[26] = {0}, count = 0;
    scanf("%100004s", s);
    for (int i = 0; s[i]; i++) seen[s[i]-'a'] = 1;
    for (int i = 0; i < 26; i++) count += seen[i];
    puts(count%2 ? "ODD" : "EVEN");
    return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin>>s;
    set<char> st(s.begin(),s.end());
    cout<<(st.size()%2?"ODD":"EVEN")<<nl;
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。