Week1 题解

A - Raising Modulo Numbers

在这里插入图片描述
在这里插入图片描述

快速幂

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
#include <iostream>
using namespace std;
// https://vjudge.net/contest/505193#problem/A  
int z;
long long fast_power(long long a, long long b, long long c)
{
    long long ans = 1;
    a %= c;
    while (b)
    {
        if (b % 2)
        {
            ans = (ans * a) % c;
        }
        b /= 2;
        a = (a * a) % c;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> z;
    while (z--)
    {
        long long ans = 0;
        int M, H;
        cin >> M >> H;
        for (int i = 1; i <= H; i++)
        {
            long long a, b;
            cin >> a >> b;
            ans += fast_power(a, b, M);
        }
        cout << ans % M << endl;
    }
    return 0;
}

B - 起床困难综合症

在这里插入图片描述
在这里插入图片描述

位运算，因为将数据转化为二进制表示后，AND，OR，XOR运算每一位计算互相独立，我们考虑贪心，直接每一位讨论，让每一位最后结果尽可能大

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
#include <bits/stdc++.h>
using namespace std;
// https://vjudge.net/contest/505193#problem/B
// 位运算（每一位分别考虑）
int n, m;
struct node
{
    string op;
    int t;
} door[110000];
int cal(int tar, int bit)
{
    for (int i = 1; i <= n; i++)
    {
        int tar2 = door[i].t >> bit & 1; //取从右往左第bit位（从0开始）
        if (door[i].op == "AND")
            tar = tar2 & tar;
        if (door[i].op == "XOR")
            tar = tar2 ^ tar;
        if (door[i].op == "OR")
            tar = tar2 | tar;
    }
    return tar;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> door[i].op >> door[i].t;
    }
    // int limit = 0;
    // while (m)
    // {
    //     m = m >> 1;
    //     limit++;
    // } //求m的最高位数
    int ans = 0;
    int tarm = 0;
    for (int bit = 30; bit >= 0; bit--)
    {
        int res0 = cal(0, bit); //若bit位填0
        int res1 = cal(1, bit); //若bit位填1
        int m0 = tarm;
        int m1 = tarm + (1 << bit);
        if (m1 <= m && res1 > res0)
        {
            ans += res1 << bit;
            tarm = m1;
        }
        if (res0 >= res1)
        {
            ans += res0 << bit;
        }
    }
    cout << ans;
    return 0;
}

C - 激光炸弹

在这里插入图片描述

二维前缀和模板题

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;
int n, r;
int a[5011][5011];//数组不能开5001，否则会tle（离谱）
// https://www.luogu.com.cn/problem/P2280
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> r;
    for (int i = 1; i <= n; i++)
    {
        int x, y, temp;
        cin >> x >> y >> temp;
        x++, y++; //本题坐标从0开始
        a[x][y] = temp;
    }
    for (int i = 1; i <= 5001; i++)
    {
        for (int j = 1; j <= 5001; j++)
        {
            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
        }
    }
    int ans = 0;
    for (int i = r; i <= 5001; i++)
    {
        for (int j = r; j <= 5001; j++)
        {
            ans = max(ans, a[i][j] - a[i - r][j] - a[i][j - r] + a[i - r][j - r]);
        }
    }
    cout << ans;
    return 0;
}

D - Tallest Cow

在这里插入图片描述
差分模板题

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 <map>
using namespace std;
// https://vjudge.net/contest/505193#problem/D
int N, I, H, R;
int cf[10010];
int a[10010];
map<int, bool> visit[10000];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> N >> I >> H >> R;
    for (int i = 1; i <= R; i++)
    {
        int a, b;
        cin >> a >> b; // a与b可以互相看见，说明下标a+1到下标b-1都要减去1
        if (a > b)
            swap(a, b);
        if (visit[a][b])
            continue;
        cf[a + 1]--;
        cf[b]++;
        visit[a][b] = true;
    }
    for (int i = 1; i <= N; i++)
    {
        a[i] = a[i - 1] + cf[i];
        cout << a[i] + H << endl;
    }
    return 0;
}

E - Best Cow Fences

