初赛整理

发布于 2019-10-05  1.03k 次阅读


窝会放一些文件,记录一些题目,整理一些知识点等等

会陆续更新的QAQ

模拟卷讲解

avatar
各种排序

方法一:

5个数,a、b、c、d、e
第一次比较a、b,不妨设a>b
第二次比较c、d,不妨设c>d
第三次比较a、c,不妨设a>c
这个时候有结果a>b且a>c>d
关键的时候到了,千万不要让b提前排序,这样会浪费掉1次。
第四次比较c,e
第五次(e>c,则e与a比较;e<c,则e与d比较)
第五次结束后会形成以下四种情况之一:(另已知a>b)
1、e>a>c>d
2、a>e>c>d
3、a>c>e>d
4、a>c>d>e
情况1、e>a>c>d
第六七次用b分别与c,d比较就行。
情况2、a>e>c>d
第六次,b与c比较
第七次(b>c,则b与e比较;b<c,则b与d比较)
情况3、a>c>e>d(方法同情况2继续六七次)
情况4、a>c>d>e(方法同情况2继续六七次)

方法二:

运用了二分的思想

简单地说,5个数的全排列,共有5*4*3*2*1=120种,而每次比较能得到或大或小两种情况,n次比较可以得到$latex 2^n $种情况,所以要想区分出这120种情况,至少要n=7,即有$latex 2^7=128>120 $。也就是说至少要7次比较。

用排列组合

将abc看成一个元素d,原问题可以分为{2a,4b,1c,1d}和{1a,3b,2d}
{1a,3b,2d}——6!/(3!*2!)=60,其中3!为b的重复,2!为d的重复;
{2a,4b,1c,1d}——8!/(2!*4!)=840
840-60=780

网络层

网络层包含ICMP/IGMP

原码 反码 补码

对于正数来说,[x]原码=[x]反码=[x]补码。对于负数来说,[x]补码=[x]反码+1[x]反码 等于 [x]原码 除符号位外逐位取反。


有关复杂度

建议看后面那个

看两个题


特征方程

举个例子


数的定点表示和浮点表示

在计算机中,小数点一般有两种表示方法,一种是小数点固定在某一位置的定点表示法,另一种是小数点的位置可任意移动的浮点表示法。相应于这两种表示的计算机分别称为定点计算机和浮点计算机。

1.定点表示法

机器中所有数的小数点位置是固定不变的,因而小数点就不必使用记号表示出来。实际上,小数点可固定在任意一个位置上。

2.浮点表示法

在数的定点表示法中,由于数的表示范围狭窄,常常不能满足各种数值问题的需要。为了扩大数的表示范围,方便用户使用,有些计算机采用浮点表示法。表示一个浮点数,要用两部分:尾数和阶码。尾数用以表示数的有效数值;阶码用以表示小数点在该数中的位置。

计算机多数情况下采用浮点数表示数值,它与科学计数法相似,把一个二进制数通过移动小数点位置表示成阶码和尾数两部分。

其中, EN 的阶码,是有符号的整数; SN 的尾数,是数值的有效数字部分,一般规定取二进制定点纯小数形式。

例如:


树转换为二叉树:

 二叉树中的节点有左右孩子之分,而在无序树中节点的各个孩子之间是无次序之分的。为了操作方便,假设树是一棵有序树,树中每个节点的孩子按照从左到右的顺序进行编号,依次定义为第一个孩子、第二个孩子、....、第i个孩子。
 将树转换为二叉树的方法可以归纳为“加线”、“删除”、”旋转“3个步骤,其具体描述如下:

  1. 加线:将树中所有相邻的兄弟之间加一条连线。
  2. 删线:对树中的每一个节点,只保留它与第一个孩子节点之间的连线,删去它与其他孩子节点之间的连线。
  3. 旋转:以树的根节点为轴心,将树平面顺时针旋转一定的角度并适当的进行调整,使得转化后所得的二叉树看起来比较规整(该步骤不是必须)

