本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-06 16:00:32

0-1 Linux 使用

linux资料1

WXL-deepseek 整理LINUX基础知识

0-1-1.5 时间复杂度分析

时间复杂度分析

0-2 初赛复习

初赛资料2

第一节 进制基础

本文转自 https:\/\/blog.csdn.net\/qq_20013653\/article\/details\/137296081，如有侵权，请联系删除。

基础知识

 进制也就是进位计数制，是人为定义的带进位的计数方法，可以用有限的数字符号代表所有的数值，可使用的数字符号的数目称为基数或底数，基数位n，即可称n进位制，简称n进制。

 对于任何一种进制——X进制，每一位置上数的运算都是逢X进一位。十进制是逢十进一，十六进制是逢十六进一，二进制就是逢二进一，以此类推，X进制就是逢X进一。

 任何一个数都可以用不同的进位制来表示。比如十进制数$57_{10}$，可以用二进制表示为$111001_{2}$，也可以用八进制表示为$71_8$，用十六进制表示为$39_{16}$，它们所表示的数值都是一样的。

十进制

• 基数为10，数码由0~9组成，计数规律为逢十进一。
• 对于十进制数可以不加标注，或加后缀D，其中D是十进制英文Decimal的首字母，如57、57D。

二进制

• 基数为2，数码由0、1组成，计数规律为逢二进一。
• 二进制数的书写通常在数的右下方注上基数2，或在后面加B表示，其中B是二进制英文Binary的首字母，如$111001_2$、$111001B$。
  在计算机领域，我们之所以采用二进制进行计数，是因为二进制具有以下优点：
• 二进制数中只有两个数码0和1，可以用具有两个不同稳定状态的元器件来表示。例如，电路中某一通路的电流的有无、某一节点电压的高低、晶体管的导通和截止等。
• 二进制数运算简单，大大简化了计算中运算部件的结构
• 二进制天然兼容逻辑运算

八进制
由于二进制的基数较小，数据的书写和阅读不方便，为此，在小型机中引入了八进制。

• 基数为8，数码由0~7组成，计数规律为逢八进一
• 八进制用下标8或在数据后面加O（Octal的首字母）表示，如718、71O。
• 在C++语言中，以数字0开头表示该数字是八进制数，如cout<<071;。

十六进制
由于二进制的位数太长，不容易记忆，所以十六进制数就出现了。

• 基数为16，数码由0~9 加上A~F组成（A表示10），计数规律为逢十六进一。
• 十六进制用下标16或在数据后面加H（Hex的首字母）表示，如3916、39H。
• 在C++语言中，以前缀0x开头表示该数字是十六进制数，如cout<<0x39;。

 更大的进制则从F表示15开始，继续类推到Z，最大可以表示三十六进制。

赛题训练

• 1.二进制数00101100和00010101的和为（ ）。
  A.00101000   B.01000001
  C.01000100   D.00111000

• 2.在计算机内部用于传送、存储、加工处理的数据或指令都是以（ ）形式存在的。
  A.二进制码   B.八进制码
  C.十进制码   D.智能拼音码

第二节 进制转换

基础知识

十进制转二进制
除二取余法： 用2连续除十进制整数，直到商为0，逆序排列余数即可得到该十进制数的二进制表示。

 例如十进制57转为二进制数：

• 57除以2得28余1
• 28除以2得14余0
• 14除以2得7余0
• 7除以2得3余1
• 3除以2得1余1
• 1除以2得0余1（商为0，结束）
  逆序排列余数（从下往上）得到二进制数：111001B。
  十进制整数转n进制同理，即除n取余法。

二进制数转十进制
按位权展开： 在数制中，各位数字所表示值的大小不仅与该数字本身的大小有关，还与该数字所在的位置有关，我们称其为数的位权， 简称权。
对于形式化的进制表示，我们可以从0开始，对数字的各个数位进行编号，即从个位起向左依次编号为0、1、2、…；对称的，小数点后的数位则是-1、-2、…。
如下表为二进制数111001.000B的位权表示：

 任意R进制数按权展开，相加即可得到十进制数，如二进制数111001B转为十进制数：

1×25+1×24+1×23+0×22+01+1×20\=57

 其他进制数转十进制数同理，十进制数的位权是以10为底的幂，二进制数的位权是以2为底的幂，十六进制数的位权是以16为底的幂。数位由高向低，以降幂的方式排列。

进制快捷转换
由于2的3次方是8，所以二进制树转为八进制数时，可三个数一组进行转换(优先满足右侧分组，左侧最高位不够可以补零)，每组内位权编号重新从零开始计算。例如，二进制数111001B转为八进制数：

(111)(001)B=(1×22+1×21+1×20)(0×22+0×21+1×20)O=71O

 同理，由于2的4次方是16，二进制数转为十六进制数时，可四个数一组进行转换(优先满足右侧分组，左侧最高位不够可以补零)，如二进制数111001B转为十六进制数：

(11)(1001)B=(1×21+1×20)(1×23+0×22+0×21+1×20)H=39H

 其他进制间转换时，若进制存在幂运算关系，也可以此方法进行快捷转换。

十进制小数转二进制小数
乘二取整法： 用2乘十进制小数，可以得到积，将积的整数部分去除，再用2乘余下的小数部分，如此循环，将每步取出的整数部分顺序排列，得到小数的二进制表示。
整数部分用除二取余法得到二进制整数，小数部分用乘二取整法得到二进制小数。例如，十进制数32.12转为二进制数的步骤如下：

1. 整数部分为32，小数部分为0.12
2. 整数部分32除二取余法得到二进制数100000。
3. 小数部分：
   0.12×2=0.24取整数0
   0.24×2=0.48取整数0
   0.48×2=0.96取整数0
   0.96×2=1.92取整数1（后续运算因数变为0.92）
   0.92×2=1.84取整数1
   0.84×2=1.68取整数1
   （此时会发现，有的数的小数部分乘二取整法可能会无线运算下去，这时须按照题目精度要求截取足够位数即可）
   顺序排列取出整数，得到小数部分二进制数为.000111。
4. 结合得到最终二进制数为100000.000111。

 总结：整数部分，除二取余，逆序排列；小数部分，乘二取整，顺序排列。

赛题训练

1. 二进制数1011转换成十进制数是（ ）。
   A.11   B.10  C.13  D.12
2. 下列四个不同进制的数中，与其他三项数值不相等的是（ ）。
   A.(269)16  B.(617)10  C.(1151)8  D.(1001101011)2
3. 请选出以下最大的数（ ）。
   A.(550)10   B.(777)8  C.210  D.(22F)16
4. 十进制小数13.375对应的二进制数是（ ）。
   A.1101.011  B.1011.011  C.1101.101  D.1010.01
5. 与二进制小数0.1相等的八进制数是（ ）。
   A.0.8 B.0.4 C.0.2 D.0.1
6. 与二进制小数0.1相等的十六进制数是（ ）。
   A.0.8 B.0.4 C.0.2 D.0.1
7. 下面有四个数据组，每个组各有三个数据，其中第一个数据为八进制数，第二个数据为十进制数，第三个数据为十六进制数。这四个数据组中三个数据的是（ ）
   A.120 82 50  B.144 100 68 C.300 200 C8 D.1762 1010 3F2

第三节 位运算

基础知识

 程序中的所有数在计算机内存中都是以二进制的形式存储的，位运算就是直接对整数在内存中的二进制位进行操作（补码和符号位也参与运算，后面再补充补码的知识），如果是十进制数间进行位运算，则将十进制数先转换成二进制数再运算。位运算符及其运算规则如下：
按位与(&)
两个都是1才是1.例如：
00101  5
11100  28
&------------------------
00100  4
&运算通常用于二进制数的取位操作，例如一个数“&1”的结果就是取二进制数的最末位。这可以用来判断一个整数的奇偶性，二进制的最末位为0表示该数为偶数，最末位为1表示该数是奇数。对于一个数a，a=a&(a-1)的作用是将a的二进制数最右边的1变为0。

按位或(|)
只要有一个为1就为1。例如：
00101  5
11100  28
|------------------------
11101  29
|运算通常用于二进制数特定位上的无条件复制，例如一个数“|1”的结果就是把二进制最末位强行变成1.如果需要把二进制数最末位变成0，对这个数“|1”之后再减一就可以了，其实际意义就是把这个数强行变成最接近的偶数。

按位异或(^)
相同为0，不同为1（可以理解为“半加”，也就是不进位的二进制数加法）。例如：
00101  5
11100  28
^------------------------
11001  25
^运算可以用于简答的加密，比如我的某个密码是123456，但又担心密码被泄露，所以我使用19960706作为秘钥，123456 ^ 19960706= 20017602，我就把20017602记下来，等要使用密码时再计算20017602 ^ 19960706 = 123456，就得到我的密码了。
加法的逆运算是减法，乘法的逆运算是除法，^运算的逆运算是它本身。由此可以写出不需要中间变量的swap(交换两个数)过程。

int a = 10,b = 5;
\/\/借助中间量交换
int t = a;
a = b;
b = t;
\/\/借助互逆运算交换
a = a + b;
b = a - b;
a = a - b;
\/\/借助^交换
a = a ^ b;
b = a ^ b;
a = a ^ b;

 注意：^的交换方法不能用于一个数的自我交换，会导致数据变为0。(大家可以自己去检验)

按位取反(~)
单目运算符，1变成0，0变成1，例如：
00101  5
~  ------------------
11010  -6
注意11010为补码。
使用~运算时要格外小心，需要注意整数类型有没有符号。如果 ~的对象是无符号整数(unsigned)，那么得到的值就是它与该类型上界的差。

左移(<<)
a<<b就表示a转为二进制后左移b位(在后面添加b个0)。例如10的二进制数为1100100，而110010000转成十进制数是400，那么100<<2=400。可以看出a<<b的值实际上就是a乘以2的b次方，因为在二进制数后面添加一个0就相当于该数乘以2。
通常认为a<<1比a\*2更快，因为前者是更底层的一些操作。因此程序中乘以2的操作可以考虑用左移一位来代替。
定义一些常量可能会用到<<运算。你可以使用1<<16-1来表示65535。很多算法和数据结构要求数据规模必须是2的幂，此时可以用<<来定义MAX\_N等常量。

右移(>>)
与<<相似，a>>b表示把a转为二进制数后右移b位，低位舍弃b位，高位补b位符号位(正数补0、负数补1)。
右移运算对于正数，相当于a除以2的b次方(取商)，用>>代替除法运算可以使程序效率大大提高。

位运算符优先级

 速记：从高到低，反、(四则运算)、移、与、异、或。

赛题训练

1. 二进制数11101110010111和01011011101011进行逻辑或运算的结果是（ ）。
   A.11111111011111 B.11111111111101
   C.10111111111111 D.11111111111111
2. 二进制数11101110010111和01011011101011进行逻辑与运算的结果是（ ）。
   A.01001010001011 B.01001010010011
   C.01001010000001 D.01001010000011
3. 为了统计一个非负整数中二进制形式中1的个数，代码如下：

int CountBit(int x){
	int ret = 0;
	while(x)
	{	
		ret++;
		________;
	}
	return ret;
}

 A.x>>=1 B.x&=x-1
C.x|=x>>1 D.x<<=1
4\. 二进制数00101100和01010101异或的结果是（ ）。
A.00101000 B.01111001
C.01000100 D.00111000

第四节 存储单位

基础知识

 存储单位是一种计量单位，指在某一领域以一个特定量或标准作为一个计数点，再以此点的某个倍数去定义另一个点，而这个点的代名词就是计数单位或存储单位。如货车的载重量是吨，也就是说这辆货车能存储货物的单位量词是吨。
二进制序列用以表示计算机、电子信息数据容量的量纲，基本单位为字节(B)，字节单位的量级为1024，比如1KB=1024B、1MB=1024KB。
计算机存储单位一般用bit、B、KB、MB、GB、TB、PB等来表示，之间的关系如下：

• bit(b，位)：读作比特，存放一个二进制数，即0和1，是最小的存储单位。
• Byte(B，字节)：8个二进制位为一字节，即1B=8bit，是最常用的单位。
• Kilo Byte(KB)：1KB=1024B。
• Mega Byte(MB)：1MB=1024KB。
• Giga Byte(GB)：1GB=1024MB。
• Tera Byte(TB)：1TB=1024GB。

 在C++中，基本变量类型所占的内存空间大小由计算机操作系统(32位和64位)和编译器决定。一般情况，各类型所占的存储空间和能表示的范围如下表所示。

 在实际问题中，若long long都不足以满足需求，则要考虑使用数组来存放高精度数据，再重新定义高精度数据的四则运算。在信奥赛中，对高精度数据的处理也是常考项。

赛题训练

1. 一个32位整型变量占用（ ）字节。
   A.32 B.128 C.4 D.8
2. 1MB等于（ ）。
   A.1000字节 B.1024字节 C.1000×1000字节 D.1024×1024字节
3. 计算机存储数据的基本单位是（ ）。
   A.bit B.Byte C.GB D.KB

第五节 整数存储

基础知识

 计算机中整数数值的存储并不是简单的将其转为二进制存入内存，因为涉及到正负数、减法运算等问题，所以科学家们设计了一套整数的存储规则–三码。

原码
整数存储的时候，用最高位表示符号(0为正数，1为负数)，后面几位存储二进制数值，如：

 我们会发现一个问题，我们计算-1+1的结果时，得到的是1001+0001=1010，结果是-2。所以就有了反码。
