排列公式
从 nnn 个数中选出 mmm 个数并且排序。
公式推导：
A32=3×2=636=6×5×4=120A62=6×5=30∴Anm=n(n−1)(n−2)…(n−m+1)又∵n!=n×(n−1)×(n−2)⋯×2×1综上所述：Anm=n!(n−m)!
A^2_3 = 3 \times 2 = 6\\3_6 = 6 \times 5 \times 4 = 120\\
A^2_6 = 6 \times 5 = 30\\
\therefore A^m_n = n(n-1)(n-2)\dots (n-m+1)\\
又\because n!=n\times (n-1)\times (n-2)
\dots \times 2\times 1 \\
综上所述：A^m_n = \frac{n!}{(n-m)!}
A32=3×2=636=6×5×4=120A62=6×5=30∴Anm=n(n−1)(n−2)…(n−m+1)又∵n!=n×(n−1)×(n−2)⋯×2×1综上所述：Anm=(n−m)!n!
组合公式
从 nnn 个数中选出 mmm 个数。
公式推导：
Cnm= ...
树的基本术语
节点的度：一个节点拥有的子树树木。
树的度：一棵树上所有节点的度的最大值。
叶子节点：度为 000 的节点。
分支节点：度大于 000 的节点。
孩子节点：节点的子树的根被称为这个节点的孩子节点。
双亲节点：就是它的父亲。
兄弟：具有同一父节点的子节点互称兄弟。
堂兄弟：其父节点在同一层。
祖先节点：从根到该节点所经分支上的所有节点。
子孙节点：以某一节点为根的子树中任一节点都成为该节点的子孙。
节点的层次：从根节点到该节点所经过的路径 +1+ 1+1。
树的深度：树中节点具有的最大层次树。
数的宽度：整棵树中某一层中最多的节点树为该树的宽度。
有序树：每颗子树从左到右是有序的（不能更换）。
第一个孩子：在有序树中，最左边的子树的根。
最后一个孩子：在有序树中，最右边边的子树的根。
我们现在令：
A=1+2+4+8+16+32+64+128+256+512+1024则2A=2+4+8+16+32+64+128+256+512+1024+2048A = 1+2+4+8+16+32+64+128+256+512+1024\\
则2A = 2+4+8+16+32+64+128+256+512+1024+2048
A=1+2+4+8+16+32+64+128+256+512+1024则2A=2+4+8+16+32+64+128+256+512+1024+2048
这样我们构造出了一个新数列，
而且这个数列的和等于原数列乘以公比。
再将两个式子相减：
2A=2+4+8+16+32+64+128+256+512+1024+2048−A=1+2+4+8+16+32+64+128+256+512+1024A=2048−1=2047\begin{array}{r}
\begin{aligned}
2A &= 2+4+8+16+32+64+128+256+512+1024+2048\\
-A &= 1+2+4+8+16+32+64+128+256+512+102 ...
![题解：P10111 [GESP202312 七级] 纸牌游戏](https://img.paulzzh.com/touhou/random?_r_=762710d8-b985-873b-5271-52711a6f93e7)
题目大意
给出三个序列：aaa ，bbb ，ccc
分别表示：分数，罚分以及小杨从第 111 轮至第 𝑁𝑁N 轮出的牌，你从第 222 轮开始，要么继续出上一轮出的牌，要么记一次“换牌”。游戏结束时，你换了 ttt 次牌，就要额外扣 b1+…+btb_1+…+b_tb1+…+bt 分。
请计算出你最多能获得多少分。
解题思路
我们使用动态规划来解决。
状态：
fi,j,kf_{i,j,k}fi,j,k表示进行到第 iii 轮，换了 jjj 次牌，牌为 kkk 的最大得分。
Code
123456789101112131415161718192021222324252627282930313233343536373839#include <bits/stdc++.h>using namespace std;int n;int a[1001], b[1001], c[1001];int f[1001][1001][5]; // 进行到第i轮，换了j次牌，牌k的最大得分int ans;int main(){ cin >> n; ...
题目大意：
给你一个 nnn 和 kkk ，再给你一个长度为 NNN 的序列 AAA ，
从 AAA 中任意选择 KKK 个元素并将其删除，然后按原来的顺序将剩余的元素连接起来，形成一个新的序列 BBB ，然后求这个序列的极差。
解题思路
错误解法
一开始我想到了贪心：把 AAA 数组排个序，然后把开头结尾依此去掉即可。
但是好比这个数据：
1 3 3 9 11
贪心可以得到：3 3 9
但是实际上应该是这样：1 3 3
正确解法
我们可以用一直类似滑动窗口的方式解决这个问题：
12345678910111213141516171819#include <bits/stdc++.h>using namespace std;const int N = 2e5 + 10;int n, k;int a[N], ans = INT_MAX;int main(){ cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i]; sort(a ...
题目
题目描述
小X正和同学们做列队的练习。
有nnn名同学排成一路纵队，编号为i的同学排在从前往后数第i个位置上，即：初始时的队列为1,2,3,...,n1, 2, 3, ..., n1,2,3,...,n。
接下来小X会发出若干条指令，每条指令形如“请编号为x的同学排到最前面来”。（例如：若当前时刻的队列为5,4,3,2,15, 4, 3, 2, 15,4,3,2,1，发出一条xxx=2的指令后，队列变成了2,5,4,3,12, 5, 4, 3, 12,5,4,3,1。）
小X发出了很多很多指令，同学们晕头转向不知道该怎么排列。于是就请你算一算，执行完这些指令后，队列应该变成什么样？
输入
从文件 queue.in 中读入数据。
第一行两个用空格隔开的正整数nnn和mmm，分别表示人数和指令数。
第二行mmm个用空格隔开的正整数x[i]，按顺序表示每次指令的xxx值。
输出
输出到文件 queue.out 中。
输出仅有一行包含nnn个正整数，相邻两个数之间用一个空格隔开，表示执行完所有指令后的队列。
样例输入
4 3
2 3 2
样例输出
2 3 1 4
数据范围限制
对 ...
题目描述
小X和小Y正在玩一个游戏，这个游戏是这样的：桌上放着n叠卡片，每叠恰好有两张。每张卡片有一个分数。小X为先手，双方轮流操作。轮到一方操作时，他可以选择取走某一叠卡片顶端的那一张（即：若这一叠还剩2张则取走上面的一张，否则取走下面的一张），并获得它的分数。他也可以选择不取。若卡片取完了、或者双方都选择不取卡片，那么游戏结束。
小X和小Y都希望自己的分数减去对方的分数尽可能大。现在假设小X和小Y都绝顶聪明，总是做出对自己最有利的决策，请算出游戏结束时小X比小Y高多少分。
输入
从文件 game.in 中读入数据。
输入的第一行包含一个正整数n。
接下来n行，每行包含2个用空格隔开的非负整数a[i], b[i]，分别表示第i叠中放在上面、下面的卡片的分值。
输出
输出到文件 game.out 中。
输出仅有一行包含一个整数，表示游戏结束时小X比小Y高多少分。如果小X的分数比小Y低则输出一个负数。
样例输入
2
1 2
4 3
样例输出
1
数据范围限制
对于30%的数据，1<=n<=1000, b[i]=0
对于70%的数据，1<=n<=1000
对于1 ...
题目描述
mxy 沉迷于一个辣鸡游戏不可自拔。
游戏地图是一个 n*n 的矩形，在每个单位格子上有一个数字，代表当前位置的生命体个数，作为一个侦察兵，mxy 的任务是计算出她所在位置的左上角和右下角的总人数（不包括她所在的行列）。
注意作为一个侦察兵，mxy 是不包括在地图上的生命体个数中的。
输入
从文件 scout.in 中读入数据。
第一行 2 个整数 n 和 t。（1≤n≤1000，1≤t≤1000）
接下来 n 行，每行 n 个整数表示每个单位格子上的生命体个数 a。（1≤a≤100）
再下来 t 行，每行两个整数 xi，yi，表示不同时刻 mxy 在地图上的位置。
输出
输出到文件 scout.out 中。
T 行，每行一个整数，表示当前时刻 mxy 所在位置的左上角和右下角的总人数。
样例输入
1234564 10 1 2 03 2 0 01 2 3 20 0 0 103 3
样例输出
116
正片开始！！！
首先，先来画个图推理一下
没错，只是一道DP题（其实就是2维前缀和)
OK，直接开始撸代码：
123456789101112131415161718192 ...
题目描述
有个背包可承受重量 N，现有 T 件物品
每件物品重量为 Wi,价值为 Vi ,每件物品只有一个,
这个背包可以装载物品的最大价值是多少?
输入
从文件 beibao1.in 中读入数据。
一行两个正整数 N T，之间用空格隔开
后面T行,每行两个正整数，分别表示重量 Wi,价值 Vi
输出
输出到文件 beibao1.out 中。
这个背包可以装载物品的最大价值
样例输入
123456100 577 9222 2229 8750 4699 90
样例输出
1133
正片开始
这是一道十分不淼的题，致以本蒟蒻打下了大片江山：
额，这题就是塞更多的东西进有空间限制的背包嘛
首先想到了贪心，先排个序嘛，然后再拿价值大的物品，结果不行，别问为什么，你猜答案错误27.3是怎么来的？
正解即为：开一个 D P数组，下标表示这个 DP 数组最大可以存的数，然后一个个试物品，代码：（看不懂就算了）x 代表：容量/重量，y 表示价值
12345678910111213141516171819if(dp[j].x==0 && dp[j].x+a[i].x<=j) ...
题目描述
有长度为N的序列:
A1 A2 …..An
求最长不下降子序列：Ai1,Ai2,,,,,Aik, 其中ai1<=ai2<=.....<=aik
求最长不下降子序列的长度
输入
从文件 seq.in 中读入数据。
第一行，n;
第二行，n 个数。
输出
输出到文件 seq.out 中。
最长不下降子序列的长度
样例输入 复制
11
1 3 6 3 4 7 5 7 6 7 8
样例输出 复制
8
如：1 3 3 4 5 6 7 8
正片开始！
首先，按照国际惯例，这是一道十分淼的题（没做出的同学请冷静），本蒟蒻也才花了0.5小时才解出来
题意为：求最长不下降子序列的长度 ，注意：并不用连续
好，这很明显就是一道DP题，我们可以推导一下
首先，我们可以画一个图
数组代表我们的输入，DP代表从第i个数开始，向后的最长不下降子序列，dp要初始化为1哦
然后呢，我们枚举i个数，看他的最长不下降子序列， 即
OK，理论存存存在！，开始Code
123456789101112131415161718192021#include <bits/st ...