下图给出了将树装换成二叉树的过程的示意图:


有关P-NP-NPC问题

P/NP/NPC问题在2012年左右曾经火了一阵,如果你做过2012年和2013年的提高组真题的话,你会发现,那两年每年都有一道这种问题的多选题(不过之后就凉凉了),所以这类问题还是有必要了解一下的。
反正重要的知识点就这么几句话,我都划重点了,其他都是瞎扯可以无视的啦QAQ(这句不是重点啊)

零、预备内容:时间复杂度

时间复杂度分为两种:多项式级复杂度和非多项式级复杂度
其中多项式级复杂度是指规模 nn 在底数位置上的或者常数级的复杂度
比如说 $latex O(1)$ 、 $latex O(n)$ 、$latex O(n log n)$ 或者 $latex O(n^2)$ 等等
而非多项式级复杂度则是规模 n 在指数位置上的复杂度
比如说 O(2^n) 或者 O(n!)

这么区分的原因是因为这两种复杂度是天差地别的,后者远大于前者。
举个例子:当 n=10 的时候

O(1)=1  
O(N)=10
O(N^2)=100

O(2^N)=1024
O(N!)=3628800
O(N^N)=10000000000

一、P问题的引入

自从发现了这两种复杂度之后,有些人就开始想了:“多项式复杂度好棒棒啊!如果所有问题都有多项式复杂度的解法就好了啊!”
这个时候,图灵跳了出来,丢了一个停机问题,人们吃惊地发现,这个问题甚至没有正确的解决方法,于是上面的flag就这样子GG了。
所以又有人来说了:“那能解的问题是不是一定有多项式解法呢?”
于是又来了一个问题:请解决3-SAT问题。
然后不用想了,又GG了。
这个时候脸被打得生疼的科学家们发现,他们有必要划分一下这些问题,以免再被打脸,因此他们就提出了P问题(Polynomial problem)(P是多项式的简写)

定义P问题为存在多项式复杂度算法的问题

二、NP问题的引入

有了P问题,科学家想了想,那我们就搞个不是P问题的专有名词,专指找不到多项式复杂度的问题(非P问题)不就行了吗?
然后他们就提出了NP问题,全剧终
嗯,事情没有这么简单,如果你要向上面那样想,你就可能要凉凉了。

NP问题不是非P问题

上面那种NP问题的定义会变得非常爆炸,因为你有时候并不能证明这个问题是不是一定没有多项式解,也就是说不确定现在这个不存在多项式复杂度的问题在未来也不存在多项式复杂度解法,显然这些问题你既不能归入P又不能归入NP,所以你还要再定义一个别的东西来表示他们,反正这个定义GG了

回顾之前所说,我们一开始的希望是找到多项式复杂度的解法,接着才会去考虑划分这些问题,所以我们的划分理应去往这个方向靠。

那么可以将NP问题定义为还不存在多项式复杂度解法的问题,用未解代替无解.(这体现了定义的科学性、准确性、严谨性、平实性、周密性)

以及我们的目标是找到NP问题的多项式解法,所以我们要使NP问题有可能能解,显然要去掉所有能证明无多项式解的问题,如果一个问题的一个解的验证都是非多项式级别的,这个问题就不可能做到多项式级复杂度,因为如果我们连它的一个条件都无法在多项式复杂度中证明,那么就更别谈在多项式复杂度中把他的所有条件都证明出来了。

终于可以给出NP问题(Non-deterministic Polynomial problem)的完全定义了(没错,这个N是不确定的意思)

一个问题的一个解可以用多项式级复杂度检验,它就是NP问题

所以有一点值得注意的

找不到多项式复杂度解的(非P问题)不一定是NP问题

因为有些无法在多项式复杂度中检验一个解的问题存在。

同时,这里可以很明显的发现,如果一个问题是P问题,那么他肯定能在多项式时间复杂度内检验任意一组解。于是又可以推出

P∈NP

但是P=NP吗?这是一个世纪难题,反正了解一下有这个问题就行了,初赛不会让你证明的,放心好了。

