浅谈c++的深拷贝与浅拷贝

浅谈 c++的深拷贝与浅拷贝

初次见面

正如字面意思，深与浅无非是拷贝力度的大小。那么怎么理解深和浅呢？

深：将拷贝对象的所有属性复制一遍

浅：仅拷贝对象的地址

那么为什么要有浅拷贝与深拷贝呢？

总的目的来说，浅拷贝是为了提高速率，让程序员可以直接操纵对象地址，不用再花时间与内存去复制一份新的出来。显而易见可以看出浅拷贝是很方便操作的。

既然浅拷贝很好 那么我不防聊一聊它的坏处

浅拷贝的坏处

程序在设计的初期，并不希望我们把所有的事情都考虑好，更希望程序在运行的过程中自行的去拓展。例如我们要存储一个学生的信息，难道我们一开始就要把学生的最高使用上限就考虑到么，肯定不是的。所以出现了 new 和 delete 。使用 new 创建的变量会放在计算机内存的一个特定部分，直到 delete 调用后这个变量才会删除。这是 new 和 delete 使用的背景。

例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#ifndef STRNGBAD_H__
#define STRNGBAD_H__
#include <iostream>
class StringBad
{
private:
    char *str;
    int len;
    static int num_strings;

public:
    StringBad();
    StringBad(const char *s);
    ~StringBad();
    friend std::ostream &operator<<(std::ostream &os, const StringBad &st);
};
#endif
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
#include <cstring>
#include "strngbad.h"
using std::cout;
int StringBad::num_strings = 0;

StringBad::StringBad(const char *s)
{
    len = std::strlen(s);
    str = new char[len + 1];
    std::strcpy(str, s);
    num_strings++;
    cout << num_strings << ": \"" << str
         << "\" default object created\n";
}
StringBad::StringBad()
{
    len = 4;
    str = new char[4];
    std::strcpy(str, "c++");
    num_strings++;
    cout << num_strings << ": \"" << str
         << "\" default object created\n";
}
StringBad::~StringBad()
{
    cout << "\"" << str << "\" object deleted, ";
    --num_strings;
    cout << num_strings << "left\n";
    delete[] str;
}
std::ostream &operator<<(std::ostream &os, const StringBad &st)
{
    os << st.str;
    return os;
}

main.cpp

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
#include "strngbad.h"
using std::cout;
using std::endl;

void callme1(StringBad &);
void callme2(StringBad);

int main()
{

    {
        cout << "Start" << endl;
        StringBad headline1("Celery Stalk at Midnight");
        StringBad headline2("Lecttuce Prey");
        StringBad sports("Spinach Leaves Bowl for Dollars");
        cout << "head1" << headline1 << endl;
        callme1(headline1);
        cout << "head2" << headline2 << endl;
        callme2(headline2);
        StringBad sailor = sports;
        cout << sailor << endl;
        StringBad knot;
        knot = headline1;
        cout << knot << endl;
        cout << "exit";
    }
    cout << "end main";
    return 0;
}
void callme1(StringBad &rsb)
{
    cout << "String pass by references:\n";
    cout << "rsb:" << rsb << endl;
}
void callme2(StringBad sb)
{
    cout << "String pass by references:\n";
    cout << "sb:" << sb << endl;
}

当我们编译之后发现程序并没有错误，可是当程序运行的时候，程序会报错，触发了 GPF 错误（GPF 表示程序试图访问禁止的内存单元）这是一种很坏的现象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Start
1: "Celery Stalk at Midnight" default object created
2: "Lecttuce Prey" default object created
3: "Spinach Leaves Bowl for Dollars" default object created
head1Celery Stalk at Midnight
String pass by references:
rsb:Celery Stalk at Midnight
head2Lecttuce Prey
String pass by references:
sb:Lecttuce Prey
"Lecttuce Prey" object deleted, 2left
Spinach Leaves Bowl for Dollars
3: "c++" default object created
Celery Stalk at Midnight
exit"Celery Stalk at Midnight" object deleted, 2left
"Spinach Leaves Bowl for Dollars" object deleted, 1left
"@Q�eC#" object deleted, 0left
a.out(14353,0x1048b4580) malloc: *** error for object 0x6000011c5140: pointer being freed was not allocated
a.out(14353,0x1048b4580) malloc: *** set a breakpoint in malloc_error_break to debug
zsh: abort      ./a.out

