欢迎辞欢迎来到“笃志以砺,决起而飞”! 如果您是第一次来到本站,建议访问 本站导读以便更快地了解本站。 如果您喜欢本站, 欢迎订阅。 | 之所以两道题放在一起,就是因为他们很相似。 本解题报告版权归 Ceeji 所有,转载请注名出处并保留本注释。 题目一:Count 大项堆是具有如下性质的二叉树: 1.它的任意一个父亲节点的权值总是比孩子的权值要大 2.它是一颗完全二叉树 先给定这个堆的节点个数N,假如每个节点的权值都为在1—N之间的整数且各不相同,求可能的大项堆的个数。当然,这个个数可能很多,这里只要求这个个数模K即可。 输入: 两个用空格隔开的整数N和Q(N<30,Q<10^9) 输出: 可能的大项堆的个数模Q 输入样例: 3 1000 输出样例: 2 题目二:树的同构 本解题报告版权归 Ceeji 所有,转载请注名出处并保留本注释。 排序二叉树是我们熟悉的一种数据结构,这里提到的排序二叉树都是指根的关键字比左 子树上的所有点都大,比右子树上的都小(假定不存在相同的关键字)的排序二叉树。如果 给定一个输入序列,按照这个序列依次将各个结点插入,我们就得到了一棵排序二叉树。比 如输入序列 4 2 1 3 5,对应如下排序二叉树: 2 4 5 1 3 而输入序列4 5 2 1 3 以及4 2 5 1 3都对应同样的树,我们说这三个序列同构。现在给定 一个长度为N的输入序列,求与之同构的序列有多少个(包括这个序列本身)。由于问题的 答案可能比较大,只要求输出答案 mod 10,007的结果。 Input 第1行:一个正整数N,即输入序列长度。 第2行:N个1—N之间的正整数,数字相互之间不重复。 Output 仅有一行,即同构序列数 [...] 昨天进行了模拟赛,很不爽,只有120分。想当然让我措失了80分,数学知识不能合理利用让我又失去了80分。懒惰也让我失去了一些分数。 从现在开始,我总结一下做题的情况和问题。将发布各题的解题报告。 第一题:不会,骗分 骗分也是一门艺术,不过只骗了20分。 我的骗分程序:(反正不会写,索性用 C++ 而不是 Pascal 写了一个骗分程序新鲜一下。) /* Cheat By Ceeji XD */ #include <cstdio> using namespace std; int n,q; int main() { freopen(“count.in”,”r”,stdin); freopen(“count.out”,”w”,stdout); scanf(“%d”,&n); scanf(“%d”,&q); if (n==1) { printf(“%d\r\n”,(1 % q)); } if (n==2) { printf(“%d\r\n”,(1 % q)); } if (n==3) { printf(“%d\r\n”,(2 % q)); } if (n==4) { printf(“%d\r\n”,(3 % q)); } if (n==5) { printf(“%d\r\n”,(8 % q)); } if (n==6) { printf(“%d\r\n”,(20 % q)); } if (n>6) { printf(“%d\r\n”,5); } fclose(stdin); fclose(stdout); return 0; } /* <br/> Cheat By Ceeji XD<br/>*/<br/>#include <cstdio><br/>using namespace std;<br/>int n,q;<br/>int main()<br/>{<br/> freopen(“count.in”,”r”,stdin);<br/> freopen(“count.out”,”w”,stdout);<br/><br/> scanf(“%d”,&n);<br/> scanf(“%d”,&q);<br/><br/> if (n==1) { printf(“%d\r\n”,(1 % q)); }<br/> [...] 首先声明这个文章不是我原创,功劳归 Matrix67(First Published By Matrix67)但合并,整理 + 改编后效果更好,也删除和添加了一些东西,献给所有需要的人。首先还是从最基础的东西说起。 什么是位运算? 程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了,就是直接对整数在内存中的二进制位进行操作。比如,and运算本来是一个逻辑运算 符,但整数与整数之间也可以进行and运算。举个例子,6的二进制是110,11的二进制是1011,那么6 and 11的结果就是2,它是二进制对应位进行逻辑运算的结果(0表示False,1表示True,空位都当0处理): 110 AND 1011 ———- 0010 –> 2 由于位运算直接对内存数据进行操作,不需要转成十进制,因此处理速度非常快。当然有人会说,这个快了有什么用,计算6 and 11没有什么实际意义啊。这一系列的文章就将告诉你,位运算到底可以干什么,有些什么经典应用,以及如何用位运算优化你的程序。 Pascal和C中的位运算符号 下面的a和b都是整数类型,则: C语言 | Pascal语言 ——-+————- a & b | a and b a | b | a or b a ^ b | a xor b ~a | not a a << b | a shl b a >> b | a shr b [...] | |
近期评论