que

¬ 等逻辑运算符优先级

最近

待办

NOIP 2011 T26

NOIP 2013 T27

CSP 模拟 2020 T18

NOIP 2015 T19

时间复杂度分析

容斥原理

康托展开

csp 2019 74

T6

由数字1, 1, 2, 4, 8, 8所组成的不同的4位数的个数是（）。

这个似乎没有更好的办法了，枚举四位数的组合

组合	个数
1124	$A(4,2)=12$
1128	$A(4,2)=12$
1148	$A(4,2)=12$
1248	$A(4,1)=24$
1288	$A(4,2)=12$
1488	$A(4,2)=12$
2488	$A(4,2)=12$
1188	$C(4,2)=6$

总和即为$102$

T8

G是一个非连通无向图（没有重边和自环），共有28条边，则该图至少有 （）个顶点。

注意到非联通，即为$8+1=9$

T9

一些数字可以颠倒过来看，例如0、1、8颠倒过来还是本身，6颠倒过来是 9,9颠倒过来看还是6,其他数字颠倒过来都不构成数字。类似的，一些多位数也可以颠倒过来看，比如106颠倒过来是901 。假设某个城市的车牌只有5位数字，每一位都可以取0到9。请问这个城市有多少个车牌倒过来恰好还是原来的车牌，并且车牌上的5位数能被3整除？（）

1. A. 40 B. 25 C. 30 D. 20

我有个绝妙的写法，首先车牌号必须是对称的（中间那位不管），因此确定了前三位我们就确定了答案

每一位的合法状态如下图

$$\begin{gathered} \begin{bmatrix} 0\\1\\8\\6\\9 \end{bmatrix} \begin{bmatrix} 0\\1\\8\\6\\9 \end{bmatrix} \begin{bmatrix} 0\\1\\8 \end{bmatrix} \\ \equiv \begin{bmatrix} 0\\1\\2\\0\\0 \end{bmatrix} \begin{bmatrix} 0\\1\\2\\0\\0 \end{bmatrix} \begin{bmatrix} 0\\1\\2 \end{bmatrix} \end{gathered}$$

统计权值之和为3的倍数的路径即可，这个可以用csp出现dp我倒立女装的 dp解决

T16 阅读程序

#include <cstdio>
using namespace std;
int n;
int a[100];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    int ans = 1;
    for (int i = 1; i <= n; ++i) {
        if (i > 1 && a[i] < a[i - 1])
            ans = i;
        while (ans < n && a[i] >= a[ans + 1])
            ++ans;
        printf("%d\n", ans);
    }
    return 0;
}

程序的意图是找接下来的第一和比他大的位置 $-1$

3） 若将第12行的 < 改为 !=，程序输出的结果不会改变。（）

本身只有这个数比上一个数小的时候才会重新找第一个比它大的的位置 $-1$，如果改成 $\neq$ 会重新走到$ans$ 的位置再继续找，对答案无影响

4） 当程序执行到第16行时，若ans - i> 2,则a[i + 1] < a[i]。 （）

就是考这个程序的作用

#include <iostream>
#include <string>
using namespace std;
const int max1 = 202;
string s, t;
int pre[max1], suf[max1];

int main() {
    cin >> s >> t;
    int slen = s.length(), tlen = t.length();

    for (int i = 0, j = 0; i < slen; ++i) {
        if (j < tlen && s[i] == t[j]) ++j;
        pre[i] = j; // t[0..j-1] 是 s[0..i] 的子序列
    }

    for (int  i = slen - 1 , j = tlen - 1; i >= 0; --i) {
        if(j >= 0 && s[i] == t [j]) --j;
        suf[i]= j; // t[j+1..tlen-1] 是 s[i..slen-1] 的子序列
    }

    suf[slen] = tlen -1;
    int ans = 0;
    for (int i = 0, j = 0, tmp = 0; i <= slen; ++i){
        while(j <= slen && tmp >= suf[j] + 1) ++j;
        ans = max(ans, j - i - 1);
        tmp = pre[i];
    }
    cout << ans << endl;
    return 0;
}

4） （2分）当t是s的子序列时，pre数组和suf数组满足：对任意0 <= i < slen, pre[i] > suf[i + 1] + 1。 （）

