权威的扬中网站建设,中国机械加工网网址,烟台市建设工程交易中心网站,成都软件培训机构排名前十UVA156 反片语 解题报告 题目链接
https://vjudge.net/problem/UVA-156
题目大意
输入一些单词#xff0c;找出所有满足如下条件的单词#xff1a;该单词不能通过字母重排#xff0c;得到输入文本中的另外一个单词。在判断是否满足条件时#xff0c;字母不分大小写… UVA156 反片语 解题报告
题目链接
https://vjudge.net/problem/UVA-156
题目大意
输入一些单词找出所有满足如下条件的单词该单词不能通过字母重排得到输入文本中的另外一个单词。在判断是否满足条件时字母不分大小写但在输出时应保留输入中的大小写按字典序进行排列所有大写字母在所有小写字母的前面。
解题思路
很显然要用map进行计数题目的要求是“该单词不能通过字母重排得到输入文本中的另外一个单词。在判断是否满足条件时字母不分大小写”也就是在忽略大小写的情况下每个单词的字母构成一样则算重复要找出所有不重复的单词。所以我们在用map进行计数的时候要先将单词“标准化”将其都转换为小写字母可以适用C内置的函数tolower()然后再将其按照字典序从小到大sort一遍再放入map。把所有单词统计完之后检查所有的单词检查每个单词的“标准化”是否在map中只统计了一次是的话就放入答案列表。
代码
#include bits/stdc.h
using namespace std;
using ll long long;
using ull unsigned long long;
using ld long double;
#define endl \n;
const int maxn 1e3 10;
const int INF 0x3fffffff;
const int mod 1e9 7;
mapstring, int cnt;
vectorstring words;// 标准化
string change(string str) {string res str;for (int i 0; i res.size(); i) {res[i] tolower(res[i]); // 都变成小写字母}sort(res.begin(), res.end()); // 字典序排序return res;
}void solve() {string s;// 输入、统计while (cin s) {if (s[0] #)break;words.push_back(s); // 放入原单词列表string s1 change(s); // 得到标准化后的字符串if (!cnt.count(s1)) // 将标准化后的字符串放入map中统计cnt[s1] 0;cnt[s1];}// 找出答案vectorstring ans;for (string str : words) {string s1 change(str);if (cnt[s1] 1) {ans.push_back(str);}}// 将答案排序并输出sort(ans.begin(), ans.end());for (string str : ans) {cout str endl;}
}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout fixed;cout.precision(18);int Case 1;// cin Case;while (Case--)solve();return 0;
}
