P3370 【模板】字符串哈希
题目描述
如题，给定 N 个字符串（第 i 个字符串长度为 Mi，字符串内包含数字、大小写字母，大小写敏感），请求出 N 个字符串中共有多少个不同的字符串。
友情提醒：如果真的想好好练习哈希的话，请自觉。
输入格式
第一行包含一个整数 N，为字符串的个数。
接下来 N 行每行包含一个字符串，为所提供的字符串。
输出格式
输出包含一行，包含一个整数，为不同的字符串个数。
输入输出样例
输入 #1复制
5 abc aaaa abc abcc 12345
输出 #1复制
4
说明/提示
数据范围
对于 30% 的数据：N≤10，Mi≈6，Mmax≤15。
对于 70% 的数据：N≤1000，Mi≈100，Mmax≤150。
对于 100% 的数据：N≤10000，Mi≈1000，Mmax≤1500。
样例说明
样例中第一个字符串 abc 和第三个字符串 abc 是一样的，所以所提供字符串的集合为 {aaaa,abc,abcc,12345}，故共计 4 个不同的字符串。
拓展阅读
以下的一些试题从不同层面体现出了字符串哈希算法的正确性分析。
- P12197 Hash Killer I
- P12198 Hash Killer II
- P12199 （目前无解）Hash Killer III
- P12200 Hash Killer Extra
- P12201 Hash Killer Phantasm
- P7350 「MCOI-04」Dream and Strings
#include<iostream> #include<string> #include<map> using namespace std; map <string, int> mp; int main() { int n; cin >> n; while (n--) { string s; cin >> s; mp[s]++; } cout << mp.size(); return 0; }P1102 A-B 数对
题目背景
出题是一件痛苦的事情！
相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！
题目描述
给出一串正整数数列以及一个正整数 C，要求计算出所有满足 A−B=C 的数对的个数（不同位置的数字一样的数对算不同的数对）。
输入格式
输入共两行。
第一行，两个正整数 N,C。
第二行，N 个正整数，作为要求处理的那串数。
输出格式
一行，表示该串正整数中包含的满足 A−B=C 的数对的个数。
输入输出样例
输入 #1复制
4 1 1 1 2 3
输出 #1复制
3
说明/提示
对于 75% 的数据，1≤N≤2000。
对于 100% 的数据，1≤N≤2×105，0≤ai<230，1≤C<230。
2017/4/29 新添数据两组
#include<iostream> #include<unordered_map> using namespace std; typedef long long LL; const int N = 2e5 + 10; LL arr[N]; //直接开数组不行，要用map unordered_map <LL,LL> mp; int main() { LL n, c; cin >> n >> c; LL cnt = 0; for (int i = 1;i <= n;i++) cin >> arr[i]; for (int i = 1;i <= n;i++) { //不同位置的数字一样的数对算不同的数对 cnt += mp[arr[i] - c]; //可以是B=A-C //也可以是B=A+C，即A=B-C cnt += mp[arr[i] + c]; //标记出现过的数 mp[arr[i]]++; } cout << cnt; return 0; }P1059 [NOIP 2006 普及组] 明明的随机数
题目描述
明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 N 个 1 到 1000 之间的随机整数 (N≤100)，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。
输入格式
输入有两行，第 1 行为 1 个正整数，表示所生成的随机数的个数 N。
第 2 行有 N 个用空格隔开的正整数，为所产生的随机数。
输出格式
输出也是两行，第 1 行为 1 个正整数 M，表示不相同的随机数的个数。
第 2 行为 M 个用空格隔开的正整数，为从小到大排好序的不相同的随机数。
输入输出样例
输入 #1复制
10 20 40 32 67 40 20 89 300 400 15
输出 #1复制
8 15 20 32 40 67 89 300 400
说明/提示
NOIP 2006 普及组 第一题
用set，自带排序和去重功能。
#include<iostream> #include<set> using namespace std; set <int> arr; int main() { int m; cin >> m; while (m--) { int x; cin >> x; arr.insert(x); } cout << arr.size() << endl; for (auto e : arr) cout << e << " "; cout << endl; return 0; }P1957 口算练习题
题目描述
王老师正在教简单算术运算。细心的王老师收集了 i 道学生经常做错的口算题，并且想整理编写成一份练习。编排这些题目是一件繁琐的事情，为此他想用计算机程序来提高工作效率。王老师希望尽量减少输入的工作量，比如 5+8 的算式最好只要输入 5 和 8，输出的结果要尽量详细以方便后期排版的使用，比如对于上述输入进行处理后输出 5+8=13 以及该算式的总长度 6。王老师把这个光荣的任务交给你，请你帮他编程实现以上功能。
输入格式
第一行一个整数 i。
接着的 i 行为需要输入的算式，每行可能有三个数据或两个数据。
若该行为三个数据则第一个数据表示运算类型，a 表示加法运算，b 表示减法运算，c 表示乘法运算，接着的两个数据表示参加运算的运算数。
若该行为两个数据，则表示本题的运算类型与上一题的运算类型相同，而这两个数据为运算数。
输出格式
输出 2×i 行。对于每个输入的算式，输出完整的运算式及结果，第二行输出该运算式的总长度。
输入输出样例
输入 #1复制
4 a 64 46 275 125 c 11 99 b 46 64
输出 #1复制
64+46=110 9 275+125=400 11 11*99=1089 10 46-64=-18 9
说明/提示
【数据规模与约定】
对于 50% 的数据，输入的算式都有三个数据。
对于所有数据，0<i≤50，第一个算式一定有三个数据，运算数为非负整数且小于 10000。
#include<iostream> #include<string> using namespace std; string input, ret, num1, num2; char ope, last_ope; typedef long long LL; LL num; int main() { int n; cin >> n; int i; //清除缓冲区中残留的换行符 cin.ignore(); while (n--) { //如果直接cin>>input，遇到空格就会停止，所以要用getline getline(cin, input); int n = input.size(); if (input[0] == 'a' || input[0] == 'b' || input[0] == 'c') { ope = input[0]; i = 2; last_ope = ope; } else { ope = last_ope; i = 0; } //处理num1和num2 while (input[i] != ' ') { num1.push_back(input[i]); i++; } i++;//跳过空格 while (i < n) { num2.push_back(input[i]); i++; } //处理ret if (ope == 'a') { num = stoll(num1) + stoll(num2); ret = num1 + '+' + num2 + '=' + to_string(num); } else if (ope == 'b') { num = stoll(num1) - stoll(num2); ret = num1 + '-' + num2 + '=' + to_string(num); } else { num = stoll(num1) * stoll(num2); ret = num1 + '*' + num2 + '=' + to_string(num); } cout << ret << endl; cout << ret.size() << endl; //一定不要忘了清空，否则会直接在原字符串追加，答案错误！ num1.clear(); num2.clear(); num = 0; ret.clear(); } return 0; }