反码
负数的二进制使用反码：符号位不变，其他相反。

 现在-1+1的结果是0001+1110=1111，等于-0。但是，0通常被认为是不具有正负之分的，所以又有了补码。

补码
负数的补码是用反码+1。

 现在我们的加法运算就完美了，0也没有分正负。

总结

1. 正数的原码、反码、补码都死它本身。
2. 负数的反码为原码(除符号位)取反，补码为反码加一。
3. 计算机内存中存储的是补码。
4. 因为存储的是补码，所以存储范围中的负数总比正数多一个(-0的原码被用来表示最小的负数)。

赛题训练

1. 在8为二进制补码中，10101011表示的数是十进制下的（ ）。
   A.43 B.-85 C.-43 D.-84
2. 在字长为16位的系统环境下，一个16位带符号整数的二进制补码位1111111111101101。其对应的十进制整数应该是（ ）。
   A.19 B.-19 C.18 D.-18

第六节 字符存储

基础知识

ASCII码表
计算机只能处理数字，那么如果要处理文本等信息，就必须先转换为数字才能处理。美国首先推出了ASCII(美国信息交换标准代码)码表，统一规定了常用的符号(使用7个bit，最多表示128位)。
对于ASCII码表，我们不需要记住每个字符的编号，只需要重点记住数字0的编码是48，大写字母A的编码是65，小写字母a的编码是97。因为剩余的数字和字母都是连续的，比如数字9的编码是57，大写字母Z的编码是90，小写字母z的编码是122，所以我们可以自己算出其他数字或字母的编码。

其他编码
ASCII码表能够解决英文字母、数字和一些符号的存储问题，但是全世界的语言有很多种，各国也有自己的编码方式，比如中文编码有用GB2312，繁体中文是BIG5，日文是Shift\_JIS，韩文是Euc\_kr等，这就会导致在多语言的混合文本中，显示会出现乱码。
因此就有了Unicode(万国码)，将世界所有的符号都纳入其中，现在又一百多万个符号(前128个仍然是ASCII字符)。
但是ASCII编码是1字节，Unicode编码通常是2字节。如果我们都统一用Unicode虽然解决了乱码问题，但是用Unicode编码比ASCII编码至少多一倍的存储空间。所以Unicode也有多种存储方式，其中UTF-8(一种可变长的编码存储方案)比较常见，它会根据不同大小编码成1 ~ 6字节，比如英文字母编码成1字节，汉字通常是3字节，复杂一点的编码成4 ~ 6字节。
字符串
在C++语言中，字符类型变量位char，若以字符串(多个连续字符)的形式出现，则借助char数组或者string来存储，以下是一些与字符串相关的名词。
字典序：一般而言，若要对两个字符串做大小比较，那么比较规则就是按字典序，字符大小即为ASCII码表编号的大小。先比较第一个字符，如果一样就比较下一个字符…。如果不一样长比如(abc和abcd)，那么短的在前，长的在后。
子串：字符串中任意个连续的字符组成的子序列称为该串的子串，空串和字符串本身也是该字符串的字串。
子序列：和子串不同，子序列不要求字符连续。

赛题训练

1. 以下关于字符串的判定语句中正确的是（ ）。
   A.字符串是一种特殊的线性表
   B.串的长度必须大于零
   C.字符串不可以用数组来表示
   D.空格字符串组成的串就是空串
2. （ ）是一种通用的字符编码，它为世界上绝大部分语言设定了统一并且唯一的二进制编码，以满足跨语言、跨平台的文本交换，目前它已经收录了超过十万个不同字符。
   A.ASCII B.Unicode C.GB2312 D.BIG5
3. 字符串的子串是其连续的局部，字符串自身是其最长的子串，空串是其最短的子串，对于字符串S=“Microsoft”，其非空子串的个数是（ ）。
   A.72 B.46 C.45 D.36
4. 若串S=“copyright”，其子串的个数是（ ）。
   A.72 B.45 C.46 D.36
5. 下列字符中，ASCII码值最小的是（ ）。
   A.a B.B C.R D.1

第七节 图像存储

基础知识

 计算机的数字化图像数据有两种存储方式：位图(Bitmap)存储和矢量(Vector)存储。
像素：整个图像中不可分割的最小单位或元素。它以一个单一颜色的小方格存在，所有小方格的颜色和位置的组合决定了该图像呈现出来的样子。
图像的位分辨率：也叫位深，用来衡量每个像素存储信息的位数，决定了多少种色彩等级的可能性，所以有时又将位分辨率称为颜色深度。常见的有8位、16位、24位、32位、64位色彩，即二进制数的位数，如24位色彩能组合出224\=16777216种色彩等级。
屏幕分辨率：指屏幕上显示的像素的个数，如1024×768的分辨率指屏幕上水平方向有1024个像素点，垂直方向上有768个像素点。
像素点距：指显示屏相邻两个像素点之间的距离，画质的细腻度就是由点距来决定的，点距越小，图像越细腻。

位图存储
由一系列像素组成的可识别图像。如果把一幅位图看成一个二维数组，则数组中的任一元素(即像素)对应于图像中的一个点，而存储的值对应于该点的颜色或者灰度。
特性：位图图像是由数目固定像素组成的图像

第八节 浮点数存储

基础知识

 (浮点数存储在CSP竞赛中还未出现过，如果有遗漏欢迎指正，这部分仅供拓展知识用)
小数：实数的一种特殊的表现形式，所有分数都可以表示成小数。
纯小数：整数部分是零的小数。
带小数：整数部分不是零的小数。
顶点数：指小数点在数中的位置是固定不变的，有定点整数和定点小数。
浮点数：小数点的位置不是固定的，用阶码和尾数表示。通常尾数为小数，阶码为整数，尾数和阶码均为带符号数。尾数的符号表示数的正负，阶码的符号表示小数点的实际位置。浮点数的精度由尾数决定，数的表示范围由阶码决定。
浮点数的表现形式类似于数学中的科学计数法，表示为N=M×RE。
其中N是浮点数自身，M为尾数，R为该浮点数的进制，E为阶码。
如二进制小数10011.101，按浮点数形式表示为1.0011101×24。
其中尾数为+1.0011101，阶码为+4。
注意：浮点数不一定是小数，定点数也不一定是整数。
移码：即补码的符号位取反，如4为二进制数的移码：-1=0111，1=1001。
0111在十进制下是7,1001在十进制下是9，相当于给原数加了8(23)。
速算技巧：n位二进制数的移码相当于加上2n-1。
在C++中，存放浮点数的变量类型有float和double，分别占用32位和64位二进制数，空间分配规则如下：

 以float类型为例，在32为二进制空间中，从左往右：

• 最高位用来表示正负(0为正数，1为负数)
• 中间8位指数位用来存放浮点数阶码(阶码的移码减1，速算偏移为127)
• 最后23位用来表示尾数部分(纯小数)

 例如，十进制数19.625，以float类型存储，二进制数计算规则：
1、19.625转换为二进制数为10011.101，浮点数表示为1.0011101×24。
2、因为是正数，所以符号位为0。
3、阶码为+4，8为指数位的移码偏移为127(27\-1)，4+127=131=10000011B。
4、尾数为1.0011101，由于所有浮点数的尾数都是1.××××的形式，所以可以将1舍去，只存储后面部分0011101.
三个部分合在一起，得到19.625在内存中的存储形式如下：

 如果是double类型存储，原理不变，只是指数位变为11位，对应的移码偏移为1023(210\-1)。

第九节 时空复杂度

基础知识

 算法是解决问题的方案，对同一个问题可能会有多种算法，那么通常如何评价一个算法的好坏，我们有以下标准：

1. 正确性：对合法输入、非法输入、边界输入都能够正确处理，输出合理的结果。
2. 可读性：算法应该描述清晰，方便阅读、理解和交流。
3. 健壮性：算法运行结果一致，对于相同的输入始终输出相同的结果。
4. 高效性：算法应占用最少的CPU和内存来得到满足的结果，这一点从时间复杂度和空间复杂度进行判定。

 简单来说就是：

• 时间效率： 算法运行有多快
• 空间效率： 内存占用有多少

但是运行时间和语言、机器和机器的状态、数据量的大小都有关系，无法准确衡量算法效率，所以通常用一个相对度量的概念来衡量。

时间复杂度

• 大T函数T(n)
  假设其他状态不变，仅当问题规模(数据大小)增大时，指令执行的次数也在增加，那么指令执行次数相对于问题规模来说，会构成一个函数T(n)。
  例如，对n个数求和的算法1+2+3+…+n：

int sum = 0;	\/\/指令数为1
for(int i = 0; i < n; i++)
	sum += n;	\/\/指令数为n
cout << n;		\/\/指令数为1

总的指令数为T(n) = n + 2。

• 大O函数O(n)
  假设一个算法的T(n) = 4n3+2n+5。当n越来越大时，对于T(n)增长的贡献来看，最高阶的n3占据主导地位，其他项可以忽略。
  我们一般用大O函数来表示最主要的贡献部分，O(T(n)) = O(n3)，就是算法的时间复杂度。
  大O函数的数学定义：存在正常数c和某个规模n0，如果对所有的n ≥ n0，都有f(n) ≤ cT(n)，则称f(n)为T(n)的大O函数，写成f(n) = O(T(n))。
  计算方法：对算法的指令次数进行计算组成T(n)，只保留最高阶项，然后去掉最高阶前面的常数。

• 常见大O函数

• 代码示例

 O(n)：输出数组元素。

for(int i = 0; i < n; i++)
	cout << a[n] << " ";

 O(log n)：给定n，求2的指数p，使得p ≤ n＜ 2p。

int p = 1;
while(p < n)
	p *= 2;
cout << p;

 $O(n^2)$：输出二维数组。

for(int i = 0; i < n; i++){
	for(int j = 0; j < n; j++)
		cout << a[i][j] << " ";
	cout << endl;
}

 O(nlog n)：

for(int i = 0; i < n; i++)
	for(int j = 0; j < n; j *= 2)
		...

空间复杂度
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量。
一个算法在计算机存储器上所占用的存储空间包括：

1. 算法代码本身所占用的存储空间
2. 算法的输入输出数据所占用的存储空间
3. 算法在运行过程中临时占用的存储空间
   其中，存储算法代码本身所占用空间与算法书写大的长短有关，要压缩这方面存储空间，就必须编写较短的代码。
   输入输出数据所占用空间由要解决的问题决定的，不会随算法的不同而改变。
   算法在运行过程中临时占用的空间会因算法的不同而异，有的算法只需要少量临时工作单元，而且不随问题规模大小而改变，是节省存储空间的算法；有的算法需要占用临时工作单元与解决问题的规模n有关，当n较大时，将占用较多的存储单元，比如归并排序。
   我们在分析算法的空间复杂度时要从各方面综合考虑。比如递归算法，一般比较简短，算法本身占用空间较少，但运行时需要一个附加栈，从而占用较多临时工作单元；若写成非递归算法，代码一般较长，本身占用空间较多，但运行时所需的存储单元较少。

• S(n)
  一个算法的空间复杂度只考虑在运行过程中为变量分配的存储空间的大小，记为S(n)，包括
  1）函数参数表中形参变量分配的存储空间
  2）函数体中定义的局部变量分配的存储空间
  若一个算法为递归算法，其空间复杂度为递归所使用的栈的空间大小，等于一次调用所分配的临时存储空间的大小乘以被调用的次数。
• 大O函数
  与时间复杂度类似，算法的空间复杂度一般也以数量级的形式O(n)给出。
  一般而言：
  1）当一个算法的空间复杂度S(n)为一个常量，即不随被处理数据量n的大小而改变，可表示为O(1)。
  2）当一个算法的空间复杂度S(n)与以2为底的n的对数成正比时，可表示为O(log n)。
  3）当一个算法的空间复杂度S(n)与n成线性比例关系时，可表示为O(n)。
  特殊的：
  1）若形参为数组，则只需要为它分配一个用于存储由实参传送来的一个地址指针的空间，即 一个机器字长空间
  2）若形参为引用方式，则也只需要为其分配用于存储一个地址的空间，即用它来存储对应实参变量的地址，以便由系统自动引用实参变量。
  在竞赛中，内存限制一般为128MB(或256MB)，都足够用了。

赛题训练

1. 若某算法的计算时间表示为递推关系式：
   T(N) = 2T(N / 2) + Nlog N
   T(1)=1
   则该算法的时间复杂度为( )。
   A.O(N) B.O(Nlog N) C.O(Nlog2 N) D.O(N2)
2. 假设某算法的计算时间表示为递推关系式：
   T(N) = 2T(N / 4) + sqrt(N)
   T(1)=1
   A.O(N) B.O(sqrt(N)) C.O(sqrt(N) log N) D.O(N2)
3. 设某算法的时间复杂度函数的递推方程是T(n) = T(n-1) + n(n为正整数)及T(0) = 1，则该算法的时间复杂度为( )。、
   A.O(log n) B.O(nlog n) C.O(n) D.O(n$^2$)

第十节 十大排序

基础知识

 十大排序是指将无序序列变为有序序列的十种常见排序算法，分别是：冒泡、选择、插入、快速、归并、希尔、堆、桶、基数、计数。
基础分类
排序方式：

 1）比较类排序：

• 交换类：冒泡排序、快速排序
• 插入类：插入排序、希尔排序
• 选择类“选择排序、堆排序
• 归并类：归并排序

 2）非比较类排序：基数排序、计数排序、桶排序。

 排序思路：

 我们这里以从小到大排序为例。

