(旧存档) 2019年上海ICPC网络赛总结

B. Light bulbs

题意： 有一个布尔数组 $ A_{n}$ ，下标从 $0$ 开始，有 $m$ 个操作，每个操作要求对区间 $[l,r]$ 取反，操作完成，输出区间 $[0,n-1]$ 中 $1$ 的个数。

范围： 有多组数据 $T$ 。$ 1\le T \le 1000 ,1 \le n \le 10^{6},1\le m \le 1000 $

限制： 时限：$1000ms$，内存：$8192K$

解法： 那么小的内存显然不能使用线段树维护区间。由于操作次数 $m$ 小于1000, 可以离散化后统计区间中 1 的个数， 时间复杂度 $O(TMlogM)$ 。

代码一： 使用map离散化(755 ms)

#include <cstdio>
#include <map>

using namespace std;
const int N = 1005;

int main() {
    int t;
    scanf("%d", &t);
    map<int, int> s;
    for (int k = 1; k <= t; ++k) {
        int n, m;
        s.clear();
        scanf("%d%d", &n, &m);
        for (int i = 0; i < m; ++i) {
            int l, r;
            scanf("%d%d", &l, &r);
            s[l] ^= 1, s[r + 1] ^= 1;
        }
        int state = 0, ans = 0;
        int last = 0;
        for (auto& p: s) {
            if(!p.second) continue;
            if (state) ans += p.first - last;
            else last = p.first;
            state = !state;
        }
        printf("Case #%d: %d\n", k, ans);
    }
    return 0;
}

代码二： 数组离散化+bitset（544 ms)

#include <cstdio>
#include <algorithm>
#include <bitset>

using namespace std;
const int N = 1005;

struct query {
    int l, r;
} q[N];

int a[N << 1];
bitset<N << 1> b;

int main() {
    int t;
    scanf("%d", &t);
    for (int k = 1; k <= t; ++k) {
        int n, m, tot = 0;
        b.reset();
        scanf("%d%d", &n, &m);
        for (int i = 0; i < m; ++i) {
            scanf("%d%d", &q[i].l, &q[i].r), ++q[i].r;
            a[tot++] = q[i].l, a[tot++] = q[i].r;
        }
        sort(a, a + tot);
        tot = unique(a, a + tot) - a;
        for (int i = 0; i < m; ++i) {
            int l = lower_bound(a, a + tot, q[i].l) - a + 1;
            int r = lower_bound(a, a + tot, q[i].r) - a + 1;
            b[l].flip();
            b[r].flip();
        }
        int j = 0, state = 0, ans = 0;
        for (int i = 0; i <= tot; ++i) {
            if (!b[i]) continue;
            if (state) ans += a[i - 1] - a[j - 1];
            else j = i;
            state = !state;
        }
        printf("Case #%d: %d\n", k, ans);
    }
    return 0;
}

D. Counting Sequences I

题意： 有一个数组 $a_{n}$ $(n\ge2)$ ，下标从 $1$ 开始， 问你满足：$a_1+a_2+ …+a_n = a_1 \times a_2 \times … \times a_n$ 的数组 $a_n$ 的个数。

范围： 有多组数据 $T$ 。$1\le T \le 300 ,1 \le n \le 3000$

限制： 时限：$1000ms$，内存：$8192K$

解法一： 离线打表即可 (这个表，还是不是很好打滴），如果先不选择 $1$, 考虑选中了其他 $x$ 个数， 其乘积为 $mul$ , 和为 $sum$ ， 那么添加 $mul - sum$ 个 $1$ 后，有 $a_1+a_2+ …+a_n = a_1 \times a_2 \times … \times a_n$ 。那么考虑搜索的算法，当 $mul - sum$ 已经大于可以使用的 $1$ 的数量时剪枝。（可行性剪枝）

打表代码：（数据生成用时 13s)

#include <cstdio>
#include <chrono>

using namespace std;
using namespace chrono;
typedef long long ll;
const int N = 3005;
const ll MOD = 1e9 + 7;
int cnt[N], n;
ll inv_fac[N], fac[N], ans;

ll quick_pow(ll a, ll p) {
    ll res = 1;
    while (p) {
        if (p & 1) res = res * a % MOD;
        a = a * a % MOD;
        p >>= 1;
    }
    return res;
}

inline ll inv(int a) {
    return quick_pow(a, MOD - 2);
}

