顺德网站制作案例教程,建设网站便宜,芜湖城建集团,销售管理系统下载题目描述#xff1a;
下面的图形是著名的杨辉三角形#xff1a; 如果我们按从上到下、从左到右的顺序把所有数排成一列#xff0c;可以得到如下数列#xff1a;
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, ...
给定一个正整数 N#xff0c;请你输出数列中第一次出现…题目描述
下面的图形是著名的杨辉三角形 如果我们按从上到下、从左到右的顺序把所有数排成一列可以得到如下数列
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, ...
给定一个正整数 N请你输出数列中第一次出现 N 是在第几个数
输入格式:
输入一个整数 N。
输出格式:
输出一个整数代表答案。
数据范围:
对于 20% 的评测用例1≤N≤10 对于所有评测用例1≤N≤1e9。
输入样例
6输出样例
13 这个图是来自acwing的东风祝酒的图片
分析步骤 第一理清思路 众所周知杨辉三角中华瑰宝他这个三角型是对称的如果我们要求出哪个点是第一次出现的那么一定是在这个三角形的左边我们可以把右半部分删掉完全不用考虑。这是本题目第一个特点。 现在我们再斜着看一看把斜着的看做一个序列。第一行数坐标就是(00)第二行从左到右就是1011.....以此类推。我们再看到中间紫色的这一列数值永远就是C2k^k并且永远是这个数最大我们就可以从这个数开始找起。而且题目中说到了N最大就是1e9那么C34^171e9 C32^161e9。所以我只需要找前面16个斜行就行了。这是本题的第二个特点。 我们现在想想如果一个一个去找的话速度太慢了。因为序列的单调的这一眼就能看出来而且我们需要找一个特定的在这个值的左边就会太小了在这个值的右边就会太大了就可以将其分为两个部分。这就符合了我们二分的特点因此我们直接从中间对称轴倒序二分找起即可!这就是本题的第三个特点。 大家一定要好好看看这图仔细去理解 第二书写主函数构建整体框架 因为我们分析过了我们只需要枚举前16行就可以了那么我们倒序枚举检查一下这一行是不是我们想要的是的话就代表找到了就break退出。
int main()
{cin n;for (int k 16; ; k -- )if (check(k))break;return 0;
} 第三书写check函数 现在我们就入了其中的一个序列进行检查运用二分的方法去查找。 首先我们要确定二分的左节点和右节点所以我们定义LL l k * 2, r n;为什么这么定义呢因为在一个序列之中我们最小的值是上图中紫色的那一些数这些数的特点是C2k^k所以定义他们为最小的左边界节点那么右边界节点就应该是最大的那个数字了但是我们的杨辉三角是无穷的所以我们应该只需要找到题目给出的那个数字就可以了那么这个数一定会在Cn^1的这个地方出现因为这个值就是N。所以我们把右边界定义为n。 如果l比r都要大就直接返回false不可能在这一行。因为这个数一定比这一序列的第一个数要小就代表答案的位置在更靠前的序列之中。 进入while循环计算我们的mid值计算我们的Cmid^k让这个数和n比较大小。如果这个数比n要大或等于的话就代表答案有可能在mid左边也就是更小的那一边所以我们把r赋值给mid。反之答案比n更小的话那么答案一定在mid的右边也就是更大的一边就让mid1赋值给l。 经过了一轮的while循环判断之后再去计算一下Cr^k看看和答案是否一致如果不一致就是错 最终输出位置即可。
bool check(int k)
{LL l k * 2, r n;if (l r) return false;while (l r){LL mid l r 1;if (C(mid, k) n) r mid;else l mid 1;}if (C(r, k) ! n) return false;cout r * (r 1) / 2 k 1 endl;return true;
} 第四书写计算组合数的函数 我们计算组合数直接暴力做就可以利用双指针一起去求解。
LL C(int a, int b)
{LL res 1;for (int i a, j 1; j b; i --, j ){res res * i / j;if (res n) return res;}return res;
}
代码
#include iostream
#include cstring
#include algorithmusing namespace std;typedef long long LL;int n;LL C(int a, int b)
{LL res 1;for (int i a, j 1; j b; i --, j ){res res * i / j;if (res n) return res;}return res;
}bool check(int k)
{LL l k * 2, r n;if (l r) return false;while (l r){LL mid l r 1;if (C(mid, k) n) r mid;else l mid 1;}if (C(r, k) ! n) return false;cout r * (r 1) / 2 k 1 endl;return true;
}int main()
{cin n;for (int k 16; ; k -- )if (check(k))break;return 0;
}
