1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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);
}

 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

#include <iostream>

using namespace std;

const int N = 1000010;

int q[N];

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);
}

int main()
{
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    quick_sort(q, 0, n - 1);

    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);

    return 0;
}

 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

bool check(int x)
{
	// 坚持元素x是否满足条件
}

// 模板1：求满足条件的第一次出现的元素下标
int bsearch_1(int* a, int l, int r)
{
	while (l < r)
	{
		int mid = l + r >> 1;
		if (check(a[mid]))
        	r = mid;
		else l = mid + 1;
	}
	return l;
}

// 模板2：求满足条件的最后一次出现的元素下标
int bsearch_2(int* a, int l, int r)
{
	while (l < r)
	{
		int mid = l + r + 1 >> 1;     // 这里要+1是因为l=mid，如何l+r>>1可能还是l，会死循环
		if (check(a[mid]))
			l = mid;
		else r = mid - 1;
	}
    return l;
}

 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

#include<iostream>

using namespace std;

const int N = 1e5 + 10;
int a[N];

void binarySearch(int* a, int n, int k) {
    int l = 0, r = n - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (a[mid] >= k) r = mid;
        else l = mid + 1;
    }
    if (a[l] != k) 
    {
        cout << -1 << " " << -1 << endl;
        return;
    } 
    else 
    {
        cout << l << " ";
        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (a[mid] <= k) l = mid;
            else r = mid - 1;
        }
        cout << l << endl;
    }
}

int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < q; i++)
    {
        int x;
        cin >> x;
        binarySearch(a, n, x);
    }
    
}

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

string addStrings(string num1, string num2) {
    int i = num1.size() - 1, j = num2.size() - 1;
    string res;
    int add = 0;
    while (i >= 0 || j >= 0 || add)
    {
        int x = i >= 0 ? num1[i] - '0' : 0;
        int y = j >= 0 ? num2[j] - '0' : 0;
        res += '0' + (x + y + add) % 10;
        add = (x + y + add) / 10;
        i --, j --;
    }
    reverse(res.begin(), res.end());
    return res;
}

 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

string multiply(string num1, string num2) {
    vector<int> a, b;
    int n = num1.size(), m = num2.size();
    for (int i = n - 1; i >= 0; i --) a.push_back(num1[i] - '0');
    for (int i = m - 1; i >= 0; i --) b.push_back(num2[i] - '0');
    vector<int> c(n + m, 0);
    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < m; j ++)
        {
            c[i + j] += a[i] * b[j];
        }
    }
    
    int add = 0;
    string ans;
    for (int i = 0; i < m + n || add; i ++)
    {
        int x = c[i] + add;
        add = x / 10;
        ans += '0' + x % 10;
    }
    
    reverse(ans.begin(), ans.end());
    int idx = 0;
    while (ans[idx] == '0' && idx < ans.size() - 1) idx ++;
    ans = ans.substr(idx, ans.size() - idx);
    return ans;
}

 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

#include <iostream>

using namespace std;

int n;

void dfs(int u, int state)
{
    if (u == n) 
    {
        for (int k = 0; k < n; k ++)
            if (state >> k & 1) 
                cout << k + 1 << " ";
        cout << endl;
        return;
    }
    dfs(u + 1, state);           // 不用第u个数
    dfs(u + 1, state | (1 << u));  // 用第u个数，就把第u个位置置成1
}

int main()
{
    cin >> n;
    dfs(0, 0);
    return 0;
}

 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

#include <iostream>

using namespace std;

int n, m;

void dfs(int u, int cnt, int state)
{   
    if (cnt + n - u < m) return;     // 提前可行性剪枝：如果后续全选都不够m个，就可以提前退出了
    if (cnt == m) 
    {
        for (int k = 0; k < n; k ++)
            if (state >> k & 1) 
                cout << k + 1 << " ";
        cout << endl;
        return;
    }
    // 这里按照字典序来排，所以得换个顺序
    dfs(u + 1, cnt + 1, state | (1 << u));  // 用第u个数，就把第u个位置置成1
    dfs(u + 1, cnt, state);                 // 不用第u个数
}

int main()
{
    cin >> n >> m;
    dfs(0, 0, 0);
    return 0;
}

 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

#include <iostream>
#include <stack>

using namespace std;

int n, m;

