青少年编程知识记录 codecoming

【题解】盈亏问题

【题目描述】

一群人团购一件物品：

如果每人出 a元，所付总金额比物价多出了x 元；

如果每人少出 1元，也就是每人出a-1元，所付总金额比物价少了y元。

给定 a,x,y求参与团购的人数及该物品的价格。

【输入描述】

单独一行：三个整数：a,x及y

【输出描述】

单独一行：两个整数。第一个整数表示参与的人数，第二个整数表示物品的价格，中间用一个空格分开。

【样例输入】

8 3 4

【样例输出】

7 53

【数据范围】

  • 1≤a≤1000

  • 1≤𝑥≤10001≤x≤1000

  • 1≤𝑦≤10001≤y≤1000



作者:亿万年的星光 分类:C++知识 浏览:

编写第一个C++程序

前面的文章介绍了Dev-C++的下载安装：【入门篇】>>> DEVC++下载、安装、简单使用 - 青少年编程知识记录 (codecoming.com)今天讲一下如何使用Dev-C++如何编写第一个程序。第一步，新建空白程序文件:第二步，输入以下代码：#include<iostream> using namespace std; int main(){ cout<<"Hello World!&quo
作者:亿万年的星光 分类:C++知识 浏览:

【数据结构】并查集2

上一篇文章，简单介绍了并查集。这篇文章，介绍一下并查集的改进以及优化。find函数的优化（路径压缩）因为并查集的merge操作：void merge(int a, int b) { //先找到两个元素对应的根对应的元素  int fa = find(a);  int fb = find(b); if(fa==fb) return; els
作者:亿万年的星光 分类:C++知识 浏览:

【数据结构】并查集1

1.引入

    对于一个集合S={a1, a2, …, an-1, an}，我们还可以对集合S进一步划分: S1,S2,…,Sm-1,Sm，我们希望能够快速确定S中的两两元素是否属于S的同一子集。

    举个栗子，S={0，1, 2, 3, 4, 5, 6}，如果我们按照一定的规则对集合S进行划分,假设划分后为S1={1, 2, 4}, S2={3, 6}，S3={0, 5}，任意给定两个元素，我们如何确定它们是否属于同一子集？某些合并子集后，又如何确定两两关系？基于此类问题便出现了并查集这种数据结构。

2.概念

    并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。

并查集的思想是用一个数组表示了整片森林（parent），树的根节点唯一标识了一个集合，我们只要找到了某个元素的的树根，就能确定它在哪个集合里。

3.作用

    并查集可以高效的对元素进行分组（合并在一起），并且能快速的查询两个元素是否属于同一组。

4.基本操作

    合并：合并两个集合。join函数

    查找：判断两个元素是否在一个集合。find函数 

5.过程解释

    假如有两个集合，之间的关系可以用下面的图像表示：

一开始，分成两组，1和2是同一组，1和3是同一组，那么有没有什么办法可以将这两组练习起来。我们将1视为2的父级，1可以视为3的父级

这样，我们可以把图片划分成下面这样：

那么如果我们有其他的数据，比如下面的4，5，6这样表示

那么新问题来了，这两个集合如果在一块应该怎么表示呢？很简单，让这两个集合中的‘老大’打一架，谁赢了，谁就是两个集合共同的‘老大’。

假如 编号1 赢了，那么集合应该变成下面这样：

也就1成了所有人的‘老大’

那么也就是形成了一个等级严格的树形结构。

从数据结构上看，我们关注的重点是两个数据之间是否连通。

那么看下面这个例子

对于上面这个图，我们如何界定两个节点之间是否有关系呢？比如下面这两个题：

(1)问：2和3之间是否存在关系？

(2)问：3和7之间是否存在关系？

对于问题(1)，我们从图中可以很明显的看出，2和3之间有关系，因为他们有共同的’老大‘。

对于问题(2),  我们从图中也可以明显的看出，3和7之间没有关系，因为从3开始往上找，发现老大是1，而从7开始找，我们发现老大是4，这两个老大（根节点）不一样，说明没有关系。

在做题中，也就是我们输入每组的对应关系如下，

1 2  1 3  4 5  4 6  6 7

然后询问任意两个数（节点）之间有没有关系?





6.代码实现

（1）初始化

我们用f数组表示父级元素节点，初始化代码如下

int f[100]; //父节点     //初始化 n个元素   void Init() {  	//使每个元素的根节点是其本身  	//即初始时每个元素都是单独的   	for(int i=1; i<=n; i++){  			f[i]=i;    	}   }

’每个节点都是自己的父节点‘



（2）查询操作

查询操作有两种实现方式，一种是递归实现，另一种是非递归实现。

递归实现：

int find(int x){      if(f[x] == x)          return x;      else          return find(f[x]);}

一层一层访问父节点，直至根节点（根节点的标志就是父节点是本身）。要判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同即可。

非递归实现：

int find(int x) {  	while(f[x] != x) {  //直到元素的父节点是它本身，表示已经查询到了树的根  		x= f[x];  	return x; 			//返回根节点对应的元素   }





（3）合并

void merge(int a, int b) {  	//先找到两个元素对应的根对应的元素   	int fa = find(a);   	int fb = find(b);  	if(fa==fb) return;  	else f[fa]=fb;  //否则令元素 a的根指向元素 b的根   }

合并操作也是很简单的，先找到两个集合的代表元素，然后将前者的父节点设为后者即可。当然也可以将后者的父节点设为前者。

作者:亿万年的星光 分类:C++知识 浏览:

unsigned

在一些代码中，经常能看到unsigned这种数据类型，比如下面这样的。#include<iostream> using namespace std; int main(){ unsigned int x; int y; cin>>x>>y; cout<<x<<" "<<y; return 0; }那么
作者:亿万年的星光 分类:C++知识 浏览:

【数论】快速乘

上一篇文章简单说了龟速乘的问题，有人觉得龟速乘还是太慢了，有没有什么办法再快一点，实际是有的，就是我们今天介绍的 快速乘。快速乘的原理和龟速乘不同，快速乘并不是基于二进制和位运算，严格来说，快速乘是利用了一个bug才实现的功能。这个bug 就是 long double 和long long 的定义范围不同。因为long double的范围比long long 大一些。它来源于下面这篇文章：什么意思呢？简单来说，就是就是在原地爆炸的边缘疯狂试探，把本来存进long long会炸掉的值先进行计算，用
作者:亿万年的星光 分类:C++知识 浏览:

【数论】龟速乘

我们前面一篇文章学习了快速幂。它可以解决两类问题：a^b，(a^b)%c对于第一类，我们可以使用递归法或者迭代法可以求出，为了计算的快，我们可以引入位运算操作，但是目前来看，无论怎么优化都不能超过long long。对于第二类，是快速幂的优点所在，通过 （a*b）%m=(a%m *　ｂ％ｍ)　％ｍ公式，我们可以将结果运算范围大大减小，使运算结果保持在m范围以内。但是，快速幂并不是万能的，比如下面这个例子求（ａ＾ｂ）％ｍ。19260817 2333333 12345676543
作者:亿万年的星光 分类:C++知识 浏览:

【数论】杨辉三角

一、起源 杨辉三角，是二项式系数在三角形中的一种几何排列。在欧洲，这个表叫做帕斯卡三角形。帕斯卡（1623----1662）是在1654年发现这一规律的，比杨辉要迟393年，比贾宪迟600年。杨辉三角是中国古代数学的杰出研究成果之一，它把二项式系数图形化，把组合数内在的一些代数性质直观地从图形中体现出来，是一种离散型的数与形的结合。可以看出，它与上节课讲的二项式系数一样。二、特点每个数等于它上方两数之和。每行数字左右对称，由1开始逐渐变大。第n行的数字有n项。前n行共[(1+n)n]/2 个数。
作者:亿万年的星光 分类:C++知识 浏览:

【数论】二项式定理

一、基本概念

上面这个式子就叫做二项式定理，又称牛顿二项式定理，该定理给出两个数之和的整数次幂诸如展开为类似项之和的恒等式。二项式定理可以推广到任意实数次幂，即广义二项式定理。

 初中高中阶段比较常用的是二次方和三次方

(a+b)²=a²+2ab+b²

(a+b)³=a³+3a²b+3ab²+b²



扩展：常见平方和立方和公式及其变形：

(a+b)²=a²+2ab+b²

(a-b)²=a²-2ab+b²

a²-b²=(a+b)(a-b)

(a+b)³=a³+3a²b+3ab²+b²

(a-b)³=a³-3a²b+3ab²-b³

a³+b³=(a+b)(a²-ab+b²)

a³-b³=(a-b)(a²+ab+b²)

作者:亿万年的星光 分类:C++知识 浏览:

【数论】均值不等式

均值不等式是高中常见的一个知识点，下面这篇文章做一下简单总结。

1、

其中a,b属于实数R，当且仅当a=b时，等号成立。这个也叫基本不等式



2、

其中a,b属于正实数，当且仅当a=b时，等号成立。





3、

其中a,b属于正实数，当且仅当a=b时，等号成立。



4、



其中a,b属于正实数，当且仅当a=b时，等号成立。

5、不等式链

6、注意使用不等式求最值的条件是：一正、二定、三相等



7、例题一



若实数满足a+b=2， 则3^a+ 3^b 的最小值是____________





作者:亿万年的星光 分类:C++知识 浏览: