发表于 | 分类于

C++大数加法总结

  • 大数加法就是把数字存在数组中，数组下标从小到大代表数字从小到大，例如数组arr[] = {0987654321}代表的是1234567890这个数字，要注意加法的进位；

  • 算法例子：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define MAX 105
    using namespace std;

    int arr[MAX];

    int main()
    {
    	char str[MAX];
    	int cnt,n,m,len,idx,temp,yu;
    	scanf("%d", &cnt);
    	while(cnt--)
    	{
    		// 初始化
    		len = 0;
    		memset(arr, 0, sizeof(arr)); 
    		
    		scanf("%d", &n);
    		for(int i=0; i<n; i++)
    		{
    			scanf("%s", str);
    			m = strlen(str);
    			
    			for(int i=m-1; i>=0; i--)
    			{
    				idx = m - i - 1;
    				temp = arr[idx]	+ (str[i] - '0') + yu;
    				arr[idx] = temp%10;
    				yu = temp/10;
    			}	 
    			
    			while(yu)
    			{
    				temp = arr[m] + yu;
    				arr[m] = temp%10;
    				yu = temp/10;
    				m ++;
    			}
    			len = max(len, m);// 记录数组长度
    		} 
    		
    		for(int i=len-1; i>=0; i--)
    		{
    			printf("%d", arr[i]);
    		}printf("\n");
    	}
    	return 0;
    }

    /*
    2
    3
    1111
    9999
    9999
    21109
    3
    123456789012345678901234567890
    123456789012345678901234567890
    123456789012345678901234567890
    370370367037037036703703703670
    */

发表于 | 分类于

整数划分总结

1.把整数n划分成不大于m的划分的种类数

  • 允许有重复的情况，eg：5 = 1 + 2 + 2，我们定义dp二维数组 ,注意当n>m时分成两部分：①不含m时dp(n)(m-1)，②至少含有一个m时dp(n-m)(m)，代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    /**
    dp[n][m] = dp[n][n]; (n < m)
    dp[n][m] = dp[n][m-1] + 1; (n = m)
    dp[n][m] = dp[n][m-1] + dp[n-m][m]; (n > m)
    */
    for(int i=1; i<MAX; i++) {
        for(int j=1; j<MAX; j++) {
            if(i < j) {
                dp[i][j] = dp[i][i];
            }else if(i == j) {
                dp[i][j] = dp[i][j-1] + 1;
            }else {
                dp[i][j] = dp[i][j-1] + dp[i-j][j];
            }
        }
    }

  • 不允许含有重复的情况，eg：5 = 1 + 4，我们定义dp二维数组 ,注意当n>m时分成两部分：①不含m时dp(n)(m-1)，②至少含有一个m时dp(n-m)(m-1)，代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    /**
    dp[n][m] = dp[n][n]; (n < m)
    dp[n][m] = dp[n][m-1] + 1; (n = m)
    dp[n][m] = dp[n][m-1] + dp[n-m][m-1]; (n > m)
    */
    for(int i=1; i<MAX; i++) {
        for(int j=1; j<MAX; j++) {
            if(i < j) {
                dp[i][j] = dp[i][i];
            }else if(i == j) {
                dp[i][j] = dp[i][j-1] + 1;
            }else {
                dp[i][j] = dp[i][j-1] + dp[i-j][j-1];
            }
        }
    }

2.把整数n划分成m个数的划分的种类数

  • 注意n>m时候分成两部分：①不含数字1，先拿m个数给每个坑一个数字1，然后这m个坑再分n-m即dp(n-m)(m)，②至少有一个数字1即dp(n-1)(m-1)，代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    /**
    dp[n][m] = 0; (n < m)
    dp[n][m] = 1; (n = m)
    dp[n][m] = dp[n-m][m] + dp[n-1][m-1]; (n > m)
    */
    for(int i=1; i<MAX; i++) {
        for(int j=1; j<MAX; j++) {
            if(i > j) {
                dp[i][j] = 0;
            }else if (i == j) {
                dp[i][j] = 1;
            }else {
                dp[i][j] = dp[i-j][j] + dp[i-1][j-1];
            }
        }
    }