三、NP-hard和NPC问题的引入

虽然说不用让你去证明P=NP这种鬼畜的东西,但是科学家不断尝试证明的这段历史是没准会考的。(毕竟这是一种自强不息的求索精神,很符合二十四字核心价值观)

在此之前我们先引入归约的定义

归约指的是将A问题进行归约后可以用B问题的解决方法解决,也就是把A问题变成B问题解决

NPhard问题是指

如果有一个问题可以使所有NP问题在多项式复杂度内归约到它,那么它就是NP-hard问题

显然如果难度有一个上界的话,解决所有的NP问题归约起来的问题难度肯定就是那个上界,所以这类问题被称为NP-hard。

如果你有了解过停机问题的话,会知道这个问题是不可判的,但是如果把问题理解成输入一个东西到某个程序里,判断他是否会停机,就可以把所有NP问题归约到停机问题上来,所以停机问题是NP-hard,于是

NP-hard问题不一定是NP问题

既然不一定是NP问题那么对我们解决P=NP就没啥用了。
所以科学家又提出了NPC问题:

一个NP问题可以使所有NP问题在多项式复杂度内归约到它,那么它就是NPC问题

也就是说如果解决了NPC问题就可以解决所有的NP问题,然后就可以证明P=NP。

常见的NPC问题有3-SAT问题,旅行商问题等等。
这些的证明有兴趣大家可以研究一下。 最后祭上这张图来总结上面知识点之间的联系

接着我们来切几道真题。

四、历年真题

2012.20.以下关于计算复杂度的说法中,正确的有( )。
A.如果一个问题不存在多项式时间的算法,那它一定是NP类问题
B.如果一个问题不存在多项式时间的算法,那它一定不是P类问题
C.如果一个问题不存在多项式空间的算法,那它一定是NP类问题
D.如果一个问题不存在多项式空间的算法,那它一定不是P类问题

解析:
A 还记得图灵停机问题吗?那是一个NP-hard而不是NP问题
B 这是对的,因为P问题的定义是存在多项式时间的复杂度算法
C、D 时间复杂度和空间复杂度都是复杂度,是等价的。

所以选BD

2013.14. ( )属于 NP 类问题。
A. 存在一个 P 类问题
B. 任何一个 P 类问题
C. 任何一个不属于 P 类的问题
D. 任何一个在(输入规模的)指数时间内能够解决的问题

解析: 这里考察的知识点是NP问题的定义以及P∈NP
由之前可知任何P问题都是NP问题,同理一定存在一个P问题是NP问题 AB都是对的 C的话我们可以继续用万能的停机问题去反驳他
D考察的是定义,指数时间内能解决不意味着多项式时间能验证解,所以D是错的

所以选AB


康拓展开

康托展开是个啥

一句话,给出一个全排列,求它是第几个全排列,叫做康托展开。

另一句话,给出全排列长度和它是第几个全排列,求这个全排列,叫做逆康托展开。

这里,全排列的顺序定义和火星人中的定义是一样的。

时间复杂度?

康托展开可以在 $latex O(n^2)$ 的复杂度内求出一个排列的排名,在用到树状数组优化时可以做到 $latex O(n log n)$  。

怎么实现?

因为排列是按字典序排名的,因此越靠前的数字优先级越高。也就是说如果两个排列的某一位之前的数字都相同,那么如果这一位如果不相同,就按这一位排序。

比如 4 的排列, [2,3,1,4]<[2,3,4,1] ,因为在第 3 位出现不同,则 [2,3,1,4] 的排名在 [2,3,4,1] 前面。

举个栗子

我们知道长为 5 的排列 [2,5,3,4,1] 大于以 1 为第一位的任何排列,以 1 为第一位的 5 的排列有 4! 种。这是非常好理解的。但是我们对第二位的 5 而言,它大于 第一位与这个排列相同的,而这一位比 5 小的 所有排列。不过我们要注意的是,这一位不仅要比 5 小,还要满足没有在当前排列的前面出现过,不然统计就重复了。因此这一位为 1,3 或 4 ,第一位为 2 的所有排列都比它要小,数量为 $latex 3\times 3!$ 。

