MSTBL的博客
0%

发表于 更新于 分类于

C++代码风格

具体的代码风格每个人都有不一样的理解，这里只放一些约定俗成的之类的东西

命名

不加前缀时：

eg.

1
2
int whatTheFuck;    //变量，驼峰式命名法
int WhatTheHell();  //函数，第一个单词就大写（帕斯卡命名法）

加前缀用匈牙利式：

eg.

1
int iWillMoYou;       //i是int的缩写

前缀

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
1.整型的前缀
short sValue;     //s为short的前缀
int iAge;         //i为int的前缀
unsigned int uiAge;   //ui为unsigned int的前缀（两个单词的首字母） //也有用u做前缀的
long lValue;      //l为long的前缀

2.浮点型的前缀
float fScore;    //f为float的前缀
double dValue;   //d为double的前缀

3.字符型的前缀
char cChar;      //c为char的前缀
TCHAR tcChar;    //多字节字符和Unicode字符兼容类型的前缀tc wchar_t  wcChar   //宽字符前缀wc

4.字符串的前缀
char szName[30];  //sz为C语言字符串的前缀 string strName;
//str为C++字符串变量的前缀 CString strInfo;  
//str为MFC字符串变量的前缀

5.布尔型的前缀
bool bPass;      //b为bool的前缀

6.指针型的前缀  
int *pValue;    //p为指针的前缀,p后是否再加变量类型自己决定

7.数组的前缀
int arrNum[10];  //arr为数组的前缀，同上，arr后是否再加数组元素的数据类型前缀自己决定。

8.枚举变量的前缀  
enum  emWeek;    //em为枚举变量的前缀

9.结构变量的前缀
T_NODE  tNode;    //结构名称以T_开头 10.字节变量的前缀：by BYTE  byInfo;  

10.字符指针的前缀
LPCTSTR  ptszInfo;     //ptsz表示前缀，t表示TCHAR类型 LPCSTR  pszInfo; LPSTR  pszInfo;

11.STL容器类型前缀
vector<int>  vecValue;   //vec表示vector容器的前缀

缩写

牛津英语缩写

韦氏词典中的缩写

注释

块注释

/* */不能嵌套

下面的有争议

using namespace std

STD里东西太多，用using namespace std有一定风险，可能会导致命名冲突，如STD里有search()函数。

可以通过把STD要用的东西分别写出来的方法，显式声明降低风险

eg.

1
2
3
4
5
6
7
8
9
10
11
12
using std::cin;
using std::cout;
using std::ios_base;
using std::max;
using std::memset;
using std::min;
using std::sort;
using std::sqrt;
using std::string;
using std::vector;
using std::endl;
...

复合类型声明

1
int * p;

*修饰的是p不是int

1
int* p1,p2;

上面的语句里只有p1是指针p2不是

两种写法

  1. int *p1;强调p1是指针
  2. int* p2;强调本次声明是复合类型声明

发表于 更新于 分类于

C++优化

输入输出

printf/scanf快于cout/cin，具体原因百度

不过后者可以通过在main开始时加下面三行代码实现优化，优化后效率和前者差不多。

1
2
3
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

位运算

参考-> 位运算

发表于 更新于 分类于

背包问题

背包问题有许多种，其中最简单的形如最优装载问题:给出n个物体，第i个物体的重量为wi。在总重量不超过c的前提下选择尽可能多的物体。这种问题就是最简单的贪心问题，用贪心算法就能得到最优解。

复杂一些的是部分背包问题。这类题在最优装载问题的基础上给了每个物体价值vi。也可以用贪心算法做，根据每个物体的性价比贪心就行。

0-1背包问题

而对于更复杂的0-1背包问题，背包问题就不一定能得到最优解了。这时候我们就要用到动态规划。

动态规划与分治法相似，都是通过组合子问题的解来求解原问题……动态规划算法对每个字问题只求解一次，将其解保存在一个表格中，从而无需每次求解一个子问题是都重新计算，避免了这种不必要的计算工作。——《算法导论》

j\i 1 2 …… c
1（底）
2
……
n（顶） 最终解

我们可以用一个如上表格所示二维数组来存储rmax的值，以c为列数，i为行，之后自底向上地求解最大值。动态转移方程为：

rmax[i][j]=max(rmax[i-w[a]][j-1]+v[a],rmax[i][j-1])

这样我们需要c*n的空间。为了减少空间，我们可以将二维数组压缩成一位数组，同样以c为列数，对i~n的物体分别倒序遍历一次这个数组，这样就只需要c的空间了。这样的动态转移方程为：

题目：P1048 采药

完全背包问题