关于为什么会出现错误呢？

1.Private 里的 num_strings 错误

这种错误主要是程序调用 c++里的默认拷贝函数，复制了一份新的 StringBad 对象，而 Static 静态类型属于整个类并不属于某个对象，故临时产生的 StringBad 对象也会调用析构函数从而导致 num_strings –

2.@Q�eC# 文字乱码

1
2
3
4
5
StringBad sports;
sports = headline1;
等同于：
  sports.str = headline1.str;
sports.len = headline1.len;

我们可以发现其中 sports.str 只是指向了 headline1.str 的地址，但是由于 headlline1 在销毁的时候会调用 delete 将 str 从内存中删除掉，从而 sports.str 没有地址可寻.

如何解决？

创建复制构造函数

1
2
3
4
5
6
7
StringBad::StringBad(const StringBad & st){
  	num_strings ++;
   len = st.len;
  str = new char [len + 1];
      cout << num_strings << ": \"" << str
         << "\" object created\n";
}

展开全文 >>

决策树

1.划分数据集

1.1 基本概念

在度量数据集的无序程度的时候，分类算法除了需要测量信息熵，还需要划分数据集，度量花费数据集的熵，以便判断当前是否正确的划分了数据集。
我们将对每个特征数据集划分的结果计算一次信息熵，然后判断按照那个特征划分数据集是最好的划分方式。
也就是说，我们依次选取我们数据集当中的所有特征作为我们划定的特征，然后计算选取该特征时的信息增益，当信息增益最大时我们就选取对应信息增益最大的特征作为我们分类的最佳特征。

下面是我们的数据集：

我们用 python 语言表示出这个数据集
dataSet= [[1, 1, ‘yes’], [1, 1, ‘yes’], [1, 0, ‘no’], [0, 1, ‘no’], [0, 1, ‘no’]]
在这个数据集当中有两个特征，就是每个样本的第一列和第二列，最后一列是它们所属的分类。

我们划分数据集是为了计算根据那个特征我们可以得到最大的信息增益，那么根据这个特征来划分数据就是最好的分类方法。

因此我们需要遍历每一个特征，然后计算按照这种划分方式得出的信息增益。信息增益是指数据集在划分数据前后信息的变化量。

1.2 具体操作

划分数据集的方式我们首先选取第一个特征的第一个可能取值来筛选信息。然后再选取第一个特征的第二个可能的取值来划分我们的信息。之后我们再选取第二个特征的第一个可能的取值来划分数据集，以此类推。

e.g:
[[1, 1, ‘yes’], [1, 1, ‘yes’], [1, 0, ‘no’], [0, 1, ‘no’], [0, 1, ‘no’]]
这个是我们的数据集。
如果我们选取第一个特征值也就是需不需要浮到水面上才能生存来划分我们的数据，这里生物有两种可能，1 就是需要，0 就是不需要。那么第一个特征的取值就是两种。

如果我们按照第一个特征的第一个可能的取值来划分数据也就是当所有的样本的第一列取 1 的时候满足的样本，那就是如下三个：
[1, 1, ‘yes’], [1, 1, ‘yes’], [1, 0, ‘no’]
可以理解为这个特征为一条分界线，我们选取完这个特征之后这个特征就要从我们数据集中剔除，因为要把他理解为分界线。那么划分好的数据就是：

[[1, ‘yes’], [1, ‘yes’], [0, ‘no’]]
如果我们以第一个特征的第二个取值来划分数据集，也就是当所有样本的第二列取 1 的时候满足的样本，那么就是

