ARC067 写题记录

[ARC067]写题记录

Factors of Factorial：记录详情

大概把每个数质因数分解后，统计所有质因数的个数，即 $n! = \prod {p_i^{\alpha_{i} } }$，答案为 $\prod (\alpha_{i} + 1)$。

#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;

template <typename T>
inline T read() {
    T x = 0, f = 1; char c = getchar();
    while (!isdigit(c)) { if (c == '-') f = - f; c = getchar(); }
    while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return x * f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read <int> ()
#define readlint read <lint> ()
const int inf = 1e9 + 1e7, MAXN = 1e3 + 1e1, Mod = 1e9 + 7;
const lint INF = 1e18 + 1e9;

lint cnt[MAXN], Ans;
int n, tmp;

int main(void) {

    n = readint, Ans = 1ll;
    for (int i = 2; i <= n; i ++) {
        tmp = i;
        for (int j = 2; j * j <= n; j ++) {
            while (!(tmp % j)) tmp /= j, ++ cnt[j];
        }
        if (tmp > 1) ++ cnt[tmp];
    }
    for (int i = 1; i <= n; i ++) (Ans *= (cnt[i] + 1)) %= Mod;
    printf("%lld\n", Ans);

    return 0;
}

Walk and Teleport：记录详情

考虑贪心，每一步的决策代价为 $\min \{ a \times \Delta{dis}, b \}$。

#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;

template <typename T>
inline T read() {
    T x = 0, f = 1; char c = getchar();
    while (!isdigit(c)) { if (c == '-') f = - f; c = getchar(); }
    while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return x * f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read <int> ()
#define readlint read <lint> ()
const int inf = 1e9 + 1e7, MAXN = 1e5 + 1e1;
const lint INF = 1e18 + 1e9;

lint d[MAXN], Ans, a, b;
int n;

int main(void) {

    n = readint, a = readlint, b = readlint;
    for (int i = 1; i <= n; i ++) d[i] = readlint;
    for (int i = 1; i < n; i ++) Ans += min(a * (d[i + 1] - d[i]), b);
    printf("%lld\n", Ans);

    return 0;
}

Grouping：记录详情

考虑设计 dp 转移方程暴力转移，令 $dp_{i, j}$ 表示此时已经选取了 $i$ 个人，并考虑从小到大依次划分到 $j$ 人一组。那么此时我们暴力枚举放置几个 $j$ 人一组，由于我们枚举的是倍数，由调和级数可以证明此时时间复杂度为 $\text{O}(n^2 \cdot \ln{n})$。

转移方程需要使用组合数学内容，大概考虑此时从剩余的 $n - i + j \times k$ 人中选出了 $j \times k$ 人中，并将这 $j \times k$ 人划分成 $k$ 个 $j$ 人一组，那么贡献为 $dp_{i - j \times k, j - 1} \times \dbinom{n - i + j \times k}{j \times k}$。考虑两种方案互不相同是一组内人的编号存在不同，那么我们又可重复元素排列数 $\frac{(j \times k)!}{(j!) ^ k}$ 得到启发，再对排列去重即除上 $k!$。具体转移方程为

$dp_{i,j} = dp_{i - j \times k, j - 1} \times \dbinom{n - i + j \times k}{j \times k} \times \frac{(j \times k)!}{(j!) ^ k \times k !}$

#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;

template <typename T>
inline T read() {
    T x = 0, f = 1; char c = getchar();
    while (!isdigit(c)) { if (c == '-') f = - f; c = getchar(); }
    while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return x * f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read <int> ()
#define readlint read <lint> ()
#define Inv(x) Qpow(x, Mod - 2)
const int inf = 1e9 + 1e7, MAXN = 2e3 + 1e1, Mod = 1e9 + 7;
const lint INF = 1e18 + 1e9;

lint fac[MAXN], inv[MAXN], dp[MAXN][MAXN];
int n, a, b, c, d;

lint Qpow(lint A, int B) {
    lint res = 1ll;
    while (B > 0) {
        if (B & 1) (res *= A) %= Mod;
        (A *= A) %= Mod, B >>= 1;
    }
    return res;
}

lint C(int A, int B) { return (A < B ? 0ll : fac[A] * inv[B] % Mod * inv[A - B] % Mod); }

int main(void) {
  
    scanf("%d%d%d%d%d", &n, &a, &b, &c, &d);
    fac[0] = dp[0][a - 1] = 1ll;
    for (int i = 1; i <= n; i ++) fac[i] = fac[i - 1] * i % Mod;
    inv[n] = Inv(fac[n]);
    for (int i = n; i; i --) inv[i - 1] = inv[i] * i % Mod;
    for (int i = 0; i <= n; i ++) for (int j = a; j <= b; j ++) {
        dp[i][j] = dp[i][j - 1];
        for (int k = c; j * k <= i && k <= d; k ++) {
            (dp[i][j] += dp[i - j * k][j - 1] * C(n - i + j * k, j * k) % Mod * fac[j * k] % Mod * Qpow(inv[j], k) % Mod * inv[k] % Mod) %= Mod;
        }
    }
    printf("%lld\n", dp[n][b]);

    return 0;
}

Yakiniku Restaurants：记录详情

考虑贪心，假定我们知道了要去到的烧烤店在区间 $[l,r]$ 中且 $l,r$ 必定要去，那么走路的代价一定是从 $l$ 走到 $r$，然后对每一张券单独考虑，贡献则是在 $[l,r]$ 中的最大值之和。暴力做的复杂度为 $\text{O}(n^2 \cdot m)$。

考虑优化，我们把一个点 $b_{i,j}$ 的贡献单独考虑，一定是在向左第一个比他大的位置 $pre$ 和向右第一个比他大的位置 $nxt$，那么一次操作的左端点在中 $(pre,i]$ 且右端点在 $[i,nxt)$ 时，贡献为 $b_{i,j}$；那么我们可以先把所有的操作产生的贡献二维差分，然后最后记下前缀和统计答案。时间复杂度为 $\text{O}(n ^ 2)$。

#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;

template <typename T>
inline T read() {
    T x = 0, f = 1; char c = getchar();
    while (!isdigit(c)) { if (c == '-') f = - f; c = getchar(); }
    while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return x * f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read <int> ()
#define readlint read <lint> ()
const int inf = 1e9 + 1e7, MAXN = 5e3 + 1e1, MAXM = 2e2 + 1e1;
const lint INF = 1e18 + 1e9;

lint a[MAXN][MAXN], b[MAXM][MAXN], d[MAXN], Ans;
int pre[MAXN], nxt[MAXN], n, m;

void Add(int x0, int y0, int x1, int y1, lint k) {
    a[x0][y0] += k, a[x1 + 1][y1 + 1] += k, a[x0][y1 + 1] -= k, a[x1 + 1][y0] -= k;
    return ;
}

int main(void) {

    n = readint, m = readint;
    for (int i = 2; i <= n; i ++) d[i] = d[i - 1] + readlint;
    for (int j = 1; j <= n; j ++) for (int i = 1; i <= m; i ++) b[i][j] = readlint;
    for (int i = 1; i <= m; i ++) {
        for (int j = 1; j <= n; j ++) pre[j] = nxt[j] = j;
        for (int j = 1; j <= n; j ++) for (; pre[j] > 1 && b[i][pre[j] - 1] < b[i][j]; pre[j] = pre[pre[j] - 1]) ;
        for (int j = n; j; j --) for (; nxt[j] < n && b[i][nxt[j] + 1] <= b[i][j]; nxt[j] = nxt[nxt[j] + 1]) ;
        for (int j = 1; j <= n; j ++) Add(pre[j], j, j, nxt[j], b[i][j]);
    }
    for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) {
        a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
        if (i <= j) Ans = max(a[i][j] - d[j] + d[i], Ans);
    }
    printf("%lld\n", Ans);

    return 0;
}