考虑AAB,AA

此时列表

	0	1	2
pre[i]	1	2	2
suf[i]	0	0	1

此时取等

5） 若tlen=10,输出为0,则slen最小为（）。

不能读入空穿，因此至少为1

6） 若tlen=10,输出为2,则slen最小为（）。

此题求得是保证 $t$ 是 $s$ 的子序列 $s$ 能删去最多连续的元素的个数，因此为10

T 19

题目太长了不复制

先读题，可以看出来是一个模拟拓扑排序的

unlock=0说明没有依赖任务了

4. ④处应填（）
   cnt[child[target][i]] -= 1
   cnt[child[target][i]] = 0
   unlock[child[target][i]] -= 1
   unlock[child[target][i]] = 0
5. ⑤处应填（）
   unlock[i] = cnt[i]
   unlock[i] = m
   unlock[i] = 0
   unlock[i] = -1

4实际上就是在模拟拓扑排序，5实际上在赋初值，故选C和B（此时cnt[i]=0，但是m和cnt[i]等价）

完善程序第二题

博弈论套路$f[i]$ 设的是剩下 $i$ 枚石子是否有必胜策略

2.②处应填（ )

A a[j] < i

B a[ j ] == i

C a[j] !=i

D a[j]>1

你看看后面 $\text{trans}$ 是不是没重新赋值啊（

况且是不是要大于等于就可以了

​ 5.⑤处应填（ )

||| trans = status | trans ^ win
||| status = trans >> 1 ^ win
||| trans = status ^ trans | win
||| status = status << 1 ^ win

首先确认对 $status$ 下手

B显然不对，所以 讲D为什么正确

$status$ 表示 $[i-64,i-1]$ 是否为 $\text{N-position}$

这就相当于取前$64$ 位，保留$[i-63,i-1]$ 在加上这一位就行了

noip 2011 79.5

T4.寄存器是CPU的重要组成部分

更细一点，从实现的功能方面看，CPU大致可分为如下八个逻辑单元：

（1）指令寄存器

（2）指令译码器

（3）控制单元

（4）寄存器

（5）逻辑运算单元（ALU）

（6）预取单元

（7）总线单元

（8）数据高速缓存

T10.防AK题

T11.是具有2011个叶子节点而不是叶节点，此时树高超过11即可（$2^{10}=1024$）

T18.阶码指明了小数点在数据中的位置

反码：解决负数加法运算问题，将减法运算转换为加法运算，从而简化运算规则；
作用：
1、在加、减、乘、除等运算过程中用作中间数。
2、实现某些特定功能的逻辑设计上经常要用到，特别是在判断语句，循环语句等需要做出判断的时候。

补码：补码主要是为了cpu运算器在进行减法运算时避免借位而设立的。

T20.网络协议

物理层：以太网 · 调制解调器 · 电力线通信(PLC) · SONET/SDH · G.709 · 光导纤维 · 同轴电缆 · 双绞线等
数据链路层：Wi-Fi(IEEE 802.11) · WiMAX(IEEE 802.16) ·ATM · DTM · 令牌环 · 以太网 ·FDDI · 帧中继 · GPRS · EVDO ·HSPA · HDLC · PPP · L2TP ·PPTP · ISDN·STP · CSMA/CD等
网络层协议：IP (IPv4 · IPv6) · ICMP· ICMPv6·IGMP ·IS-IS · IPsec · ARP · RARP · RIP等
传输层协议：TCP · UDP · TLS · DCCP · SCTP · RSVP · OSPF 等
应用层协议：DHCP ·DNS · FTP · Gopher · HTTP· IMAP4 · IRC · NNTP · XMPP ·POP3 · SIP · SMTP ·SNMP · SSH ·TELNET · RPC · RTCP · RTP ·RTSP· SDP · SOAP · GTP · STUN · NTP· SSDP · BGP 等

估计就要IP IS-IS TCP HTTP SSH 这些

T22.

DACHEBGIF->ACDHEBGIF->ABCDHEGIF->ABCDHEFGI->ABCDEFGHI

故四次

T26

本质就是模拟二进制位数，然后枚举每两个数的popcount

这个还没理，明天来

NOIP 2013 76.5

T9.