[[1, 1, ‘yes’], [1, 1, ‘yes’], [0, 1, ‘no’], [0, 1, ‘no’]]
那么得到的数据子集就是下面这个样子：
[[1,’yes’],[1,’yes’],[1, ‘no’], [1, ‘no’]]
因此我们可以很容易的来构建出我们的代码：

下面我们来分析一下这段代码，

代码功能：划分数据集

1
2
3
4
5
6
7
8
9
10
11
def splitDataSet(dataSet,axis,value): #传入三个参数第一个参数是我们的数据集，是一个链表形式的数据集；第二个参数是我们的要依据某个特征来划分数据集
retDataSet = [] #由于参数的链表 dataSet 我们拿到的是它的地址，也就是引用，直接在链表上操作会改变它的数值，所以我们新建一格链表来做操作
for featVec in dataSet:
    if featVec[axis] == value: #如果某个特征和我们指定的特征值相等
    #除去这个特征然后创建一个子特征
        reduceFeatVec = featVec[:axis]
        reduceFeatVec.extend(featVec[axis+1:])
        #将满足条件的样本并且经过切割后的样本都加入到我们新建立的样本中
        retDataSet.append(reduceFeatVec)

return retDataSet

1
2
3
4
5
6
7
8
9
10
11
12
13
总的来说，这段代码的功能就是按照某个特征的取值来划分数据集。

为方便您测试实验我们在贴出这段代码：

1
2
3
4
5
6
7
8
9
10
11
def splitDataSet(dataSet,axis,value):
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reduceFeatVec = featVec[:axis]
            reduceFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reduceFeatVec)

return retDataSet
#在这里我们可以注意到一个关于链表的操作：
#那就是extend 和append

完整代码

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
import numpy as np
import pandas as pd
from math import *

#构建数据集
def createDataset():
    dataSet = [[1, 1, 'yes'],
            [1, 1, 'yes'],
            [1, 0, 'no'],
            [0, 1, 'no'],
            [0, 1, 'no']]
    labels = ['no surfacing', 'flippers','is fish']
    w1 = pd.DataFrame(dataSet,columns = labels)
    display(w1)
    return dataSet, labels
createDataset()

def calcShannoEnt(dataset):
    allnums = len(dataset)
    labels = {}
    for data in dataset:
        datalabel = data[-1]
        #初始化所有标签
        if datalabel not in labels:
            labels[datalabel] = 0
        labels[datalabel] += 1
    hx = 0.0
    for key in labels:
        #计算每种决策的概率
        px = float(labels[key]/allnums)
        hx -= px * log(px,2)
    print("hx:",hx);
    #计算墒
    return hx
calcShannoEnt(createDataset()[0])

def splitDataSet(dataSet, index, value):
    retDataSet = []
    for featVec in dataSet:
        # index列为value的数据集【该数据集需要排除index列】
        # 判断index列的值是否为value
        if featVec[index] == value:
            #
            reducedFeatVec = featVec[:index]
            reducedFeatVec.extend(featVec[index+1:])
            # [index+1:]表示从跳过 index 的 index+1行，取接下来的数据
            # 收集结果值 index列为value的行【该行需要排除index列】
            retDataSet.append(reducedFeatVec)
    #print(retDataSet)
    return retDataSet
splitDataSet(createDataset()[0],1,1)

def chooseBestFeatureToSplit(dataSet):
    #需要进行多少次判断特征值
    nums = len(dataSet[0]) - 1
    baseEnt = calcShannoEnt(dataSet)
    bestInfoGain, bestFeature = 0.0, -1
    for i in range(nums):
        #找出第一个特征值可能取得的值
        featList = [example[i] for example in dataSet]
        print("featList:",featList)
        #将取得的值离散化 取出唯一值
        uniqueList = set(featList)
        print("uniqueList",uniqueList)
        newE = 0.0
        for j in uniqueList:
            #取出划分出来的子集
            subDataset = splitDataSet(dataSet,i,j)
            print("subDataset:",subDataset)
            # 计算概率
            prob = len(subDataset)/float(len(dataSet))
            # 计算数学期望
            newE += prob * calcShannoEnt(subDataset)
        #计算出信息增益
        infoGain = baseEnt - newE
        print(f"信息增益:{infoGain},特征值:{i}")
        if infoGain > bestInfoGain:
            bestFeature = i
            bestInfoGain = infoGain
        #返回最优特征值
        return bestFeature
