鸣谢：LYF、YQH、PML、CHH、HJY、SJA、FCJ（无先后顺序）
NOIP2011-2016 解题思路
2011 NOIP Day1
T1 铺地毯
题意
模拟
细节
没啥细节。唯一的细节就是没答案要输出-1 直接模拟就行
T2 选择客栈
题意
有n个点，k种颜色，有权值；要求选择两个颜色相同的点，找出所有选择，保证两点之间最低权值≤p的方案数。（n≤2e5,k≤50,p≤100)
讲解
k__jle：枚举每一个点，如果它的权值满足≤p,则它的两边所有同色客栈均满足，根据乘法 原理，将两边相乘即可，注意当两边与被枚举的点同色时，方案数要增加
aface0427：枚举左右端点，前缀和，计算中间小于p的咖啡店的个数。我们观察可以发现，枚举 左端点，右端点的值是单调的，然后二分找到第一个满足的右端点，那么后面的相同颜色的点都可以计算上。 复杂度：O(nlogn)。
T3 Mayan游戏
题意
实现细节：1.下落的写法：记录一个指针，表示当前累到第几个，如果遇到有值，就累加。
inline void drop(int tmp[][10])
{
int t1=1,t2=0;
rep( i , 1 , 5)
{
t1=1;
rep( j , 1 , 7)
{
t2=tmp[i][j];
tmp[i][j]=0;
if( t2 != 0 )
tmp[i][t1++]=t2;
}
}
}
2011 NOIP Day2
T1 计算系数
题意
给定一个多项式$$(by+ax)^k$$，请求出多项式展开后$$x^n \cdot y^m$$ 项的系数.
思路
杨辉三角 qpow 处理一下系数就行 $ans=C_{n}^{k} \cdot a^n \cdot b^m$
T2 聪明的质监员
题意
给定每个矿石的重量和价值，给定一个检验矿石的算法，要求一个参数(w)，使得检验结果(Y)和标准值(s)最接近.
思路
二分答案(w)使得 $|Y-s|$（注意：是绝对值）最小.检验时可以用前缀和优化.
注意
二分时会得到Y>s和Y<s两个值，需要确定哪个才是真正的最优解。而且要开long long，注意long long的最大值赋值方法。
T3 观光公交
题意
https://www.luogu.org/problem/show?pid=1315
思路
公交车离开某一站最早的时间等于以这一站为起点的乘客最晚到达的时间(可以用数组记录)，用前缀和记录下车人数，在不加速的情况下，答案等于每个人到的终点站的时间（车到某站的时间）减去开始的时间。
对于加速器，尽量在汽车载人最多的时候使用(贪心)。如果车到站还要等人，就说明这个加速器只能影响到这个站，否则还可以影响下一个站
2012 N0IP Day1
T1 Vigenère 密码
题意
定义一种对于字符的运算：® ，给出一张运算值表。
思路
由于数据范围较小，直接模拟，O(n)
T2 国王游戏
题意
对于n+1个点，有左右两个权值，对于一个点答案是前面数的左权值的乘积除以他自己的右权值。有一种排列使得获得答案最大的点获得的答案尽可能少。求出这个答案。
思路
题目要求找到一种排列使得获得答案最大的点获得的答案尽可能少。我们考虑序列中的两 个点j和k。我们发现：只要使得$\frac{j.left}{k.right}<\frac{k.left}{j.right}$即可
排序完成后，我们O(n)扫描一遍查出最大权值。经过观察数据范围 我们发现需要高精度。套上高精度即可。
T3 开车旅行
题意
https://www.luogu.org/problem/show?pid=1081
给了一个序列，每个点具有权值h。有两个人轮流开飞机，A先开（他喜欢找到距离第二近的城市），B后开(他喜欢找到距离最小的城市)。如果总路程超过x或无法走旅行结束。距离定义为$dist(i,j)=|h_i-h_j|$。题目给出100000组询问：
- 给定最大距离x，问从那个城市出发使得A的距离与B的距离的比值最小
- 给定x和出发城市，求A和B的路程。
思路
70分：暴力模拟 对于第一问：暴力枚举从某个城市出发再模拟 O(n^2m) 对于第二问：暴力模拟O(nm) 优化：考虑倍增 预处理倍增数组 dp[i][j]维护从i城市出发走了$$2^j$$步到达的城市 用set维护查一个点之后和他最近的两个点 倒着插入海拔 查出前后缀 处理出每个点下一步走到哪儿，然后大力胡搞 ，Ac。
2012 NOIP Day 2
T1 同余方程
题意
求同余方程$ax \equiv 1(\mod p)$
思路
我们可以把原方程转化成这样：$$a \cdot x=1+k \Rightarrow a \cdot x+(-k) \cdot b= 1\Rightarrow a \cdot x+b \cdot y=1$$ 转化成了这样，我们就可以用Exgcd解决 一个细节：求出来的x可能是负数，需要+mod之后再取模。 eg: $$ans=(ans \mod p+p)\mod p (p为模数)$$
inline int Exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1; y = 0;
return a;
}
else {
int Q = Exgcd(b, a%b, y, x);
y -= (a / b)*x;
return Q;
}
}
T2 借教室
题意
首先给定一个序列s[]，然后给定一些操作：对于给定的一个区间里的每个s都减去一个数。求直到哪个操作，s[]序列开始出现负数。
思路
经观察知，答案满足单调性和有界性，可以进行二分查找(顺序查找可以得到四十分)： 在验证的时候，我们可以使用一个差分数组sum: 对于x以前的命令，
$$sum[order[i].start] += order[i].delta;\sum[order[i].end+1] -= order[i].delta;$$
然后再把sum数组前缀和处理。
只要存在一个i，使得$sum[i]>s[i]$，即为不合法。（YQH）
T3 疫情控制
题意
给定一个树 以1为根。每个边都有权(时间),每个点都可以控制它的子树。现在给出了一些点 可以沿着树上路径移动(不能停在1上) 现在要求最少需要多少时间才能使每个叶子节点都能被控制
思路
为什么要二分呢（aface0427） 我们发现题目要求的东西是最少需要多少个小时才能控制疫情。那么控制疫情的根本原因是某一个军队通过最近的距离控制了一个最远的关键点。这等价于所有军队同时移动，而我们要求的就是这些军队中花费时间的最大值，同时满足全局最小。这不就是找最小值的最大值么。
2013 NOIP Day 1
T1 转圈游戏
题意
原题很清楚
思路
模拟+快速幂
T2 火柴排队
题意
求某一个序列中【第i大的数所在的位置】的逆序对
思路
记录某一个序列第i大的数所在的位置，那么另一个序列的第i大的数就也应该被排在这个位置，故利用归并排序求一下逆序对即可。
T3 货车运输
题意
A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物.
思路
求瓶颈路问题可以转化为最大/小生成树的原理是： 我们如果求出最大生成树，而瓶颈路如果不在生成树上，那么添加一条边之后，一定可以找出一颗更大的生成树。 同理： 如果遇到此类问题，不妨贪心地去想一些优化解，然后尝试证明即可。 最大生成树（kruskal）(因为图是稀疏的) 求LCA
实现细节
如果目标点和当前节点不在一个生成树内则无法到达 注意在kruskal时顺便建树，求LCA跳点时对ans取min
2013 NOIP Day 2
T1 积木大赛
题意
给定一个全部为零的序列，长度为n，每次可以选定一个区间，将区间内每个数+1，求达到目标序列最少需要多少次操作。
思路
贪心（电光火石之间一闪而过的贪心思路），每次要加的序列越长越好，每次扫到一个$ai>a{i-1}$时，就需要再多$ai-a{i-1}$次操作，每次对$$ans$$取$$max$$
T2 花匠
题意
求一个序列的最长波动子序列
思路
使得最后的序列为/\/\/\/\/\/\型或\/\/\/\/\/\/\/型 \/和/\两个状态交替进行，上升是由减小递推得来，减小是由上升递推得来 不需要使用数组，只需两个状态$$f_1$$和$$f_2$$相互转移即可
扩展题目
地精部落(洛谷P2467)、教主的后花园(Vijos)(洛谷P1133)
T3 华容道
题意
给定一个华容道模型，固定点位置和空白格子位置以及可移动棋子的初始位置和目标位置，第一问求是否有解，第二问求最短路径
思路
70分思路 不需要任何预处理，对每次讯问进行BFS，若步数大于总格子数仍未到达目标点则无解 BFS中状态判重：$$f [i] [j] [h] [k]：i,j为空格坐标，h,k为曹操坐标（皆为纵横坐标）$$，若到达其旁边就交换，记下步数并入队，到达终点就return; 100分思路 以状态为点建图求最短路
2014 NOIP Day1
T1 生活大爆炸版石头剪刀布
题意
我认为石头剪刀布大家都会，就是多了几种情况而已
思路
按照题目描述模拟就好（分类讨论谁不会啊） aface0427：定义一个优先级
T2 联合权值
题意
一棵树上距离为2的两点权值乘积的(最大值)与(总和%1e4+7)
思路
对于每一个可作为一棵子树的根节点的点枚举其儿子的联合权值 数学变形： 假设每个中转点周围有两个点，权值分别为a、b，则联合权值为$$2ab=(a+b)^2-(a^2+b^2)。$$ 若有三个点，权值分别为a、b、c，则联合权值为:$$2ab+2bc+2ac=(a+b+c)^2-(a^2+b^2+c^2)$$
ps：真正的带花树是一个长的像仙人掌的东西，不是我说的那种带花。
为了分析这种问题，建议大家画那种”花图“啊
T3 飞扬的小鸟
题意
默认大家都会玩(用过codevs)flappy bird
判断是否可以完成游戏。如果可以 ，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。
思路
暴搜思路：搜索点或者不点 aface0427 DP思路：向上可以无限次点，即为完全背包，向下一次不点就会掉，即为0/1背包
实现细节
先处理向上的完全背包在处理向下的0/1背包，因为向下的状态会消除向上的状态
2014 NOIP Day2
T1 无线网络发射器选址
题意
我觉得题目描述很清楚。
思路
二重循环枚举发射器安放位置，取最大值
实现细节
注意数组下标非负
T2 寻找道路
题意
在有向图G 中，每条边的长度均为1 ，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：
路径上的所有点的出边所指向的点都直接或间接与终点连通。
在满足条件1 的情况下使路径最短。
注意：图G 中可能存在重边和自环，题目保证终点没有出边。
请你输出符合条件的路径的长度。
思路
先从终点往回搜，找到所有符合条件的点，再正向SPFA，判断每个点是否有无法到达的点即可
T3 解方程
题意
求方程$a_0+a_1x^1+a_2x^2+......+a_nx^n$在[1,m]内的整数解
思路
从1到m枚举，利用秦九韶算法（乘法结合律），$sum=sum \cdot x+a_i$
注意取模
2015 NOIP Day1
T1 信息传递
题意
求最小环
思路
并查集：
图论求最小环，我在里面看到了并查集。 假如说信息由A传递给B，那么就连一条由A指向B的边，同时更新A的父节点，A到它的父节点的路径长也就是B到它的父节点的路径长+1。 这样我们就建立好了一个图，之后信息传递的所有环节都按照这些路径。游戏结束的轮数，也就是这个图里最小环的长度。 如果有两个点祖先节点相同，那么就构成一个环，环的长度为两点到祖先节点的距离之和+1。
tarjan:
找最小环边数
T3 斗地主
思路
先预处理不打顺子的情况：记下有c1种1张的数码，c2种2张的数码，c3种3张的数码，c4种4张的数码时打光所有牌需要的最小次数。然后DFS搜索已经打过顺子的所有可能情况。 俩王不能被带...还要加个特判。
2015 NOIP Day2
T1 跳石头
思路
二分答案；枚举去掉的石头判断是否>m
子串
思路
$$f[i][j]:a中取j个与b中i个相等的方案数$$
$$sum[i][j]:a中取j个与b中取i 个相等的当前方案数$$
for(int i=1;i<=n;i++)
for(int j=m;j>=1;j--)
for(int k=K;k>=1;k--)
{
if(a[i-1]==b[j-1]) sum[j][k]=sum[j-1][k]+f[j-1][k-1];
else sum[j][k]=0;
f[j][k]=(sum[j][k]+f[j][k])%1000000007;
}
T3 运输计划
思路
使 $$C(t)$$表示是否可以改造一条边，使得改造之后所有运输计划中最长的时间不大于 t。这是惯用伎俩，用二分的的话，我们就可以确定一个变量 t，正因为有了这个 t，我们才能有的放矢的进行贪心或是干别的。 如何判断 C(t) 呢？在开始的时候用倍增预处理出所有计划的时间，如果小于等于 t，就可以忽略，如果大于 t，那么就要考虑在其路径上改造一条边。 由于所有时间大于 t 的计划都要改造一条边，问题就变为了求所有时间大于 t 的计划的路径交集，改造其中一条最大的边，看看去掉这条边之后，是否可以满足条件。
求交集方法：
方法1 ：模拟：
枚举两个点看是否在两条路径之中且路径需要尽可能长
方法2：树上差分
2015 NOIP Day1
T1 玩具谜题
由于太简单，直接给出趣味std
std
#include<cstdio>
#define A int
#define B n
#define C m
#define E ,
#define F now
#define D step
#define G =
#define H direction
#define I p
#define J char
#define K name
#define L ;
#define M scanf
#define N " %d%d"
#define O "%d%s"
#define P (
#define Q )
#define R &
#define S for
#define T <
#define U +
#define V -
#define W 0
#define X i
#define Y if
#define Z %
#define QAQ {
#define QWQ }
#define QVQ [
#define QMQ ]
#define EX "%s"
#define AA 11
#define BB 100005
#define CC else
#define DD main
#define EE using
#define FF std
#define GG namespace
#define HH m--
#define II ++i
#define JJ while
#define KK printf
#define LL return
EE GG FF
L A DD P
Q QAQ
A B E C E D E F G W E H QVQ BB QMQ E I L
J K QVQ BB QMQ QVQ AA /*"QAQ"*/ QMQ L
M P N E R B E R C Q L
S P A X G W L X T B L II Q
M P O E R H QVQ X QMQ E K QVQ X QMQ Q L JJ P HH Q QAQ M P N E R I E R
D Q L Y P H QVQ F QMQ Q Y P I Q F G P F V D U B Q Z B L CC F G P F
U D Q Z B L CC Y P I
Q F G P F U D Q Z B L
CC F G P F V D U B Q
Z B L QWQ KK P EX E
K QVQ F QMQ Q L LL W L QWQ
T2 天天爱跑步
思路
25分：模拟
可以考虑对于每一个人$$ (u, v)$$，都使用 BFS 找出$$ u \rightarrow v$$ 的路径，然后更新路径上有满足条件的点即可。至于找出路径的方法，只需要从 u 开始 BFS，并且在 BFS 中从 a 扩展到 b 时，记录 a 的前继为 b，最后我们从 v开始，不断地找前继，最终到 u，这样就还原出了路径，你可能还需要记录一个到点v 的距离来帮助判断路径上的点是否满足条件。
40分：
由于链上的点依次是 ，而题目中的路径有从编号小的点走到编号大的点或者从编号大的点走到编号小的点。我们将这两种路径分开考虑，先考虑从编号小的点走到编号大的点$$(u,v)(u\le v)$$ 对于 (u, v)，如果路径上的点 $$i(u\le i\le v)$$要满足条件的话，必然是满足$$ w_i = i - u$$，我们不妨设 $${w'}_i = w_i - i$$，那么现在的条件转化为了$$ {w'}_i = -u$$，也就是说，路径上的点 i 答案 + 1 的充分必要条件是满足 $${w'}_i$$ 等于一个定值。
现在问题转化成了支持两种操作：
- 将一段链上的每个点插入一个数。
- 查询点 i 上有多少个数是 $${w'}_i$$。
那么差分可做。
由于差分的逆运算是前缀和，我们顺序遍历这条链，维护$$ \mathrm{cnt}_v$$ 为数 v 出现的次数（由于 i 有负数，所以我们考虑将这个数组向右平移 n 个单位来方便存储），每遍历到一个点 i，我们就处理它上面所有的标记 $$(v, t)$$,将 $$\mathrm{cnt}_v$$加上 t。这样遍历到每个点的时候，$$\mathrm{cnt}_v$$就是在它上面数 v 的出现次数。
100分：
考虑一种简单一些的情况：玩家都在序列而不是树上跑，而且所有玩家都在往右跑。
假设某个玩家从l跑到r，那么他会在满足$$j∈[l,r]$$且$$j−w_j=l$$的点$$j$$上被观测到。
于是，我们可以将所有的玩家按照l排序，把序列上的所有点按照$$j−wj$$排序，每次加入$$l=p$$的所有玩家，用树状数组统计序列上每个点被覆盖了几次，据此计算所有$$j−w_j=p$$的点的答案，最后把$$l=p$$的玩家删去。这样每个玩家被加入一次，删去一次，序列上每个点被计算一次，时间复杂度为$$O(nlogn)$$。
考虑复杂一点的情况，有的玩家往右跑，有的往左跑。
此时可以把这两种玩家分开处理，往右跑的处理方法同上，对于往左跑的玩家，假设他从r跑到l，那么他会在满足$$j∈[l,r]$$且$$j+w_j=r$$的点$$j$$上被观测到。于是往左跑的玩家也可以用类似上面的办法处理。
现在需要把序列上的做法弄到树上。
一个简单的想法是使用树链剖分，不过码量可能会有一点大，时间复杂度$$O(nlog2n)$$。
其实可以不用树链剖分。考虑一个玩家从u跑到v，u和v的最近公共祖先为w。那么其实可以把它拆成u向上跑到w和w向下跑到v两部分。把上面的$$j±w_j$$改成$$dep_j±w_jdep$$就可以用类似的方法来做了。
此时需要一个数据结构，支持链上加一个数以及单点查询，可以树上差分再用树状数组来维护。这样时间复杂度是$$O(nlogn)$$的。
T3换教室
思路
首先有$$ v\le 300$$，使用 $$floyd$$ 算法求出两两点对之间的最短路。接着可以发现，这是一个经典的序列 DP 的模型，每个点有选或者不选两种决策，那么根据期望的线性性，容易发现每次DP 只与最后两个选不选有关，考虑 $$dp{i, j, k}$$ 为到第 i 个点，已经选了 j个，k 表示第 i 个点是否选择换教室，那么转移就是根据后两个是否选择更换，来分情况讨论（设 $$p_i$$ 为更换成功的概率，$$c_i$$ 为不换的教室，$$d_i$$为换的教室，$$G{i, j}$$ 为 i 与 j 之间的最短路）：
如果点 ii 不选，那么根据上一个选不选来计算期望（期望的线性告诉我们可以这样做）。
$$dp{i, j, 0} = \min \begin{cases} dp{i - 1, j, 0} + G{c{i - 1}, ci}\ dp{i - 1, j, 1} + p{i - 1} \cdot G{d{i - 1}, c_i} + (1 - p{i - 1}) \cdot G{c{i - 1}, c_i} \end{cases}$$
如果点 i 选，也是根据上一个选不选来计算期望，第二个式子会比较麻烦，有四种情况。
$$dp{i, j, 1} = \min \begin{cases} dp{i - 1, j - 1, 0} + pi \cdot G{c{i - 1}, d_i} + (1 - p_i) \cdot G{c{i - 1}, c_i}\ dp{i - 1, j - 1, 1} + p{i - 1} \cdot p_i \cdot G{d{i - 1}, d_i} + (1 - p{i - 1}) \cdot pi \cdot G{c{i - 1}, d_i} &+ p{i - 1} \cdot (1 - pi) \cdot G{d{i - 1}, c_i} + (1 - p{i - 1}) \cdot (1 - pi) \cdot G{d_{i - 1}, d_i} \end{cases}$$
2016 NOIP Day2
T1 组合数问题
思路
$$n \le2000$$，显然直接 $$O(n^2)$$ 算一遍组合数是没有问题的。题目中求恰好是 K 的倍数的组合数的个数，是 K 的倍数这个条件可以转化为：不为 0 且对 K 取模为 0。所以我们使用杨辉三角的递推公式来计算组合数，并在计算的时候对 K 取模：
$$\binom n m = \binom {n - 1} m + \binom {n - 1} {m - 1}$$
考虑快速回答询问，只需要记录 $$s{i, j}$$ 为 $$n = i, m = j$$时的答案，我们可以用常见的二维前缀和的思想预处理出 $$s{i, j}$$：
$$s{i, j} = [j \le i, \binom i j \bmod k = 0] + s{i - 1, j} + s{i, j - 1} - s{i - 1, j - 1}$$
复杂度：$$O(n^2 + m)$$
T2 蚯蚓
思路
40-65分：用stl中的优先队列，维护最大值。如何每次+p呢，开一个变量now，记录如今已经加过多大的数了，最后在输出时再加回去。那么如何解决当前被切的的蚯蚓不+p呢，我们插入优先队列时插入num-p即可。
100分：
首先我们考虑$$ q = 0$$ 的情况——蚯蚓长度不增长，那么每次取出的蚯蚓长度一定单调不增。我们可以维护三个单调不增的序列，初始的时候第一个序列是原序列（从大到小排序），第二个序列是左半部分蚯蚓序列（一开始是空的），第三个序列是右半部分蚯蚓序列（一开始是空的）。每一次取出蚯蚓，找到三个序列首最大的蚯蚓，剁成左右两部分加入左半部分蚯蚓序列和右半部分蚯蚓序列的末尾。显然第二、三个序列也是单调不增的，所以整个操作可以在 $$O(n\log n + m)$$的复杂度内完成。
接着考虑 $$q\neq 0$$ 的情况——蚯蚓长度每次增长，注意到每次只有取出来的蚯蚓不增长，其余的蚯蚓都要 $$+q$$，那么其实上可以将每一个蚯蚓都 $$+q$$，然后将剁成的两个蚯蚓$$ -q$$。每一次取出的蚯蚓长度还是单调递减的！因为每次的操作是取出蚯蚓，剁成两部分，然后$$ -q$$ 再放回去，整个过程中没有蚯蚓的长度相对增加（整体 $$+q$$ 是不影响相对长度的），所以我们依然可以套用之前的算法，只不过每次切除的时候要换算一下蚯蚓的长度（因为每次 $$+q$$ 并不真正直接加上，而是打了一个“标记”）。
复杂度：$$O(n\log n + m)$$.
T3 愤怒的小鸟
思路
$$n \leq18$$，比较明显的状态压缩 DP 的模型。你需要明白，集合是以二进制位来存储的（不懂的话先去做状压 DP 入门题）。 我们设$$ dps$$ 为将集合 s 中的猪全部打掉所需的最小次数，那么我们枚举第一次发射。每次发射要么只打死一头猪，要么打到两头猪 i 和 j，预处理出 $$c{i, j}$$ 为打出一条经过猪 i 和 j 的抛物线，能打掉的点的集合，注意如果解出经过 ii,j 的抛物线 $$a \ge 0$$,那么没有任何猪能被打掉——因为根本就不合法。 所以有转移方程：
$$dps = \min\begin{cases}dp{s \backslash i} + 1 & i\in s\dp{s \backslash c{i, j}} + 1 & i \in s, j\in s\end{cases}$$
由于每一次需要枚举 i 和 j，然后还需要在集合 s 中剔除这一次发射能够打掉的点，所以复杂度是 $$O(n^32^n)$$ 的，有点大，能不能更优呢？我们首先考虑用位运算优化剔除点，设 $$c{i, j}$$ 为打出一条经过猪 i 和 j 的抛物线，不能打掉的点的集合，那么如果选择 i 和 j 发射，新的集合就是 $$s\;\mathrm{and}\;c{i, j}$$（按位与），我们来看一个例子：
$$s=(1101101)_2$$
$$c_{i,j}=(0110111)_2$$
$$ s\;\mathrm{and}\;c_{i,j}=(0100101)_2$$
对于 s 中是 0 的位置，表示这个元素已经被打掉了，无论怎么与都是 0。对于 s 中是 1 的位置，如果 $$c{i, j}$$ 中这个位置是 1，表示不能打掉这个位置，那么与运算之后这一位还是 1，如果 $$c{i, j}$$ 中这个位置是 0，表示可以打掉这个位置，那么与运算之后结果是 0，符合我们的预期。 位运算优化之后，复杂度变为了$$ O(n^22^n)$$，还是有点卡，能不能更优呢？考虑集合 s 中最小的点 i，在最优解中它一定会被打掉，我们只需要枚举 i 是如何被打掉的即可（单独被打或者跟别人一起），这样就固定了 i，只需要枚举 j 就行了，复杂度降为 $$O(n2^n)$$，轻松通过所有数据。