首页 程序设计 AtCoder

# A

水题

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve() {
    int n, d;
    string s;

    cin >> n >> d >> s;

    int cnt = 0;

    for (char& x : s)
        cnt += (x == '@');

    cout << n - cnt + d << endl;
}

# B

水题，倒着找就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve() {

    int n, d;
    string s;

    cin >> n >> d >> s;

    for (int i = s.size() - 1; i >= 0; i--)
        if (s[i] == '@') {
            s[i] = '.', d--;
            
            if (d == 0)
                break;
        }
        
    cout << s << endl;
}

# C

只有当前寿司的美味程度 BjB_j 大于等于某个人的美食等级 AiA_i 时，才会吃
按顺序的话，越大的肯定越先被吃掉

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
struct Soshi {
    int b, place;
    int peo = -1;
};

int n, m;
int a[N];
Soshi soshi[N];

bool cmp1(Soshi x, Soshi y) {
    return x.b > y.b;
}

bool cmp2(Soshi x, Soshi y) {
    return x.place < y.place;
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= m; i++)
        cin >> soshi[i].b, soshi[i].peo = -1, soshi[i].place = i;

    sort(soshi + 1, soshi + m + 1, cmp1);

    int idxA = 1, idxB = 1;

    while (idxA <= n && idxB <= m) {
        while (a[idxA] <= soshi[idxB].b)
            soshi[idxB].peo = idxA, idxB++;
        idxA++;
    }

    sort(soshi + 1, soshi + m + 1, cmp2);

    for (int i = 1; i <= m; i++)
        cout << soshi[i].peo << endl;
        
    return;
}

# D

# 个人代码

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
#include <bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

int n, m, maxx;

int num[30];

int cnt = 0;

void dfs(int u) {
    if (u == n) {
        if (num[1] != 0) {
            for (int i = 1; i <= n; i++)
                cout << num[i] + 10 * (i - 1) << " ";
            cout << endl;
        }
        return;
    }
    

    for (int i = num[u]; i <= maxx; i++) {
        num[u + 1] = i, dfs(u + 1);
    }
}

void dfs1(int u) {
    if (u == n) {
        if (num[1] != 0)
            cnt++;
        return;
    }


    for (int i = num[u]; i <= maxx; i++) {
        num[u + 1] = i, dfs1(u + 1);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;

    maxx = m - (n - 1) * 10;

    dfs1(0);
    cout << cnt << endl;
    memset(num, 0, sizeof num);
    dfs(0);

    return 0;
}

写的 DFSDFS，但是无意义 DFSDFS 了两次（因为先要得出次数）

# 参考题解

思路是类似的，用数组存答案，用 sumsum 记答案

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>
using namespace std;

int n, m, sum, ans[1000000][13], k[13];

void dfs(int i, int d){
    if (i > n) {
        sum++; // 存数量
        for (int j = 1; j <= n; j++)
            ans[sum][j] = k[j];
    }
    else {
        for (int j = d; j + (n - i) * 10 <= m; j++) { // 条件枚举
            k[i] = j; // 存状态
            dfs(i + 1, j + 10); // 搜索下一层
        }
    }
}

void solve() {
	cin >> n >> m;
	dfs(1, 1);
	for (int i = 1; i <= sum; i++) {
		for (int j = 1; j <= n; j++)
			cout << ans[i][j] << " ";
		cout << endl;
	}
}

int main() {
    ios::sync_with_stdio(0),cout.tie(0);
    cin >> n >> m;
    dfs(1, 1);
    cout << sum << '\n';
    for (int i = 1; i <= sum; i++){
        for (int j = 1; j <= n; j++)
            cout << ans[i][j] << ' ';
        cout << '\n';
    }
    return 0;
}

更新于 阅读次数 次

请我喝[茶]~(￣▽￣)~*

duoxichangan 微信支付

微信支付

duoxichangan 支付宝

支付宝