struct State
{
    int pos, u, cnt, state;     // pos：已经运行到的状态区域; u,cnt,state：递归参数

};

// void dfs(int u, int cnt, int state)
// {   
//     // 状态0区域：
//     if (cnt + n - u < m) return;
//     if (cnt == m) 
//     {
//         for (int k = 0; k < n; k ++)
//             if (state >> k & 1) 
//                 cout << k + 1 << " ";
//         cout << endl;
//         return;
//     }
//     // 状态1区域：
//     dfs(u + 1, cnt + 1, state | (1 << u));
//     // 状态2区域：
//     dfs(u + 1, cnt, state);
// }

int main()
{
    cin >> n >> m;
    
    stack<State> stk;                   // 模拟递归栈
    stk.push({0, 0, 0, 0}); 

    while (stk.size())
    {
        auto cur = stk.top();
        stk.pop();
        switch (cur.pos)
        {
            case 0:                     // 如果对应区域0状态
                // 把递归dfs里面区域1的代码翻译过来就可以了：return翻译成continue，变量改一下,递归调用变成进栈操作
                if (cur.cnt + n - cur.u < m) continue;     
                if (cur.cnt == m) 
                {
                    for (int k = 0; k < n; k ++)
                        if (cur.state >> k & 1) 
                            cout << k + 1 << " ";
                    cout << endl;
                    continue;
                }  
                stk.push({1, cur.u, cur.cnt, cur.state});      // 当前状态进栈    
                stk.push({0, cur.u + 1, cur.cnt + 1, cur.state | (1 << cur.u)}); // dfs(u+1, cnt+1, state | (1 << u));

                continue;
            case 1:                     // 如果对应区域1状态
                stk.push({2, cur.u, cur.cnt, cur.state});      // 当前状态进栈           
                stk.push({0, cur.u + 1, cur.cnt, cur.state});                    // dfs(u+1, cnt, state);

                continue;
            case 2:                     // 如果对应区域2状态
                continue;
        }
    }

    return 0;
}

 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

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> ans;

void dfs(int state)
{
    if (ans.size() == n) 
    {
        for (auto i : ans)
            cout << i << " ";
        cout << endl;
        return;
    }
    for (int u = 0; u < n; u ++)
    {
        if (!(state >> u & 1))
        {
            ans.push_back(u + 1);
            dfs(state | (1 << u));  // 用第u个数，就把第u个位置置成1
            ans.pop_back();         // 恢复现场
        }
    }
}

int main()
{
    cin >> n;
    dfs(0);
    return 0;
}

 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

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int s[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {   
        int a;
        cin >> a;
        s[i] = s[i - 1] + a;
    }
    while (m--)
    {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}

 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

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N], b[N], s[N];

int main()
{
    cin >> n >> m;
    for (int i = 1;i <= n; i++)
    {
       cin >> a[i];
       b[i] = a[i] - a[i - 1];
    }
    while (m--)
    {
        int l, r, c;
        cin >> l >> r >> c;
        b[l] += c;
        b[r + 1] -= c;
    }

    for (int i = 1; i <= n; i++)
    {
        s[i] = s[i - 1] + b[i];
        cout << s[i] << " ";
    }
    return 0;
}

 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

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int a, b[N];

void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

int main()
{
    cin >> n >> m;
    for (int i = 1;i <= n; i++)
    {
       cin >> a;
       insert(i, i, a);               // 点金之笔，代码复用
    }
    while (m--)
    {
        int l, r, c;
        cin >> l >> r >> c;
        insert(l, r, c);
    }

    for (int i = 1; i <= n; i++)
    {
        b[i] += b[i - 1];             // 直接偷懒不再用s数组来存前缀和了
        cout << b[i] << " ";
    }
    return 0;
}

 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

#include <iostream>

using namespace std;

const int N = 100010;

int n, m, x;
int a[N], b[N];

int main()
{
    cin >> n >> m >> x;
    for (int i = 0; i < n; i ++) cin >> a[i];
    for (int i = 0; i < m; i ++) cin >> b[i];
    
    for (int i = 0, j = m - 1; ; )
    {
        if (a[i] + b[j] > x) j --;
        else if (a[i] + b[j] < x) i ++;
        else 
        {
            cout << i << ' ' << j << endl;
            return 0;
        }
    }
}

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