chooseBestFeatureToSplit(createDataset()[0])

def createTree(dataSet,labels):
    classList = [x[-1] for x in dataSet]
    #如果所有的标签都相同 就返回一个
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    #如果只有一列 则表明只有一类
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)
    bestFeatLabel = labels[bestFeat]
    #创建决策树
    myTree = {bestFeatLabel:{}}
    #删除同名变量
    del(labels[bestFeat])
    #选择最优列 作为分类依据
    featValues = [x[bestFeat] for x in dataSet]
    uniqueVals = set(featValues)
    for i in uniqueVals:
        #拷贝一个标签labels副本
        subLabels = labels[:]
        myTree[bestFeatLabel][i] = createTree(splitDataSet(dataSet,bestFeat,i),subLabels)
    return myTree
a,b = createDataset()
createTree(a,b)


def test(moudelTree,featLabels,testVec):
    index = featLabels.index(list(moudelTree.keys())[0])
    key = featLabels[index]
    val = testVec[index]
    print(f"key:{key},val:{val}")
    newTree = moudelTree[key][val]
    print(newTree)
    if isinstance(newTree,dict):
        test(newTree,featLabels,testVec)
    else:
        return val



a,b = createDataset()
test(createTree(a,b),['no surfacing', 'flippers'],(1,1))

展开全文 >>

k-NearestNeighbor

KNN 近邻算法的初次实现和做法

KNN 概述

k-近邻（kNN, k-NearestNeighbor）算法是一种基本分类与回归方法，我们这里只讨论分类问题中的 k-近邻算法。

一句话总结: 近朱者赤近墨者黑！

k 近邻算法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。 k 值的选择、距离度量以及分类决策规则是 k 近邻算法的三个基本要素。

KNN 场景

电影可以按照题材分类，那么如何区分 动作片 和 爱情片 呢？

  1. 动作片: 打斗次数更多
  2. 爱情片: 亲吻次数更多

基于电影中的亲吻、打斗出现的次数，使用 k-近邻算法构造程序，就可以自动划分电影的题材类型。

KNN 原理

KNN 工作原理
  1. 假设有一个带有标签的样本数据集（训练样本集），其中包含每条数据与所属分类的对应关系。
  2. 输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较。
    1. 计算新数据与样本数据集中每条数据的距离。
    2. 对求得的所有距离进行排序（从小到大，越小表示越相似）。
    3. 取前 k （k 一般小于等于 20 ）个样本数据对应的分类标签。
  3. 求 k 个数据中出现次数最多的分类标签作为新数据的分类。
KNN 通俗理解

给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的 k 个实例，这 k 个实例的多数属于某个类，就把该输入实例分为这个类。

KNN 算法的特点
1
2
3
优点: 精度高、对异常值不敏感、无数据输入假定
缺点: 计算复杂度高、空间复杂度高
适用数据范围: 数值型和标称型
more >>

展开全文 >>

归一化

什么是归一化？

以实际例子来说，在国家贸易中，各个国家的货币价值不一样，当 A 国想买 10 吨煤的时候，我们一般是先将钱转化为美元，再用美元去买 10 吨煤，这样中间就有了一个标准

归一化有什么用？

归一化在处理数学问题和权重问题的时候具有实用的意义，比如说大学生自习室安排问题中，宿舍距各教室路线长短，教室大小，照明质量，满座率等都是影响结果的因素，这些因素本身有一个相对值，但没有一个统一的标准去衡量他们，于是出现了归一化。使每个大因素和小变量之间都有了一个桥梁，合理的去参与到对决策的影响中。

展开全文 >>

排序算法

三种排序[选择，归并，冒泡]

选择排序

优点：处理小数据的时候很快，时间复杂度(O^2)

