比赛链接

AtCoder Beginner Contest 160

Problem D. Line++

观察数据范围,直接暴力解决即可。

时间复杂度 $O(n^2)$

#include <bits/stdc++.h>

using namespace std;

const int N = 2e3 + 5;

int cnt[N];
int n, x, y;

int main() {
  ios::sync_with_stdio(false);
  cin >> n >> x >> y;
  for (int s = 1; s <= n; s++)
    for (int t = s + 1; t <= n; t++)
      cnt[min(t - s, abs(s - x) + 1 + abs(t - y))]++;
  for (int i = 1; i < n; i++)
    cout << cnt[i] << '\n';
  return 0; 
}

Problme E. Red and Green Apples

第一次写了一个假的贪心,发现题解中有更加简单的贪心

选出 $A$ 中前 $X$ 大的和 $B$ 中前 $Y$ 大的,和 $C$ 中所有的进行排序,取前 $X+Y$ 大即可。

时间复杂度 $\Theta (nlogn)$

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 5;

int x, y, a, b, c;
ll A[N], B[N], C[N], D[N * 2];

int main() {
    ios::sync_with_stdio(false);
    cin >> x >> y >> a >> b >> c;
    for (int i = 1; i <= a; i++) cin >> A[i];
    for (int i = 1; i <= b; i++) cin >> B[i];
    for (int i = 1; i <= c; i++) cin >> C[i];
    sort(A + 1, A + 1 + a, [](int x, int y) {
        return x > y; 
    });
    sort(B + 1, B + 1 + b, [](int x, int y) {
        return x > y; 
    });
    sort(C + 1, C + 1 + c, [](int x, int y) {
        return x > y; 
    });
    int tot = 0;
    for (int i = 1; i <= x; i++) D[++tot] = A[i];
    for (int i = 1; i <= y; i++) D[++tot] = B[i];
    for (int i = 1; i <= c; i++) D[++tot] = C[i];
    sort(D + 1, D + 1 + tot, [](int x, int y) {
        return x > y; 
    });
    ll ans = 0;
    for (int i = 1; i <= x + y; i++) ans += D[i];
    cout << ans << '\n';
    return 0; 
}

Problem F. Distributing Integers

第一眼没有看出这是一个有根树拓扑排序计数。

这是分析的链接:Link

然后考虑用换根 $DP$ 来实现多根的查询。

时间复杂度 $\Theta(n)$

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 5, mod = 1e9 + 7;

int n;
int siz[N], mul[N], ans[N];
vector<int> g[N];

int pw(int x, int y) {
    int res = 1;
    while (y) {
        if (y & 1)
            res = (ll)res * x % mod;
        x = (ll)x * x % mod;
        y >>= 1;
    }
    return res; 
}

void dfs(int u, int fa) {
    siz[u] = 1, mul[u] = 1;
    for (auto v : g[u]) 
        if (v != fa) {
            dfs(v, u);
            siz[u] += siz[v];
            mul[u] = (ll)mul[u] * mul[v] % mod;
        }
    mul[u] = (ll)mul[u] * siz[u] % mod;
}

void dfs2(int u, int fa, int fromFa) {
    if (u != 1)
        ans[u] = (ll)mul[u] * pw(siz[u], mod - 2) % mod * n % mod * fromFa % mod;
    else 
        ans[u] = (ll)mul[u] * fromFa % mod; 
    for (auto v : g[u]) 
        if (v != fa) {
            int tmp = (ll)fromFa * mul[u] % mod * pw(mul[v], mod - 2) % mod * pw(siz[u], mod - 2) % mod * (n - siz[v]) % mod;
            dfs2(v, u, tmp);
        }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    dfs2(1, 0, 1);
    int x = 1;
    for (int i = 1; i <= n; i++)
        x = (ll)x * i % mod;
    for (int i = 1; i <= n; i++)
        cout << (ll)x * pw(ans[i], mod - 2) % mod << '\n';
    return 0; 
}

后言

  • 将题意抽象的越简单越直接越好,这样容易想出模型。
最后修改:2020 年 04 月 12 日 12 : 32 PM
如果觉得我的文章对你有用,请随意赞赏