在这里插入图片描述
在这里插入图片描述
实数范围二分
蓝书有模板

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
#include <iostream>
#include <string.h>
using namespace std;
// https://vjudge.net/contest/505193#problem/E
double eps = 1e-5;
int n, f;
double a[100100];
double sum[100100];
double b[100100], pre[100100];
bool check(double ans)
{
    for (int i = 1; i <= n; i++)
    {
        sum[i] = a[i] - ans + sum[i - 1];
    }
    double min1 = 1e5;
    double judge = -1e5;
    for (int i = f; i <= n; i++)
    {
        min1 = min(sum[i - f], min1);
        judge = max(sum[i] - min1, judge);
    }
    if (judge >= 0)
        return true;
    else
        return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    scanf("%ld %ld", &n, &f);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lf", &a[i]);
    }
    double l = -1e5, r = 1e5;
    while (l + eps < r)
    {
        double mid = (l + r) / 2;
        if (check(mid))
        {
            l = mid;
        }
        else
        {
            r = mid;
        }
    }
    cout << int(r * 1000);
    return 0;
}

F - 借教室

在这里插入图片描述
在这里插入图片描述
二分查找模板题

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
#include <bits/stdc++.h>
using namespace std;
//https://vjudge.net/contest/505193#problem/F
int n, m;
int a[10000000];
int cf[10000000];
int temp[10000000];
struct node
{
    int num;
    int s;
    int e;
} ask[10000000];
bool check(int ans)
{
    memset(temp, 0, sizeof(temp));
    memset(cf, 0, sizeof(cf));
    for (int i = 1; i <= ans; i++)
    {
        int s = ask[i].s;
        int e = ask[i].e;
        int n = ask[i].num;
        cf[s] += n;
        cf[e + 1] -= n;
    }
    for (int i = 1; i <= n; i++)
    {
        temp[i] = temp[i - 1] + cf[i];
        if (temp[i] > a[i])
            return true;
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> ask[i].num >> ask[i].s >> ask[i].e;
    }
    int l = 1, r = m;
    if (!check(m))
    {
        cout << 0 << endl;
        return 0;
    }
    int ans = -1;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
        {
            ans = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << -1 << endl;
    cout << ans;
    return 0;
}

G - Cinema

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
离散化，思路有点难懂，模板在蓝书上

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 <bits/stdc++.h>
using namespace std;
//https://vjudge.net/contest/505193#problem/G
int n, m, a[200010], audio[200010], subtitute[200010];
int lan[200010 * 3], tot;
int uni[200010 * 3], num;
int ans[200010 * 3]; //记录离散化后科学家会的语言的出现次数
int find(int yuan)
{
    return lower_bound(uni + 1, uni + 1 + num, yuan) - uni; //返回该数的离散化结果
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%ld", &a[i]);
        lan[++tot] = a[i];
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%ld", &audio[i]);
        lan[++tot] = audio[i];
    }
    for (int i = 1; i <= m; i++)
    {
        scanf("%ld", &subtitute[i]);
        lan[++tot] = subtitute[i];
    }
    sort(lan + 1, lan + tot + 1);
    for (int i = 1; i <= tot; i++)
    {
        if (i == 1 || lan[i] != lan[i - 1])
            uni[++num] = lan[i];
    } //离散化
    for (int i = 1; i <= n; i++)
    {
        ans[find(a[i])]++; //统计所有科学家会的语言出现有多少
    }
    int ans0 = 0;           // 存当前答案
    int ans1 = 0, ans2 = 0; //存当前答案的各个参数，字幕和音频满足情况
    for (int i = 1; i <= m; i++)
    {
        int anx = ans[find(audio[i])];
        int any = ans[find(subtitute[i])];
        if (anx > ans1 || (anx == ans1 & any > ans2))
        {
            ans0 = i; //该电影入选
            ans1 = anx;
            ans2 = any;
        }
    }
    if (ans0 == 0) //所有电影的字幕和音频都对不上，随便选好了
    {
        cout << 1;
    }
    else
    {
        cout << ans0;
    }
    return 0;
}

H - Balanced Lineup