选择排序就跟扑克牌一样，从牌堆里面选择一张牌插入到牌中，依次选择手中的牌，把相对较小的插入到其中

1
2
3
4
5
6
7
8
9
10
11
void insertionSort(int arr[]){
    for(int i = 0 ; i < 6 ; i ++){
        int key = arr[i];
        int j = i - 1;
        while(j >= 0 && arr[j] > key){
            arr[j + 1] = arr[j];
            j --;
        }
        arr[j + 1] = key;
    }
}

快速排序

时间复杂度为 O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

归并排序

**时间复杂度 O(n log n) **

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void mergeSort(int arr[], int l, int r)
{
    if (l >= r)
        return;
    int mid = (l + r) / 2;
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    int tmp[r - l + 1];
    while (i <= mid && j <= r)
    {
        if (arr[i] < arr[j])
            tmp[k++] = arr[i++];
        else
            tmp[k++] = arr[j++];
    }
    while (i <= mid)
        tmp[k++] = arr[i++];
    while (j <= r)
        tmp[k++] = arr[j++];

    for (i = l, j = 0; i <= r; i++, j++)
        arr[i] = tmp[j];
}

快速排序和快速排序都是分治思想

展开全文 >>

哈希表

近似 O(1)的时间复杂度

哈希表一般算法中处理的问题

  1. 插入一个数
  2. 查找一个数
  3. 删除一个数

实现哈希表的两种做法

拉链法

首先选择拉链法来解决问题，拉链法用通俗的话来说，就是数组+单链表的实现
选择 hash 函数 将大整数 x 映射成为小整数的

840. 模拟散列表

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
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100002;

int e[N],ne[N],idx;
int h[N];

void insert(int x){
    int y = (x % N + N) % N; //为了缩小y 同时也避免负数的存在
    e[idx] = x; //在每一个数组下面拉出一条链 insert等同于单链表的操作
    ne[idx] = h[y];
    h[y] = idx++;
}

bool find(int x){
    int y = (x % N + N ) % N;
    for(int i = h[y] ; i != -1 ; i = ne[i])
        if(e[i] == x)
            return true;
    return false;
}

int main(){
    int n;
    cin >> n;
    memset(h,-1,sizeof h);
    while(n --){
        char op;
        int k;
        cin >> op >> k;
        if(op == 'I')insert(k);
        else{
            if(find(k))puts("Yes");
            else puts("No");
        }
    }
    return 0;
}
more >>

展开全文 >>

堆排序

堆分为小根堆和大根堆（本质上是一颗完全二叉树）

堆可以干什么？

  • 找到一个集合当中的最小值
  • 删除一个集合当中的最小值
  • 插入一个数

如何调整小根堆或者大根堆？

以小根堆为例子

  • down -> 选择这个数和子节点的最小值进行交换
  • up -> 选择这个节点与父节点进行交换

如何存储堆？

下标从 1 开始 保证了数组子节点的可行性

选择用数组的形式来存储 1 2 3 4 5 6 7 8
k 的 子节点为 2k 2k+1

如何手写一个堆

  1. 插入一个数：heap[++size] = x;
  2. 求集合当中的最小元素：heap[1];
  3. 删除最小的元素：heap[1] = heap[size]; size ++; down(1) //将末尾的元素覆盖到头节点，数组删除头节点是很麻烦的一件事
  4. 删除任意一个元素：heap[k] = heap[size]; size ++; down(k); up(k)；
  5. 修改任意一个元素：heap[k] = x;up(x);down(x); 保证 down 和 up 只执行一次 more >>

展开全文 >>

并查集

近似 O(1)的时间复杂度

并查集能解决什么问题？

  • 如何合并两个集合
  • 如何两个元素在不在同一个区间内

并查集原理？

用一棵树来存储整个集合，树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x]代表它的父节点

衍生出问题

  1. 如何判断树根？if(p[x] == x)
  2. 如何求 x 的编号？while(p[x] != x) x = p[x]
  3. 如何合并两个集合，x 代表第一个集合，y 代表第二个集合？p[x] = y

