比赛链接

AtCoder Beginner Contest 160

Problem D. Banned K

按照题意模拟即可。

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

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 5;

int n;
ll cnt[N], a[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        cnt[a[i]]++;
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) ans += cnt[i] * (cnt[i] - 1) / 2;
    for (int i = 1; i <= n; i++) printf("%lld\n", ans - cnt[a[i]] + 1);
    return 0;
}

Problem E. Dividing Chocolate

考虑枚举行的切割状态,然后贪心切列。

令笔者不解的是,这道题目需要开的空间比原题空间要大。

时间复杂度 $\Theta (2^HWH)$

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f

using namespace std;

const int N = 1000, M = 1000;

int n, m, k;
char s[N][M];
int a[N][M];
int bel[N], sum[N];

int main() {
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0; i < n; i++) scanf("%s", s[i]);
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < m; j++) 
            a[i][j] = s[i][j] - '0';
    int ans = n + m;
    for (int mask = 0; mask < (1 << (n - 1)); mask++) {
        int tot = 0, res = 0;
        for (int i = 0; i < n; i++) {
            bel[i] = tot;
            if (mask >> i & 1)
                ++tot;
        }
        memset(sum, 0, sizeof sum);
        for (int i = 0; i < m; i++) {
            int flg = 0;
            for (int j = 0; j < n; j++) {
                sum[bel[j]] += a[j][i];
                if (sum[bel[j]] > k) 
                    flg = 1;
            }
            if (flg) {
                memset(sum, 0, sizeof sum);
                res++;
                for (int j = 0; j < n; j++) {
                    sum[bel[j]] += a[j][i];
                    if (sum[bel[j]] > k) res = n + m;
                }
            }
            if (res == n + m) break;
        }
        ans = min(ans, res + tot);
    }
    printf("%d\n", ans);
    return 0;
}

Problem F. Knapsack for All Segments

笔者一开始没写出来,看来 $DP$ 水平有待加强。

直接考虑一个区间 $[l,r]$ 满足两端都取的情况下,可以对答案产生的贡献。

显然是 $l\times (n-r+1)$。

我们可以发现对于一个端点 $r$,我们只需要计算满足条件左端点的下标和即可。

考虑 $f[i][j]$ 表示当前的右端点为 $i$,和为 $j$ 的左端点和的下标。

转移为 $f[i][j]=\sum f[i-1][j-a[i]]$

这个可以用滚动数组优化,但是需要每一次都将 $f[s]$ 清空,因为你可以不取,所以 $f[i][s]$ 的答案就继承到了 $f[i+1][s]$ 上,那么显然答案重复统计。

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

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod = 998244353, N = 3005;

int n, s;
int a[N];
int f[N];

int main() {
    scanf("%d %d", &n, &s);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = s; j > a[i]; j--) f[j] = (f[j] + f[j - a[i]]) % mod;
        f[a[i]] = (f[a[i]] + i) % mod;
        ans = (ans + (ll)f[s] * (n - i + 1) % mod) % mod;
        f[s] = 0;
    }
    printf("%d\n", ans);
    return 0; 
}

后言

  • 动态规划仍需加强,需要注意特化出模型,提高思维能力,然后多做题,熟悉每一种模型。
  • 动态规划计数需要注意会不会对一个答案进行多次的计算,要用最简单的办法解决困难的问题。
最后修改:2020 年 04 月 13 日 09 : 02 PM
如果觉得我的文章对你有用,请随意赞赏