void dfs(int now, int pos, ll sum, ll mul) {
    int len = now + (mul - sum);
    if (len > n) return;
    if (len == n) {
        ll res = fac[n];
        for (int i = 2; i < N; ++i) {
            if (cnt[i]) {
                res = res * inv_fac[cnt[i]] % MOD;
            }
        }
        res = res * inv_fac[mul - sum] % MOD;
        ans = (ans + res) % MOD;
        return;
    }
    for (int i = pos; i >= 2; --i) {
        ++cnt[i];
        dfs(now + 1, i, sum + i, mul * i);
        --cnt[i];
    }
}

void init() {
    freopen("C:\\output\\out.txt", "w", stdout);
    fac[0] = 1, inv_fac[0] = inv(fac[0]);
    for (int i = 1; i < N; ++i) {
        fac[i] = fac[i - 1] * i % MOD;
        inv_fac[i] = inv(fac[i]);
    }
}

int main() {
    auto t1 = steady_clock::now();
    init();
    for (n = 1; n < N; ++n) {
        ans = 0;
        dfs(0, n, 0, 1);
        printf("%lld,", ans);
    }
    auto t2 = steady_clock::now();
    printf("\n%fms\n", (t2 - t1).count() / 1e6);
    return 0;
}

解法二： 离线查询 + 剪枝搜索。注意到上述打表代码对某个询问 $n$ 的dfs过程中，实际上会出现其他的满足条件的解，而以上的暴力算法并没有统计这些解，在下一次遇到这些解还得重新计算。因此，我们可以统计所有在结果中出现的解，这样下次可以不必再次dfs计算，一次dfs便得到所有结果。

代码二： dfs 处理所有的值 (145 ms)

#include <cstdio>

using namespace std;
typedef long long ll;

const int N = 3005;
const ll MOD = 1e9 + 7;
ll inv_fac[N], fac[N], ans[N], cnt[N];

ll quick_pow(ll a, ll p) {
    ll res = 1;
    while (p) {
        if (p & 1) res = res * a % MOD;
        a = a * a % MOD;
        p >>= 1;
    }
    return res;
}

inline ll inv(int a) {
    return quick_pow(a, MOD - 2);
}

void dfs(int now, int pos, ll sum, ll mul) {
    int len = now + (mul - sum);
    if (len >= N) return;
    if (len > 0) {
        ll res = fac[len];
        for (int i = 2; i < N; ++i) {
            if (cnt[i]) {
                res = res * inv_fac[cnt[i]] % MOD;
            }
        }
        res = res * inv_fac[mul - sum] % MOD;
        ans[len] = (ans[len] + res) % MOD;
    }
    for (int i = pos; i >= 2; --i) {
        ++cnt[i];
        dfs(now + 1, i, sum + i, mul * i);
        --cnt[i];
    }
}

void init() {
    fac[0] = 1, inv_fac[0] = inv(fac[0]);
    for (int i = 1; i < N; ++i) {
        fac[i] = fac[i - 1] * i % MOD;
        inv_fac[i] = inv(fac[i]);
    }
    dfs(0, 3000, 0, 1);
}

int main() {
    init();
    int t, n;
    scanf("%d",&t);
    while(t--) {
        scanf("%d",&n);
        printf("%lld\n", ans[n]);
    }
    return 0;
}

解法三： 可以对解法二进行优化，只处理与询问有关的值。

代码三： dfs 处理与询问有关的值 (26 ms)

#include <cstdio>

using namespace std;
typedef long long ll;
const ll N = 3005, MOD = 1e9 + 7;

int cnt[N], query[N];
bool hasQuery[N];
ll p[N], inv_p[N], res[N];

ll quick_pow(ll a, ll p) {
    ll res = 1;
    while (p) {
        if (p & 1) res = res * a % MOD;
        a = a * a % MOD;
        p >>= 1;
    }
    return res;
}

inline ll inv(ll a) {
    return quick_pow(a, MOD - 2);
}

inline void process_query(int n, ll sum, ll mul) {
    ll ans = p[n];
    for (int i = 2; i < N; ++i) {
        if (cnt[i]) ans = ans * inv_p[cnt[i]] % MOD;
    }
    ans = ans * inv_p[mul - sum] % MOD;
    res[n] = (res[n] + ans) % MOD;
}

void dfs(int now, int pos, ll sum = 0, ll mul = 1) {
    int n = now + (mul - sum);
    if (n >= N) return;
    if (n > 0 && hasQuery[n]) process_query(n, sum, mul);
    for (int i = pos; i >= 2; --i) {
        ++cnt[i];
        dfs(now + 1, i, sum + i, mul * i);
        --cnt[i];
    }
}

inline void init() {
    p[0] = 1, inv_p[0] = inv(p[0]);
    for (int i = 1; i < N; ++i) {
        p[i] = i * p[i - 1] % MOD;
        inv_p[i] = inv(p[i]);
    }
}

