Codeforces Round #621 (Div. 1 + Div. 2) 题解

作者: xht37 分类: 题解 发布时间: 2020-02-20 03:50

点击数:89

Codeforces Round #621 (Div. 1 + Div. 2)

Cow and Haybales

贪心。

const int N = 107;
int n, d, a[N];

inline void solve() {
    rd(n), rd(d);
    for (int i = 1; i <= n; i++) rd(a[i]);
    for (int i = 2; i <= n; i++) {
        int now = min(d, a[i] * (i - 1));
        a[1] += now / (i - 1), d -= now;
    }
    print(a[1]);
}

int main() {
    int T;
    rd(T);
    while (T--) solve();
    return 0;
}

Cow and Friend

贪心。

const int N = 1e5 + 7;
int n, d, a[N], x;

inline void solve() {
    rd(n), rd(d);
    for (int i = 1; i <= n; i++) rd(a[i]);
    sort(a + 1, a + n + 1);
    x = upper_bound(a + 1, a + n + 1, d) - a - 1;
    if (!x) print(2);
    else if (x == n) print((d - 1) / a[x] + 1);
    else print(min(2, (d - 1) / a[x] + 1));
}

int main() {
    int T;
    rd(T);
    while (T--) solve();
    return 0;
}

Cow and Message

前缀和,组合计数。

const int N = 1e5 + 7;
int n, c[26];
char s[N];
ll ans, f[26][26];

int main() {
    rds(s, n);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 26; j++)
            f[j][s[i]-'a'] += c[j];
        ++c[s[i]-'a'];
    }
    ans = *max_element(c, c + 26);
    for (int j = 0; j < 26; j++)
        for (int k = 0; k < 26; k++)
            ans = max(ans, f[j][k]);
    print(ans);
    return 0;
}

Cow and Fields

求出每个点与 $1$ 到 $n$ 的最短路,一条新的路只可能从离 $n$ 更远的点连向离 $n$ 更近的点,贪心即可。

const int N = 2e5 + 7, inf = 1e9;
int n, m, k, a[N], ds[N], dt[N], v[N], ans;
vi e[N];

inline void dij(int s, int *d) {
    for (int i = 1; i <= n; i++) d[i] = inf, v[i] = 0;
    pq<pi> q;
    d[s] = 0, q.push(mp(0, s));
    while (q.size()) {
        int x = q.top().se;
        q.pop();
        if (v[x]) continue;
        v[x] = 1;
        for (int y : e[x])
            if (d[y] > d[x] + 1)
                d[y] = d[x] + 1, q.push(mp(-d[y], y));
    }
}

int main() {
    rd(n), rd(m), rd(k);
    for (int i = 1; i <= k; i++) rd(a[i]);
    for (int i = 1, x, y; i <= m; i++) rd(x), rd(y), e[x].pb(y), e[y].pb(x);
    dij(1, ds), dij(n, dt);
    sort(a + 1, a + k + 1, [&](int i, int j) { return dt[i] < dt[j]; });
    for (int i = 1; i < k; i++)
        ans = max(ans, ds[a[i+1]] + 1 + dt[a[i]]);
    print(min(ans, ds[n]));
    return 0;
}

Cow and Treats

垃圾题。

Cow and Vacation

题目太神仙了,先咕咕咕着。

Cow and Exercise

题目太神仙了,先咕咕咕着。

发表评论

电子邮件地址不会被公开。 必填项已用*标注