2023寒假集训摸底测试

7-1 统计各个数据个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
int cnt[100];
int main()
{
    int a;
    int res = 0;
    while(cin >> a)
    {
        res ++;
        cnt[a]++;
    }
    cout << res << endl;
    for(int i = 0; i <= 20; i++)
        cout << cnt[i] << " ";
    return 0;
}

7-2 分解质因子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
int main()
{
    int n, flag = 1;
    cin >> n;
    for(int i = 2; i <= n; i++)
    {
        while(n % i == 0) 
        {
            if(flag) cout << i;
            else cout << " " << i;
            flag = 0;
            n /= i;
        }
    }
    return 0;
}

7-3 h0039. 平方数 -前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
const int N = 100010;
int s[N];
int main()
{
    int a, b;
    for(int i = 1; i*i < N; i++)
        s[i*i] = 1;
    //前缀和
    for(int i = 1; i < N; i++)
        s[i] += s[i-1];
    while(cin >> a >> b, a|b)
        cout << s[b] - s[a-1] << endl;
    return 0;
}

7-4 马踏棋盘 -bfs(宽度优先搜索)

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
#include <iostream>
#include <queue>
#include <cstring>
#define x first
#define y second
using namespace std;
const int N = 410;
typedef pair<int, int> PII;
int d[N][N], n, m, x0, y0;
int nx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
int ny[8] = {2, -2, 2, -2, 1, -1, 1, -1};
void bfs()
{
    memset(d, -1, sizeof d);
    queue<PII> q;
    q.push({x0, y0});
    d[x0][y0] = 0;
    while(q.size())
    {
        PII t = q.front();
        q.pop();
        for(int i = 0; i < 8; i++)
        {
            int x = nx[i] + t.x, y = ny[i] + t.y;
            if(d[x][y]!=-1||x < 1 || y < 1|| x > n||y >m)
                continue;
            q.push({x, y});
            d[x][y] = d[t.x][t.y] + 1;
        }
    }    
}
int main()
{
    cin >> n >> m >> x0 >> y0;
    bfs();
    for(int i = 1; i <= n; i++, puts(""))
        for(int j = 1; j <= m; j++)
            printf("%-5d", d[i][j]);
    return 0;
}

7-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
31
32
33
34
35
36
#include <iostream>
using namespace std;
const int N = 100010;
int cnt[N], p[N];
int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    int T; cin >> T;
    while(T--)
    {
        int n, m;
        cin >> n >> m;
        for(int i = 1; i <= n; i++)
            p[i] = i, cnt[i] = 0;
        for(int i = 1; i <= m; i++)
        {
            int a, b;
            cin >> a >> b;
            p[find(a)] = find(b);
        }
        int num = 0, res = 0;
        for(int i = 1; i <= n; i++)
        {
            int p = find(i);
            if(!cnt[p]) num++;
            cnt[p]++;
            res = max(cnt[p], res);
        }
        cout << num << " " << res << endl;
    }
    return 0;
}

7-6 多参加活动，生活才精彩 -贪心

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
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
struct node{
    int s, t, e;
    bool operator < (const node &x){
        return t < x.t;
    }
} f[N];
int main(){
    int n; cin >> n;
    for(int i = 0; i < n; i++)
        cin >> f[i].s >> f[i].t >> f[i].e;
    //按右端点从小到大排序
    sort(f, f + n);
    int cnt = 0, num = 0, la = -0x3f3f3f3f;
    for(int i = 0; i < n; i++)
    {
        if(f[i].s >= la)
        {
            cnt ++;
            num += f[i].e;
            la = f[i].t;
        }
    }
    cout << cnt << " " << num << endl;
    return 0;
}

7-7 部落冲突 -二分查找

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
#include <iostream>
#define int long long
using namespace std;
const int N = 110;
int n;
struct node{
    int x1, x2, h;
} f[N];
bool check(int x)
{
    //sum1计算左侧面积，sum2计算右侧面积
    int sum1 = 0, sum2 = 0;
    for(int i = 0; i < n; i++)
    {
        int x1 = f[i].x1, x2 = f[i].x2, h = f[i].h;
        if(x >= x2) sum1 += h * (x2 - x1); // 如果当前部落全在x左边
        else if(x <= x1) sum2 += h * (x2 - x1); // 如果当前部落全在x右边
        else //如果x将部落一分为2
        {
            sum1 += h * (x - x1); 
            sum2 += h * (x2 - x);
        }
    }
    //左侧面积大于等于右侧面积
    return sum1 >= sum2;
}
signed main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        int x, y, w, h;
        cin >> x >> y >> w >> h;
        f[i].x1 = x; f[i].x2 = x + w;
        f[i].h = h;
    }
    // 二分查找一个数mid，满足以x=mid为分割线时满足题意
    int l = 0, r = 1e9;
    //一定是l==r时循环结束
    while(l < r)
    {
        int mid = l + r >> 1;
        //如果满足以mid分割时左侧面积大于等于右侧面积，则减小mid使两侧区间尽可能接近
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}