//外层循环扩展右边界，内层循环扩展左边界
for (int l = 0, r = 0 ; r < n ; r ++) 
{
	// 1. 先更新右指针

    // 2. 窗口大小不足 k 跳过
    if (r < k - 1) continue;
    
    // 3. 区间[left,right]符合题意，统计相关信息
    
    // 4. 调整左窗口
	
    // 5. 拓展左边界

}

 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

class Solution {
public:
    bool check(char c)
    {
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
            return true;
        return false;
    }
    int maxVowels(string s, int k) {
        int n = s.size();
        int mx = 0;
        int cnt = 0;
        for (int l = 0, r = 0; r < n; r ++)
        {
            // 右端点进入窗口
            if (check(s[r])) cnt ++;
            
            // 窗口大小不足 k 跳过
            if (r < k - 1) continue;
            
            // 更新答案
            mx = max(mx, cnt);
            
            // 左端点离开窗口
            if (check(s[l])) cnt --;
            l ++;
        }
        return mx;
    }
};

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

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> hash_c;
        int ans = 0;
        
        for (int l = 0, r = 0; r < s.size(); r ++)
        {
            hash_c[s[r]] ++;              // 先更新右指针
            while (hash_c[s[r]] > 1)      // 调整左指针
                hash_c[s[l]] --, l ++;
            ans = max(ans, r - l + 1);    // 区间符合题意，统计相关信息
        }
        return ans;
    }
};

 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

#include <iostream>

using namespace std;

const int N = 100000;

int lowbit(int x)  // 返回最低位1及其后面所有的0构成的子串
{
    return x & -x;
}

int main()
{
    int n;
    cin >> n;
    while (n --)
    {   
        int x;
        cin >> x;
        int cnt = 0;
        while (x)
            cnt ++, x -= lowbit(x);
        cout << cnt << " ";
    }
    return 0;
}

 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 <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010, INF = 0x3f3f3f3f;

PII a[N];
int ans;
    
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> a[i].first >> a[i].second;
    sort(a, a + n);

    int l = -INF, r = -INF;
    
    for (int i = 0; i < n; i ++) 
    {
        if (a[i].first > r) 
        {
            ans ++;
            l = a[i].first;
            r = a[i].second;
        }
        else r = max(r, a[i].second);
    }
    cout << ans << endl;
    return 0;
}

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

#include <iostream>

using namespace std;

int dp[3];
int n;

int main()
{
    cin >> n;
    dp[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        dp[i % 3] = dp[(i - 1) % 3] + dp[(i - 2) % 3];
    }
    
    cout << dp[n % 3] << endl;
    return 0;
}

 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

#include <iostream>

using namespace std;

const int N = 100010;

int m;
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;              // 下标-1表示为空
    idx = 0;
}

// 头插法插入
void add_to_head(int x)
{
    e[idx] = x, ne[idx] = head, head = idx ++;
}

// 在下标为 k 的数后面插入一个数 x

void add(int k, int x)
{   
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++;
}
// 在下标为 k 的数后面删掉一个数
void remove(int k)
{
   ne[k] = ne[ne[k]]; 
}

int main()
{
    cin >> m;
    init();
    while (m-- )
    {
        char op;
        cin >> op;
        if (op == 'H')
        {
            int x;
            cin >> x;
            add_to_head(x);
        }
        else if (op == 'D')
        {
            int k;
            cin >> k;
            if (!k) head = ne[head];
            remove(k - 1);
        }
        else
        {
            int k, x;
            cin >> k >> x;
            add(k - 1, x);
        }

    }
    
    for (int i = head; i != -1; i = ne[i]) cout << e[i] << " ";           // 标准的遍历方式
    return 0;
}

 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

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>

using namespace std;

const int N = 100010;

int a[N], s[N];

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> a[i];
    
	vector<int> left(n, -1);
    stack<int> stk;
    for (int i = 0; i < n; i ++)
    {
        while (!stk.empty() && a[i] <= a[stk.top()]) stk.pop();   // 因为需要维护一个严格单调递增的栈
        if (!stk.empty()) left[i] = stk.top();                    // 如果栈没空说明有
        stk.push(i);
    }
    for (int i = 0; i < n; i ++) 
    {
        if (left[i] == -1) cout << -1 << ' ';
        else cout << a[left[i]] << ' ';
    }
    return 0;
}