按照这样统计下去,答案就是 $latex 1+4!+3\times 3!+2!+1=46$ 。注意我们统计的是排名,因此最前面要 +1 。

注意到我们每次要用到 当前有多少个小于它的数还没有出现 ,这里用树状数组统计比它小的数出现过的次数就可以了。

逆康托展开

因为排列的排名和排列是一一对应的,所以康托展开满足双射关系,是可逆的。可以通过类似上面的过程倒推回来。

如果我们知道一个排列的排名,就可以推出这个排列。因为 4! 是严格大于 $latex 3\times 3!+2\times 2!+1\times 1! $ 的,所以可以认为对于长度为 5 的排列,排名 x 除以 4! 向下取整就是有多少个数小于这个排列的第一位。

引用上面展开的例子

首先让 46-1=45 , 45 代表着有多少个排列比这个排列小。 $latex \lfloor\frac {45}{4!}\rfloor=1 $ ,有一个数小于它,所以第一位是 2 。

此时让排名减去 $latex 1\times 4! $ 得到 21 , $latex \lfloor\frac {21}{3!}\rfloor=3 $ ,有 3 个数小于它,去掉已经存在的 2 ,这一位是 5 。

$latex 21-3\times 3!=3 $ , $latex \lfloor\frac {3}{2!}\rfloor=1 $ ,有一个数小于它,那么这一位就是 3 。

让 $latex 3-1\times 2!=1 $ ,有一个数小于它,这一位是剩下来的第二位, 4 ,剩下一位就是 1 。即 [2,5,3,4,1] 。

实际上我们得到了形如 有两个数小于它 这一结论,就知道它是当前第 3 个没有被选上的数,这里也可以用线段树维护,时间复杂度为 $latex O(n\log n) $ 。

几种想法

1.发现固定左端点为起始位置后,线段期望长度为 0.5 。那么答案肯定比 0.5 小,所以选B

2.可以通过几何概型+体积什么什么的求。建立一个三维坐标系Oxyz,x轴代表点A位置,y轴代表点B位置,z轴代表线段长度期望,那么长度的期望就是两个四面体拼起来的图形,顶点为(0,0,0),(1,0,0),(0,1,0),(0,0,1)和(1,1,0),(1,0,0),(0,1,0),(1,1,1)。这个几何体的体积为1/3(锥体体积为底面积乘以高再除以3),由于底面积为1,所以高度平均为1/3,即长度期望为1/3。


A处应当为n个节点

常见的卡特兰数前几项:1,2,5,14,42,132

卡特兰数还可以用于集合划分问题、阶梯切分问题、乘积重组问题和网格路径问题等。


图灵奖是ACM创办的


要使得a*b=(a or b)*(a and b),则要么(a or b)=a,同时(a and b)=b,要么相反。假如a的二进制值为10010,a是a,b两个数中较大的一个,则b可以等于10010,10000,00010,00000即为a的子集(雾)。

那么可以列出式子:

由于a,b位置可以交换,所以243*2减去两数相等的32种情况,最终答案为454



错排公式

给图中区域涂色,要求相邻区域不同色,现有4种可选颜色,则不同的着色方法有多少种?

选用3种颜色时,必须是1、5同色,3、4同色,与2进行全排列,涂色方法有C 4 3 *A 3 3 =24种。4色全用时涂色方法:是1、5同色或3、4同色,有2种情况,涂色方法有C 2 1 *A 4 4 =48种。所以不同的着色方法共有48+24=72种。故答案为72种

三人互相传球,由甲开始发球,并作为第一次传球,经过5次传球后,球仍回到甲手中,则不同的传球方式共有多少种?

根据题意,做出树状图,注意第四次时球不能在甲的手中。分析可得,共有 10 种不同的传球方式。

第二类 Stirling (斯特林)数