在这里插入图片描述
在这里插入图片描述
ST表。可以当模板直接用
蓝书上也有

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
#include <bits/stdc++.h>
using namespace std;
// https://vjudge.net/contest/505193#problem/H
// ST 表
int N, Q;
int cow[50010];
int f1[500010][100];
int f2[500010][100];
// f[i][j]代表从[i,i+2^j-1]这段区间的极值
void pre_work()
{
    for (int i = 1; i <= N; i++)
        f1[i][0] = cow[i], f2[i][0] = cow[i];
    int t = log(N) / log(2) + 1; //子区间数
    for (int j = 1; j < t; j++)
    {
        for (int i = 1; i <= N - (1 << j) + 1; i++)
        {
            f1[i][j] = max(f1[i][j - 1], f1[i + (1 << (j - 1))][j - 1]);
            f2[i][j] = min(f2[i][j - 1], f2[i + (1 << (j - 1))][j - 1]);
        }
    }
}
int ST_query1(int l, int r)
{
    int k = log(r - l + 1) / log(2);
    return max(f1[l][k], f1[r - (1 << k) + 1][k]);
}
int ST_query2(int l, int r)
{
    int k = log(r - l + 1) / log(2);
    return min(f2[l][k], f2[r - (1 << k) + 1][k]);
}
int main()
{
    scanf("%d %d", &N, &Q);
    for (int i = 1; i <= N; i++)
    {
        cin >> cow[i];
    }
    pre_work();
    for (int i = 1; i <= Q; i++)
    {
        int l, r;
        cin >> l >> r;
        cout << ST_query1(l, r) - ST_query2(l, r) << endl;
    }
    return 0;
}

I - Best Cow Line

在这里插入图片描述
在这里插入图片描述

emmm怎么说，应该算贪心+双向队列，每次只能前后找，我们选择找最小的
关键是，假如遇到前后相同应该怎么选择
比如：ABBCA
此时前后都是A，但是我们想让字典序最小，应该先取第一个A，因为取完那个A我们就可以用后面的B
所以思路有了，定俩个指针，一个前一个后，遇到相同的就往中间扫，直到遇到不一样的

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>
using namespace std;
// https://vjudge.net/contest/505193#problem/I
int N;
vector<char> a;
vector<char> ans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        char ch;
        cin >> ch;
        a.push_back(ch);
    }
    while (a.empty() == false)
    {
        vector<char>::iterator it1 = a.begin();
        vector<char>::iterator it2 = a.end() - 1;
        while (*it1 == *it2 && it1 <= it2)
        {
            it1++;
            it2--;
        }
        // cout << "!" << *it1 << "! " << *it2 << " !";
        if (it1 < it2)
        {
            if (*it1 < *it2)
            {
                ans.push_back(a.front());
                a.erase(a.begin());
                // cout << "called ";
            }
            else if (*it1 > *it2)
            {
                ans.push_back(a.back());
                a.pop_back();
                // cout << "here ";
            }
        }
        else
        {
            ans.push_back(a.front());
            a.pop_back();
        }
        // for (int i = 0; i < a.size(); i++)
        //     cout << a[i];
        // cout << endl;
    }
    int l = ans.size();
    for (int i = 0; i < l; i++)
    {
        cout << ans[i];
        if ((i + 1) % 80 == 0)
            cout << endl;
    }
    if (l % 80)
        cout << endl;
    return 0;
}

J - Fence Repair

在这里插入图片描述
在这里插入图片描述
Huffman树
用小根堆来构造
建议当板子

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
#include <iostream>
#include <algorithm>
using namespace std;
// https://vjudge.net/contest/505193#problem/J
// https://www.luogu.com.cn/problem/P1090
// Huffman树(此一类问题)蓝书P86
int N;
int heap[20010], heap_size = 0;
long long sum = 0;
long long ans;
void add(int tar)
{
    heap[++heap_size] = tar;
    int son = heap_size;
    while (son > 1)
    {
        int fa = son / 2;
        if (heap[fa] <= heap[son])
            break;
        swap(heap[fa], heap[son]);
        son = fa;
    }
}
int get_min()
{
    return heap[1];
}
void extract() //清除堆顶
{
    heap[1] = heap[heap_size--];
    int fa = 1;
    while (fa * 2 <= heap_size)
    {
        int son = fa * 2;
        if (son < heap_size && heap[son + 1] < heap[son]) //找最小的上来
            son++;
        if (heap[fa] <= heap[son])
            break;
        swap(heap[son], heap[fa]);
        fa = son;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        int remp;
        cin >> remp;
        add(remp);
    }
    for (int i = 1; i < N; i++)
    {
        int remp1, remp2;
        remp1 = get_min();
        extract();
        remp2 = get_min();
        extract();
        ans += (remp1 + remp2);
        add(remp1 + remp2);
    }
    cout << ans;
    return 0;
}