完全背包问题在0-1背包问题的基础上又增加了难度，背包中物品数量没有限制。不过完全背包还是可以用动态规划做，在0-1背包的基础上修改一下就行。

动态转移方程为

题目：P1616 疯狂的采药 这题c*n太大，只能用一维数组做。

发表于 更新于 分类于

KMP算法

KMP算法是一种线性时间的字符串匹配算法，相对朴素字符串匹配算法来说效率大大提高。它充分利用匹配后的已知信息，使匹配一次后能跳过尽可能多的字符继续搜索。

预处理

为了知道能跳过几个字符，需要先对模式（待搜索的字符，亦即pattern）进行预处理。要建立一个前缀表，用数组来存。它表示模式的各个前缀的真前缀和真后缀最大有多少个字符匹配。下面是预处理的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Init()
{
    Next[1] = 0;                        //小写next和STD冲突
    int k = 0;

    for (int i = 1; i < palen; i++)     //为什么这么些就可以还没搞明白
    {
        while ((k > 0) and (pattern[k] != pattern[i]))
        {
            k = Next[k];
        }

        if (pattern[k] == pattern[i])
        {
            k++;
        }

        Next[i] = k;
    }
}

搜索

预处理完成后剩下的当然就是搜索了。搜索的代码只要在朴素算法基础上做些修改即可。以下是搜索函数的实现：

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
void See()                                      //取名search()会和STD有冲突
{
    for (int i = 0; i < txtlen - palen + 1; i++)
    {
        p = 0;                                  //用来记录本次搜索中匹配的字符数

        for (int j = 0; j < palen; j++)
        {
            if (text[i + j] == pattern[j])
            {
                p++;
            }
            else
            {
                i = i + j - Next[j + 1]-1;
                break;
            }
        }

        if (p == palen)                         //完全匹配
        {
            cout << i + 1 << endl;              //输出
            i = i + palen - Next[palen]-1;
        }
    }
}

完整代码

以下是程序完整的代码：

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<string>
using namespace std;
string text, pattern;
int Next[10005];
int res[10005];
int palen, txtlen;
int p;
void Init()
{
    Next[1] = 0;
    int k = 0;

    for (int i = 1; i < palen; i++)
    {
        while ((k > 0) and (pattern[k] != pattern[i]))
        {
            k = Next[k];
        }

        if (pattern[k] == pattern[i])
        {
            k++;
        }

        Next[i] = k;
    }
}

void See()
{
    for (int i = 0; i < txtlen - palen + 1; i++)
    {
        p = 0;

        for (int j = 0; j < palen; j++)
        {
            if (text[i + j] == pattern[j])
            {
                p++;
            }
            else
            {
                i = i + j - Next[j + 1] - 1;
                break;
            }
        }

        if (p == palen)
        {
            cout << i + 1 << endl;          
            i = i + palen - Next[palen] - 1;
        }
    }
}

int main()
{
    cin >> text >> pattern;
    palen = pattern.size();
    txtlen = text.size();
    Init();
    See();
    return 0;
}

发表于 分类于

排列组合问题

输出排列组合这类问题通常是递归的，比较适合用递归求解。可以作为深度优先搜索（DFS）的理解练习。

P1706 全排列问题

本题要求输出 1n n个数的全排列。可以以1n为根节点分别建立一棵树，这棵树每个节点都有n个子节点，深度为n，对这些树组成的森林进行深度优先搜索,每次搜索到叶子节点时输出搜索路径并回溯。遇到用过的数时跳过搜索下一个。这样就可以实现题目要求的功能。

关于建树，我们也可以以“0”作为根节点，将上述n棵树作为它的子树。这样就可以进行单源深搜。

对于如何建树，我们只要在递归里用一层循环：

1
2
3
4
5
6
7
void dfs(int k)
{
    for (int i = 1; i <= n; i++)
    {
            dfs(k + 1);
    }
}

在dfs函数中用一个判断语句同时实现判断是否到达子节点和输出：

1
2
3
4
5
if(k == n)
   {
       print();
       return;
   }

用一个res[]数组来存答案,每次搜索前把i填入res[k + 1]中，因为我们从0开始搜索。为了知道每个数字是否用过，还需要一个used[] 数组来存储1~n是否用过；在下一层搜索前将其改为true，下一层搜索完之后回归。

下面是完整的dfs()函数的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dfs(int k)
{
    if(k == n)                  //到达叶子结点
    {
        print();
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if(!used[i])
        {
            used[i] = true;     //记录使用情况
            res[k + 1] = i;
            dfs(k + 1);         //递推
            used[i] = false;    //回归
        }
    }
}

此外，由于题目要求每个数字5位场宽，我们还需要设置场宽。这需要用到<iomanip>中的setw()。以下是print函数的实现：

