I have no surprise that one of your favorite musical artists is Charlie Puth, his songs is also very popular in China, and he has a nickname in Chinese, called “断眉(duan mei)”, which means that his eaybrow is broken(but it’s pretty cool for him). And i found that i have listened some of your sharing songs before:

Speaking

Part 1

I myself enjoy cinema, drama, poetry and travelling.

One of my friends like to read biography of great men to enhance himself.

She majored in International Economy at university.

Geometry is a piece of cake for me but a big headache for my friend Claire.

But hey, leaving work at five o’ clock means I eat dinner with my family.

不过，嘿，5点钟就下班，意味着我可以和家人一起吃晚饭啦。

Hereby I would like to present my point of view.

这里我将阐述一下自己的观点

here are several reasons to support my point of view.

对于我的观点有很多理由。

be drawn toward 向靠拢

I’m drawn toward the neutral view;

In short

EXERCISE 1:

In China, the tide of opinion is now running steadily against homosexuality, in my opinion, I’m drawn toward the neutral view, here are several reasons to support my point of view. The first is that someone is born to be a homosexual, regardless of where they live, the society and government should support every citizen, including them, to developing a harmony society. On the contrast, someone became a homosexual just because they indulge in carnal pleasure without restraint, It’s a well-established fact that carnalism is pretty bad, and most important is that homosexual can be more easily effected the AIDS than normal people. In short, It’s an opened question about morality which cannot be stantardized by anyone.

Flood Fill

• 优点：可以在线性时间内找到某个点所在的联通块；

池塘计数

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

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1002;

char M[N][N];
bool st[N][N];
typedef pair<int, int> PII;
PII q[N * N];
int n, m;

void bfs(int tx, int ty)
{
    int hh = 0, tt = 0;
    q[tt++] = {tx, ty};
    st[tx][ty] = true;
    while(hh <= tt)
    {
        auto t = q[hh++];
        int x = t.first, y = t.second;
        for(int i = -1; i <= 1; i++)
            for(int j = -1; j <= 1; j ++)
            {
                if(i == j && j == 0) continue;
                int a = x + i, b = y + j;
                if(a >= n || a < 0 || b >= m || b < 0) continue;
                if(M[a][b] == '.' || st[a][b]) continue;
                st[a][b] = true;
                q[tt++] = {a, b};
            }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i ++) scanf("%s", &M[i]);
    
    int res = 0;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            if(M[i][j] == 'W' && !st[i][j])
            {
                res++;
                bfs(i, j);
            }
    
    printf("%d\n", res);
    
    return 0;
}

手写堆

• 需要的操作：

  • 插入一个数：heap[++size] = x; up(size);

  • 求集合当中的最小值 ：heap[1]；

  • 删除最小值 ：heap[1] = heap[size]； size —; down(1)

  • 删除任意一个元素：heap[k] = heap[size]; size— ; down(k); up(k)；

  • 修改任意一个元素：heap[k] = x; down(k); up(k);

863. 国庆旅行

https://www.acwing.com/problem/content/865/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include<iostream>
using namespace std;
const int N = 100006;
int arr[N];
int main()
{
    int n; cin >> n;
    for(int i=1; i<= n; i++)
        cin >> arr[i];
    int Max = arr[1] + 1;
    int res = 0;
    for (int j = 2; j <= n; j++)
    {
        res = max(res, Max + arr[j] - j);
        Max = max(arr[j] + j, Max);
    }
    cout <<  res;
}

双指针

799. 最长连续不重复子序列

https://www.acwing.com/problem/content/801/

• 解析：双指针算法：$O(n)$；i一直往前；j往左最远能到什么地方；

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

#include <iostream>
using namespace std;
const int N = 100010;
int arr[N], q[N];

int main()
{
    int n; scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &arr[i]);
    
    
    int res = 0;
    for( int i = 0, j = 0; i < n; i++) 
    {
        q[arr[i]]++;
        while(q[arr[i]] > 1)
        {
            q[arr[j++]]--;
        }
        res = max(res, i - j + 1);
    }
    printf("%d", res);
    
    return 0;
}

最短路

• 单源最短路：分为：

  ​ 1、所有边权都是正数；n是点数，m是边数，两个算法：朴素Dijkstra算法$O(n^2)$、堆优化版Dijkstra算法$O(mlogn)$ 。

  ​ 2、存在负权边；两个算法：Bellman-Ford $O(nm)$、 SPFA 一般情况：$O(m)$、最坏$O(nm)$.

• 课上：理解主要思想；

• 课后：背过，针对题目进行模板默写；

• 熟练度练习：AC之后，删除然后重写，重复3~5次。

快速排序算法模板：

• 步骤：1.随便找一个x； 2.二分数组，使得左边的的小于x，右边的大于x。3. 递归。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

  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); } 作者：yxc 链接：https://www.acwing.com/blog/content/277/ 来源：AcWing 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

背包问题

DP问题：两个方面去考虑：

一、状态表示，如两维度$f(i,j)$；集合（$f$代表什么集合）、属性（最大值、最小值、数量）。

集合：1、所有选法；2、条件 ①只从前$i$个物品中选；②总体积不超过j。

二、状态计算；

一般是对集合的划分：把集合$f(i,j)$分解为子集，对于背包问题，划分为包含第i个物品的，与不包含第i个物品的。

高精度—-基础算法篇2

791. 高精度加法

题:https://www.acwing.com/problem/content/793/

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> add(vector<int> &a, vector<int> &b)
{
    int t = 0;
    vector<int> res;
    for(int i = 0; i < a.size() || i < b.size(); i++)
    {
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        res.push_back(t % 10);
        t /= 10;
    }
    if (t) res.push_back(t);
    reverse(res.begin(), res.end());
    return res;
}
int main()
{
    string a, b; cin >> a >> b;
    vector<int> avec, bvec;
    for (int i = a.size() -1; i >= 0; i--) avec.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i--) bvec.push_back(b[i] - '0');
    vector<int> res = add(avec, bvec);
    for(auto num : res) cout << num;
    
}