北京网站开发公司电话,外链网址,搜索引擎营销是什么,高端h5手机网站设计案例组合数学
数位排序
【问题描述】 小蓝对一个数的数位之和很感兴趣,今天他要按照数位之和给数排序。当两个数各个数位之和不同时,将数位和较小的排在前面,当数位之和相等时,将数值小的排在前面。 例如,2022 排在 409 前面, 因为 2022 的数位之和是 6,小于 409 的数位 之和 13。…组合数学
数位排序
【问题描述】 小蓝对一个数的数位之和很感兴趣,今天他要按照数位之和给数排序。当两个数各个数位之和不同时,将数位和较小的排在前面,当数位之和相等时,将数值小的排在前面。 例如,2022 排在 409 前面, 因为 2022 的数位之和是 6,小于 409 的数位 之和 13。又如,6 排在 2022 前面,因为它们的数位之和相同,而6小于 2022 给定正整数 n,m,请问对1到n 采用这种方法排序时,排在第 m 个的元 素是多少? 【输入格式】 输入第一行包含一个正整数 n。 第二行包含一个正整数 m 。 【输出格式】 输出一行包含一个整数,表示答案。
题目详解
对于数字 1-n 而言可以事先求出每个数字的数位之和。根据每个数字的数位之和自定义排序函数即可。
代码
#include bits/stdc.h
using namespace std;
typedef long long ll;
const int maxn 1e6 10;
int a[maxn], b[maxn];//自定义排序函数
bool cmp(int x, int y)
{return b[x] b[y] || b[x] b[y] x y;
}int main()
{int n, m;cin n m;for (int i 1; i n; i ){//求i的数位之和int num i;while (num)b[i] num % 10;num / 10;a[i] i;}sort(a 1, a 1 n, cmp);cout a[m] endl;return 0;
}计数原理加法原理 加法原理 集合 S 被分成两两不相交的部分 S1,S2,S3,…,Sm那么 S 的对象数目等于∣S∣∣S1∣∣S2∣∣S3∣…∣Sm∣ 例 一个学生想学一门数学课一门文化课但不能同时选现在从 4 门数学课和 4 门文化课中选一共有 448 种方法选一门课。 加法原理的关键是将计数分解为若干个独立不相容的部分保证既不重复也不遗漏地进行计数。 加法原理是利用完备事件组的一个体现我们可以利用一个集合的补集做题。
例题分割立方体 lanqiaoOJ 题号 1620
题目描述 一个立方体边长为 n分割成 n×n×n 个单位立方体。任意两个单位立方体或者有 2 个公共点或者有 4 个公共点或者没有公共点。 请问没有公共点和有 2 个公共点的立方体共有多少对 输入描述 一个整数 n1≤n≤30 思路 反过来计算先算出有 4 个公共点的立方体有多少对然后用总对数减去。分几种情况讨论
正方体和周围 3 个正方体相邻这种情况共有 8 个就是顶角上的 8 个总个数 3×8正方体和周围 4 个正方体相邻这种情况共有 (n−2)×12 个 棱总个数 4×(n−2)×12正方体和周围 5 个正方体相邻这种情况共有 6×(n×n−4×n4) 个总个数 5×6×(n×n−4×n4)正方体和周围 6 个正方体相邻这种情况共有 (n×n×n−n×n×6n×12−8) 个总个数 6×(n×n×n−n×n×6n×12−8) 最后把这 44 个情况求和再除以 2。
正方体一共 n 3 n^3 n3 个共有 n 3 ( n 3 − 1 ) 2 \frac{n^3(n^3-1)}{2} 2n3(n3−1) 种关系
正方体和周围 3 个正方体相邻总个数 3×8正方体和周围 4 个正方体相邻总个数 4×(n−2)×12正方体和周围 5 个正方体相邻总个数 5×6×(n×n−4×n4)正方体和周围 66 个正方体相邻总个数 6×(n×n×n−n×n×6n×12−8)最后把这 4 个情况求和再除以 2。
#includebits/stdc.h
using namespace std;
int main()
{int n; cin n;if(n 1){ // 边长为 1 时特判cout 0 endl;return 0;}long long sum n * n * n * (n * n * n - 1) / 2; //总数int edge3 8;int ans3 3 * edge3;int edge4 (n - 2) * 12;int ans4 4 * edge4;int edge5 n * n - 4 * n 4;int ans5 5 * 6 * edge5;int edge6 n * n * n - n * n * 6 n * 12 - 8;int ans6 6 * edge6;cout sum - (ans3 ans4 ans5 ans6) / 2 endl;return 0;
}计数原理乘法原理
令 S 是对象的有序对 (a,b) 的集合其中第一个对象 a 来自大小为 p 的一个集合对于对象 a 的每个选择对象 b 有 q 个选择那么 S 的大小∣S∣p×q 例中性笔的长度有 3 种颜色有 4 种直径有 5 种。不同种类的中性笔有3×4×560 种。 例 3 4 ∗ 5 5 ∗ 7 2 ∗ 1 1 3 3^4*5^5*7^2*11^3 34∗55∗72∗113 的正整数因子有多少答这是算数基本定理的概念。3 有 0 ~ 4 这 5 种选择5 有 6 个选择7 有 3 个选择11 有 4 个选择因子总数是 5×6×3×4360 种。
排列数
排列是有序的。 不可重复排列数从 n 个不同的物品中取出 r 个排列数为 A n r n ( n − 1 ) ( n − 2 ) … ( n − r 1 ) n ! ( n − r ) ! A_{n}^{r}n(n-1)(n-2)\dots (n-r1)\frac{n!}{(n-r)!} Anrn(n−1)(n−2)…(n−r1)(n−r)!n! 可重复排列数从 n 个不同的物品中可重复地取出 r 个的排列数为 n r n^r nr。
组合数
排列是有序的组合是无序的。 如果 S 中的元素都不相同组合数 C n r A n r r ! n ! r ! ( n − r ) ! C_{n}^r\frac{A_{n}^r}{r!}\frac{n!}{r!(n-r)!} Cnrr!Anrr!(n−r)!n!
糊涂人寄信 lanqiaoOJ 题号 1622
题目描述 有一个糊涂人写了 n 封信和 n 个信封到了邮寄的时候把所有的信都装错了信封。求装错信封可能的种类数。 输入描述 每行输入一个正整数 n表示一种情况。(n≤20) 输出描述 输出相应的答案。
解题思路
题目建模为有 1∼n 个数字分别放在 n 个位置问都放错的情况有多少种。 用 DP 来做。定义 dp[]dp[i] 表示数字 1∼i 都放错的种类数。dp[n] 是答案。 下面考虑状态转移方程从 1∼i 递推到 i。 数字 i 如果放错有 i−1 个位置可以放(不能放在自己的位置上)假设其放在第 k 个位置。对于数字 k可以放在 i 位置也可以不放在 i 位置。
如果 k 放在 i 位置那么对于剩下 i−2 个数字放的次数就是 i−2 个数字都放错的方法数 dp[i−2]。如果 k 不放在 i 位置和 i−1 个数字放错的情况相同为 dp[i−1]。 状态转移方程dp[i] (i − 1)*(dp[i−1] dp[i−2])
#include bits/stdc.h
using namespace std;
typedef long long ll;
ll dp[30];int main()
{dp[1] dp[0]0;dp[2] 1;for(int i 3; i 22; i ) dp[i] (i - 1) * (dp[i - 1] dp[i - 2]);int n;while(cin n) cout dp[n] endl;return 0;
}鸽巢原理
鸽巢原理又称抽屉原理。 鸽巢原理 把 n1 个物体放进 n 个盒子至少有一个盒子包含 2 个或更多的物体。
例在 370 人中至少有 2 人生日相同例n 个人互相握手一定有 2 个人握手次数相同。 n 个人互相握手一定有 2 个人握手次数相同。 每人跟其他人握手最少可以是 0 次最多可以是n−1次。不存在重复握手
如果握手最少的是 0 次那么剩下的n−1人中握手最多的人不会超过n−2次。0∼n−2 共n−1种情况。如果握手最少的张三是 1 次那么剩下的n−1人中握手最多的李四除了跟张三握手一次跟其他n−2人最多握手n−2次李四最多握手n−1次。1∼n−1 共n−1种情况。如果握手最少的张三是 2 次那么剩下的n−1人中握手最多的李四除了跟张三握手一次跟其他n−2人最多握手n−2次李四最多握手n−1次。2∼n−1 共n−2种情况。 …… 所以握手次数最多有n−1种情况最少只有 1 种情况。 把最多的n−1种情况看成n−1个抽屉n个人放进这n−1个抽屉至少有一个抽屉里面有 2 人。
例题小蓝吃糖果 lanqiaoOJ 题号 1624
题目描述 Gardon 有 n 种糖果每种数量已知。Gardon 不喜欢连续 2 次吃同样的糖果。问有没有可行的吃糖方案。 输入 第一行是整数 N0n1000000 第二行是 n 个数表示 n 种糖果的数量 m i m_{i} mi0 m i m_{i} mi1000000 输出 输出一行包含一个 “Yes” 或 “no”。
解题思路
继续处理格式鸽巢原理用“隔板法”求解。 找出最多的一种糖果把它的数量 K 看成 K 个隔板隔成 K 个空间把每个隔板的右边看成一个空间其它所有糖果的数量为 S。
如果 SK−1把 S 个糖果放到隔板之间这 K 个隔板不够放必然至少有 2 个隔板之间没有糖果由于这 2 个隔板是同一种糖果所以无解。S≥K−1 时肯定有解。 其中一个解是把 S 个糖果排成一个长队其中同种类的糖果是挨在一起的然后每次取 K 个糖果按顺序一个一个地放进 K 个空间。由于隔板数量比每一种糖果的数量都多所以不可能有 2 个同样的糖果被放进一个空间里。把 S 个糖果放完就是一个解一些隔板里面可能放好几种糖果。
#include bits/stdc.h
using namespace std;
int a[1005000];int main()
{long long sum 0;int Max 0;int n; scanf(%d, n);for (int i 1; i n; i ){scanf(%d, a[i]);sum a[i]; //所有糖果数量if(a[i] Max) Maxa[i]; //最多的一种糖果}if(sum - Max 1 Max) printf(Yes\n);else printf(No\n);return 0;
}二项式定理和杨辉三角
杨辉三角排列成如下三角形的数字 11 11 2 11 3 3 11 4 6 4 1每个数是它上面 2 个数的和。 求杨辉三角第 n 行的数字可以模拟这个推导过程逐级递推复杂度 O(n2)。 用数学公式计算可以直接得到结果这个公式是(1x)n。 二项式系数就是 ( 1 x ) n (1x)^n (1x)n 展开后第 r 项的系数。 C n r n ! r ! ( n − r ) ! C_{n}^r\frac{n!}{r!(n-r)!} Cnrr!(n−r)!n! 对应杨辉三角的第 n 行第 r 个数是 C n − 1 r − 1 C_{n-1}^{r-1} Cn−1r−1 例杨辉三角的第 4 行是“1331” C n − 1 r − 1 C 4 − 1 1 − 1 C 3 0 1 , C 3 1 3 , C 3 2 3 , C 3 3 4 C_{n-1}^{r-1}C_{4-1}^{1-1}C_{3}^01,C_{3}^13,C_{3}^23,C_{3}^34 Cn−1r−1C4−11−1C301,C313,C323,C334 理解 ( 1 x ) n (1x)^n (1x)n的第 r 项就是从 n 个 x 中选出 r 个这就是组合数的定义 当 n 较大且需要取模时二项式系数有两种计算方法 1递推公式 C n r C n − 1 r − C n − 1 r − 1 C_{n}^{r}C_{n-1}^{r-}C_{n-1}^{r-1} CnrCn−1r−Cn−1r−1 公式是杨辉三角的定义即“每个数是它上面 2 个数的和”。计算复杂度是 O ( n 2 ) O(n^2) O(n2)。 2用逆直接计算 因为输出取模那么不用递推公式直接用公式计算更快。不过由于除法不能直接取模需要用到逆。用逆计算二项式系数有 C n r n ! r ! ( n − r ) ! C_{n}^{r}\frac{n!}{r!(n-r)!} Cnrr!(n−r)!n! C n r C_{n}^r Cnr mod m n ! r ! ( n − r ) ! \frac{n!}{r!(n-r)!} r!(n−r)!n! mod m ( n ! n! n! mod m)( ( r ! ) − 1 (r!)^{-1} (r!)−1 mod m)( ( ( n − r ) ! ) − 1 ((n-r)!)^{-1} ((n−r)!)−1mod m)mod m 用逆计算二项式系数复杂度是 O(n) 的。
杨辉三角形
【题目描述】 如果我们按从上到下、从左到右的顺序把杨辉三角形的所有数排成一列可以得到如下数列:111121133114641…给定一个正整数N请你输出数列中第一次出现N是在第几个数? 【输入描述】 输入一个整数N。 N ≤ 1000000000 N \le 1000000000 N≤1000000000 【输出描述】 输出一个整数表示答案
题目解析
直接计算杨辉三角的每个数然后推导出N的位置 下一行的2个数相加得下一行得一个数。例如上一行是b[0]~b[k]下一行是a[0]~a[k1]那么a[i] b[i-1] b[i] 推算过程只用一个数组完成和DP的自我滚动数组的原理一样即a[i] a[i-1] a[i]
include bits/stdc.h
using namespace std;
long long a[100050];
long long n, sum, line;//sum等于1~line行的数字个数
int main()
{cin n;sum a[0] 1;if(n 1){ cout l;return 0;}for (line l; line 50000; line )//line:杨辉三角的第1ine行{for (int i line; i 1; i --)//倒过来循环和DP的自我滚动数组的原理一样{a[i] a[i-1] a[i]; //上一行的2个数相加得下一行的一个数if(a[i] n){cout sum line - i 1;return 0;}}sum (line1);//1~line行的数字个数。每行比上一行多一个累加}return 0;
}代码只能通过40%的测试:
搜索范围小只搜了前50000行;运行时间是 O ( n 2 ) 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
我们知道杨辉三角的第i行第 j列的值为 C i j C_{i}^j Cij 用黄色印记标记的数字为我们需要考虑的部分(图一的左侧部分)我们称其为有效部分。 那么不难发现对于每一列比如第i列)它们的有效部分都是从 C 2 i i C_{2i}^i C2ii开始的。即第i列的有效部分为 C 2 i i , C 2 i 1 i , C 2 i 2 i … C_{2i}^i,C_{2i1}^i,C_{2i2}^i\dots C2ii,C2i1i,C2i2i… 显然对于同一行列数越大则对应的数值也越大对于同一列来说行数越大则数值也越大。也就是说如果某一行的某一列的值为 X那么在列数不变的情况下无论行数怎么变大都不会再出现比 X小的数了同理在行数不变的情况下列数怎么变大也不会再出现比小的数了。 于是我们可得当n≤ 1 0 9 10^9 109时有效列数为第0~16列(因为第 17列的有效部分是从 C 17 C^{17} C17_34( C 17 C^{17} C17_34 1 0 9 10^9 109)开始的所以该列无论如何都不可能出现n了其它的列就就更不可能了)。 我们考虑一列一列处理。那么对于某一列来说我们怎么确定该列中是否存在n若存在n这个n又会在该列的第几行呢? 由于随着行号的变大数值是单调递增的且知道了行号列号对应的数值也就知道了于是就很显然可以二分行号。 设当前列数为i那么二分的左边界l就为 2i右边界r为 R(满足 C R i ≥ n C_{R}^{i}\ge n CRi≥n的任意 R都可)。然后不断搜索直到n出现后返回行号(或者直到搜索结束还是没找到n返回 false)再计算出该行号、列号在数列中对应的位置即可 由于数列的构造顺序是从上到下、从左到右所以我们需要从第16 列开始找找到了即是答案直接退出程序找不到再找第 15 列。。 复杂度为 O(16Clog)(C 为计算排列组合的复杂度)。
#include bits/stdc.h
#define int long long
using namespace std;
int n;
int C(int a, int b)
{int res 1;for (int i a, j 1; j b; i ){res res * i / j;if (res n)return res;}return res;
}
signed main()
{cin n;for (int k 16; ~k; k --){int l 2 * k;int r max(n, l);int res -1;while (l r){int mid l r 1;if (C(mid, k) n){res mid;r mid - 1;}elsel mid 1;}if (C(res, k) n)cout (res 1) * res / 2 k 1 \n;}return 0;
}
2*N 名编号为1~ 2N 的选手共进行 见 轮比赛。每轮比赛开始前以及所有比赛结束后都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。总分相同的约定编号较小的选手排名靠前。 每轮比赛的对阵安排与该轮比赛开始前的排名有关:第1名和第2名、第3名和第4名、…第2K -1名和第 2K 名、…、第 2N -1名和策 2N 名各进行一场比赛每场比赛胜者得1分负者得0分。也就是说除了首轮以外其它轮比赛的安排均不能事先确定而是要取决于选手在之前比赛中的表现。 现给定每个选手的初始分数及其实力值试计算在R轮比赛过后排名第Q的选手编号是多少。我们假设选手的实力值两两不同且每场比赛中实力值较高的总能获胜。
暴力法每轮做一次排序R轮后输出 计算量:排序nlogn、共R轮Rnlogn超时 归并排序的思路: 每组比赛的胜者:赛前总分按降序排;获胜后都得1分仍是降序; 每组比赛的负者:赛前总分按降序排的;不得分仍是降序。 先按初始分数排序然后按分数高低两人一组比赛 胜者入队A负者入队B。这样A、B自身仍是有序的 那么每次对于每轮比赛结束只需进行合并操作即可O(n)的时间就能让序列变成有序的了。
归并排序 归并排序的主要操作
分解。把初始序列分成长度相同的左右两个子序列然后把每个子序列再分成更小的两个子序列…直到子序列只包含1个数。用递归实现。求解子问题对子序列排序。最底层的子序列只包含1个数其实不用排序。合并。归并2个有序的子序列这是归并排序的主要操作
对n个数进行归并排序:
需要logn趟归并;在每一趟归并中有很多次合并操作一共需要O(n)次比较。 所以计算复杂度是O(nlogn)。 空间复杂度:需要一个临时的b[]存储结果所以空间复杂度是O(n).
#include bits/stdc.h
using namespace std;
const int N 2e5 10;
int n, q, mwnls;
struct Player
{int s, w, id;bool operator (const player x) const {if(x.sl s)return s x.s;return id x.id;}
}P[N]winner[N], loser[N];
signed main()
{cin n m q;for (int i 1; i n * 2; i)P[i].id i;for (int i 1; i n * 2; i)cin P[i].s;for (int i 1; i n * 2; i)cin P[i].w;sort(p1, P 1 n * 2);while(m --){wn ls 0;for(int i 1; i n; i){if(P[i * 2].w P[i * 2 - 1].w){P[i * 2].s ;winner[ wn] P[i * 2];loser[ ls] P[i*2-1];}else {P[i * 2 - 1].s;winner[ wn] p[i * 2 - 1];loser[ ls] P[i * 2];}}merge (loser 1, loser 1 n, winner 1, winner 1 n, P 1);}cout P[q].id \n;return 0;
}
