打卡信奥刷题（3069）用C++实现信奥题 P6919 [ICPC 2016 WF] Ceiling Function

P6919 [ICPC 2016 WF] Ceiling Function题目描述高级天花板制造商ACM正在分析其新系列的极其防坍塌天花板ICPC的特性。一个 ICPC 由n nn层材料组成每层都有不同的抗坍塌值以正整数表示。ACM 想要进行的分析将把各层的抗坍塌值存储在一个二叉搜索树中并检查该树的形状是否与整个结构的质量相关。因为为什么不呢具体来说ACM 将从顶层到底层依次获取各层的抗坍塌值并将它们逐一插入到树中。插入值v vv的规则是如果树是空的则将v vv作为树的根。如果树不为空将v vv与树的根进行比较。如果v vv较小则将v vv插入到根的左子树中否则插入到右子树中。ACM 有一组天花板原型它想通过尝试坍塌它们来进行分析。它想将具有相同树形状的天花板原型分组并一起分析。例如假设 ACM 正在考虑五个具有三层的天花板原型如样例输入 1 所述并如图 1 所示。注意第一个原型的顶层抗坍塌值为 2中间层的值为 7底层的值为 1。第二个原型的层的抗坍塌值为 3、1 和 4——然而这两个原型产生了相同的树形状因此 ACM 将一起分析它们。给定一组原型您的任务是确定它们产生了多少种不同的树形状。图 1样例输入 1 中天花板原型所产生的四种树形状。输入格式输入的第一行包含两个整数n nn(1 ≤ n ≤ 50 1 \le n \le 501≤n≤50)表示要分析的天花板原型的数量以及k kk(1 ≤ k ≤ 20 1 \le k \le 201≤k≤20)表示每个原型的层数。接下来的n nn行描述了天花板原型。每行包含k kk个不同的整数范围在1 11到10 6 10^6106之间包括边界这些整数是天花板原型中各层的抗坍塌值从上到下排列。输出格式输出不同树形状的数量。输入输出样例 #1输入 #15 3 2 7 1 3 1 4 1 5 9 2 6 5 9 7 3输出 #14输入输出样例 #2输入 #23 4 3 1 2 40000 3 4 2 1 33 42 17 23输出 #22说明/提示时间限制5000 毫秒内存限制1048576 KB。国际大学生程序设计竞赛ACM-ICPC世界总决赛 2016。题面翻译由 ChatGPT-4o 提供。C实现#includebits/stdc.husingnamespacestd;intn,k,a,cnt;mapint,intnow1,now2;mapmapint,int,boolmp;intmain(){scanf(%d%d,n,k);for(inti1;in;i){now1.clear(),now2.clear();for(intj1;jk;j){scanf(%d,a);if(j1){introot1;while(now1[root]){if(now1[root]a)rootroot*21;//右儿子elserootroot*2;//左儿子}now1[root]a,now2[root]1;}elsenow1[1]a,now2[1]1;//第一个数为根}if(mp[now2]!1){//若不重复就统计mp[now2]1;cnt;}}printf(%d,cnt);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容