Codeforces Round 451 (Div.2)

比赛链接：https://codeforces.ml/contest/898

A. Rounding

简单的四舍五入

void solve() {
    int n; cin >> n;
    if (n % 10 <= 5) cout << n / 10 * 10 << endl;
    else cout << (n / 10 + 1) * 10 << endl;
}

B. Proper Nutrition

$ax+by=n$ 直接枚举a的个数就可以

void solve() {
    int n, a, b; cin >> n >> a >> b;
    for (int i = 0; i <= 1e7; i++) {
        if (i * a > n) break;
        if ((n-i*a)%b==0) {
            cout << "YES" << endl;
            cout << i << ' ' << (n-i*a)/b << endl;
            return;
        }
    }
    cout << "NO" << endl;
}

C. Phone Numbers

暴力去除后缀

map<string, set<string>> mp;
void check(string s, string ss) {
    set<string> tmp;
    for (auto it : mp[s]) {
        int ff = 0;
        if (it.size() >= ss.size()) {
            for (int l = ss.size() - 1, r = it.size() - 1; l >= 0 && r >= 0; l--, r--) {
                if (ss[l] != it[r]) {
                    ff = 1;
                    tmp.insert(it);
                }
            }
            if (!ff) return;
        } else {
            for (int l = ss.size() - 1, r = it.size() - 1; l >= 0 && r >= 0; l--, r--) {
                if (ss[l] != it[r]) {
                    tmp.insert(it);
                }
            }
        }
    }
    mp[s] = tmp;
    mp[s].insert(ss);
}
void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        string s; cin >> s;
        int m; cin >> m;
        for (int j = 1; j <= m; j++) {
            string ss; cin >> ss;
            check(s, ss);
        }
    }
    cout << mp.size() << endl;
    for (auto it : mp) {
        cout << it.fi << ' ';
        cout << it.se.size() << ' ';
        for (auto item : it.se) cout << item << ' ';
        cout << endl;
    }
}

D. Alarm Clock

考虑贪心，每次都保留最前面k-1个数

我利用单调队列模拟了一下

int a[N];
int q[N];
void solve() {
    int n, m, k; cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a+1, a+n+1);
    int ans = 0;
    int hh = 1, tt = 0;
    for (int i = 1; i <= n; i++) {
        while (hh <= tt && a[i] - a[q[hh]] >= m) ++hh;
        q[++tt] = i;
        if (tt - hh + 1 >= k) --tt, ans++;
    }
    cout << ans << endl;
}

E. Squares and not squares

先预处理出每个数

如果是平方数，处理出到达非平方数的最小步数

如果不是平方数，处理出到达平方数的最小步数

然后分开讨论一下就可以

int a[N], b[N], c[N];
bool check(int x) {
    int s = sqrt(x);
    if (s * s == x) return true;
    else return false;
}
void solve() {
    int n; cin >> n;
    vector<int> ve, ve2;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        if (check(a[i])) {
            b[i] = 0;
            if (a[i] == 0) c[i] = 2, ve.push_back(2);
            else c[i] = 1, ve.push_back(1);
        }
        else {
            int s = sqrt(a[i]);
            b[i] = min(a[i] - s * s, (s+1)*(s+1) - a[i]);
            ve2.push_back(b[i]);
        }
    }
    if (ve.size() > n / 2) {
        sort(ve.begin(), ve.end());
        ll ans = 0;
        for (int i = 0; ve.size() - i > n / 2; i++) {
            ans += ve[i];
        }
        cout << ans << endl;
        return;
    }
 
    sort(ve2.begin(), ve2.end());
    ll ans = 0;
    for (int i = 0; ve.size() + i < n / 2; i++) {
        ans += ve2[i];
    }
    cout << ans << endl;
}