ABC388

6个月前更新

A. ?UPC

模拟

代码实现

print(input()[0]+'UPC')

B. Heavy Snake

模拟

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int main() {
    int n, d;
    cin >> n >> d;
    
    vector<int> t(n), l(n);
    rep(i, n) cin >> t[i] >> l[i];
    
    for (int k = 1; k <= d; ++k) {
        int ans = 0;
        rep(i, n) {
            int w = t[i]*(l[i]+k);
            ans = max(ans, w);
        }
        cout << ans << '\n';
    }
    
    return 0;
}

C. Various Kagamimochi

二分或双指针

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    
    vector<int> A(n);
    rep(i, n) cin >> A[i];
    
    ll ans = 0;
    rep(b, n) {
        int r = upper_bound(A.begin(), A.begin()+b, A[b]/2) - A.begin();
        ans += r;
    }
    
    cout << ans << '\n';
    
    return 0;
}

D. Coming of Age Celebration

考虑实现以下功能的数据结构：

加入一个数
将集合中的所有数 -1
将集合中的 0 删除
查询集合的大小

可以发现用小根堆就能做，时间复杂度为 \(O(n\log n)\)

也有一种 \(O(n)\) 做法

可以考虑每个外星人到哪一年就不需要再送石头了

具体可以维护变量 \(S\) 表示到目前为止已经有 \(S\) 个成年外星人需要送石头，再开一个 \(R\) 数组用来记录第 \(i\) 年之后不需要再送石头的成年外星人的人数

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    
    int s = 0;
    vector<int> r(n);
    rep(i, n) {
        a[i] += s;
        int num = min(a[i], n-i-1);
        a[i] -= num;
        s++;
        r[i+num]++;
        
        s -= r[i];
    }
    
    rep(i, n) cout << a[i] << ' ';
    
    return 0;
}

E. Simultaneous Kagamimochi

二分出 \(k\)
对于判定是一种贪心，选择最左边 \(k\) 个放在蛋糕塔的上方，再将最右边的 \(k\) 个放在蛋糕塔的下方，然后每个上方的蛋糕选择下方还没被匹配的大小最小的进行配对
也可以双指针，左边一半放上方，右边一半放下方

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    
    int m = n/2, j = m;
    int ans = 0;
    rep(i, m) {
        while (j < n and a[i]*2 > a[j]) j++;
        if (j == n) break;
        ans++;
        j++;
    }
    
    cout << ans << '\n';
    
    return 0;
}