如何优化？

每遍历一次，让这个节点直接指向根节点，即可将时间复杂度优化为 O(1);

模版应用

836. 合并集合

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
import java.util.*;
import java.io.*;
public class Main{
    private static int p[] = new int[100010]; //声明父节点;
    public static void main(String [] args) throws IOException {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = in.nextInt();
        for(int i = 1 ; i <= n ; i ++)p[i] = i;
        int m = in.nextInt();
        while(m -- != 0){
            String op = in.next();
            if(op.equals("M")){
                int a = in.nextInt();
                int b = in.nextInt();
                p[find(a)] = find(b);
            }else{
                int a = in.nextInt();
                int b = in.nextInt();
                if(find(a) == find(b))log.write("Yes\n");
                else log.write("No\n");
            }
        }
        log.flush();
        log.close();
    }
    //查找x节点的父亲
    public static int find(int x){
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
}

837. 连通块中点的数量

同时维护当前区间内，有多少个数量

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
import java.util.*;
import java.io.*;
public class Main{
    public static int p[] = new int[100010];
    public static int size[] = new int[100010];

    public static void main(String[] args) throws IOException
    {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = in.nextInt();
        int m = in.nextInt();
        for(int i = 1 ; i <= n ; i ++){
            p[i] = i;
            size[i] = 1;
        }
        while(m -- != 0){
            String op = in.next();
            if(op.equals("C")){

                int a = in.nextInt();
                int b = in.nextInt();
                if(find(a) == find(b)) continue;
                size[find(b)] += size[find(a)];
                p[find(a)] = b;
            }else if(op.equals("Q1")){
                int a = in.nextInt();
                int b = in.nextInt();
                if(find(a) == find(b))log.write("Yes\n");
                else log.write("No\n");
            }else{
                int k = in.nextInt();
                log.write(size[find(k)] + "\n");
            }
        }
        log.flush();
        log.close();

    }
    public static int find(int x){
        if(p[x] != x)p[x] = find(p[x]);
        return p[x];
    }
}

240. 食物链

维护当前集合里面到根节点的距离

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
68
69
70
71
72
73
74
import java.io.*;
import java.util.*;
public class Main{
    public static int[] p,d; //p存储父节点 d存储距离
    public static void main(String[] args) throws IOException{
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = in.nextInt();
        int m = in.nextInt();
        p = new int[n + 1];
        d = new int[n + 1];
        int ans = 0 ; //表示假话的个数
        for(int i = 1 ; i <= n ; i ++)p[i] = i;
        while(m -- != 0){
            int op = in.nextInt();
            int x = in.nextInt();
            int y = in.nextInt();
            if(x > n || y > n){
                ans += 1;
                continue;
            }
            int px = find(x);
            int py = find(y);
            switch (op) {
                case 1 : {
                    //同一个集合中，表示已确立相互关系
                    if (px == py) {
                        if ((d[x] - d[y])%3 != 0) {
                            ans++;
                            continue;
                        }
                    }
                    //不同集合中，现在建立相互关系
                    else {
                        d[px] = d[y] - d[x];
                        p[px] = py;
                    }
                    break;
                }
                case 2 : {
                    //同一个集合中，表示已确立相互关系
                    if (px == py) {
                        //推导出的关系为 （d[x]-d[y]）%3 == 1 则认为x可以吃y
                        //写成（d[x]-d[y]-1）%3 == 0 可以避免余数是负数的问题
                        //也可以写成（d[x]-d[y]）%3 +3 == 1
                        //==正确 -> != 错误
                        if ((d[x] - d[y] - 1) % 3 != 0) {
                            ans++;
                            continue;
                        }
                    }
                    //不同集合中，现在建立相互关系
                    else {
                        d[px] = d[y] - d[x] + 1;
                        p[px] = py;
                    }
                    break;
                }
                default : System.out.print("--");
            }
        }
        log.write(ans + " ");
        log.flush();
        log.close();
    }
    public static int find(int x){
        if(x != p[x]){
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }
}

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

希望你能喜欢