• 冒泡排序：两两比较、顺序不对就交换。
• 选择排序：左无序，右有序。找出无序部分中的最大值，放在最后(交换)。
• 插入排序：左有序，右无序。将无序部分第一个数往前移动，放在第一个比他小的数的后面。
• 快速排序：序列中选取基准值，然后分区(比基准值小的放在左侧，大的放在右侧)，然后递归每个分区。
• 归并排序：先分后合，将两个小的有序部分合并为大的有序部分。
• 希尔排序：插入排序的增量可视为1，在某些极端情况下效率较差。希尔排序改为设立增量序列，按增量序列执行多次插入排序。
• 堆排序：无需部分构建大顶堆，根节点值最大，与最后一个节点交换，重复这个过程，类似于选择排序。
• 桶排序：通过映射函数将待排序数据分组，对每个组选择合适的排序算法排序后，遍历每个桶，依次赋值回原数组。
• 基数排序：设立0~9是个桶数组，待排序数按个位放入桶中，依次拿出，再按十位、百位，重复上述过程。
• 计数排序：借助数组下标有序，先存入数组并统计个数，再遍历赋值回原数组。

 稳定性：
排序前如果有两个数a和b相等，a在b的前面，排序后a仍在b的前面，则该算法稳定；否则该算法不稳定。
稳定的排序：冒泡、插入、归并、计数、桶、基数
不稳定的排序：快速、堆、选择、希尔

 时空复杂度：
(n表示待排序数据规模，k表示待排序数据范围，对数以2为底)

赛题训练

1. 排序的算法很多，若按排序的稳定性和不稳定性分类，则( )是不稳定排序。
   A.冒泡排序 B.插入排序 C.快速排序 D.归并排序
2. 以下排序算法中，不需要进行关键字比较操作的算法是( )。
   A.基数排序 B.冒泡排序 C.堆排序 D.插入排序
3. 以下排序算法中，最好情况下最快的是( )。
   A.快速排序 B.冒泡排序 C.堆排序 D.归并排序
4. 设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组。那么，任何以元素比较作为基本运算的归并算法，在最坏情况下至少要做多少次比较？( )
   A.n2 B.nlog n C.2n D.2n - 1

第十一节 排列组合

基础知识

 排列是指从给定个数的元素中取出指定个数的元素进行排序。
组合是指从给定个数的元素中仅仅取出指定元素个数的元素，不考虑排序。
排列组合问题的关键就是研究给定要求的排列和组合可能出现的情况的总数。

定义与公式
排列：从n个不同元素中，任取m(m≤n，均为自然数)个不同的元素按照一定的顺序排成一列，所有排列的个数，称作从n个元素中取出m个元素的排列数。用符号 A ( n , m ) A(n,m) A(n,m)或 A n m A^m\n Anm​表示。计算公式如下：
A n m = n ! ( n − m ) ! A^m\_n=\frac{n!}{(n-m)!} Anm​\=(n−m)!n!​
组合：从n个不同元素中，任取m(m≤n)个元素并成一组，所有组合的个数，称作从n个元素中取出m个元素的组合数。用符号 C ( n , m ) C(n,m) C(n,m)或 C n m C^m\_n Cnm​表示。计算公式如下：
C n m = A n m m ! = n ! m ! ( n − m ) ! C^m\_n=\frac{A^m\_n}{m!}=\frac{n!}{m!(n-m)!} Cnm​\=m!Anm​​\=m!(n−m)!n!​
基本计数原理
加法原理：做一件事，完成它可以有n类办法，在第一类办法中有m1种不同的犯法，在第二类办法中有m2种不同的方法…在第n类办法中有mn种不同的方法，那么完成这件事共有 N = m 1 + m 2 + . . . + m n N=m\{1}+m\{2}+...+m\{n} N\=m1​+m2​+...+mn​种不同的方法。
乘法原理：做一件事，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法…做第n步有mn种不同的方法，那么完成这件事共有 N = m 1 × m 2 × . . . × m n N=m\{1}×m\{2}×...×m\_{n} N\=m1​×m2​×...×mn​种不同的方法。

范例精讲

 例1 从一个 4 × 4 4×4 4×4的棋盘中选取不在同一行也不在同一列上的两个方格，共有( )种方法。
A.60  B.72  C.86  D.64
【正确答案：B】
解析：对每个方格来说，与其不在同一行同一列的方格有 3 × 3 = 9 3×3=9 3×3\=9个，总共有 4 × 4 = 16 4×4=16 4×4\=16个方格，也就是会有 16 × 9 16×9 16×9种，但是会有重复的情况(A格和B格，B格和A格，是一种情况)，所以有 16 × 9 ÷ 2 = 72 16×9÷2=72 16×9÷2\=72种。

 例2 5个小朋友排成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有( )种不同的排列方法。
A.48  B.36  C.24  D.72
【正确答案：A】
解析：我们可以把双胞胎先看成一个整体，则问题变成了4个人的排列问题，共有 A ( 4 , 4 ) = 24 A(4,4)=24 A(4,4)\=24种，然后两个双胞胎内部的排列有 A ( 2 , 2 ) = 2 A(2,2)=2 A(2,2)\=2种，所以共有 24 × 2 = 48 24×2=48 24×2\=48种。

 例3 有5副不同颜色的手套(共10只手套，每副手套左右手各一只)，一次性从中取6只手套，请问恰好能配成两副手套的不同取法有( )种。
A.120  B.180  C.150  D.30
【正确答案：A】
解析：首先确定两副凑成一对的手套颜色组合用 C ( 5 , 2 ) = 10 C(5,2)=10 C(5,2)\=10种。然后是不成一副手套的两个手套的选择，先确定颜色组合有 C ( 3 , 2 ) = 3 C(3,2)=3 C(3,2)\=3种取法，再分左右手，每种颜色下又有 C ( 2 , 1 ) = 2 C(2,1)=2 C(2,1)\=2种取法，总共 10 × 3 × 2 × 2 = 120 10×3×2×2=120 10×3×2×2\=120种。

 例4 由数字 1 、 1 、 2 、 4 、 8 、 8 1、1、2、4、8、8 1、1、2、4、8、8所组成的不同的 4 4 4位数的个数是( )。
A.104  B.102  C.98  D.100
【正确答案：B】
解析：因为存在相同的值，不能一次性考虑完，需要分情况讨论。

• 1 、 2 、 4 、 8 1、2、4、8 1、2、4、8组成的 4 4 4位数： A ( 4 , 4 ) = 24 A(4,4)=24 A(4,4)\=24种。
• 1 、 1 、 2 、 4 、 8 1、1、2、4、8 1、1、2、4、8组成的 4 4 4位数(一定有两个 1 1 1)：先从 2 、 4 、 8 2、4、8 2、4、8三个数种选两个，再除去两个 1 1 1内部的重复排列： C ( 3 , 2 ) × A ( 4 , 4 ) / A ( 2 , 2 ) = 36 C(3,2)×A(4,4)/A(2,2)=36 C(3,2)×A(4,4)/A(2,2)\=36种。
• 1 、 2 、 4 、 8 、 8 1、2、4、8、8 1、2、4、8、8组成的 4 4 4位数(一定有两个 8 8 8)：同上，也有 36 36 36种。
• 1 、 1 、 8 、 8 1、1、8、8 1、1、8、8组成的 4 4 4位数：考虑两个 1 1 1和两个 8 8 8各自内部重复排列，共有 A ( 4 , 4 ) / ( A ( 2 , 2 ) × A ( 2 , 2 ) ) = 6 A(4,4)/(A(2,2)×A(2,2))=6 A(4,4)/(A(2,2)×A(2,2))\=6种。
  总共： 24 + 36 + 36 + 6 = 102 24+36+36+6=102 24+36+36+6\=102种。

 例5 设含有 10 10 10个元素的集合的全部子集数位 S S S，其中由 7 7 7个元素组成的子集数位 T T T，则 T / S T/S T/S的值为（ ）。
A. 5 / 32 5/32 5/32  B. 15 / 128 15/128 15/128  C. 1 / 8 1/8 1/8  D. 21 / 128 21/128 21/128
【正确答案：B】
解析：每个元素选入子集和不选入子集两种选择， 10 10 10个元素就有210\=1024种选择，即 S = 1024 S=1024 S\=1024。 T = C ( 10 , 7 ) = C ( 10 , 3 ) = 120 T=C(10,7)=C(10,3)=120 T\=C(10,7)\=C(10,3)\=120。 T / S = 120 / 1024 = 15 / 128 T/S=120/1024=15/128 T/S\=120/1024\=15/128。

 相同与不同、空与不空问题
盒子不空：

• 5个不同的小球放入3个不同的盒子(每盒不空)，一共有多少种放法？
  C 5 2 C 3 2 A 2 2 A 3 3 + C 5 1 C 4 1 A 2 2 A 3 3 = 150 \frac{C^2\_5C^2\_3}{A^2\_2}A^3\_3+\frac{C^1\_5C^1\_4}{A^2\_2}A^3\_3=150 A22​C52​C32​​A33​+A22​C51​C41​​A33​\=150
• 5个不同的小球放入3个相同的盒子(每盒不空)，一共有多少种放法？
  C 5 2 C 3 2 A 2 2 + C 5 1 C 4 1 A 2 2 A = 25 \frac{C^2\_5C^2\_3}{A^2\_2}+\frac{C^1\_5C^1\_4}{A^2\_2}A=25 A22​C52​C32​​+A22​C51​C41​​A\=25
• 5个相同的小球放入3个不同的盒子(每盒不空)，一共有多少种放法？
  C 4 2 = 6 C^2\_4=6 C42​\=6
• 5个相同的小球放入3个相同的盒子(每盒不空)，一共有多少种放法？
  1 + 1 = 2 1+1=2 1+1\=2

 盒子可空：

• 5个不同的小球放入3个不同的盒子(可有空盒)，一共有多少种放法？
  3 5 = 243 3^5=243 35\=243
• 5个不同的小球放入3个相同的盒子(可有空盒)，一共有多少种放法？
  1 + C 5 1 + C 5 2 + C 5 2 C 3 2 A 2 2 + C 5 1 C 4 1 A 2 2 = 41 1+C^1\_5+C^2\_5+\frac{C^2\_5C^2\_3}{A^2\_2}+\frac{C^1\_5C^1\_4}{A^2\_2}=41 1+C51​+C52​+A22​C52​C32​​+A22​C51​C41​​\=41
• 5个相同的小球放入3个不同的盒子(可有空盒)，一共有多少种放法？
  C 7 2 = 21 C^2\_7=21 C72​\=21
• 5个相同的小球放入3个相同的盒子(可有空盒)，一共有多少种放法？
  1 + 2 + 2 = 5 1+2+2=5 1+2+2\=5

赛题训练

1. 10个三好学生名额分配到7个班级，每个班级至少有一个名额，一共有( )种不同的分配方案。
   A.84 B.72 C.56 D.504
2. 把8个同样的球放在5个同样的袋子里，允许有的袋子空着，共有( )种不同的分法。(提示：如果8个球都放在一个袋子里，无论是哪个袋子，都只算一种分法。)
   A.22 B.24 C.18 D.20
3. 将7个名额分给4个不同的班级，允许有的班级没有名额，有( )种不同的分配方案。
   A.60 B.84 C.96 D.120
4. 甲、乙、丙三位同学选修课程，从4门课程中，甲选修2门，乙、丙各选修3门，则不同的选修方案共有( )种。
   A.36 B.48 C.96 D.192
5. 有7各一模一样的苹果，放到3个一模一样的盘子中，一共有( )种放法。
   A.7 B.8 C.21 D.37

第十二节 鸽巢原理

基础知识

 “鸽巢原理”又称“抽屉原理”，是组合数学中一个重要的原理，最先由19世纪的德国数学家狄利克雷运用于解决数学问题，所以又称“狄利克雷原理”。

第一抽屉原理
原理1：把多于n个物体放到n个抽屉里，则至少有一个抽屉里的物体不少于两个。
原理2：把多于mn+1（n不为0）个物体放到n个抽屉里，则至少有一个抽屉里有不少于m+1个物体。
原理3：把无数个物体放入n个抽屉，则至少有一个抽屉里有无数个物体。
第二抽屉原理
把mn-1个物体放入n个抽屉，其中必有一个抽屉中至多有m-1个物体。
原理案例

• 把10个苹果任意放在9个抽屉里，则至少有一个抽屉里含有两个或两个以上的苹果。
• 一年有365天，现有366人，则至少有两个人同一天生日。
• 抽屉中有10双手套，从中取11只出来，其中至少有两只是完整配对的。

鸽巢原理的题目在解题过程中就是保证在不达成题目条件的情况下，尽可能地多取。

范例精讲

 例1 5种颜色的袜子各15只混装在箱子里，试问无论如何取，从箱子中至少取出几只袜子，就能保证有3双袜子。（袜子无左右之分）
解析：首先保证不成对地取5只袜子，再取一只(6只)成第一对，再取刚刚成对的颜色的袜子(7只)，保证不成对；再取一只成第二对(8只)，同理，再取刚刚成对的颜色的袜子(9只)，保证不成对；最后取一只(10只)成第三对，总共10只。

 例2 有35个球，红、白、黄各10个，另外有3个蓝色、2个绿色，试问无论如何取，至少取几个小球就能保证有4个同色球。
解析：先取完蓝色和绿色（5个），再取红、白、黄各3个（14个），最后随便取一个（15），总共15个。

赛题训练