K - Radar Installation

在这里插入图片描述
在这里插入图片描述
一个贪心问题，我们以每个岛屿以d维半径画圆，与x轴的交点即必须有雷达站的区域
我们要保证可能少的点让每个线段都能兼顾
我们采用贪心思想
如果从左往右找，尽可能让雷达站靠右建立
在这里插入图片描述

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
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
// 参考题解：https://www.luogu.com.cn/problem/solution/UVA1193
// https://www.luogu.com.cn/problem/UVA1193
// 贪心
int n;
double d;
struct node
{
    double l;
    double r;
} r[1010];
bool cmp(node a, node b)
{
    return a.l < b.l;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int num = 0;
    while (cin >> n >> d)
    {
        if (n == 0 && d == 0)
            break;
        bool flag = true;
        for (int i = 1; i <= n; i++)
        {
            double x, y;
            cin >> x >> y;
            double temp = d * d - y * y;
            if (temp < 0)
            {
                flag = false;
                continue;
            }
            double limit = sqrt(temp);
            r[i].l = x - limit;
            r[i].r = x + limit;
        }
        if (flag == false || d < 0)
        {
            printf("Case %d: -1\n", ++num);
            continue;
        }
        sort(r + 1, r + 1 + n, cmp);
        double rlimit = -0x7fffffff;
        int ans = 0;
        for (int i = 1; i <= n; i++)
        {
            double templ = r[i].l;
            double tempr = r[i].r;
            if (rlimit < templ)
            {
                ans++;
                rlimit = tempr;
            }
            rlimit = min(rlimit, tempr); //因为我们排序的时候只考虑了左端点，所以必须取最小的，保证这些能兼顾
        }
        printf("Case %d: %d\n", ++num, ans);
    }

    return 0;
}

L - Corral the Cows

在这里插入图片描述
在这里插入图片描述
题目要我们找最适合的边长，第一反应就是二分查找，check验证，但是如何去写这个check函数呢
坐标最大可以到10000，直接找肯定会爆，我们考虑离散化， 利用离散化点为端点去维护一个区域的包含的点，所以我们又能想到二维前缀和

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
#include <iostream>
#include <algorithm>
using namespace std;
// 传送门：https://vjudge.net/contest/505193#problem/L
// 洛谷：  https://www.luogu.com.cn/problem/P2862
// 二分+前缀和+离散化
struct node
{
    int x;
    int y;
} clover[510];
int num[1000000], cnt;
int N, C;
int sum[5000][5000]; //离散化后的前缀和数组
int get_pos(int x)
{
    return lower_bound(num + 1, num + 1 + cnt, x) - num;
}
bool check(int ans)
{
    int x1, x2; //横坐标的离散化
    int y1, y2; //纵坐标的离散化
    for (x1 = 1, x2 = 1; x2 <= cnt; x2++)
    {
        while (num[x2] - num[x1] + 1 > ans) //一定要加1！！！因为(x1,y1)是算在里面的！
            x1++;
        for (y1 = 1, y2 = 1; y2 <= cnt; y2++)
        {
            while (num[y2] - num[y1] + 1 > ans)
                y1++;
            if (sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1] >= C)
                return true;
        }
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> C >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> clover[i].x >> clover[i].y;
        num[++cnt] = clover[i].x;
        num[++cnt] = clover[i].y;
    }
    //开始构造离散化
    sort(num + 1, num + 1 + cnt);
    cnt = unique(num + 1, num + 1 + cnt) - num - 1;
    //初始化前缀和
    for (int i = 1; i <= N; i++)
    {
        int x = clover[i].x;
        int y = clover[i].y;
        sum[get_pos(x)][get_pos(y)]++;
    }
    for (int i = 1; i <= cnt; i++)
        for (int j = 1; j <= cnt; j++)
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
    //前缀和初始化结束
    int r = 10000;
    int l = 1;
    int ans = -1;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
        {
            ans = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << ans;
    return 0;
}

