1

题面

给定数组有N+M个数字, 数字的范围为1…N, 打印重复的元素, 要求算法的时 间渐进复杂度为O(M+N)，算法的额外空间复杂度为O(1)。 输入格式：两行，第一行为N、M两个整数（int）；第二行为M+N个整数。各整数 之间均用空格间隔。 输出格式：一行，若干个整数，可重复输出，顺序无所谓， 各 整数之间均用空格间隔。

输入：

5 3

1 5 4 5 3 2 5 4

输出

5 5 4

Code

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

using namespace std;

const int N = 1e5 + 10;
int a[N];
int n, m, s;

void solve1(){
    cin >> n >> m;
    memset(a, 0xff, sizeof(a));
    for(int i = 1, t = n + m; i <= t; i++){
        cin >> s;
        if(a[s] != s){
            a[s] = s;
        }else{
            cout << s << " ";
        }
    }
}

int main(){
    solve1();
    return 0;
}

2

题面

=LeetCode 接雨水

Code

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

using namespace std;

const int N = 10010;
int a[N];
int n;

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int res = 0, l = 1, r = n;
    while(l < r){
        int minn = min(a[l], a[r]);
        if(a[l] == minn){
            l++;
            while(l < r && a[l] < minn){
                res += minn - a[l];
                l++; 
            }
        }else{
            r--;
            while(l < r && a[r] < minn){
                res += minn - a[r];
                r--;
            }
        }
    }
    cout << res << endl;
    return 0;
}

3

题面

给定一个正整数 N（1 ≤ N ≤ $2^{59}$）,求出1…N 这N个数的二进制表示中总共的1的个数。

输入: (1-10)二进制串为 11011100101110111100010011010 有17个1.

10

输出:

17

数位dp = 找规律

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
long long n;

int main(){
    cin >> n;
    //1ll << 59 -> 17005592192950992897
    //1ll << 30 -> 16106127361
    //n = (1ll << 59);
    ll k = 1; // 2 ^ k
    ull res = 0;
    for(; n >= k; ){
        ll tn = n - (k - 1);
        res += (tn / (k * 2)) * k + min(tn % (k * 2), k);
        k *= 2;
        //cout << res << endl;
    }
    cout << res << endl;
    return 0;
}

4

题面

给定非负整数N、M，求出N的M次幂的准确结果。

输入格式：一行，包含两个32位整数（int）N和M。各整数之间均用空格间隔。

输出格式：一行，输出N的M次幂结果即可。

输入:

2 65

输出:

36893488147419103232

快速幂 + 高精度

Code1

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

using namespace std;

int n, m;

vector<int> add(vector<int> a, vector<int> b){
    vector<int> c;
    int alen = a.size(), blen = b.size();
    for(int i = 0, t = 0; i < alen || i < blen || t; i++){
        if(i < alen) t += a[i];
        if(i < blen) t += b[i];
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}

vector<int> mull(vector<int> a, int b, int off){
    vector<int> c;
    int len = a.size();
    for(int i = 0, t = 0; i < len || t; i++){
        if(i < len) t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while(off--){
        c.insert(c.begin(), 0);
    }
    return c;
}

vector<int> mul(vector<int> a, vector<int> b){
    vector<int> c;
    c.push_back(0);
    int len = b.size();
    for(int i = 0; i < len; i++){
        int k = b[i];
        c = add(c, mull(a, k, i));
    }
    return c;
}

int main(){
    cin >> n >> m;
    vector<int> res;
    res.push_back(1);
    vector<int> base;
    while(n){
        base.push_back(n % 10);
        n /= 10;
    }
    while(m){
        if(m & 1) res = mul(res, base);
        base = mul(base, base);
        m >>= 1;
    }	
    reverse(res.begin(), res.end());
    for(auto c: res) cout << c;
    return 0;
}

Code2

1