7-8 拼题A打卡奖励 -dp(动态规划)

1
常规背包做法: dp[i]表示时间为i时能得到的最大金币数 //时间复杂度: O(n*m) 1000*365*24*60 
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
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1000010;
//dp[i]表示，赢得i枚金币要花费的最少时间，时间复杂度O(n*n*c) 1000*1000*30
int dp[N], v[N], w[N];
int main()
{
    //初始化花费时间位正无穷
    memset(dp, 0x3f, sizeof dp);
    int n, m;
    scanf("%d%d", &n, &m);
    int sum = 0;
    for(int i = 1; i <= n; i++)
        scanf("%d", &v[i]);
    dp[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &w[i]);
        sum += w[i];
    }
    for(int i = 1; i <= n; i++)
        for(int j = sum; j >= w[i]; j--)
            dp[j] = min(dp[j], dp[j - w[i]] + v[i]);
    int res = sum;
    while(dp[res]> m) res--;
    cout << res << endl;
    return 0;
}

7-9 相邻差值（南大）

做法一: dfs(深度优先搜索)

时间复杂度O(2^n) 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
25
26
27
28
29
30
31
#include <iostream>
using namespace std;
int res = 0, l, r;
void dfs(int x)
{
    // 如果超出范围停止递归
    if(x > r) return;
    //如果x在范围内则x满足条件
    if(x >= 10 && x >= l && x <= r)
        res ++;
    //取出x的尾位t
    int t = x % 10;
    //如果尾位t不为0，则可以往后添加t-1
    if(t > 0) dfs(x * 10 + t - 1);
     //如果尾位t不为9，则可以往后添加t+1
    if(t < 9) dfs(x * 10 + t + 1);
}
int main()
{
    int T; cin >> T;
    while(T--)
    {
        cin >> l >> r;
        res = 0;
        // 遍历首位为1~9
        for(int i = 1; i <= 9; i++)
            dfs(i); // dfs(i) 遍历以i开头满足题意的数
        cout << res << endl;
    }
    return 0;
}

做法二: 数位dp

时间复杂度O(n * 100) 

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
// f[i][j] 表示i位数字, 结尾为j, 满足条件的数的个数
int f[12][15];
void init()
{
    for(int i = 0; i < 10; i ++) f[1][i] = 1;
    for(int i = 2; i < 12; i ++)
        for(int j = 0; j < 10; j ++)
            for(int k = 0; k < 10; k ++)
                if(abs(k - j) == 1)
                    f[i][j] += f[i - 1][k];
}
// dp(n) 1~n内满足条件的数的个数
int dp(int n)
{
    if(n < 10) return 0;
    vector<int> nums;
    // 取出n的每一位
    while(n) nums.push_back(n % 10), n /= 10;
    int len = nums.size();
    //last 记录上一位的数
    int res = 0, last = -1;
    
    // 计算等于n的位数的满足题意数的个数
    for(int i = len - 1; i >= 0; i --)
    {
        int x = nums[i];
        //前一位为last 当前位要小于x 后可以加什么数
        //特判首位不能为0，首位为0时1~x-1任选
        for(int j = (i == len - 1 ? 1 : 0); j < x; j ++)
            if(i == len - 1 || abs(j - last) == 1)
                res += f[i + 1][j];
       	// 如果不是第一位且下一位和前一位相差不为1 break
        if(i != len - 1 && abs(last - x) != 1) break;
        //如果到最后一位任然满足条件着说明n这个数满足条件
        if(!i) res ++;
        last = x;
    }
    
	// 加上低于n的位数的情况
    for(int i = nums.size() - 1; i >= 2; i --)
        for(int j = 1; j < 10; j ++)
            res += f[i][j];

    return res;
}

signed main()
{
    init();
    int T; cin >> T;
    while(T --)
    {
        int l, r;
        cin >> l >> r;
        // 1~r满足题意的个数 - 1~l-1满足题意得数的个数
        cout << dp(r) - dp(l - 1) << endl;
    }
    return 0;
}
算法刷题 > school
#算法竞赛
2023寒假集训摸底测试
https://leaf-domain.gitee.io/2024/01/12/winVacaExam/
作者
叶域
发布于
2024年1月12日
许可协议