M - 超级钢琴

在这里插入图片描述
在这里插入图片描述

N - 糖果传递

在这里插入图片描述
一个很有意思的题，建议先看线性的模型：拆分纸牌
我们的策略就是：将所有的数字和平均值比较，从一端开始（设为a[i]）如果该值和平均值不相同，我们通过和a[i+1]进行交换，从而使a[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
#include <bits/stdc++.h>
using namespace std;
// https://www.luogu.com.cn/problem/P1031
int n, a[10010];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    int aver = sum / n;
    for (int i = 1; i <= n; i++)
        a[i] -= aver;
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        // cout << a[i] << endl;
        if (a[i] != 0)
        {
            a[i + 1] += a[i];
            a[i] = 0;
            ans++;
        }
    }
    cout << ans << 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
#include <iostream>
#include <algorithm>
using namespace std;
// 传送门：https://www.luogu.com.cn/problem/P2512
// 题解：https://www.luogu.com.cn/problem/solution/P2512
// 中位数！
int m;
long long a[1000010];
long long c[1000010];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> m;
    long long aver = 0, ans = 0;
    for (int i = 1; i <= m; i++)
    {
        cin >> a[i];
        aver += a[i];
    }
    aver /= m;
    for (int i = 1; i <= m; i++)
    {
        c[i] = c[i - 1] + aver - a[i - 1];
    }
    sort(c + 1, c + 1 + m);
    int mid = c[(1 + m) >> 1];
    for (int i = 1; i <= m; i++)
    {
        ans += abs(mid - c[i]);
    }
    cout << ans;
    return 0;
}

O - Too Rich

在这里插入图片描述
在这里插入图片描述
这个题挺麻烦的，思路肯定是贪心解决，但是不能无脑贪心，因为有些数据是没有办法靠小面额凑出来的。
为什么会出现这种现象呢？是因为有50，500这样的数据，比如有 10 20 20 50 50，现在要凑110，110 - 10 - 20 - 20 = 60，50不能整除60，则就需要两个50的，因为只用一个50的话，剩下的凑不出60。
那我们怎么解决这个问题呢？因为50和500这样的特殊数据，分凑偶数张和凑奇数张两种情况，必能有一种能把目标凑出来 (如果存在解的话)，所以，我们考虑深搜，从大面额往回搜，把每张面额按奇数张or偶数张分别进行讨论搜索，必能找到可行解

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>
using namespace std;
// https://vjudge.net/contest/505193#problem/O
int T, tar;
int coin[11];
long long value[11] = {0, 1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000};
long long sum[11];
int ans;
void dfs(long long rest, int cnt, int value_id) // rest是进行到第value_id个面额时所剩下的目标钱数，cnt是目前已经凑过的钱币数
{
    if (rest < 0)
        return;
    if (value_id == 0)
    {
        if (rest == 0)
            ans = max(ans, cnt);
        return;
    }
    long long current = max(rest - sum[value_id - 1], (long long)(0));
    int cur_num = current / value[value_id];
    if (current % value[value_id])
        cur_num++;
    if (cur_num <= coin[value_id])
        dfs(rest - value[value_id] * cur_num, cnt + cur_num, value_id - 1);
    cur_num++;
    if (cur_num <= coin[value_id])
        dfs(rest - value[value_id] * cur_num, cnt + cur_num, value_id - 1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--)
    {
        cin >> tar;
        for (int i = 1; i <= 10; i++)
        {
            cin >> coin[i];
        }
        for (int i = 1; i <= 10; i++)
        {
            sum[i] = sum[i - 1] + (long long)(coin[i] * value[i]);
        }
        ans = -1;
        dfs(tar, 0, 10);
        cout << ans << endl;
    }
    return 0;
}