int main() {
    init();
    int t, x;
    scanf("%d", &t);
    for (int i = 1; i <= t; ++i) {
        scanf("%d", &x);
        hasQuery[x] = 1, query[i] = x;
    }
    dfs(0, N);
    for (int i = 1; i <= t; ++i) {
        printf("%lld\n", res[query[i]]);
    }
    return 0;
}

J. Stone game

题意： 有一个多重数集S, 将S划分为两部分 $S_{1}, S_{2}$ 并且 $Sum(S_{1}) \ge Sum(S_{2})$ && $Sum(S_{1})-Min(S_{1})\le Sum(S_{2})$, 求划分数的个数。

范围： 有多组数据 $T$ 。$1\le T \le 10 ,1 \le n \le 300,1\le a_{i} \le 500$

限制： 时限：$3000ms$，内存：$262144K$

解法： 先将数组从大到小排序，然后进行$dp$。设 $dp[i][j]$ 表示以 $a[i]$ 为最小值的，和为 $j$ 的集合 $S$ 的个数，那么显然：$dp[i][j] += dp[i-1][j-a[i]]$ 。在 $dp$ 过程中更新答案，过程中 $dp$ 数组第一维可以省略。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <functional>

using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
int a[305];
ll dp[150005];

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        memset(dp, 0, sizeof(dp));
        int n = 0, sum = 0, ans = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            sum += a[i];
        }
        sort(a + 1, a + 1 + n, greater<int>());
        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = (sum - 2 * a[i] + 1) / 2; 2 * j + a[i] <= sum; ++j) {
                ans = (ans + dp[j]) % MOD;
            }
            for (int j = sum - a[i]; j >= 0; --j) {
                dp[j + a[i]] = (dp[j + a[i]] + dp[j]) % MOD;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

L. Digit sum

题意： 求 $[1,n]$中，b进制的数位和

范围： 有多组数据 $T$ 。$1\le T \le 10^{5} ,1 \le n \le 10^{6},1\le b \le 10$

限制： 时限：$2000ms$，内存：$131072K$

解法一： 没看清数据范围，用数位 dp 演了一发，实际上暴力就好 $qaq$。

代码一：

#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;
const int N = 32, BASE = 15;
ll dp[N][2][10][BASE];
int a[N];


ll dfs(int pos, int state, bool lead, bool limit, int x, int base) {
    if (pos == -1) return state;
    int up = limit ? a[pos] : base - 1;
    if (!lead && !limit && dp[pos][state][x][base] != -1) return dp[pos][state][x][base];
    long ans = 0;
    for (int i = 0; i <= up; ++i) {
        if (state == 0) {
            if (lead && i == 0) {
                ans += dfs(pos - 1, 0, true, limit && i == up, x, base);
            } else if (i == x) {
                ans += dfs(pos - 1, 1, false, limit && i == up, x, base) +
                       dfs(pos - 1, 0, false, limit && i == up, x, base);
            } else {
                ans += dfs(pos - 1, 0, false, limit && i == up, x, base);
            }
        } else {
            ans += dfs(pos - 1, 1, lead && i == 0, limit && i == up, x, base);
        }
    }
    if (!lead && !limit) return dp[pos][state][x][base] = ans;
    return ans;
}

ll solve(ll n, int x, int base) {
    int tot = 0;
    while (n != 0) {
        a[tot++] = (int) (n % base);
        n /= base;
    }
    return dfs(tot - 1, 0, true, true, x, base);
}

int main() {
    int t;
    scanf("%d", &t);
    memset(dp, -1, sizeof(dp));
    for (int k = 1; k <= t; ++k) {
        int base, n;
        scanf("%d%d", &n, &base);
        ll sum = 0;
        for (int i = 0; i < base; ++i) {
            sum += solve(n, i, base) * i;
        }
        printf("Case #%d: %lld\n", k, sum);
    }
    return 0;
}

解法二： 暴力… …

代码二：

#include <cstdio>

typedef long long ll;
const int N = 1e6 + 5;
ll ans[N][15];

int resolve(int x, int base) {
    int ans = 0;
    while (x) {
        ans += x % base;
        x /= base;
    }
    return ans;
}

void init() {
    for (int i = 1; i <= 1e6; ++i) {
        for (int base = 2; base <= 10; ++base) {
            ans[i][base] += ans[i - 1][base] + resolve(i, base);
        }
    }
}

int main() {
    init();
    int t;
    scanf("%d", &t);
    for (int i = 1; i <= t; ++i) {
        int n, base;
        scanf("%d%d", &n, &base);
        printf("Case #%d: %lld\n", i, ans[n][base]);
    }
    return 0;
}