差分计数，hash算法

差分计数查看题解 查看答案题目描述Time Limit: 1000 msMemory Limit: 256 mb给定个整数和一个整数。求有多少有序对满足。输入输出格式输入描述:第一行两个整数分别代表整数的个数和题目中的。 第二行个用空格隔开的整数第个代表。输出描述:一行一个整数代表满足的有序对个数。输入输出样例输入样例#:复制5 1 1 1 5 4 2输出样例#:复制3提示(1(1),2(5)),(1(2),2(5)),(5(3),4(4)) 这三个有序对。题目来源华东师范大学2022年机试#includebits/stdc.h using namespace std; long long s[2000005]; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; long long x; while(cin n x){ for(int i 0; i n; i ){ cin s[i]; } sort(s, s n); long long count 0; for(int i 0; i n; i ){ long long target s[i] x; long long num_of_target upper_bound(s, s n, target) - lower_bound(s, s n, target); count num_of_target; } cout count \n; } return 0; }刷出一道墙查看题解 查看答案题目描述Time Limit: 2000 msMemory Limit: 256 mb在一面很长的墙壁上工人们用不同的油漆去刷墙然而可能有些地方刷过以后觉得不好看他们会重新刷一下。有些部分因为重复刷了很多次覆盖了很多层油漆小诺很好奇那些地方被刷过多少种颜色的油漆。输入输出格式输入描述:若干行输入每行两个数字B[i],E[i](0B[i]E[i]200000)表示这次刷的墙壁是哪一段 假设每次刷的时候油漆颜色都和之前的不同以0 0结束 又若干行输入每行两个数字begin[i],end[i]0begin[i]end[i]200000表示小诺询问的段 以0 0结束输出描述:对于每个小诺的询问输出(end[i]-begin[i]1)行,表示对应询问段的每个点被多少种颜色的油漆覆盖过。输入输出样例输入样例#:复制1 20 5 10 10 20 0 0 4 6 10 11 0 0输出样例#:复制1 2 2 3 2#includebits/stdc.h using namespace std; long long s[200001]; int main() { long long m, n; while(cinmn){ if(m 0 n 0){ break; } s[m] ;//起点颜色多一种 s[n 1] --;//终点颜色在减去这一种 } int current 0; for(int i 0; i 200001; i ){ current s[i]; s[i] current; } while(cinmn){ if(m 0 n 0){ break; } for(long long i m; i n; i ){ couts[i]\n; } } }字符串哈希查看题解 查看答案题目描述Time Limit: 1000 msMemory Limit: 256 mb如题给定N个字符串第i个字符串长度为Mi字符串内包含数字、大小写字母大小写敏感请求出N个字符串中共有多少个不同的字符串。输入输出格式输入描述:第一行包含一个整数N为字符串的个数。 接下来N行每行包含一个字符串为所提供的字符串。 N10000Mi≈1000Mmax1500输出描述:输出包含一行包含一个整数为不同的字符串个数。输入输出样例输入样例#:复制5 abc aaaa abc abcc 12345输出样例#:复制4#includebits/stdc.h using namespace std; int main() { int n; cinn; setstrings; string str; while(n--){ cinstr; s.insert(str); } couts.size()endl; }统计同成绩学生人数查看题解 查看答案题目描述Time Limit: 1000 msMemory Limit: 256 mb读入N名学生的成绩将获得某一给定分数的学生人数输出。输入输出格式输入描述:测试输入包含若干测试用例每个测试用例的格式为 第1行N 第2行N名学生的成绩相邻两数字用一个空格间隔。 第3行给定分数 当读到N0时输入结束。其中N不超过1000成绩分数为包含0到100之间的一个整数。输出描述:对每个测试用例将获得给定分数的学生人数输出。输入输出样例输入样例#:复制3 80 60 90 60 2 85 66 0 5 60 75 90 55 75 75 0输出样例#:复制1 0 2题目来源浙江大学机试题#includebits/stdc.h using namespace std; int main() { int n; while(cinn){ if(n 0){ return 0; } unordered_mapint, intm; int temp; for(int i 0; i n; i ){ cintemp; m[temp] ; } int score; cinscore; coutm[score]endl; } }剩下的树已解决查看题解 查看答案题目描述Time Limit: 1000 msMemory Limit: 32768 mb有一个长度为整数L(1L10000)的马路可以想象成数轴上长度为L的一个线段起点是坐标原点在每个整数坐标点有一棵树即在0,1,2...L共L1个位置上有L1棵树。 现在要移走一些树移走的树的区间用一对数字表示如 100 200表示移走从100到200之间包括端点所有的树。 可能有M(1M100)个区间区间之间可能有重叠。现在要求移走所有区间的树之后剩下的树的个数。输入输出格式输入描述:两个整数L(1L10000)和M(1M100)。 接下来有M组整数每组有一对数字。输出描述:可能有多组输入数据对于每组输入数据输出一个数表示移走所有区间的树之后剩下的树的个数。输入输出样例输入样例#:复制500 3 100 200 150 300 470 471输出样例#:复制298题目来源清华大学上机题#includebits/stdc.h using namespace std; int main() { int l, m; while(cinlm){ int s[100001]; for(int i 0; i 100000; i ){ s[i] 1; } int x, y; for(int i 0; i m; i ){ cinxy; for(int i x; i y; i ){ s[i] 0; } } int count 0; for(int i 0; i l; i ){ count s[i]; } coutcountendl; } }谁是你的潜在朋友已解决查看题解 查看答案题目描述Time Limit: 1000 msMemory Limit: 256 mb“臭味相投”——这是我们描述朋友时喜欢用的词汇。两个人是朋友通常意味着他们存在着许多共同的兴趣。然而作为一个宅男你发现自己与他人相互了解的机会并不太多。幸运的是你意外得到了一份北大图书馆的图书借阅记录于是你挑灯熬夜地编程想从中发现潜在的朋友。 首先你对借阅记录进行了一番整理把N个读者依次编号为1,2,…,N把M本书依次编号为1,2,…,M。同时按照“臭味相投”的原则和你喜欢读同一本书的人就是你的潜在朋友。你现在的任务是从这份借阅记录中计算出每个人有几个潜在朋友。输入输出格式输入描述:每个案例第一行两个整数N,M2 N M 200。接下来有N行第i(i 1,2,…,N)行每一行有一个数表示读者i-1最喜欢的图书的编号P(1PM)输出描述:每个案例包括N行每行一个数第i行的数表示读者i有几个潜在朋友。如果i和任何人都没有共同喜欢的书则输出“BeiJu”即悲剧^ ^输入输出样例输入样例#:复制4 5 2 3 2 1输出样例#:复制1 BeiJu 1 BeiJu题目来源北京大学机考题#includebits/stdc.h using namespace std; int main(){ int n, m; while(cinnm){ // unordered_mapint, intm; vectorints(201); vectorintresult(201); int temp; for(int i 0; i n; i ){ cins[i]; result[s[i]] ; } for(int i 0; i n; i ){ if(result[s[i]] 2){ coutBeiJuendl; } else{ coutresult[s[i]] - 1endl; } } } }