AtCoder Beginner Contest 231（E、F补题）_atcoder beginner contest 231 e

E - Minimal payments

题意：

给$N$种面值的钱币，现在需要支付$X$元，现在定义$A$为支付的钞票数，$B$为找钱找回来的钞票数，问$A+B$最小是多少？

思路：

直接记忆化搜索，金额较大，所以开$map$
定义$f(n,x)$为前$n$种钞票支付$x$元的情况下，最小的$A+B$
那么此时为了让$A+B$最小，一定是尽可能用大钞票，所以
$f(n,x)=f(n-1,x\%a[n])+x/a[n]$，代表尽可能的用$a[n]$这种钞票，使得用前$n-1$种钱，解决剩下的钱。
如果$x\%a[n]=0$,那么说明不需要找钱，所以就不需要第二种策略了
反之可能需要第二种策略
即$f(n,x)=f(n-1,a[n]-(x\%a[n]))+x/a[n]+1$，这个的含义就是多给一张$a[n]$这种金额的钱，前$n-1$种钱来解决剩下的钱。
所以就是上述两种策略的最小值

#include<bits/stdc++.h>
using namespace std;
const int N=70;
using ll = long long ;
ll n,x;
ll a[N];
map<int,ll> f[N];

ll dfs(int n,ll x) {
    if(n==1) {
        return x;
    }
    if(x==0) {
        return 0;
    }

    if(f[n].find(x)!=f[n].end()) {
        return f[n][x];
    }

    f[n][x]=dfs(n-1,x%a[n])+x/a[n];

    if(x%a[n]) {
        f[n][x]=min(f[n][x],dfs(n-1,a[n]-(x%a[n]))+x/a[n]+1);
    }
    return f[n][x];
}
int main() {
    cin>>n>>x;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
    }

    cout<<dfs(n,x)<<endl;


}
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

F - Jealous Two

题意：

现在给定$N$个物品，有$2$个人，对每种物品的评价分别为$A_i$和$B_i$，让你求$\sum _{i=1}^n\sum _{j=1}^n[A_i\ge A_j\&\&\le B_i\le B_j]$

思路：

可以用所有情况，即$N^2$减去不符合的情况数量
不符合的情况就是$A_i<A_j||B_i>B_j$
那么就直接找$A_i<A_j$的数量和$B_i>B_j$的数量，再次减去$A_i<A_j\&\&B_i>B_j$的数量(因为算重了，容斥)
前面两种数量直接排完序后，直接计数即可
最后一种情况利用树状数组来求即可，就类似于求逆序对的数量。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
#define ll long long
struct node {
    int x;
    int id;
    bool operator<(const node &t) const { return x < t.x; }
} a[N], b[N];
int n;
int A[N], B[N];
int tr[N];
int lowbit(int x) { return x & (-x); }
void Insert(int x) {
    for (int i = x; i <= n; i += lowbit(i)) {
        tr[i]++;
    }
}

int Query(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) {
        res += tr[i];
    }
    return res;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x;
        a[i].id = i;
    }
    sort(a + 1, a + n + 1);

    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (i == 1 || a[i].x != a[i - 1].x) {
            cnt++;
        }
        A[a[i].id] = cnt;
    }

    for (int i = 1; i <= n; i++) {
        cin >> b[i].x;
        b[i].id = i;
    }
    sort(b + 1, b + n + 1);
    cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (i == 1 || b[i].x != b[i - 1].x) {
            cnt++;
        }
        B[b[i].id] = cnt;
    }
    ll res = 0;
    int r = n;
    while (r) {
        int l = r;
        for (; l && a[l].x == a[r].x; l--) {
            res += n - r;
        }
        r = l;
    }

    r = n;
    while (r) {
        int l = r;
        for (; l&&b[l].x == b[r].x; l--) {
            res += n - r;
        }
        r = l;
    }

    r = n;
    while (r) {
        int l = r;
        for (; l&&a[l].x == a[r].x; l--) {
            res -= Query(B[a[l].id] - 1);
        }
        l = r;

        for (; l&&a[r].x == a[l].x; l--) {
            Insert(B[a[l].id]);
        }
        r = l;
    }
    printf("%lld\n", 1ll * n * n - 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
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

To be continued
如果你有任何建议或者批评和补充，请留言指出，不胜感激