本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderB - Laboratories That Can Collaborate【题目描述】Takahashi works at the university’s research support center. The university hasN NNlaboratories, and each laboratory is working on several research themes. Laboratoryi ii(1 ≤ i ≤ N 1 \leq i \leq N1≤i≤N) is working onM i M_iMi​research themes, each represented by a string of lowercase English lettersW i , 1 , W i , 2 , … , W i , M i W_{i,1}, W_{i,2}, \ldots, W_{i,M_i}Wi,1​,Wi,2​,…,Wi,Mi​​. Note that the same research theme does not appear more than once within the same laboratory.高桥在大学的研究支持中心工作。该大学有N NN个实验室每个实验室正在进行若干研究课题。实验室i ii1 ≤ i ≤ N 1 ≤ i ≤ N1≤i≤N正在进行M i M_iMi​个研究课题每个课题用一个小写英文字母字符串W i , 1 , W i , 2 , … , W i , M i W_{i,1}, W_{i,2}, \ldots, W_{i,M_i}Wi,1​,Wi,2​,…,Wi,Mi​​表示。注意同一研究课题不会在同一实验室内出现超过一次。To promote collaborative research, the university has decided to investigate pairs of laboratories that are “eligible for collaboration.” LetS i { W i , 1 , W i , 2 , … , W i , M i } S_i \{W_{i,1}, W_{i,2}, \ldots, W_{i,M_i}\}Si​{Wi,1​,Wi,2​,…,Wi,Mi​​}be the set of research themes that laboratoryi iiis working on. Two laboratoriesi , j i, ji,j(i ≠ j i \neq jij) are said to be “eligible for collaboration” if the number of research themes common to bothS i S_iSi​andS j S_jSj​is at leastK KK, that is,∣ S i ∩ S j ∣ ≥ K |S_i \cap S_j| \geq K∣Si​∩Sj​∣≥Kholds. Here, whether two research themes are identical is determined by whether their representing strings match exactly.为促进合作研究该大学决定调查那些具备合作资格的实验室对。令S i W i , 1 , W i , 2 , … , W i , M i S_i {W_{i,1}, W_{i,2}, \ldots, W_{i,M_i}}Si​Wi,1​,Wi,2​,…,Wi,Mi​​表示实验室i ii正在进行的研究课题集合。两个实验室i , j i, ji,j(i ≠ j i \neq jij) 被称为具备合作资格如果它们共同的研究课题数量至少为K KK即满足∣ S i ∩ S j ∣ ≥ K |S_i \cap S_j| \geq K∣Si​∩Sj​∣≥K。这里两个研究课题是否相同取决于它们的表示字符串是否精确匹配。Takahashi has the list of research themes each laboratory is working on. Based on this information, find the number of pairs of laboratories that are “eligible for collaboration.” Note that the pair of laboratoryi iiand laboratoryj jjis considered the same as the pair of laboratoryj jjand laboratoryi ii. Count the number of pairs( i , j ) (i, j)(i,j)satisfying1 ≤ i j ≤ N 1 \leq i j \leq N1≤ij≤Nthat meet the condition.高桥拥有每个实验室正在进行的研究课题列表。基于此信息求具备合作资格的实验室对的数量。注意实验室i ii与实验室j jj组成的对被视为与实验室j jj与实验室i ii组成的对相同。统计满足条件且满足1 ≤ i j ≤ N 1 ≤ i j ≤ N1≤ij≤N的对( i , j ) (i, j)(i,j)的数量。【输入】The input is given from standard input in the following format.N NNK KKM 1 M_1M1​W 1 , 1 W_{1,1}W1,1​W 1 , 2 W_{1,2}W1,2​… \ldots…W 1 , M 1 W_{1,M_1}W1,M1​​M 2 M_2M2​W 2 , 1 W_{2,1}W2,1​W 2 , 2 W_{2,2}W2,2​… \ldots…W 2 , M 2 W_{2,M_2}W2,M2​​⋮ \vdots⋮M N M_NMN​W N , 1 W_{N,1}WN,1​W N , 2 W_{N,2}WN,2​… \ldots…W N , M N W_{N,M_N}WN,MN​​The first line contains the number of laboratoriesN NNand the thresholdK KKused for determining “eligibility for collaboration,” separated by a space.Then, for each laboratoryi ii(i 1 , 2 , … , N i 1, 2, \ldots, Ni1,2,…,N), the following2 22lines are given in order:The first line contains the number of research themesM i M_iMi​that laboratoryi iiis working on.The second line contains theM i M_iMi​stringsW i , 1 , W i , 2 , … , W i , M i W_{i,1}, W_{i,2}, \ldots, W_{i,M_i}Wi,1​,Wi,2​,…,Wi,Mi​​representing the research themes of laboratoryi ii, separated by spaces.【输出】Output the number of pairs of laboratories that are “eligible for collaboration” in a single line.【输入样例】3 2 3 ai ml data 4 ml data web security 2 ai ml【输出样例】2【解题思路】【算法标签】#模拟#【代码详解】#includebits/stdc.husingnamespacestd;constintN505,M55;intn,k,m[N],ans;// n: 集合数量k: 阈值m[i]: 第i个集合的大小ans: 结果计数string a[N][M];// a[i][j]: 第i个集合的第j个元素intmain(){cinnk;// 读入集合数量和阈值for(inti1;in;i){cinm[i];// 读入第i个集合的元素数量for(intj1;jm[i];j){cina[i][j];// 读入第i个集合的第j个元素}}// 遍历所有集合对(i, j)其中ijfor(inti1;in;i){for(intji1;jn;j){intcnt0;// 记录两个集合的共同元素个数// 统计集合i和集合j的共同元素个数for(intkk1;kkm[i];kk)// 注意这里使用kk避免与变量k重名{for(intl1;lm[j];l){if(a[i][kk]a[j][l])// 如果元素相同{cnt;// 计数加1}}}// 如果共同元素个数达到阈值kif(cntk){ans;// 结果计数加1}}}coutansendl;// 输出满足条件的集合对数量return0;}【运行结果】3 2 3 ai ml data 4 ml data web security 2 ai ml 2