需要注意的是$34\mod 11=1,\lfloor\sqrt{2}\rfloor=1$

T11.

需要注意的是 $\frac{144}{4}=36$

(上面两个都死在了计算错误)

T10.

ipv6的常识？

冒分十六进制表示法：

格式为：X:X:X:X:X:X:X:X 前导0可省略

0位压缩表示法

连续的0压缩成 ::

内嵌IPv4地址表示法

X:X:X:X:X:X:d.d.d.d

T13.

浮点数，是属于有理数中某特定子集的数的数字表示，在计算机中用以近似表示任意某个实数。具体的说，这个实数由一个整数或定点数（即尾数）乘以某个基数（计算机中通常是2）的整数次幂得到，这种表示方法类似于基数为10的科学计数法。

一个浮点数a由两个数m和e来表示：a = m × b^e

由此可以看出，在计算机中表示一个浮点数，其结构如下：
尾数部分（定点小数） 阶码部分（定点整数）

阶符±	阶码e	数符±	尾数m
1	8	23	32

下面仅以float（带符号，单精度,32位）类型的浮点数说明C++中的浮点数是如何在内存中表示的。先讲一下基础知识，纯小数的二进制表示。
纯小数要想用二进制表示，必须先进行规格化，即化为 $1.xxxxx * ( 2 ^ n )$ 的形式。对于一个纯小数D,求n的公式如下：
$n = 1 + \log2(D)$ // 纯小数求得的n必为负数
再用 $D / ( 2 ^ n ) $就可以得到规格化后的小数了。接下来就是十进制到二进制的转化问题，为了更好的理解，先来看一下10进制的纯小数是怎么表示的，假设有纯小数D,它小数点后的每一位数字按顺序形成一个数列：${k1,k2,k3,…,kn}$
那么D又可以这样表示：

$D = k1 / (10 ^1 ) + k2 / (10 ^ 2 ) + k3 / (10 ^ 3 ) + ... + kn / (10 ^ n )$

推广到二进制中，纯小数的表示法即为：

$D = b1 / (2 ^ 1 ) + b2 / (2 ^ 2 ) + b3 / (2 ^ 3 ) + ... + bn / (2 ^ n )$

