。

当两个数各个数位之和不同时,将数位和较小的排在前面,当数位之和相等时,将数值小的排在前面。

例如,2022

小蓝对一个数的数位之和很感兴趣,今天他要按照数位之和给数排序。

当两个数各个数位之和不同时,将数位和较小的排在前面,当数位之和相等时,将数值小的排在前面。

例如,2022

而言可以事先求出每个数字的数位之和。

根据每个数字的数位之和自定义排序函数即可。

#include

的对象数目等于∣S∣∣S1​∣∣S2​∣∣S3​∣…∣Sm​∣

门数学课和

加法原理的关键是将计数分解为若干个独立不相容的部分保证既不重复也不遗漏地进行计数。

加法原理是利用完备事件组的一个体现我们可以利用一个集合的补集做题。

例题分割立方体

Anr​n(n−1)(n−2)…(n−r1)(n−r)!n!​

n^r

C_{n}^r\frac{A_{n}^r}{r!}\frac{n!}{r!(n-r)!}

糊涂人寄信

个信封到了邮寄的时候把所有的信都装错了信封。

求装错信封可能的种类数。

输入描述

次那么剩下的n−1人中握手最多的人不会超过n−2次。

0∼n−2

次那么剩下的n−1人中握手最多的李四除了跟张三握手一次跟其他n−2人最多握手n−2次李四最多握手n−1次。

1∼n−1

次那么剩下的n−1人中握手最多的李四除了跟张三握手一次跟其他n−2人最多握手n−2次李四最多握手n−1次。

2∼n−1

把最多的n−1种情况看成n−1个抽屉n个人放进这n−1个抽屉至少有一个抽屉里面有

例题小蓝吃糖果

C_{n-1}^{r-1}C_{4-1}^{1-1}C_{3}^01,C_{3}^13,C_{3}^23,C_{3}^34

Cn−1r−1​C4−11−1​C30​1,C31​3,C32​3,C33​4

(1x)^n

C_{n}^{r}C_{n-1}^{r-}C_{n-1}^{r-1}

Cnr​Cn−1r−​Cn−1r−1​

因为输出取模那么不用递推公式直接用公式计算更快。

不过由于除法不能直接取模需要用到逆。

用逆计算二项式系数有

Cnr​r!(n−r)!n!​

如果我们按从上到下、从左到右的顺序把杨辉三角形的所有数排成一列可以得到如下数列:111121133114641…给定一个正整数N请你输出数列中第一次出现N是在第几个数?

【输入描述】

下一行的2个数相加得下一行得一个数。

例如上一行是b[0]~b[k]下一行是a[0]~a[k1]那么a[i]

b[i-1]

推算过程只用一个数组完成和DP的自我滚动数组的原理一样即a[i]

a[i-1]

(line1);//1~line行的数字个数。

每行比上一行多一个累加}return

O(n^2)

O(n2)即使只搜50000行也超时了如果是C编码会溢出。

杨辉三角的有些数字可能很大导致溢出。

杨辉三角是左右对称的。

所以若n在右边出现了那也必然在左边出现过。

而数列的构造顺序是从左往右所以我们只需看左半部分即可。

第0列第1列第2列第3列第4列第5列第0行1第1行11第2行121第3行1331第4行14641第5行15101051

第0列第1列第2列第3列第4列第5列第0行1第1行1第2行12第3行13第4行146第5行1510

C_{i}^j

用黄色印记标记的数字为我们需要考虑的部分(图一的左侧部分)我们称其为有效部分。

C_{2i}^i

C_{2i}^i,C_{2i1}^i,C_{2i2}^i\dots

C2ii​,C2i1i​,C2i2i​…

显然对于同一行列数越大则对应的数值也越大对于同一列来说行数越大则数值也越大。

也就是说如果某一行的某一列的值为

X小的数了同理在行数不变的情况下列数怎么变大也不会再出现比小的数了。

10^9

109)开始的所以该列无论如何都不可能出现n了其它的列就就更不可能了)。

我们考虑一列一列处理。

那么对于某一列来说我们怎么确定该列中是否存在n若存在n这个n又会在该列的第几行呢?

由于随着行号的变大数值是单调递增的且知道了行号列号对应的数值也就知道了于是就很显然可以二分行号。

2i右边界r为

R都可)。

然后不断搜索直到n出现后返回行号(或者直到搜索结束还是没找到n返回

复杂度为

轮比赛。

每轮比赛开始前以及所有比赛结束后都会按照总分从高到低对选手进行一次排名。

选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。

总分相同的约定编号较小的选手排名靠前。

每轮比赛的对阵安排与该轮比赛开始前的排名有关:第1名和第2名、第3名和第4名、…第2K

-1名和第

名各进行一场比赛每场比赛胜者得1分负者得0分。

也就是说除了首轮以外其它轮比赛的安排均不能事先确定而是要取决于选手在之前比赛中的表现。

现给定每个选手的初始分数及其实力值试计算在R轮比赛过后排名第Q的选手编号是多少。

我们假设选手的实力值两两不同且每场比赛中实力值较高的总能获胜。

暴力法每轮做一次排序R轮后输出

那么每次对于每轮比赛结束只需进行合并操作即可O(n)的时间就能让序列变成有序的了。

归并排序

分解。

把初始序列分成长度相同的左右两个子序列然后把每个子序列再分成更小的两个子序列…直到子序列只包含1个数。

用递归实现。

求解子问题对子序列排序。

最底层的子序列只包含1个数其实不用排序。

合并。

归并2个有序的子序列这是归并排序的主要操作

对n个数进行归并排序:

需要logn趟归并;在每一趟归并中有很多次合并操作一共需要O(n)次比较。

空间复杂度:需要一个临时的b[]存储结果所以空间复杂度是O(n).

#include