1. 一副纸牌除去大小王共有52张牌，四种花色，每种花色13张。假设从这52张牌中随机取13张纸牌，则至少( )张牌的花色一致。
   A.4 B.2 C.3 D.5

第十三节 容斥原理

基础知识

 在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥除去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。
基本计算公式
∣ A ∪ B ∣ = ∣ A ∣ + ∣ B ∣ − ∣ A ∩ B ∣ | A\\cup B|=|A|+|B|-|A\\cap B| ∣A∪B∣\=∣A∣+∣B∣−∣A∩B∣
∣ A ∪ B ∪ C ∣ = ∣ A ∣ + ∣ B ∣ + ∣ C ∣ − ∣ A ∩ B ∣ − ∣ A ∩ C ∣ − ∣ B ∩ C ∣ + ∣ A ∩ B ∩ C ∣ | A\\cup B\\cup C|=|A|+|B|+|C|-|A\\cap B|-|A\\cap C |-|B\\cap C|+|A\\cap B\\cap C| ∣A∪B∪C∣\=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣
( A 、 B 、 C A、B、C A、B、C为集合， ∣ A ∣ |A| ∣A∣表示 A A A集合内成员数量， ∪ \\cup ∪运算为并集， ∩ \\cap ∩为交集)

范例精讲

 例1 某班有学生45人，每人在暑假里都参加体育训练队，其中参加足球队的有25人，参加排球队的有22人，参加游泳队的有24人，足球、排球都参加的有12人，足球、游泳都参加的有9人，排球、游泳都参加的有8人，问：三项都参加的有多少人？
解析：设参加足球队的人数为A，参加排球队的人数为B，参加游泳队的人数为C，三项都参加的人数设为X。带入计算公式： 25 + 22 + 24 − 12 − 99 − 8 + X = 45 25+22+24-12-99-8+X=45 25+22+24−12−99−8+X\=45，解得 X = 3 X=3 X\=3。

 例2 分母是1001的最简分数一共有多少个？
解析：此题实际是找分子中不能与1001进行约分的数。由于先对1001质因子分解，可知 1001 = 7 × 11 × 13 1001=7×11×13 1001\=7×11×13，所以就是找不能被 7 、 11 、 13 7、11、13 7、11、13整除的数。
在 1 1 1~ 1001 1001 1001中，是 7 7 7的倍数的有 1001 / 7 = 143 1001/7=143 1001/7\=143个；是 11 11 11的倍数的有 1001 / 11 = 91 1001/11=91 1001/11\=91个；是 13 13 13的倍数的有 1001 / 13 = 77 1001/13=77 1001/13\=77个；是 7 × 11 7×11 7×11的倍数的有 1001 / 77 = 13 1001/77=13 1001/77\=13个；
是 7 × 13 7×13 7×13的倍数的有 1001 / 91 = 11 1001/91=11 1001/91\=11个；是 11 × 13 11×13 11×13的倍数的有 1001 / 143 = 7 1001/143=7 1001/143\=7个；是 7 × 11 × 13 7×11×13 7×11×13的倍数的有 1001 / 1001 = 1 1001/1001=1 1001/1001\=1个。
代入容斥原理基本计算公式：能被7或11或13整除的数有 ( 143 + 91 + 77 ) − ( 13 + 11 + 7 ) + 1 = 281 (143+91+77)-(13+11+7)+1=281 (143+91+77)−(13+11+7)+1\=281个，所以不能被 7 、 11 、 13 7、11、13 7、11、13整除的数有 1001 − 281 = 720 1001-281=720 1001−281\=720个。

赛题训练

1. 一次期末考试，某班有15个数学得满分，有12人语文得满分，并且有4人语、数都是满分，那么这个班至少有一门得满分得同学有多少人？( )
   A.23 B.21 C.20 D.22

2. 10 000以内，与10 000互质得正整数有( )个。
   A.2000 B.4000 C.6000 D.8000

   第十四节 概 率

基础知识

 概率是反映随机事件出现的可能性大小。随机事件是指在相同条件下，可能出现也可能不出现的事件。设对某一随机现象进行了 n n n次实验与观察，其中 A A A事件出现了 m m m次，即其出现的频率为 m / n m/n m/n。经过大量反复实验，常有 m / n m/n m/n越来越接近与某个确定的常数。该常数即为事件A出现的概率，常用 P ( A ) P(A) P(A)表示。
如果一个实验满足以下两条：
1)实验只有有限个基本结果
2)实验的每个基本结果出现的可能性是一样的
此类实验被称作古典实验，对于古典实验中的事件 A A A，它的概率定义为 P ( A ) = m / n P(A)=m/n P(A)\=m/n。其中 n n n表示该实验中所有可能出现的基本结果的总数目。 m m m表示事件 A A A包含的实验基本结果数，这种定义概率的方法称为概率的古典定义。

事件
在一个特定的随机试验中，称每一个可能出现的结果为一个基本事件，全体基本事件的集合称为基本空间，事件可分为以下几类：

• 必然事件：实验中必定会发生的事件。
• 随机事件：在一定的条件下可能发生也可能不发生的事件。
• 互斥事件：不可能同时发生的两个事件。
• 对立事件：两个事件中必有一个发生的互斥事件。

期望
是实验中每次可能出现的结果的概率乘以该结果的总和。反映了随机变量平均取值的大小。
举例说明：某城市有10万个家庭，没有孩子的家庭有1000个，有一个孩子的家庭有9万个，有两个孩子的家庭有6000个，有3个孩子的家庭有3000个。
将此城市中任一个家庭中孩子的数目看作一个随机变量，记为 X X X。它可能的取值有 0 、 1 、 2 、 3 0、1、2、3 0、1、2、3。其中， X X X取0的概率为0.01，取1的概率为0.9，取2的概率为0.06，取3的概率为0.03。
则它的数学期望 E ( X ) = 0 × 0.01 + 1 × 0.9 + 2 × 0.06 + 3 × 0.03 = 1.11 E(X)=0×0.01+1×0.9+2×0.06+3×0.03=1.11 E(X)\=0×0.01+1×0.9+2×0.06+3×0.03\=1.11，即此城市一个家庭平均有小孩1.1个，当然要按整数计算，约等于2个。

范例精讲

 例1 小明要去南美洲旅游，一共乘坐三趟航班才能达到目的地，其中第1个航班的准点概率是0.9，第2个航班的准点概率是0.8，第3个航班的准点概率是0.9.如果存在第i个(i=1,2)航班晚点，第i+1个航班准点，则小明将赶不上第i+1个航班，旅行失败；除了这种情况，其他情况下旅行都能成功。请问小明此旅行成功的概率是( )。
A.0.8 B.0.648 C.0.72 D.0.74
解析：倒着算更容易一些，找询问事件的对立事件，即旅行失败的概率，失败的情况有：

• 一晚二准三任意，概率为 0.1 × 0.8 × 1 0.1×0.8×1 0.1×0.8×1
• 一任意二晚三准，概率为 1 × 0.2 × 0.9 1×0.2×0.9 1×0.2×0.9
  P ( 失败的概率 ) = 0.1 × 0.8 + 0.2 × 0.9 = 0.26 P(失败的概率)=0.1×0.8+0.2×0.9=0.26 P(失败的概率)\=0.1×0.8+0.2×0.9\=0.26
  P ( 成功的概率 ) = 1 − 0.26 = 0.74 P(成功的概率)=1-0.26=0.74 P(成功的概率)\=1−0.26\=0.74

 例2 一家四口人，至少两个人的生日属于同一月份的概率是( )。(假定每个人的生日属于每个月份的概率相同且不同人之间相互独立)
A.1/12 B.0.1/144 C.41/96 D.3/4
解析：还是倒着算，“至少两个人的生日属于同一月份”的对立事件是“所有人的生日都不在同一月份”。
第一个人有12种选择，第二个人有11种，第三个人有10种，第四个人有9种。
P ( 都不在同一月份 ) = 12 × 11 × 10 × 9 / ( 12 × 12 × 12 × 12 ) = 55 / 96 P(都不在同一月份)=12×11×10×9/(12×12×12×12)=55/96 P(都不在同一月份)\=12×11×10×9/(12×12×12×12)\=55/96
P ( 至少两个人的生日属于同一月份 ) = 1 − 55 / 96 = 41 / 96 P(至少两个人的生日属于同一月份)=1-55/96=41/96 P(至少两个人的生日属于同一月份)\=1−55/96\=41/96

赛题训练

1. 假设一台抽奖机中有红、蓝两色的球，任意时刻按下抽奖按钮，都会等概率获得红球或蓝球之一。有足够多的人每人都用这台抽奖机抽奖，假如他们的策略均为：抽中蓝球则继续抽奖，抽中红球则停止。最后每个人都把自己获得的所有球放到一个大箱子里，最终大箱子里的红球与蓝球的比例接近于( )。
   A.1:2 B.2:1 C.1:3 D.1:1
2. 欢乐喷球：儿童游乐场有个游戏叫“欢乐喷球”，正方形场地中心能不断喷出彩色乒乓球，以场地中心为圆心还有一 圆形轨道，轨道上有一列小火车在匀速运动，火车有六节车厢。
   假设乒乓球等概率落到正方形场地的每个地点，包括火车车厢。小朋友玩这个游戏时，只能坐在同一个火车车厢里，可以在自己的车厢里捡落在该车厢内的所有乒乓球，每个人每次游戏有三分钟时间，则一个小朋友独自玩一次游戏期望可以得到（ ）个乒乓球。假设乒乓球喷出的速度为 2个/秒，每节车厢的面积是整个场地面积的 1/20。
   
   A.60 B.108 C.18 D.20
3. 在一条长度为1的线段上随机取两个点，则以这两个点为端点的线段的期望长度是( )。
   A.1/2 B.1/3 C.2/3 D.3/5

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-10-24 11:31:54