现在问题就是怎样求得b1,b2,b3,……,bn。算法描述起来比较复杂，还是用数字来说话吧。声明一下,1 / ( 2 ^ n ）这个数比较特殊，我称之为位阶值。

T19

P 验证和找到答案都容易

NP 验证容易找到答案难

NPC 所有NP都可以规约到这个NP

NP hard 不确定是不是NP 但可以规约到NPC

T22.

递推 $\frac{\sum{}f(i)}{n}+1=f(n)$

T24.

B看成100了痛失8分

T27.

看做是分治，离开分治的是有序满足答案的数组，否则就不是

然后一直做即可

NOIP2012 46

暴死力

T4

OSI模型

T6

电子管->晶体管->集成电路->大规模和超大规模集成电路

T11 看做是有一个 $2$ 的常数

T14 三原色

颜料三原色（CMYK）：品红、黄、青(天蓝)、黑 [1] 。色彩三原色可以混合出所有颜料的颜色，同时相加为黑色，黑白灰属于无色系。
光学三原色（RGB）：红、绿、蓝(靛蓝)。光学三原色混合后，组成显示屏显示颜色，三原色同时相加为白色，白色属于无色系（黑白灰）中的一种。

T16

对于边权全为正的，最短路一定不包括环

T17

异或不满足分配律的例子：

1^(0&1)!=(1^1)&(0^1)

1^(1|0)!=(1^1)|(1^0)

T18

十进制下的无限循环小数（不包括循环节内的数字均为 0 或均为 9 的平凡情况），在二进制下有可能是（ ）。

显然会出现循环节

T19

E-mail服务协议

常用的电子邮件协议有SMTP、POP3、IMAP4，它们都隶属于TCP/IP协议簇，默认状态下，分别通过TCP端口25、110和143建立连接。下面分别对其进行简单介绍。

T20

以下关于计算复杂度的说法中，正确的有（ ）。

1. A. 如果一个问题不存在多项式时间的算法，那它一定是 NP 类问题
2. B. 如果一个问题不存在多项式时间的算法，那它一定不是 P 类问题
3. C. 如果一个问题不存在多项式空间的算法，那它一定是 NP 类问题
4. D. 如果一个问题不存在多项式空间的算法，那它一定不是 P 类问题

不存在多项式时间，就说明是个 $NP,NP-hard$

不存在多项式空间，即不是$PH$,不是$P$ 也不是 $NP$

T21

问了一下有神仙用真值表做的有神仙用卡诺图做的还有神仙枚举做的

还是不会？

T22

树形 $dp$

设$f(i),g(i)$ 表示选或不选这个点得到的独立集种类

$f(1)=1,g(1)=1$

转移就是$f(t)=g(lson)*g(rson)$

$g[t]=(f(lson)+g(lson))*(f(rson)+g(rson))$

直接大力做

注意没有左儿子或右儿子把没有那边设为$f=1,g=1$

然后得到左儿子和右儿子都是 $f=16,g=44$

答案即为$3600+1936=5536$

海亮CSP2020模拟 68.5

怀疑存在的问题：splay是平衡树（2分），$O(mlogn)$ 的生成树（4分）,T10

T9

-g 是产生调试信息，-debug啥都不是

-o 是指定生成文件的名称

蒙对了草

已知袋子 $\alpha$ 装有 4 张 5 元纸币和 3 张 1 元纸币，袋子$\beta$ 中 装有 2 张 10 元纸币和 3 张 1 元纸币，袋子 $\gamma$ 装有 3 张 20 元纸币和 3 张 50 元纸币，现在每个袋子从随机选出 2 张纸币丢弃，记第 $i$ 个袋子此时剩下的纸币面值之和为 $v_i$ ,则 $v_{\alpha} < v_{\beta}<v_{\gamma}$ 的概率为____.

是个高联的题，然后加上了一堆没用的东西

即$\Delta \alpha>\Delta b$

B只能取 $2$ 个 $1$ ，情况为$C_{3,2}=3$

A只能取最多一个 $1$ 情况次数是 $C_{7,2}-C_{3,2}=18$

总情况为$\frac{3*18}{C_{7,2}C_{5,2}}=\frac{9}{35}$

如果算概率的话就是$\frac{C_{3,2}}{C_{5,2}}*\frac{C_{7,2}-C_{3,2}}{C_{7,2}}=\frac{9}{35}$

好像没更简单的做法了

T12

第二类斯特林数，待办

T13

煮定理

设一个递推关系

$T(n)=aT(\frac{n}{b})+f(n)$

$a$ 为递推的子问题数量,是常数

$\frac{n}{b}$ 为子问题规模,$b$ 是常数

$f(n)$ 为递推以外进行的工作

此题是求$T(n)=k\sqrt{n}T(\sqrt{n})+n$ 的复杂度

这个比较麻烦，感觉是不可做之题，而且把式子转成 $T(n) = C_1\frac{n}{e^2}+n\log_2(\ln n)$ 才能计算复杂度

先咕咕咕

T14

感觉是个模拟吧，不知道是不是矩阵树的那个 $G\cdot e$

有空再看吧

T18 取模就不用怕

T21

利用了自然溢出

T25

有点怪，我觉得$n=100,m=1$ 也是合法的输入

T32

T33 眼瞎了没看到新图

NOIP 2014 69.5

草为啥今天都是这个分

T1 面向对象

一般认为，较典型的面向对象语言有：
simula 67，支持单继承和一定含义的多态和部分动态绑定；
Smalltalk支持单继承、多态和动态绑定；
EIFFEL，支持多继承、多态和动态绑定；
C++，支持多继承、多态和部分动态绑定。
Java，支持单继承、多态和部分动态绑定。
五种语言涉及概念的含义虽然基本相同，但所用术语有别。
C#，也支持单继承，与Java和C++等有很多类似之处

T12

同时查找2n 个数中的最大值和最小值，最少比较次数为( ).

两个分组，小的和最小值比，大的和最大值比，此时次数为$3n$

对开始的两个显然不需要比，所以次数为$3n-2$

T18

Oracle貌似是个数据库管理系统？

T21

见CSP2019的解析

T24

从$(3,1,6)$ 开始

合法的状态有 $(2,2,6),(2,3,6),(2,4,6),(2,5,6),(2,6,6)$

$(1,3,6),(1,4,6),(1,5,6),(1,6,6)$ 分别能贡献$4,3,2,1$ 的答案

总和就是 $4+3+2+1+3+2+1+2+1+1=20$

T26

没有注意到从1开始转两次，然后后面的都错位了

T27

没有注意到 一次给出数组各项（数组下标从0到a-1）

然后头铁默认的$(0,n)$ 暴死

总结：知识性错误是最少的，但是粗心犯的最多

洛咕模拟 83

交上去uke了还行（

T4

我记得写的是 25，怎么交上了个 8 MB(

这个考小学的乘法

T7

没看后面的更正，以为每次第一个第二个可以只用盘一次，于是就是79，以为有更好下届，于是选了78

实际上首先两两分组，然后再分组，答案为$42*2=82$

T11

枚举$c$ ,然后插板，答案就是$C_{5,1}+C_{5,1}+C_{5,1}+C_{3,1}$

T14

森林的定义：

森林是一个高密度树木的区域。这些植物群落覆盖着全球大面积并且对二氧化碳下降、动物群落、水文湍流调节和巩固土壤起着重要作用，构成地球生物圈当中的一一个最重要方面。森林包括乔木林和竹林。

如果一个无向图的每一个连通分支都是树，称为森林

因此就是 $21-6=15$

T19（R1T4）

$\text{memset(255,-1)}$ 在char里面表示都是 $(11111111)_2$ 因此是一样的

T23 (R2T2)

现在不知道为啥与 $m$ 无关

草读入 $m$ 条边

T29 (R3T2)

这个是组合数，并且存在模数

T30

显然是因为存在模数

T35(C1T2)

从题意出发，是求独立集的个数，从叶子开始，最后，由于有$n+1$ 条边故存在环，第一次dfs是求得不包含环的块的的最大独立集数量，第二次是剩下的环和环到根这一块。

考虑贪心的正确性，由于如果是叶子的父亲是一个点，叶子的父亲的儿子大于等于1，因此正确性显然

NOIP2015 79.5

T6

下面有四个数据组，每个组各有三个数据，其中第一个数据为八进制数，第二个数据为 十进制数，第三个数据为十六进制数。这四个数据组中三个数据相同的是（ ）。

1. A. 120 82 50 B. 144 100 68 C. 300 200 C8 D. 1762 1010 3F2

$(120)_8=64+16=80$

$(144)_8=64+32+4=100,(68)_{16}=96+8=104$

$(300)_8=64*3=192$

$(1762)_8=512+7*64+6*8+2=1010,(3F2)_{16}=256*3+15*16+2=1010$

T7

前序遍历序列与后序遍历序列相同的二叉树为（ ）。

1. A. 非叶子结点只有左子树的二叉树 B. 只有根结点的二叉树 C. 根结点无右子树的二叉树 D. 非叶子结点只有右子树的二叉树

前序遍历：根左右

后序遍历：左右根

因此只能有根

T19

下列有关树的叙述中，叙述正确的有（ ）。

1. A. 在含有 n 个结点的树中，边数只能是(n-1)条 B. 在哈夫曼树中，叶结点的个数比非叶结点个数多 1 C. 完全二叉树一定是满二叉树 D. 在二叉树的前序序列中，若结点 u 在结点 v 之前，则 u 一定是 v 的祖先

涉及到哈夫曼树的性质，咕一下

T21

在 1 和 2015 之间（包括 1 和 2015 在内）不能被 4、5、6 三个数任意一个数整除的数 有_________个。

列容斥原理式子（自动脑补下取整）

$\frac{2015}{4}+\frac{2015}{5}+\frac{2015}{6}-\frac{2015}{20}-\frac{2015}{30}-\frac{2015}{12}+\frac{2015}{60}=940$

上面求得是能被整除的，答案即为 $2015-940=1075$

注意容斥的时候分母是 $\text{lcm}$

T22

考察卡特兰数基本应用

令h(0)=1,h(1)=1，catalan数满足递推式。**h(n)= h(0)*h(n-1)+h(1)*h(n-2) + … + h(n-1)h(0) (n>=2)。**也就是说，如果能把公式化成上面这种形式的数，就是卡特兰数。

当然，上面这样的递推公式太繁琐了，于是数学家们又求出了可以快速计算的通项公式。h(n)=c(2n,n)-c(2n,n+1)(n=0,1,2,…)。这个公式还可以更简单得化为h(n)=C(2n,n)/(n+1)。后一个公式都可以通过前一个公式经过几步简单的演算得来。

（CSDN）

T27

且两个连续子序列之间至少间隔 1 个数

没看到这句话，我死了

NOIP2016: 81?

怪毙了洛咕的补全程序基本得自己给分（

第 6 题

表达式 a*(b+c)-d 的后缀表达形式为（ ）。

A. abcd*± B. abc+d- C. abc+d- D. -+*abcd

这个没补锅

T10

$0\pmod 3=0$!

T11

盘子是一样的！

插板应该比较麻烦，看了下网上的有用插板口胡的（

插板可以确定答案的上界是21（此时盘子得不同）

枚举，如果只有一个盘子非空，答案是1

如果有两个，答案是3((1,6),(2,5),(3,4))

如果有三个，答案是4((1,3,3),(1,1,5),(1,2,4),(2,1,4),(2,2,3),(3,1,3),(3,2,2)去重)

T14

假设某算法的计算时间表示为递推关系式$ T(n) = 2T(\frac{N}{4})+sqrt(n)$$T(1) = 1$
则算法的时间复杂度为（ ）

这个做的时候完全是因为发现树的深度会降一半，考虑$\log n^{0.5}=0.5\log n$ 然后才选对的

考虑主定理，$b=4,a=2,\log_b(a)=0.5$

因此复杂度即为$\sqrt{n}\log n$

(本质上似乎也等价于主定理？)

T16 防AK题

GPRS英文简称为 General packet radio service，中文名称为通用无线分组业务，是一种基于GSM系统的无线分组交换技术，提供端到端的、广域的无线IP连接。相对原来GSM的拨号方式的电路交换数据传送方式，GPRS是分组交换技术，具有“实时在线”“按量计费”“快捷登录”“高速传输”“自如切换”的优点。通俗地讲，GPRS是一项高速数据处理的技术，方法是以“分组”的形式传送资料到用户手上。GPRS是GSM网络向第三代移动通信系统过渡的一项2.5代通信技术，在许多方面都具有显著的优势

T24

我又老又笨，脑子短路了，这实际上就是判断后面的缩写是不是前面的字符，但是我脑子短路认为第一个循环是因为缩写的长度都比后面小于是直接输出NO

T23

注意每个数字后面都要输出一个,

NOIP2018 78

废了废了

T9

假设一台抽奖机中有红、蓝两色的球，任意时刻按下抽奖按钮，都会等概率获得红球或蓝球之一。有足够多的人每人都用这台抽奖机抽奖，假如他们的策略均为：抽中蓝球则继续抽球，抽中红球则停止。最后每个人都把自己获得的所有球放到一个大箱子里，最终大箱子里的红球与蓝球的比例接近于（ ）。

A. 1 : 2 B. 2 : 1 C. 1 : 3 D. 1 : 1

很水，期望蓝球的个数是$\sum\frac{1}{n}\to1$,红球必然是 $1$ 因此是 $1:1$

T14

下列说法中，是树的性质的有（ ）。

A. 无环 B. 任意两个结点之间有且只有一条简单路径 C. 有且只有一个简单环 D. 边的数目恰是顶点数目减1

理解错题意了草，以为是只有树具备的性质

ABD显然

T15

下列关于图灵奖的说法中，正确的有（ ）。

A. 图灵奖是由电气和电子工程师协会（IEEE）设立的。 B. 目前获得该奖项的华人学者只有姚期智教授一人。 C. 其名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵。 D. 它是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称。

由美国计算机协会(ACM)于1966年设立，防AK题差评

T17

方程 a*b = (a or b) * (a and b)，在 a, b 都取 [0, 31] 中的整数时，共有_____组解。（*表示乘法；or 表示按位或运算；and 表示按位与运算）

性质找对了（$b$是 $a$ 的子集的情况成立），但是没考虑$a$ 是 $b$ 的子集

分两部分考虑，设 $f(a)$ 表示 $[0,a]$ 中满足 $a\geq b$ 使得等式成立的个数，考虑二进制，可以得到转移 $f(i)=f(i>>1)\times 2+f(i)>>1$

可以得到$f(31)=243$

考虑 $a $ 是 $b$ 的子集，记 $a$ 的有 $k$ 位 $1$，那么一共有$2^{6-k}-1$ 种情况(存在一个$1$ )

$31+C_5^1\times15+C_5^2\times7+C_5^3\times3+C_5^4\times1+C_5^5\times0=211$

答案即为$243+211=454$

T21

求这个排列的接下来$n$ 项

这东西就是细心，真的没啥办法了

待办康托展开

T22

这个大概懂了，刚开始这个链表是有序的，然后你不断地把这个点插入到对应的下标

T23

首先搞懂$f[i]$ 的意义，即前$k$次消费中在第一家店花 $i$ 元在第二家店花费最小值，每次刷新前先统计答案

NOIP2017 77.5

头铁去写了，还好没炸太惨

2017 年 10 月 1 日是星期日，1949 年 10 月 1 日是（ ）。

A. 星期三 B. 星期日 C. 星期六 D. 星期二

直接计算$51\times365+17\times366=18615+6222=24837$,$24837\%7=1$ 选前一天星期六

由四个不同的点构成的简单无向连通图的个数是（ ）。

A. 32 B. 35 C. 38 D. 41

是树，$cayley $得到答案16,由于$k_3$只有3条边，因此剩下的是$C_6^4+C_6^5+C_6^6=22$

答案即为38

若 f[0] = 0, f[1] = 1, f[n + 1] = (f[n] + f[n - 1]) / 2，则随着 i 的增大，f[i]将接近于( )。

1. A1/2
2. B. 2/3
3. C. (√5 − 1)/2
4. D. 1

$f_2=0.5$ 这一步开始我就错了md

随便推几项就很接近B了，考虑严格证明

$f(n+1)-f(n)=\frac{f(n-1)-f(n)}{2}$

设$a(n)=f(n)-f(n-1)$

那么就可以是

$\large{a(n+1)=-\frac{a(n)}{2}}$

$\large{a(n+1)=\frac{a(1)=1}{2^{n-1}}}$

然后把 $a(n),a(n-1),...,a(1)$ 累加

然后基本就是$\sum\frac{1}{4^n}-\frac{1}{2\times4^{n}}$

答案即为$\frac{2}{3}$，还是暴力枚举吧

如下图所示，A 到 B 是连通的。假设删除一条细的边的代价是 1，删除一条粗的边的代价是 2，要让 A、B 不连通，最小代价是(____)（2 分），最小代价的不同方案数是()（3 分）。（只要有一条删除的边不同，就 是不同的方案）

第一问答案显然是$4$

考虑第第二问

平面图转化成对偶图

T23 注意$x$从$0$开始会调用（8,3,0）,(8,2,0)等

画dfs图即可

T26

wtf没看到cnt在里面还清空了一次，能得分真的是奇迹

实际上跑到$\text{lcm}(x-1,y-1)$ 次就会停下

前两个数据是互质的，就是$x$会在$y-1$次统计到cnt停下，y会在$x-1$次统计到cnt结束

后面一个有$\gcd=2$ 即$x$ 移动 160次，y移动 493 次

T27

呜呼没看到下标从0开始

后面的rest 已经除了，因此得先$\times 10$ 再取模

康托展开

$a_n(n-1)!+a_{n-1}(n-2)!+...+a_1(0)!$

$a_i$表示原数的第i位在当前未出现的元素中是排在第几

既然康托展开是一个双射，那么一定可以通过康托展开值求出原排列，即可以求出n的全排列中第x大排列。

如n=5,x=96时：

首先用96-1得到95，说明x之前有95个排列.(将此数本身减去1)用95去除4! 得到3余23，说明有3个数比第1位小，所以第一位是4.用23去除3! 得到3余5，说明有3个数比第2位小，所以是4，但是4已出现过，因此是5.用5去除2!得到2余1，类似地，这一位是3.用1去除1!得到1余0，这一位是2.最后一位只能是1.所以这个数是45321。

按以上方法可以得出通用的算法。