CodeCraft-21 and Codeforces Round #711 (Div. 2)

A题 GCD Sum

原题链接

题意:

给定\(n\), 求最小的\(x(x >= n)\)使得\(gcd(x, sum) > 1\), \(sum\)等于\(x\)的各位之和

思路:

暴力

#include 
#include 
#include 

using namespace std;

const int N = 1e5 + 10;

long long gcd(long long a, long long b)
{
    return b ? gcd(b, a % b) : a;
}

void solve()
{
    long long t;
    scanf("%lld", &t);
    while (1){
        long long a = 0;
        long long b = t;
        while (b){
            a += b % 10;
            b = b / 10;
        }
        long long k = gcd(a, t);
        if (k > 1){
            printf("%lld\n", t);
            return;
        }
        t++;
    }
    return ;
}

int main()
{
    int t;
    cin >> t;
    while (t -- )
        solve();
    return 0;
}

B题 Box Fitting

原题链接

题意:

给定长度为\(m\)的盒子, 给定\(n\)个为\(a_{i} \times 1\)的长条, 将长条加入到盒子中, 最少需要几层。、

思路:

这里所有的\(a_{i}\)都是\(2\)的次方。

贪心, 将所有长条从大到小排列, 依次选取最大的, 每次将其填入到剩余的空格中(当存在一个空格长度大于\(a_{i}\)时), 否则, 需要新添一层。

信息用mulitset维护, set是无重复的, multiset中元素可以重复。

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e5 + 10;

int a[N];

multiset s;

void solve()
{
    int n, w;
    cin >> n >> w;
    s.clear();
    int x;
    for (int i = 1; i <= n; i ++ ){
        cin >> x;
        a[i] = x;
    }

    sort(a + 1, a + n + 1);
    reverse(a + 1, a + n + 1);
    int ans = 0;
    for (int i = 1; i <= n; i ++ ){
        int t = a[i];

        auto it = s.lower_bound(t);         //寻找是否存在一个空位使得可以塞进t

        if (it == s.end()){                 //没有找到, 重新开一层
            ans++;
            s.insert(w - t);
        }else{                              //找到, 将t塞进其中, 剩余空位为*it - t
            int k = *it - t;
            s.erase(it);
            s.insert(k);
        }
    }

    cout << ans << endl;
    return;
}

int main()
{
    int t;
    cin >> t;
    while (t -- )
        solve();
    return 0;
}