1
2
3
4
5
6
7
8
void print ()
{
    for(int i = 1; i <= n; i++)
    {
        cout << setw(5) << res[i];
    }
    cout << endl;
}

最后还要注意一点的是在主函数中调用的是dfs(0)，用的是上述第二种建树方法，以下几题用的也是此种方法

P1157 组合的输出

本题要求不用递归输出n个数中r个数的全排列。然而我用了递归。如果用递归的话有了上一题的经验就比较简单，稍微修改一下即可。可以在遍历下一层时只遍历比k大的数，这样就能实现功能，还不用判重。下面给出dfs_2()函数的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dfs_2(int k)
{
    if (b == r)         //n改成r，上题中是n是因为全排列，n=r，下同 还要记得将print()中的n改成r
    {
        res[r] = k;     //这里需要注意一定要把最后一位填上
        print();
        return;
    }
    for (int i = k + 1; i <= n; i++)
    {
        res[b] = k;
        b++;            //b用来记录位数
        search(i);
        b--;
    }
}

P1691 有重复元素的排列问题

本题要求输出重复元素的全排列。也只需在P1706的基础上修改即可。可以记录每个元素的数目，像之前一样进行深搜，不一样的是，遇到用过的元素时将数目-1，直到数目变成0为止再进行类似上面的“剪枝”操作。

不过首先本题的输入就是个问题。需要知道题目中的每个“元素”实际上就是26个字母之一。这样就可以用<string>，先将输入存入一个字符串，再对其进行处理：

1
2
3
4
5
6
7
8
9
10
void input()
{
    cin >> n;
    cin >> tmp;
    for (int i = 0; i < n; i++)
    {
        num[tmp[i] - 96]++;     //记录用过的次数 先-96会好理解一些
    }
}

经过了上面两个题，本题的深搜代码本身不难改，下面是dfs_3()的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dfs_3(int k)
{
    if (k == n)
    {
        print();
        return;
    }
    for (int i = 1; i <= 26; i++)   //每次对26个字母进行遍历
    {
        if (num[i])                 //如果这个元素还有
        {
            num[i]--;
            res[k] = i;
            dfs_3(k + 1);
            num[i]++;
        }
    }
}

然而，本题的输出并不是很直接，我用了显式类型转换：

1
2
3
4
5
6
7
8
9
10
void print()
{
    for (int i = 0; i < n; i++)
    {
        char tmpchar = static_cast<char>(res[i] + 96); //显式类型转换 记得把96加回去
        cout << tmpchar;
    }
    cout << endl;
    sum++;                          //排列总数，在其他地方迭代也可
}

发表于 更新于 分类于

Git

Git用#注释

初次使用

1
2
3
git config --global user.name  [名字]
git config --global user.email [邮箱]
ssh-keygen -t rsa #生成ssh公钥，用RSA加密

之后把ssh公钥放到GitHub之类的代码管理网站上

  • ssh公钥生成在c:\users\[用户名]\.ssh\

库

1
2
git init 把当前目录初始化成库
git clone [url] 从URL克隆库

常用操作

提交

1
2
3
git add . #把所有改动的文件放入暂存区
git commit -m [信息] #提交暂存区文件到库
git push #提交本地库到远程库

其他

1
git status #查看库状态：有哪些改动文件，暂存区是否已提交等

.gitignore

设置提交时忽略哪些文件

  1. 以斜杠/开头表示目录；
    以星号*通配多个字符；
    以问号?通配单个字符
    以方括号[]包含单个字符的匹配列表；
    以叹号!表示不忽略(跟踪)匹配到的文件或目录；

a.
规则：fd1/*
说明：忽略目录 fd1 下的全部内容；注意，不管是根目录下的 /fd1/ 目录，还是某个子目录 /child/fd1/ 目录，都会被忽略；
b.
规则：/fd1/*
说明：忽略根目录下的 /fd1/ 目录的全部内容；
c.
规则：
/*
!.gitignore
!/fw/bin/
!/fw/sf/
说明：忽略全部内容，但是不忽略 .gitignore 文件、根目录下的 /fw/bin/ 和 /fw/sf/ 目录；

  1. .txt #忽略所有 .txt结尾的文件,这样的话上传就不会被选中！
    !lib.txt #不忽略lib.txt
    build/ #忽略build/目录下的所有文件
    doc/    .txt #会忽略 doc/notes.txt 但不包括 doc/server/arch.txt

TIPS

git bash 里不能 ctrl+c ctrl+v 要右键复制粘贴

相关链接

狂神说的视频教程

码云 Git大全

GitHub上的一个.gitignore集合