\/*
信友队：2024csp-j考前模拟赛 
x^6+2x^5-8x^4-10x^3+19x^2+8x-12
(x-2)(x-1)^2(x+1)(x+2)(x+3)


   anxn+a[n-1]x^(n-1)+....+a1x^1+a0
=(b[n-1]x^(n-1)+b[n-2]x^[n-2]...b1x+b0)*(x+c)   c是a0的因子
正向推导 
an=b[n-1]=1;                     b[n-1]=1
a[n-1]=c*b[n-1]+b[n-2]           b[n-2]=a[n-1]-c*b[n-1]
....

逆向推到
b0=a0\/c
a1=b0*c+b1   b1=a1-b0*c 
 
*\/ 

#include<bits\/stdc++.h>
#define ll long long
using namespace std;
const int N = 25;
ll n,cnt[N+5],a[N],na[N],nb[N],b[N];
string s;
bool check(int cp){

	b[n]=0;b[n-1]=1;
	for(int i=n-1;i>=1;i--){
		b[i-1]=a[i]-cp*b[i];
	}

	if(b[0]*cp!=a[0])return 0;
	return 1;
}
int main(){

	cin>>s;
	if(isdigit(s[0])){
		cout<<s;
		return 0;
	}
	int lstB=-1,len=s.length();
	for(int i=0,tmp;i<len;i++){
		if(s[i]=='x'){\/\/处理x的系数和指数 
			if(!i){\/\/i==0,直接向后找指数 
				if(s[i+1]!='^'){
					tmp=1;
				}else{
					i+=2;
					tmp=0;
					while(isdigit(s[i])){
						tmp=tmp*10+s[i]-'0';
						i++;
					}
					if(!tmp)tmp=1;
				}
				a[tmp]=1;
				n=tmp;
			}else{\/\/向前找对应的系数 tp
				int tp=0,tmpi=i;
				i--;
				while(isdigit(s[i])){
					i--;	
				}
				int flg=(s[i]=='-');
				i++;
				while(isdigit(s[i])){
					tp=tp*10+s[i]-'0';
					i++;
				}
				if(flg)tp*=-1;
				if(s[i+1]!='^'){\/\/向后找对应的指数 
					tmp=1;
				}else{
					i+=2;
					tmp=0;
					while(isdigit(s[i])){
						tmp=tmp*10+s[i]-'0';
						i++;
					}
				}
					
				a[tmp]=tp;
			}
		}
	}
	int ii=len-1;\/\/处理常数项 
	while(isdigit(s[ii]))ii--;
	bool flg=(s[ii]=='-');
	int tmp=0;
	ii++;
	while(isdigit(s[ii])){
		tmp=tmp*10+s[ii]-'0';
		ii++;
	}
	if(flg)tmp*=-1;
	a[0]=tmp;
	vector<int>vec;
	for(int i=1;i*i<=abs(a[0]);i++){\/\/处理常数项的因子 
		if(abs(a[0])%i==0){
			vec.push_back(i);
			if(i*i!=abs(a[0]))vec.push_back(abs(a[0])\/i);
		}
	}
	sort(vec.begin(),vec.end());

	vector<pair<int,int> >ans;
	int siz=vec.size();
	for(int i=0;i<siz;i++){
		int pos=vec[i]*-1;
		int cnt=0;
		while(check(pos)){\/\/找因子 
			for(int i=n;i>=0;i--)a[i]=b[i];
			cnt++;
			while(!a[n]&&n>=1)n--;
		}
		if(cnt)ans.push_back({pos,cnt});
		pos=vec[i];
		cnt=0;
		while(check(pos)){\/\/找到对应的的指数 
			for(int i=n;i>=0;i--)a[i]=b[i];
			cnt++;
			while(!a[n]&&n>=1)n--;
		}
		if(cnt)ans.push_back({pos,cnt});
	}	
	sort(ans.begin(),ans.end());
	for(auto i:ans){
		if(i.second==1){
			cout<<"(x"<<(i.first>0?"+":"")<<i.first<<")";
		}else{
			cout<<"(x"<<(i.first>0?"+":"")<<i.first<<")"<<"^"<<i.second;
		}
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-01 16:57:00

题解：

https://www.luogu.com.cn/blog/107669/cheng

https://www.luogu.com.cn/blog/mrc/k-ti-xie

https://www.luogu.com.cn/blog/107669/mystia

https://www.luogu.com.cn/blog/mrc/dai-ma-xiu-gai-ti-xie

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-29 10:02:28

作者：ryp

山东提供的是 Windows + NOI Linux 虚拟机。使用 Linux 主要是为了测试编译、时间与内存限制。

传输文件

首先打开终端。按 Super 键（Windows 键）打开搜索框，搜索 terminal 并运行，打开的是一个深紫色背景窗口。

把文件复制到主文件夹，类比 Windows 中的用户目录。在终端中，可以用 ls 命令查看当前文件夹内有哪些文件，检查代码是否复制错了地方。

我在我的工作目录下输入 ls，会得到类似这样的信息：

蓝色的是目录、绿色的是可执行文件，白色的是普通文件。因为我的系统是日用的，所以和考场中有的文件夹不同。一般的，看到有 Documents、Desktop，或者 文档、桌面 等文件夹，就是主目录。

编译源代码

要编译 a.cpp ，可以输入命令：

g++ a.cpp -o a -Wall -Wextra -std=c++14 -O2 -g

其中，g++ 是必须的；a.cpp 是文件名，可以更改；-o a 是指定可执行文件名，Linux 下的可执行文件是不带后缀名的；-Wall -Wextra 是打开所有警告；-std=c++14 是指定标准；-O2 是打开优化，可以删掉；-g 是打开调试符号，不会使用调试器的可以忽略。

运行测试

编译后，可以用 ls 命令查看是否多出来了 a 文件，即指定的可执行文件名。随后，使用 .\/a 命令可以运行这个程序。

以 A + B 为例。我这里的源代码名为 c.cpp，我希望它编译成 c。使用如下命令并运行、输入，得到期望输出：

如果运行编译命令后出现额外信息，是编译错误或者警告，具体和 Dev C++ 下栏中显示的错误相同。比如我将 cin >> a >> b 误写作 cin >> a >> c，会得到：

我们看看 RE 会怎么样。如下图：

我们故意 RE。

Segmentation fault，或者 段错误，是内存访问越界，或者 STL 容器的使用出错。删掉 cout << q[0] << '\n'，看看除零：

会显示 Floating point exception，或 浮点错误 等。有的 STL 错误还会附带 STL 的错误信息，这点和 Windows 是大体一致的。

测试用时

测试程序用时，可以用 time 或者 \/bin\/time 命令，后者显示的更多，不会的可以只用前者。具体的，使用 time .\/a 命令运行并测速，其他的和不测速时一样。由于用键盘输入的时间计入总时，所以最好使用文件输入。

我们以测速 .\/c 为例。这里我用了文件输入输出。

这里我测试了两次，分别是同一份源代码，O2 与不开启 O2 的速度。测评时间是 user 行后面的。这里是 0.104s（O2）与 0.258s（无优化）。

测试内存

内存分为静态内存和动态的。静态的是直接开的全局数组、变量、还有代码本身的长度。动态的如 vector、栈等 STL 容器。

静态内存可以用 size 命令测试。

找到输出的 dec，也就是倒数第三个，6408903，就是静态内存占用，单位是字节。除以 1048576 得到以 MB 为单位的静态内存。

动态内存不好直接测试，但是可以通过限制总内存使用量来判断是否超过内存限制。具体命令是：ulimit -v X，其中 X 是内存限制，单位是 KB。或者，可以使用 ulimit -v $((X * 1024))，X 同样是内存限制，但单位是 MB。记不住可以计算器换算后用前者。

以下面程序为例。

笔算可知内存占用是大概是 380MB。我们把内存放到 256MB：

ulimit 命令前，执行是正常的。执行 ulimit 命令后，我们发现出现 RE。这是因为 MLE 了。

注意内存限制如果过小，会导致终端的正常任务无法执行。这时打开一个新终端即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-05 14:43:14

T1:

考察基本表达式和最值函数

#include<iostream>
#include<stdio.h>\/\/文件输入输出需要用到的头文件 

using namespace std;
int a,b,c,s,ma;
int main(){
	freopen("exam.in","r",stdin);
	freopen("exam.out","w",stdout); 
	cin>>a>>b>>c;
	s=a+b+c;
	ma=max(max(a,b),c);
	cout<<s<<" "<<ma<<endl;

	return 0;
} 

T2

\/*
考察点1：数字分解，预计得分 40
考察点2：字符数组、ascii码，累加和 
*\/
#include<bits\/stdc++.h>
using namespace std;
int l,sum=0;
char s[10009];
int main(){
	freopen("bit.in","r",stdin);
	freopen("bit.out","w",stdout); 
	cin>>l;
	cin>>s;\/\/注意用字符串处理，数字的长度已经超过了long long 类型 
	for(int i=0;i<l;i++){
		sum+=s[i]-'0'; 
	}
	cout<<sum<<endl;
	return 0;
} 

T3

考察点：容斥。 这道题在考试中得分率比较低，小学生对平面直角坐标系理解和掌握的较少。找矩形的交集对很多考生来说是难点。

\/*
1.给定的矩形描述不一定是哪个两个对角线上的点，需要整理成统一的的左上角、右下角描述
2. 部分分n==1的情况容易处理：长×宽即可
3. n==2分两种情况
	两个矩形分离
	两个矩形有交集
需要注意的点：数据范围为10000*100000，要用long long 类型。 
*\/
#include <iostream>
#include <iomanip>
#include<stdio.h> 
using namespace std;
typedef long long ll;
struct node{\/\/左上角 和右下角 
	ll xa,ya,xb,yb;
}jx1,jx2,jx3;
int n;

node le_ri(){
	node t;
	cin>>t.xa>>t.ya>>t.xb>>t.yb;
	if(t.xa>t.xb)swap(t.xa,t.xb);
	if(t.ya>t.yb)swap(t.ya,t.yb);
	return t;
}
ll s(node t){
	return (t.xb-t.xa)*(t.yb-t.ya);
}
int main()
{
    freopen("garden.in","r",stdin);
    freopen("garden.out","w",stdout);
	cin>>n;
    jx1=le_ri();
    if(n==1){
    	cout<<s(jx1)<<endl;
    	return 0;
	}
	jx2=le_ri();
	if(jx1.xa>=jx2.xb||jx1.xb<=jx2.xa||jx1.ya>=jx2.yb||jx1.yb<=jx2.ya) {\/\/2在1的左侧，右侧，下侧，上侧 
		cout<<s(jx1)+s(jx2)<<endl;
		return 0;
	}
	\/\/相交的情况
	 jx3.xa=max(jx1.xa,jx2.xa);
	 jx3.xb=min(jx1.xb,jx2.xb);
	 jx3.ya=max(jx1.ya,jx2.ya);
	 jx3.yb=min(jx1.yb,jx2.yb);
	 cout<<s(jx1)+s(jx2)-s(jx3)<<endl;
       
}

T4

\/*
部分分1：考察数学与循环 50分
部分分2：N很大，循环超时，要优化。
	N%i==0的情况下，i，N\/i都是因子，找到小的，一定能对应到另一个大的。
	小的最大多大呢？sqrt(N) 
*\/
#include <bits\/stdc++.h>
using namespace std;
typedef long long LL;

int main()
{
	freopen("gem.in","r",stdin) ;
	freopen("gem.out","w",stdout);
	LL N,M;scanf("%lld%lld",&N,&M);
	LL ans=1;
	for(LL i=1;i*i<=N;++i)if(N%i==0)
	{
		if(i<=M) ans=max(ans,i);
		if(N\/i<=M) ans=max(ans,N\/i);
	} 
	printf("%lld\n",N\/ans);
	return 0;
}

T5

\/\/数据范围小，本题考察递归、回溯。算法是深度优先搜索 
#include <iostream>
using namespace std;
long long a[12],ans=0x7fffffffffffffff;
\/\/初始化ans无限大
int n;
char ope[12];\/\/记录操作字符
bool vis[12];\/\/状态数组
void dfs(int cur) {
	int i,j;
	if(cur==n-1) { \/\/回溯条件明确
		for(i=0; i<n; i++) {
			if(!vis[i])
				ans=min(ans,a[i]);\/\/没有被记录的数就是最终结果，求最小
		}
		return ;\/\/回溯
	}
	for(i=0; i<n; i++) {
		for(j=0; j<n; j++) {
			if(i==j||vis[i]||vis[j])   continue;
			\/\/若为同一个数或已被选用，跳过
			long long p=a[i];
			vis[j]=1;
			if(ope[cur]=='+')
				a[i]+=a[j];
			else if(ope[cur]=='*')
				a[i]*=a[j];
			dfs(cur+1);
			vis[j]=0;
			a[i]=p;\/\/还原
		}
	}
}
int main() {
\/\/	cout<<(long long)850*957*975*935<<endl;
	freopen("smallest.in","r",stdin);
	freopen("smallest.out","w",stdout);

	int i;
	cin>>n;
	for(i=0; i<n; i++)   cin>>a[i];
	for(i=0; i<n-1; i++)   cin>>ope[i]; \/\/输入

	dfs(0);
	cout<<ans;
	return 0;
}
\/*
7 17 3 25
+ * +
17+25=42
3*7=21
42+21=63
*\/

T6

\/*本题考察宽度优先搜索。镜像处理起来比较麻烦
在搜索的过程中记录前驱，以便输出路径。
*\/
#include <bits\/stdc++.h>

using namespace std;
const int maxn = 25;

char s1[maxn][maxn], s2[maxn][maxn];
int vis[maxn][maxn][maxn][maxn];
array<int,4> pre[maxn][maxn][maxn][maxn];
char ans[maxn][maxn][maxn][maxn];
int step[maxn][maxn][maxn][maxn];
vector<char>rec;

queue<array<int,4>>q;

void down(int x, int y, int x_, int y_) {
	int dx = x, dy = y, dx_ = x_, dy_ = y_;
	if(s1[x + 1][y] == '.') dx++;
	if(s2[x_ + 1][y_] == '.') dx_++;
	if(!vis[dx][dy][dx_][dy_]) {
		vis[dx][dy][dx_][dy_] = 1;
		q.push({dx, dy, dx_, dy_});
		pre[dx][dy][dx_][dy_] = {x, y, x_, y_};
		ans[dx][dy][dx_][dy_] = 'D';
		step[dx][dy][dx_][dy_] = step[x][y][x_][y_] + 1;
	}
}

void left(int x, int y, int x_, int y_) {
	int dx = x, dy = y, dx_ = x_, dy_ = y_;
	if(s1[x][y - 1] == '.') dy--;
	if(s2[x_][y_ + 1] == '.') dy_++;
	if(!vis[dx][dy][dx_][dy_]) {
		vis[dx][dy][dx_][dy_] = 1;
		q.push({dx, dy, dx_, dy_});
		pre[dx][dy][dx_][dy_] = {x, y, x_, y_};
		ans[dx][dy][dx_][dy_] = 'L';
		step[dx][dy][dx_][dy_] = step[x][y][x_][y_] + 1;
	}
}

void right(int x, int y, int x_, int y_) {
	int dx = x, dy = y, dx_ = x_, dy_ = y_;
	if(s1[x][y + 1] == '.') dy++;
	if(s2[x_][y_ - 1] == '.') dy_--;
	if(!vis[dx][dy][dx_][dy_]) {
		vis[dx][dy][dx_][dy_] = 1;
		q.push({dx, dy, dx_, dy_});
		pre[dx][dy][dx_][dy_] = {x, y, x_, y_};
		ans[dx][dy][dx_][dy_] = 'R';
		step[dx][dy][dx_][dy_] = step[x][y][x_][y_] + 1;
	}
}

void up(int x, int y, int x_, int y_) {
	int dx = x, dy = y, dx_ = x_, dy_ = y_;
	if(s1[x - 1][y] == '.') dx--;
	if(s2[x_ - 1][y_] == '.') dx_--;
	if(!vis[dx][dy][dx_][dy_]) {
		vis[dx][dy][dx_][dy_] = 1;
		q.push({dx, dy, dx_, dy_});
		pre[dx][dy][dx_][dy_] = {x, y, x_, y_};
		ans[dx][dy][dx_][dy_] = 'U';
		step[dx][dy][dx_][dy_] = step[x][y][x_][y_] + 1;
	}
}

signed main() {
	freopen("maze.in","r",stdin);
	freopen("maze.out","w",stdout);
	int qwq;
	scanf("%d",&qwq);
	for(int i = 1; i <= 20; i++) {
		scanf("%s", s1[i] + 1);
		scanf("%s", s2[i] + 1);
	}
	vis[20][20][20][1] = 1;
	q.push({20, 20, 20, 1});

	while(!q.empty()) {
		array<int,4>u = q.front();
		q.pop();
		\/\/ if(step[u[0]][u[1]][u[2]][u[3]] > 26 && u[0] == 1 && u[2] == 1) cout << u[0] << ' ' << u[1] << ' ' << u[2] << ' ' << u[3] << ' ' << step[u[0]][u[1]][u[2]][u[3]] << "\n";
		if(u[0] == 1 && u[1] == 20 && u[2] == 1 && u[3] == 1) {
			break;
		}
		down(u[0], u[1], u[2], u[3]);
		left(u[0], u[1], u[2], u[3]);
		right(u[0], u[1], u[2], u[3]);
		up(u[0], u[1], u[2], u[3]);
	}
	array<int,4> u = {1, 20, 1, 1};
	array<int,4> st = {20, 20, 20, 1};
	while(u != st) {
		rec.push_back(ans[u[0]][u[1]][u[2]][u[3]]);
		s1[u[0]][u[1]] = 'A';
		s2[u[2]][u[3]] = 'A';
		u = pre[u[0]][u[1]][u[2]][u[3]];
	}
	s1[20][20] = s2[20][1] = 'A';
	cout << rec.size() << "\n";
	if(qwq == 1) return 0;
	reverse(rec.begin(), rec.end());
	for(auto i : rec) cout << i;
	puts("");
	for(int i = 1; i <= 20; i++) {
		cout << s1[i] + 1 << ' ' << s2[i] + 1 << '\n';
	}
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-11 20:57:41

T1 病毒

这是一道签到题，考查数据类型和算术运算。 一个简单的除法，但是需要注意：$ 0 \leq m≤n≤2^{32} $，$ 2^{32} $正好是无符号长整型(unsigned (long int))的最大值加一，需要开超长整型((signed) long long (int)) 保留三位小数，有两种方法： 第一种：

#include<cstdio>
\/\/#include<stdio.h> 这两个头文件用其中一个即可

printf("%.3lf",ans);\/\/.3表示保留三位小数，lf表示double类型 

第二种：

#include<iomanip>

cout<<fixed<<setprecision(3)<<ans;\/\/3表示保留三位小数 

参考代码

#include<iostream>\/\/或者用万能头<bits\/stdc++.h>
#include<cstdio>
using namespace std;
int main()
{
	\/\/freopen("norovirus.in","r",stdin);
	\/\/freopen("norovirus.out","w",stdout);
	long long n,m;
	double ans;
	cin>>n>>m;
	ans=double(m*100)\/n;\/*处理百分号(%)，同时将m转换为double*\/
	\/\/输出可以使用以下三种方法其中之一。 
	\/\/方法1 
	printf("%.3lf%% ",ans);
	\/\/方法2
	cout<<fixed<<setprecision(3)<<ans<<"%";
	\/\/方法3 
	printf("%.3lf ",ans);
	cout<<"%"; 
	 
	return 0;
}

T2 四季

本题想考查分支结构，为了防止输出任意一种骗分，增加为四组数据。不会使用循环的同学可以将代码复制4次。

对有些同学来说，可能难点在提取月份上，有两种方法，一是通过整体读入整数取模，二是通过字符读入，只取最后两个，运算得出月份。

然后使用if语句或switch语句完成代码。

参考代码

#include<bits\/stdc++.h>
using namespace std;
int main() {
	int n;
	char a,b;
	for(int i = 1; i <= 4; i++) {
		\/*方法一 
		 
		cin >> n; \/\/输入
		int date = n % 100; \/\/取日期的后两位 月份
		*\/ 
		\/\/方法二 
		cin>>a>>a>>a>>a>>a>>b;
		int date= (a-'0')*10+b-'0'; 
		if(date == 0 || date > 12) { \/\/判断日期是否合法
			cout << "error" << endl;
			continue;
		}
		if(date >= 9 && date <= 11) { \/\/秋天
			cout << "autumn" << endl;
		} else if(date >= 3 && date <= 5) { \/\/春天
			cout << "spring" << endl;
		} else if(date >= 6 && date <= 8) { \/\/夏天
			cout << "summer" << endl;
		} else { \/\/冬天
			cout << "winter" << endl;
		}
	}
	return 0;
}

T3 二进制

本题考查了循环，进制转换，绝对值等。

参考代码

#include<bits\/stdc++.h>
using namespace std;
int n, ans;
long long a[200050];
short fun(long long x){
	int cnt[2] = {0};
	while(x){
		cnt[x&1] ++;
		x >>= 1;
	}
	return (cnt[1] > cnt[0]) ? 1 : -1;
}
int main(){
	
	freopen("binary.in","r",stdin);
	freopen("binary.out","w",stdout);
	cin >> n;
	for(int i = 1; i <= n; i ++) cin >> a[i];
	for(int i = 1; i <= n; i ++)
		ans += fun(abs(a[i]));
	cout << ans << endl;
	return 0;
}

T4 猜拳

本题考查了贪心算法。

思路

我们只讲述满分做法。

根据题意，对于小容出的每一个剪刀或石头或布，我们都尽量让他赢，得 $2$ 分。

所以我们尽量的让 $a_1$ 和 $b_2$ 匹配，$a_2$ 和 $b_3$ 匹配，$a_3$ 和 $b_1$ 匹配。

对于剩下的，我们尽量让他达成平局，得 $1$ 分。

因此尽量让剩下的 $a_1$ 和 $b_1$，$a_2$ 和 $b_2$，$a_3$ 和 $b_3$ 匹配。

剩下的只能输，不能得分。

可以证明，没有其他任何一种方法使得分数更高。

可结合代码理解。

参考代码

#include <bits\/stdc++.h>
#define endl '\n'
#define int long long
#define fi first
#define se second
using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f3f3f3f3f;
int n;
int a[3],b[3]; 
int ans;
signed main()
{
    \/\/freopen(".in","r",stdin);
    \/\/freopen(".out","w",stdout);
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=0;i<=2;i++) cin>>a[i];
    for(int i=0;i<=2;i++) cin>>b[i];
    int p=min(a[0],b[1]);
    ans+=2*p;
    a[0]-=p,b[1]-=p;
    p=min(a[1],b[2]);
    ans+=2*p;
    a[1]-=p,b[2]-=p;
    p=min(a[2],b[0]);
    ans+=2*p;
    a[2]-=p,b[0]-=p;
    ans+=min(a[0],b[0]);
    ans+=min(a[1],b[1]);
    ans+=min(a[2],b[2]);
    cout<<ans; 
    return 0;
}

还可以用循环优化下代码表达

参考代码二

#include<bits\/stdc++.h>
using namespace std;
int main(){
	int n,a[3],b[3],ans=0;
	cin>>n>>a[0]>>a[1]>>a[2]>>b[0]>>b[1]>>b[2];
	for(int i=0;i<3;i++)
	{
		int j=(i+1)%3;
		int k=min(a[i],b[j]);
		ans+=k*2;
		a[i]-=k;
		b[j]-=k;
	}
	for(int i=0;i<3;i++){
		int k=min(a[i],b[i]);
		ans+=k;
		a[i]-=k;
		b[i]-=k;
	}
	cout<<ans;
	return 0;
}

T5 写作业

本题考查了模拟和贪心算法，以及结构体排序等语法运用。

对于 $50\%$

考虑直接模拟这个过程，设立一个访问标记数组，每一轮找到没有选择过的最大值。因为答案最大为 $n$，所以时间复杂度 $O(n^2)$。

对于 $100\%$

考虑实际上要让最大的先拿，然后再让次大的拿，以此类推。

考虑最大的拿完后我们可能传到次大的，这样就可以在同一轮里拿多个，实际上就是如果他们的下标递增，那么就可以在同一轮里拿。

所以我们可以按照大小为第一关键字，从大到小排序，然后问题转化到了当前这个序列上，求有多少递增的连续段。

循环的同时我们判断当前的数是否比前面的数小，如果小的话那就说明不递增了，我们要新开一轮，然后就做完了。

参考代码

#include <bits\/stdc++.h>

using namespace std;

#define pii pair<int, int>

#define fi first
#define se second

#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

const int N = 1e5 + 10;

int n;

pii a[N];

int main()
{
    fst
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].fi, a[i].se = i;
    sort (a + 1, a + n + 1, [] (pii x, pii y) { return x.fi > y.fi; });
    int res = 1;
    for (int i = 1; i <= n; i++) if (a[i - 1].se > a[i].se) res++;
    cout << res;
    return 0;
}

T6 迷宫

信息学的成长路上怎么能少了迷宫问题呢？

思路

首先判断迷宫内空地的连通性，如果本来就不连通，那么及直接输出“No”。如果连通，连通块中包含的格式数要减少 $s$ 个，原来有 $ t $ 个，现在需要有 $t-s$个。

方法一

那么从任意一个空地开始，可以直接通过 $dfs$ 或者 $bfs$ 遍历找到$ t-s $个空地格子打标记，那么没打标记的空地格子就转换位字符'X'。

方法二

先将所有的空的格子转化为'X',再遍历，将 $ t-s $个'X'变为空地'.'

参考代码 方法二

#include <bits\/stdc++.h>
using namespace std;
int n,m,k,sx,sy,cnt,tot;
int dx[4] = {0,1,-1,0},dy[4] = {1,0,0,-1};
char mp[505][505];
void dfs(int x,int y){
    if (cnt == tot - k){
        for (int i = 1;i <= n;i++){
            for (int j = 1;j <= m;j++) cout << mp[i][j];
            cout << '\n';
        }
        exit(0);
    }
    for (int i = 0;i < 4;i++){
        int nx = x + dx[i],ny = y + dy[i];
        if (nx < 1 || nx > n || ny < 1 || ny > m || mp[nx][ny] != 'X') continue;
        mp[nx][ny] = '.',cnt++;
        dfs(nx,ny);
    }
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= m;j++){
            cin >> mp[i][j];
            if (mp[i][j] == '.') mp[i][j] = 'X',sx = i,sy = j,tot++;
        }
    }
    cnt = 1,mp[sx][sy] = '.';
    dfs(sx,sy);
    cout << "No";
    return 0;
}

参考代码 方法一

#include <bits\/stdc++.h>
using namespace std;
const int N = 510, dir[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
char s[N][N];
bool vis[N][N];
int n, m, k, cnt = 0, nr = 0;

void dfs (int x, int y) {
	if (vis[x][y]) return;
	--cnt;
	vis[x][y] = true;
	for (int l=0; l<4; l++) {
		int dx=dir[l][0], dy= dir[l][1];
		int i = dx + x, j = dy + y;
		if (!cnt) return;
		if (1 <= i && i <= n && 1 <= j && j <= m && !vis[i][j] && s[i][j] == '.') dfs (i, j);
	}
}

void dfs1 (int x, int y) {
	if (vis[x][y]) return;
	vis[x][y] = true, ++nr;
	for (int l=0; l<4; l++) {
		int dx=dir[l][0], dy= dir[l][1];
		int i = dx + x, j = dy + y;
		if (1 <= i && i <= n && 1 <= j && j <= m && !vis[i][j] && s[i][j] == '.') dfs1 (i, j);
	}
}

int main (void) {
	freopen("maze.in","r",stdin);
	freopen("maze.out","w",stdout);
	cin.tie (0)->sync_with_stdio (false);
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) cin >> (s[i] + 1);
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cnt += s[i][j] == '.';
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (s[i][j] == '.') {
				dfs1 (i, j);
				if (cnt != nr) {\/\/迷宫本来不连通 
					cout << "No\n";
					return 0;
				}
			}
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) vis[i][j] = false;

	cnt -= k;
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
			if (s[i][j] == '.') {
				dfs (i, j);
				if (cnt) {\/\/空地不够 
					cout << "No\n";
					return 0;
				}
				for (int i = 1; i <= n; i++, cout << '\n') for (int j = 1; j <= m; j++)
						if (s[i][j] == '.') cout << (vis[i][j] ? '.' : 'X');
						else cout << s[i][j];
				return 0;
			}
	abort ();
}

T6 奏鸣曲

思路分析

Subtask1

枚举，数据分为 $ 4 $ 类 A\B\C 或者 D...Z,每个位置暴力枚举，时间复杂度 $O(4^{n}) $

Subtask2

要出现ABC三种符号，可以同个状态压缩枚举当前出现的符号类型转移，但我们只需要种类数，可以直接记录出现的类别，就不要状态压缩了。 设 $f[i][j]$ 为前 $i$ 个位置出现过几个ABC。初始状态为 $f[0][0]=1$ 。 那么可以设计线性转移方程，时间复杂度 $O(n)$. $$ f[i][0]=f[i-1][0] \times 23
$$ $$ f[i][1]=f[i-1][0] \times 3 +f[i-1][1] \times 24 $$ $$ f[i][2]=f[i-1][1] \times 2 +f[i-1][2]*25 $$ $$ f[i][3]=f[i-1][2] +f[i-1][3] \times 26 $$

动态规划优化了解多的同学可以发现，这个式子可以用 $4 \times 4$ 矩阵快速幂优化，时间复杂度降为 $O(64*log^n)$,也可以解决 $100\%$的数据。

Subtask3

这是一个计数类问题，设 包含字符A的集合设为集合A;包含字符B的集合设为集合B,包含字符C的集合设为集合C. 那么问题的答案就是 $A \cap B \cap C $.

根据组合计数原理， $$|A \cap B \cap C|=\sum_{i=1}^{n-3}C_n^i \sum_{j=1}^{n-i-1}C_{n-i}^j\sum_{k=1}^{n-i-j}C_{n-i-j}^k23^{n-i-j-k} $$

这一坨式子看起来就很难计算，我们换个思路。

计数类问题常见的一个方法是正难则反。设所有可能字符串的集合是全集 $U$ ,$|U|=26^n$ 。

从全集中扣除 同时不包含ABC的符号，剩下的就是同时包含ABC的诗句了。 $$ A \cap B \cap C =

U-A' \cup B' \cup C' $$ 我们求集合 $A$ 的补集 $A'$,就是不包含字符'A'的集合，也就是每个位置其他 $25$ 个字符可选,$|A'|=25^n$ 。 同样的原理计算 $|A'B'|=24^n$ , $|A'B'C'|=23^n$,

$A' \cup B' \cup C' $= $$ |A'|+|B'|+|C'|-|A' \cap B'|-|A' \cap C'|-|B' \cap C'|+|A' \cap B' \cap C'| $$

带入上面的公式可得$26^n-325^n+324^n-23^n$

#include <iostream>
using namespace std;
#define int long long

const int P = 1e9+7;

int qpow(int a, int b)
{
	int res = 1;
	while(b)
	{
		if(b & 1)
			res = res * a % P;
		b >>= 1;
		a = a * a % P;
	}
	return res;
}

int F(int x) { return (x % P + P) % P; }

signed main()
{
	freopen("sonata.in","r",stdin); 
	freopen("sonata.out","w",stdout); 
	int n; cin >> n;
	if(n < 3)
		return cout << 0, 0;
	int all = qpow(26, n);
	int xxy = qpow(25, n);
	int x   = qpow(24, n);
	int oth = qpow(23, n);
	int res = F(3 * xxy - 3 * x + oth);
	cout << F(all - res) << '\n';
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-09 15:21:54

• 题目大意：从1号格子开始，每次可以跳跃到$i+a_i \times x$且$ \leq N$的位置。
• 题目分析

根据题意可以得出一个dp的方程 $dp[j]+=dp[i+a_i \times x]$ 时间复杂度$O(N^2)$

考虑优化：

$j=i+a_i \times x (x>=1)$

这里面$a_i$有可能相同，可能重合的线，这些线可以合并处理。 如果$a_i$互不相同，可以用类似埃筛的方法完成。 $a_i$大的时候直接处理。 $a_i$小的时候可以合并，通过前缀或后缀完成。$a_i$选多大呢，一般选$\sqrt n$。

• 如果 $a_k > \sqrt n$,直接枚举，时间复杂度为$ o(\sqrt n)$
• 如果$a_k \leq \sqrt n$ 时间复杂度$ o(\sqrt n)$预处理前缀和。

计算 $i=ak \times x+k$
$dp[i]=\sum(dp[k]) $ 如何找符号要求的k呢？
枚举已知$i，ak$，找到符合要求的$k $ ?

$k=i-ak \times x=i\%a_k $的数;令$j=a_k$，那么 $sum[j][i\%j]$存储了这样能到达$i$的$a_k$和$k$的对应情况

例如：i=11的时候，可以由哪些点转移而来呢？

        sum[1][0] 1+x;2+x,..,10+x
	sum[2][1] 1+2x,3+2x,..
	sum[3][2] 2+3x,5+3x..
	sum[4][3] 3+4x,7+4x..
	sum[5][1] 1+5x，6+5x..
	....
	sum[10][1] 1+10x... 

通过前缀和转移。
4+3x  sum[3][1]
5+3x  sum[3][2]
7+3x  这就可以与前面的4+3x合并处理sum[3][1] 

参考代码

#include<bits\/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int N=200005,M=400;
int n,a[N];
ll dp[N],sum[M][N],ans=0;\/\/sum[m][n]  kx+b 
int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
		scanf("%d",&a[i]);
	dp[1]=1;
	for(int i=1; i<=n;i++) {
		for(int j=1;j<M;j++){\/\/枚举前面符合要求的ak的前缀和 sum[ak][i] 
            dp[i]+=sum[j][i%j],dp[i]%=mod; 
        }
        ans=(ans+dp[i])%mod;
        \/\/维护前缀和 
		if(a[i]<M){
			sum[a[i]][i%a[i]]+=dp[i],sum[a[i]][i%a[i]]%=mod;
		}		 
		else{
			for(int j=i+a[i]; j<=n; j+=a[i])
				dp[j]+=dp[i],dp[j]%=mod;
		} 
	}
	printf("%lld\n",ans);
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-21 17:01:15

T417071 写作业

• 题目分析：

  • 50% 的数据：dp或者dfs记忆化均可

  $f[n]=min(f[n-1],f[n/2]+1$ ,$n$为偶数.

  $f[n]=f[n-1]+1$ ,$n$为奇数.

  • 100% 的数据，考察点：数学方法，二进制运算。 参考代码：

#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
ll n,cnt;
int main(){
	cin>>n;
	while(n>1){
		if(n&1)n--,cnt++;
		else n\/=2,cnt++;
	}
	cout<<cnt<<endl;
}

T417086 促销

• 题目分析 贪心+01背包变形。购买商品的方式可以通过优惠，也可以单独购买。题目要求最少的购买件数，那么我们买便宜的件数会更多。因此先排序。 设购买前i件的最少花费为$f[i]$. $$ f[i]=min(f[i-1]+a[i],f[i-k]+2 \times a[i])

$$

参考代码

\/*
物品可以有用优惠购买，也可以不用优惠。 
*\/ 
#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+9;
ll a[N], f[N],n,p,k,ans=0;
int main() {
    cin >> n>>p>>k;
   	for(int i=1;i<=n;i++)cin>>a[i],f[i]=2e9;
   	sort(a+1,a+1+n);
   	for(int i=1;i<=n;i++){
   		if(f[i-1]>p) break;
   		f[i]=min(f[i],f[i-1]+a[i]);
   		if(i>=k)f[i]=min(f[i],f[i-k]+2*a[i]);
   		if(f[i]<=p)ans=i;
	}
	cout<<ans<<endl;
}

T418732 种花还是种草

• 题目大意 给出有 $N $个顶点的带边权完全图，选任意条顶点不重合的线段，求最大边权和。 $N<=16$,暴搜或者状压DP都可以。

  状态DP,设$f(i)$为选了二进制i中包含点的最大距离，从$i$状态中枚举其中的两个点$j,k$个点为新连接的两个点，则，则转移方程为 $$ f(i)=max(f(i-2^j-2^k)+a_{i,j})
  $$

时间复杂度$o(n^22^n)$

参考代码

#include <bits\/stdc++.h>
using namespace std;
int a[1010][1010];
long long f[1010101];
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n-1; ++i) for (int j = i + 1; j < n; ++j) cin >> a[i][j];
	for (int i = 0; i <= (1 << n); ++i) {
		for (int j = 0; j < n; ++j) {
			if (i & (1 << j)) {
				for (int k = j + 1; k < n; ++k) {
					if (i & (1 << k)) f[i] = max(f[i ^ (1 << j) ^ (1 << k)] + a[j][k], f[i]);
				}
			}
		}
	}
	long long an = 0;
	for (int i = 0; i <= (1 << n); ++i) {
		an = max(an, f[i]);
	}
	cout << an << '\n';
	return 0;
}

T275408 收菜

每个袋子只能装1种物品，用刚好能装的下的最下背包来装这个物品。

60%的数据

$n^2$处理把物品放入哪个袋子。

100%的数据

要找更快的匹配方法。

• 方法一 处理价值大的物品，给物品找袋子

贪心先从价值大的开始装。找到能装上且浪费空间最少的袋子，用上他。可以用一个袋子的多重集，二分查找，用掉一个删掉一个。

• 方法二 找出袋子能装入的最大价值物品，给袋子找物品。 看袋子能装入那些，从可以装入的物品中选出价值最大的。

把袋子和物品都按照体积排序。

把袋子大小能容纳的物品放入价值优先的优先队列。从能装入的物品中选择价值最大的。

T417069 小容玩Arcaea

• 题目分析 考虑 DP。

$f(i,j)$为掷了$i$次硬币，计数器示数为 连续$j$次为正面的最大收益。 如果 $j=0$，则说明上一次掷到的是反面，所以上一次计数器的示数可以是$0$到 $i$之间的任意整数。因为上一次为反面，所以没有奖励。 所以此时 $f(i,j)=max (f(i-1,k)),0\leq k<j$的最大值。

如果 $j≥1$,则说明上一次掷到的是正面，所以上一次计数器的示数一定是$j-1$。因为上一次是正面，所以会有奖励,所以此时

$f(i,j)=max(f(i-1,j-1)+a_i+b_i)$

答案为$max( f(n,k))$ $(0≤k≤n) $的总和。

参考代码

\/\/ABC261D
#include<iostream>
#define int long long
using namespace std;

const int N = 5010;

int n, m, ans;
int a[N], b[N];
int f[N][N];

signed main()
{
	cin >> n >> m;
	for(int i=1; i<=n; i++)
	{
		cin >> a[i];
	}
	for(int i=1; i<=m; i++)
	{
		int x, y;
		cin >> x >> y;
		b[x] = y;
	}
	for(int i=1; i<=n; i++)
	{
		for(int j=0; j<=i-1; j++)
		{
			f[i][0] = max(f[i][0], f[i-1][j]);
		}
		for(int j=1; j<=i; j++)
		{
			f[i][j] = max(f[i][j], f[i-1][j-1] + a[i] + b[j]);
		}
	}
	for(int i=1; i<=n; i++)
	{
		ans = max(ans, f[n][i]);
	}
	
	cout << ans;
	return 0;
}

T417054 菜园

• 题目分析

一个有 $n$个格子的长纸条，第 $ i$个格子颜色为 $a_i$，价值为$ b_i$，现在要任选 $ k$种颜色，使得所有颜色是较大编号的格子都在较小编号的后面，求最大价值。

按照题目的意思，想在要求同样的格子颜色是连续的，那么需要选的两种颜色要分布的左右区间不能相交。这样就转换为一段一段区间的选。考虑设计以颜色为主体的状态，在加上所选的颜色种类数，也就是序列的长度，设计两维状态。设 $f(i,k)$为选了颜色 $i$ 为结尾，选了 $k$ 种颜色的最小价值 。

那么需要统计每种颜色左侧和右侧 出现的位置。 记 $l_i$表示颜色$ i$ 第一次出现的位置， $ r_i$表示颜色 $i $最后一次出现的位置。那么只有满足$ r_j<l_i$时才能选$i,j$两种颜色。

$f(i,k)=min(f(j,k-1)+b[i])$，$j<i,r_j<l_i$. 第$i$种颜色对应的格子都在第j种格子的右边,$j<i$保证了颜色编号的上升。

• 时间复杂度$o(n^2k)$，加了区间限制条件后跑不满。

参考代码：

#include<bits\/stdc++.h>
using namespace std;
typedef long long ll;
const int N=509; 
ll n,m,ans=-1,a[N],b[N];
ll l[N],r[N],f[N][N];
int main(){
	memset(f,-1,sizeof(f));
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
	for(int i=1;i<=n;i++){
		if(!l[a[i]]) l[a[i]]=i;
		r[a[i]]=max(r[a[i]],(ll)i);
	}
	f[0][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<i;j++){
		    if(l[i]<=r[j])continue;
			for(int k=1;k<=m;k++){
				if(f[j][k-1]!=-1) f[i][k]=max(f[i][k],f[j][k-1]+b[i]);
			}
		}
	}
	for(int i=1;i<=n;i++) ans=max(ans,f[i][m]);
	printf("%lld\n",ans);
	return 0;
}

T275421 逛菜园

• 题目大意

给你一个矩阵，从最后一行开始走，到了每一行第一个到的点时只能向左或者向上走，否则就可以向左向右向上走，最终走到第一行结束，求经过所有格子的最小值。

坐标类型的动态规划。考虑设 $f(i,j)$表示从到 $i$ 行，第 $j $可以获得的最小代价。

那么如何转移呢？

显然，进入第 $ i$ 行时的列数一定是 $≥j$ 的，这样才能到达第 $j $列。

考虑从刚进到第 $ i$ 行的点 $ k$ 跑到 $ j $的路径上的点一定是要算代价的，而同时可以再往左跑一段后跑回来。

这样此题复杂度就成 $O(n^3 )$ 的了,会超时。

如何优化呢?可以发现从右下走到左上的过程中，可以向左多跑一段，跑到哪里为止呢？越小越好，大于$0$就停止了，转化为预处理一个以 $j$ 为终点的最小子段和$sum(i,j)$。

两种情况：

• 从$i+1$过来,到$j$列的左侧逛一圈。
• 从$j+1$过来，如果$j+1$已经往左逛一圈了，到$j$这里就没必要再逛了，实际就是$j+1$的子段和是否连接了j，条件就是$sum[i][j]>0$。

$$ f(i,j)= min(f(i+1,j)+sum(i,j),f(i,j+1)+max(sum(i,j),0)) $$

于是此题复杂度 $ O(n^2 )$。

写作业: B3636 文字工作(数据增加了，和原题不一样)

促销:忘记来源了，自己造的数据

收菜:P6538 [COCI2013-2014#1] LOPOV

小容玩Arcaea:ABC261D

种花还是种草:AT_abc318_d [ABC318D] Gener

单调不下降的菜园: P9688 Colo.

逛菜园：P6649 「SWTR-5」Grid

描述： 虽然叫动态规划的期末考试，也不一定都是动态规划，还是根据题目时间情况分析。

难度：普及-到普及+

赛时答疑与赛后题解： 题解 奖励：

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-22 19:32:56

• 题目大意

给定一个长度为$n$的序列，如果区间 $[L,R]$ 中存在 $L \leq i<j<k\leq R$ ,使得 $a_i-a_j=a_j-a_k$ 成立，则这个区间为好区间。问共有多少个好区间。

• 题目分析

为了不重不漏的统计，我们限定右端点 $k$ ,去找符和要求的左端点 $left$ 。 找出符要求的 $i,j,k$ ,可以发现 $a_i,a_j,a_k$ 构成等差数列，数据的范围是 $1...10$ ,符合要求的的情况为 $1，5，9$ ; $10， 6，2$ 等。可以推导出公差的范围为 $-4..4$ .

已知 $a_k$ ,枚举公差，找到符合要求的前两项的值，设数组 $mp[i][j]$ 存储符合要求的最近数值。找到以 $k$ 为结束点的最近 $left$。

如何去维护 $mp[i][j]$ 呢？对于当前点 $k$ 来说，只会改变与 $mp[i][a_k]$ 相关的数据，$mp[i][a_k]=( i$ 出现的最后位置 $)$ 。因此我们还需要用一个桶记录这个位置。

再维护一个 $left$ 的前缀 $max\_left$ ,那么答案就是不断累加从 $1$号结点到 $max\_left$ 的值，也就是 $ans+=max\_left$ 。

时间复杂度为 $O(N \times 10)$ 。

• 参考代码

#include <bits\/stdc++.h>
using namespace std;
#define int long long
int n;
int a[100005];
int mp[11][11],l[11];
signed main(){
	
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	int ans=0,lf=0,mlf=0;
	\/\/对每一个右端点q，找其符合要求的最近左端点lf，和前缀最大左端mlf点比较  ans+=mlf
	for(int k=1;k<=n;k++) {
		for(int d=-4;d<=4;d++){\/\/枚举公差 
			if(a[k]+2*d>=1&&a[k]+2*d<=10)lf=max(lf,mp[a[k]+2*d][a[k]+d]);
			mlf=max(mlf,lf);
		}
		ans+=mlf;
		for(int i=1;i<=10;i++){
			if(l[i])mp[i][a[k]]=l[i];
		}
		l[a[k]]=k;	
	}
	
	cout<<ans<<endl;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-29 20:24:02

过马路

假如一个人 $i$ 和一个车 $j$ 在 $T$ 相撞，有 $(T,a_i)=(b_j,T)$。

所以此时一定有 $a_i=b_j=T$，又由于 $a_i,b_j$ 两两不同，所以一个人仅可能和一辆车相撞，对于一组人与车，只要删去其中任何一个即可。

所以需要维护一个查询一个数是否在一个集合中出现的数据结构，使用 $\text{std::set}$ 即可。

时间复杂度 $O(n\log n)$。

参考代码：liuzixuan

#include <bits\/stdc++.h>
#define endl '\n'
using namespace std;
const int N=1e5+10;
unordered_map<int,int> mp;
int n,m,r,c;
int cnt;
int t;
int x;
signed main()
{
\/\/	freopen("cece3.in","r",stdin);
\/\/    freopen("cece.out","w",stdout);
    cin>>t;
    while(t--)
    {
        cin>>n>>m>>r>>c;
        mp.clear();
        cnt=0;
        for(int i=1;i<=n;i++)
        {
            cin>>x;
            mp[x]++;
        }
        for(int i=1;i<=m;i++)
        {
            cin>>x;
            mp[x]++;
        }
        for(auto y:mp)
        {
            if(y.second==2)
            {
                cnt++;
            }
        }
        cout<<cnt<<endl;
    }
    return 0;
}

子序列

算法一：$n\le12$，$q\le100$

我会状压！

预处理出每个长度不超过 $n$ 的 01 串的答案。具体来说，枚举一个子序列并判断是否合法，如果合法则把它加入答案集合。

时间复杂度 $\text O(2^n+q)$。

算法二：$n\le100$，$q\le100$

我会 DP！

对于每个询问，设 $f_{i,j}$ 表示区间匹配到 $i$，在原串上子序列匹配到 $j$ 是否可行，转移类似 LCS。

时间复杂度 $\text O(n^2q)$

算法三：$n\le1000$，$q\le1000$

我会优秀地枚举！

对于每个询问，考虑枚举一个子序列没选择的位置 $i$，预处理出区间 $[l,r]$ 在 $s_{1\dots i-1}$ 作为子序列出现的最长前缀长度 $pre_i$ 和在 $s_{i+1\dots n}$ 作为子序列出现的最长后缀长度 $suf_i$，那么有答案等价于 $pre_i+suf_i\ge r-l+1$ 且 $pre_i,suf_i>0$。

时间复杂度 $\text O(nq)$

算法四：$n\le1\times10^5$，$q\le1\times10^5$

我会找性质！

答案是 Yes 当且仅当下面两种情况至少满足一个：

1. $s_l$ 第一次出现不是在 $l$。

2. $s_r$ 最后一次出现不是在 $r$。

证明：

• 必要性：

以情况 1. 为例，选择 $s_l$ 第一次出现的位置和 $s_{l+1\dots r}$ 即可，情况 2. 类似。

• 充分性：考虑它的逆否命题。

假设 $s_l$ 第一次出现在 $l$ 且 $s_r$ 最后一次出现在 $r$。

仍然考虑算法三中的做法，枚举一个子序列没选择的位置 $i$。由于 $s_l$ 第一次出现在 $l$，所以 $p_1\ge l$，因此 $pre_i\le \max\{i-l,0\}$。同理可得 $suf_i\le\max\{r-i,0\}$。

因为要求 $pre_i,suf_i>0$，所以 $l<i<r$，此时 $pre_i+suf_i\le (i-l)+(r-i)=r-l<r-l+1$，因此无解，证毕。

本题时间复杂度 $\text O(n+q)$。

参考代码：guoweifeng

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<map>
#define int long long
using namespace std;
const int N=1e5+10;
const int M=20+10;
const int maxs=1e9;
const int mins=-1e9;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; ch=getchar();}
	while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
	return s*w;
}
int T;
int n,q;
char s[N];
int st[2],e[2];
signed main()
{
	T=read();
	while(T--)
	{
		n=read();
		q=read();
		cin>>s+1;
		st[0]=maxs;\/\/0在串中第一次出现的位置 
		st[1]=maxs;
		e[0]=0;\/\/在串中最后一次出现的位置 
		e[1]=0;
		for(int i=1;i<=n;i++)
		{
			if(st[0]==maxs&&s[i]=='0')\/\/更新0出现的位置 
				st[0]=i;
			if(st[1]==maxs&&s[i]=='1')
				st[1]=i;
		}
		for(int i=n;i>=1;i--)
		{
			if(e[0]==0&&s[i]=='0')
				e[0]=i;
			if(e[1]==0&&s[i]=='1')
				e[1]=i;
		}
		while(q--)
		{
			int l,r;
			l=read();
			r=read();
			if(l>st[s[l]-'0']||r<e[s[r]-'0'])\/\/左端点之前或右端点之后。 
				cout<<"Yes"<<"\n";
			else
				cout<<"No"<<"\n";
		}
	}
	return 0;
}

烦恼

本题由于同时有两个变量，如果同时考虑，过于复杂。

1. 小Z本身在动，每秒可以走S步。

2. 狗仔每秒同时向4个方向在动

其实样例解释也是在提示我们，我们可以把停留若干秒后再去判定是否到家比较容易，所以，我们可以把计算问题转换为判定问题。

由于小Z和狗仔的步长不一样，同时处理不太方便。我们可以用BFS预处理出每一个格子被狗仔占领的最早时间$t_{i,j}$,那么我们只需要保证小Z到达每一个格子的时间严格小于被狗仔占领的最早时间$t_{i,j}$即可。

小Z的步长有 $S$ ,每一秒可以往外走 $S$ 步，其实我们也可以用BFS解决，BFS处理出小Z到达每一个格子的曼哈顿距离(最小步数),设为 $step$ ,那么就可以算出来小Z到达这个格子所需的时间为 $step/S$ ,设这个时间为 $t$。

• 其实，我们可以贪心的来看，小Z每一秒一定是走S步的，走得快一定比走得慢要好，除非离家已经不足S步。

那么,我们只需要保证小Z到达这个格子的时间t加上小Z在原地吃饭停留的时间x严格小于ti,j即可。我们只需要不断地扩展这个合法的格子直到回到家或者没有状态可以更新(只剩下私人住宅)。

计算时间复杂度

• 我们预处理狗仔队到达每一个格子的时间，只需要把狗仔队起点全部入队做一次BFS,为 $O(n^2)$

• 然后我们枚举小Z停留的时间 $x$,显然停留时间范围在 $[0,n]$ 中间

• 总时间复杂度为 $O(n^4)$,无法通过 $n≤800$ 的数据。

但是，我们很容易发现，该问题具有單调性，可以二分，如果停留 $x$ 秒可以到家，那么停留小于 $x$ 秒一样可以可以到家，如果 $x$ 秒不能到家，那么大于 $x$ 秒也不能到家。

参考代码

#include <bits\/stdc++.h>
#define mk make_pair
#define pii pair<int, int>
#define fr first
#define sc second
using namespace std;

int sx, sy, ex, ey, n, s;
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
char m[1001][1001];
int bk[1001][1001], vis[1001][1001];

bool checkbfs(int x, int y) {
    if (x < 1 || x > n || y < 1 || y > n)
        return false;
    if (m[x][y] == 'T' || m[x][y] == 'D')
        return false;
    if (bk[x][y] != -1)
        return false;
    return true;
}
bool check1(int x, int y, int step) {
    if (x < 1 || x > n || y < 1 || y > n)
        return false;
    if (step >= bk[x][y] * s && m[x][y] != 'D')
        return false;
    if (vis[x][y])
        return false;
    return true;
}

bool check(int t) {
    queue<pair<pii, int> > q;
    memset(vis, 0, sizeof(vis));
    q.push(mk(mk(sx, sy), t * s));
    vis[sx][sy] = 1;
    while (!q.empty()) {
        int x = q.front().fr.fr, y = q.front().fr.sc, st = q.front().sc;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (check1(nx, ny, st + 1)) {
                if (nx == ex && ny == ey)
                    return 1;
                vis[nx][ny] = 1;
                q.push(mk(mk(nx, ny), st + 1));
            }
        }
    }
    return false;
}
int i, j;
int main() {
    cin >> n >> s;
    memset(bk, -1, sizeof(bk));
    queue<pair<pii, int> > q;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            cin >> m[i][j];
            if (m[i][j] == 'M')
                sx = i, sy = j;
            if (m[i][j] == 'D')
                ex = i, ey = j;
            if (m[i][j] == 'H')
                bk[i][j] = 0, q.push(mk(mk(i, j), 0));
        }
    }
    while (!q.empty()) {
        int x = q.front().fr.fr, y = q.front().fr.sc, st = q.front().sc;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (checkbfs(nx, ny))
                bk[nx][ny] = st + 1, q.push(mk(mk(nx, ny), st + 1));
        }
    }
    if (!check(0))
        return cout << -1, 0;
    int l = 0, r = bk[sx][sy], mid;
    while (l < r) {
        mid = (l + r) >> 1;
        if (check(mid))
            l = mid + 1;
        else
            r = mid;
    }
    cout << l - 1;
    return 0;
}

种树

因为我们只能将序列中的数增加，对于 $A_i<A_j$，$A_j$ 能移动到的位置 $A_i$ 一定能移到，所以我们将 $A$ 从大到小排序。

考虑如下贪心策略：排序后由大往小遍历，并将当前数移动到目前最小的未被占用的位置，这个可以使用一个栈进行维护，实现不难，具体可以参考 std（如果能拿到的话）。

证明：考虑两个数 $x,y\ (x<y)$，他们最终将移到 $p$ 和 $q\ (p<q)$，显然会将距离较大的一组匹配较小的 $b_i$，又由于无论是哪种匹配方式，移动的距离和不变，所以说两个的距离差越大越好，即 $x\to q$，$y\to p$ 是更好的方案，可以发现，这要求我们对更大的 $A_i$ 匹配尽量小的位置，即上述结论。

时间复杂度 $\text O(n\log n)$，瓶颈在于排序。

例如：1 3 3 3 4 4 4 9 最终：1 3 4 5 6 7 8 9

例如：1 3 3 3 4 4 4 9 最终：1 3 5 6 4 7 8 9

高度和最后是固定的，一样的。怎样最小呢？用的$$b_i$排序后中来数越小越好。 变化的数： 3 3 4 4 匹配到： 5 6 7 8 匹配的顺序 8 7 6 5 匹配的差值 5 4 2 1

#include<bits\/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pi pair<int,int>
#define ld long double
#define vi vector<int>
#define all(x) begin(x),end(x)
using namespace std;
const int N=3e6+10,p=998244853;
int a[N],b[N],val[N];
int main()
{
	
	int n;
	scanf("%d", &n);
	for(int i=1;i<=n;i++) scanf("%d", &a[i]);
	for(int i=1;i<=n;i++) scanf("%d", &b[i]);
	sort(a+1,a+n+1),sort(b+1,b+n+1);
	vector<pi>s;
	a[n+1]=2e9;
	for(int i=n;i;i--)
	{
	    if(a[i]!=a[i+1])s.push_back({a[i],a[i+1]-1});
	    int &l = s.back().first, &r = s.back().second;
	    val[i]=(l++)-a[i];
	    if(l>r)s.pop_back();
	}
	ll ans=0;
	
	sort(val+1,val+n+1);
	for(int i=1;i<=n;i++)ans=(ans+(ll)val[n-i+1]*b[i]%p)%p;
	cout<<ans<<endl;
}

\/*
8
1 3 3 3 4 4 7 15
1  3 4 10 20 30 40 50
*\/