3.把整数n划分成若干个奇正整数之和的划分数

  • g(n)(m)：将n划分成m个偶数；f(n)(m)：将n划分成m个奇数，这个比较难，先看偶数g(n)(m)的分法：先拿出m个1填每个坑，然后把剩下的n-m分成j个奇数即f(n-m)(m)；再看奇数f(n)(m)的分法：①不含1的情况，先拿出m个1填坑，然后把剩的n-m分成m个偶数即g(n-m)(m)；②至少有一个1的情况即f(n-1)(m-1)。代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    /**
    g[0][0] = f[0][0] = 1;
    g[n][m] = f[n-m][m];
    f[n][m] = f[i-1][j-1] + g[i-j][j];
    */
    for(int i=1; i<MAX; i++) {
        for(int j=1; j<=i; j++) {
            g[i][j] = f[i-j][j];
            f[i][j] = f[i-1][j-1] + g[i-j][j];
        }
    }

发表于 | 分类于

c++中的sort与qsort的使用

  1. sort函数

    • sort(arr, arr+n, cmp)函数有三个参数：数组首地址，数组首地址加上要排序的元素个数，比较函数cmp；如果第三个参数不写则按照降序排列。

    • cmp函数的编写：

      1
      2
      3
      4
      bool cmp(int a, int b)
      {
          return a > b;//按照降序排列
      }

  2. qosrt函数

    • qsort(arr, n, sizeof(arr[0]), cmp)函数有四个参数：数组首地址，待排元素个数，单个元素长度，cmp比较函数。

    • cmp比较函数的编写：

      1
      2
      3
      4
      int cmp(const void *a, const void *b)
      {
          return *(int *)a - *(int *)b;//降序排列
      }

发表于 | 分类于

c++优先队列的总结

  • 如下代码，优先队列是按照元素由大到小排列的，a.x > b.x则a < b，排列顺序是：ba，所以x越小越排在前面。 
1
2
3
4
5
6
7
8
9
#include<queue>
using namespace std;
struct node{
	int x,y;
    bool operator < (const node &a) const {
        return x > a.x;//x越小优先级越高
    }
};
priority_quue<struct node> pq;
  • less和greater优先队列
1
2
3
4
5
6
7
8
9
#include<queue>
using namesapce std;

priority_queue<int, vector<int>, less<int> > pq;
priority_queue<int, vector<int>, greater<int> > pq;

输出：
less<int> : 5,4,3,2,1
greater<int> : 1,2,3,4,5

发表于 | 分类于

最小生成树总结

1、最小生成树

  • 在含有n个顶点的连通图中选择（n-1）条边，构成一棵极小连通子图，并使该连通子图中（n-1）条边上的权值之和达到最小，则称其为连通图的最小生成树。

2、prim算法

  • 在保证连通的情况下依次选取点加入S集合，得到最小生成树。

  • 算法步骤：

    • 初始化memset(dist, 0x7f, sizeof(dist))，把第一个点dist[0]=0然后从dist中每次选取dist最小的点point，标记vis[point]=1；
    • 遍历map数组，当map[point][i]<dist[i]时更新dist数组；
    • 累加dist数组计算出结果。

  • prim算法代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    #define INF 0x7f7f7f7f
    int vis[MAX],dist[MAX];
    int map[MAX][MAX];

    // 初始化
    memset(dist, 0x7f, sizeof(dist));
    memset(vis, 0, sizeof(vis));
    dist[0] = 0;

    int prim(int n)
    {
        int cnt=n-1,,point,dist_min,res=0;
        // 找n-1条边
        while(cnt--)
        {
            dist_min = INF;
            for(int i=0; i<n; i++)
            {
                if(vis[i]==0 && dist[i]<dist_min)
                {
                    dist_min = dist[i];
                    point = i;
                }
            }
            // 把点point加到S集合中
            vis[point] = 1;
            // 根据最新的点point和条件更新dist数组
            for(int i=0; i<n; i++)
            {
                if(vis[i]==0 && map[point][i]<dist[i] && map[point][i]!=INF)
                {
                    dist[i] = map[point][i];
                }
            }
        }
        // 计算权值和       
        for(int i=0; i<n; i++)
        {
            res += dist[i];
        }
        return res;
    }