定理:第二类 Stirling 数 S(n,k) 是将 n 个元素的集合划分成 k 个不可辨认的非空盒子的划分的个数。注意,这里的不可辨认是指不能把一个盒子与另一个盒子分辨开,它们看起来都一样。

下面给出第二类 Stirling 数的递推关系:

#include<iostream>
#include<cstdio>

using namespace std;

int s(int n,int k)
{
    if (n==k) return 1;
    if (k==1) return 1;
    return k*s(n-1,k)+s(n-1,k-1);
}

int main()
{
    int n,k;
    cin>>n>>k;
    cout<<s(n,k)<<endl;
    return 0;
}

例题:盒子与球

有 3 个一模一样的盒子和 6 个不同颜色的球,将这些球放到 3 个盒子里并且保证每个盒子里至少有 1 个球,求放置的方案总数。

答案:第二类 Stirling 数 S(6,3)=90

抽屉原理

将这32个数构造为集合{1,10}, {2,11}, …, {8,17}, {18,27}, {19,28},…,{23,32} ,{24},{25},{26},这17个集合中的任一个集合不能包含两个或两个以上的 ,否则它们的差为9

例如,当 n=17 时,可以把队列构造成 1 1 1 1 1 1 1 1 10 1 1 1 1 1 1 1 1,不存在恰好为 9 的情况

所以 n 的最小值是 18



NIM取石子游戏

题目地址

可以看一下题解和代码

#include<iostream>
using namespace std;
int main()
{
	int t,ans,n,x;
	cin>>t;
	while(t--)
	{
		ans=0;
		cin>>n;
		for(int i=1;i<=n;i++) 
		{
			cin>>x;
			ans=ans^x;
		}
		if (ans==0) cout<<"No"<<endl;
		else cout<<"Yes"<<endl;
	}
	return 0;
}

有关二分图

一个图是二分图的充分必要条件是这个图中不含奇环

由条件可知这个图是一个二分图,设某一类点有 x 个,那么另一类点有 (7-x) 个,原题即求 x(7-x) 的最大值,其中 x 是正整数。可以用一元二次方程的性质或者一些经典的不等式,很快能得到答案为 12



最小相邻交换排序

将数组{8, 23, 4, 16, 77, -5, 53, 100}中的元素按从大到小的顺序排列,每次可以交换相邻两个元素,最少需要交换( )次。

注意到相邻交换只会改变相邻两个数的相对大小而不会影响到别的数,因此我们考虑能不能从改变相对大小这个方面入手。在数列中,有一个值和相对大小密切相关,那就是逆序对数。显而易见的是,一个排好序的数列的逆序对数为 0 。而对于一个没有排好序的数组,我们一定可以找到两个相邻的数是逆序对。这样当逆序对数大于 0 的时候,我们总可以通过一次交换使逆序对数减 1 。于是最小相邻交换排序的交换次数就等于原数列的逆序对数。


运用图论的思想,用一个节点代表一个人,如果两个人互相认识就用线连上,不认识就不连。原题的要求就变成了了这样:

  • 没有一个节点与其他所有点相连

  • 每个子集中,任何三个节点中,至少两个不相连(没有三角形)

  • 同一子集中的任意不直接相连的两点,彼此之间有只通过一个节点的路径。

发现最小为画一个五角星满足情况,所以答案为 401


这个提示可还行

发现当有 $latex 2^m $ 个人围成一圈,按 1212··· 报数,凡报到 2 的人离开,最后剩下一个人,一定是 1 号。那么对于任意的 N ,都可以写成 $latex 2^m+r(0<=r<2^m) $ ,这样第 r 个人出列后,剩下的人数就是 $latex 2^m $ ,这时对剩下的人重新编号,排在第 1 号的就是最后剩下的那个人,将这个人还原到原队伍中的编号就是 2r+1

对于本题,因为 $latex 400=2^8+144=2^m+r $ ,r=144,所以结果就是 2r+1=144*2+1=289


最美好的事情就是和OI一起成长呢。