3、kruskal算法

  • 在保证无回路的情况下依次选取权值最小的边加入到生成树中，构成最小生成树。

  • 算法步骤：

    • 构造边的边的结构体，按照边权值w的大小对边从小到大进行排序；
    1
    2
    3
    4
    struct node {
        int u,v;// 起点u，终点v
        int w;// 权值
    } edge[MAX];
    • 如果(u,v)这条边没有构成回路则把这条边加入生成树中，利用并查集算法；
    • 计算结果。

  • kruskal算法代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    int pre[MAX];
    int map[MAX][MAX];
    struct node {
        int u,v;
        int w;
    } edge[MAX];

    bool cmp(struct node a, struct node b)
    {
        return a.w < b.w;
    }

    // 并查集
    int find(int x)
    {
    	int r=x,a=x,b;
    	while(pre[r] != r)// 搜索 
    	{
    		r = pre[r];
    	}
    	// 压缩
    	while(pre[a] != r) 
    	{
    		b = pre[a];
    		pre[a] = r;
    		a = b;
    	}
    	return r;// 根节点 
    }

    int join(int x, int y)
    {
    	int a,b;
    	a = find(x);
    	b = find(y);
    	if(a != b)
    	{
    		pre[b] = a;
    		return 1;
    	}	
    	return 0;
    }

    int kruskal(int n)
    {
        int edge_num = 0,sum = 0;
        // 对egde进行排序
        sort(edge, edge+n, cmp);
        // 如果(u,v)没有构成回路则把这条边加入进来
        for(int i=0; i<n; i++)
        {
            if(join(edge[i].u, edge[i].v) == 1)// 表示(u,v)不连通，可以加入
            {
                edge_num ++;
                sum += edge[i].w;
            }
        }
        // 边数为n-1
        if(edge_num == n-1)
        {
            printf("%d\n", sum);
        }
        else
        {
            printf("no.\n");
        }
    }

发表于 | 分类于

字符编码总结

1.注意位与字节的区别

  • 位是计算机存储的最小单位，外文名称是bit，音译比特，1bit；

  • 字节是计算机存储的第二小单位，英文名称是byte；

  • 字节与位的换算方式：1byte = 8bits，即一字节等于8比特。在计算机中一般int类型有4个字节，所以Int类型有32位（对于有符号类型最高位表示符号位0表示正数1表示负数，表示范围是-2^31^ 至2^31^-1，对于无符号unsigned int表示范围为0至2^32^-1）。

  • 对于int类型有符号的，0000 0000 0000 0000 0000 0000 0000 0000注意位数是从0位开始的，int类型最大可以表示的正整数是2^31^-1；下面看一下负数的表示，==值得注意的是数据在计算机中是用补码形式存储的（正数的原码和补码一样，负数的补码是反码求反加一并且符号位不能变，反码是数据位求反符号位不变）==；那么，我们这样来算

    原码：1111 1111 1111 1111 1111 1111 1111 1111（-2^31^ +1 = -2147483647）==这难道就是最小负数？？？==肯定不是的，我们注意到：

    • +0的原码：0000 0000 0000 0000 0000 0000 0000 0000

    • -0的原码：1000 0000 0000 0000 0000 0000 0000 0000

    为了节约存储，我们把-0最为int类型最小负数，即-2^31^ = -2147483648。所以对于int类型最大为2^31^-1 = 2147483647，最小为-2^31^ = -2147483648。对于无符号型int来说最大为2^32^-1，最小为0

2.了解ASCLL编码、GB2312编码(中文)、unicode编码和UTF-8编码

  • ==ASCLL编码：==由于计算机是美国人发明的，因此，最早只有127个字符被编码到计算机里，比如大写字母A的编码是65，小写字母z的编码是122。
  • ==GB2312编码(中文)：==处理中文一个字节是不够的(2^8^-1=255)，至少要两个字节（2^16^-1 = 65535个汉字差不多）。
  • ==unicode编码：==Unicode把所有语言都统一到一套编码里，这样就不会再有乱码问题了。
  • ==UTF-8编码：==UTF-8编码把一个Unicode字符根据不同的数字大小编码成1-6个字节，常用的英文字母被编码成1个字节，汉字通常是3个字节，只有很生僻的字符才会被编码成4-6个字节。如果你要传输的文本包含大量英文字符，用UTF-8编码就能节省空间。