Kalorona

P3924:康娜的线段树题解

思路

这道题很好，很有趣。

如果您是神仙的话呢，可以考虑直接线段是卡掉本题（有人试过了），但是我这个菜鸡不行，所以写了题解的\(O(1)\)询问解法。

首先，树形 DP 的方程为：

\[ dp[u] = \frac{1}{2} * (dp[lson]+dp[rson]) \]

我们观察叶子节点对答案的贡献，发现为该条链上的权值和除掉\(2^{dep-1}\)，也就是与深度有关。那么，为了简化答案，我们可以把这个写作：

\[ \frac{1}{2^{dep-1}} = 2^{1-dep} = \frac { 2^{maxDep – dep} }{ 2^{maxDep-1} } \]

就变成了乘法形式。我们在讨论询问的问题。在区间\([l,r]\)之间加上\(x\)，链对答案的贡献是：

\[ x · \sum_{i = 1}^{dep} \frac{1}{2^{i-1}} \]

所以，维护一个前缀和，往答案上面加上前缀和段和这个贡献的积即可获得答案。（记得用 gcd 约分）

代码

// P3924.cpp
#include <bits/stdc++.h>
#define ll long long
#define mid ((l + r) >> 1)
#define lson (p << 1)
#define rson ((p << 1) | 1)
using namespace std;
const int MAX_N = 1e6 + 2000;
ll n, m, qwq, sum[MAX_N << 2], depth[MAX_N << 2], arr[MAX_N], s[MAX_N], max_dep;
inline ll read()
{
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}
void build(ll l, ll r, ll dp, ll p)
{
    if (l == r)
    {
        sum[p] = arr[l], depth[l] = dp, max_dep = max(max_dep, dp);
        return;
    }
    build(l, mid, dp + 1, lson), build(mid + 1, r, dp + 1, rson);
    sum[p] = sum[lson] + sum[rson];
}
ll query(ll l, ll r, ll p, ll dep, ll prefix)
{
    if (l == r)
        return (1 << dep) * (prefix + sum[p]);
    return query(l, mid, lson, dep - 1, prefix + sum[p]) + query(mid + 1, r, rson, dep - 1, prefix + sum[p]);
}
ll gcd(ll a, ll b) { return (b == 0) ? a : gcd(b, a % b); }
int main()
{
    n = read(), m = read(), qwq = read();
    for (int i = 1; i <= n; i++)
        arr[i] = read();
    build(1, n, 1, 1);
    ll ans = query(1, n, 1, max_dep - 1, 0), dominator = 1 << (max_dep - 1);
    ll fact = gcd(dominator, qwq);
    dominator /= fact, qwq /= fact;
    for (int i = 1; i <= n; i++)
        s[i] = s[i - 1] + (((1 << depth[i]) - 1) << (max_dep - depth[i]));
    while (m--)
    {
        ll l = read(), r = read(), w = read();
        ans += (s[r] - s[l - 1]) * w;
        printf("%lld\n", ans / dominator * qwq);
    }
    return 0;
}

Educational DP Contest : M – Candies 题解

主要思路

我这个傻逼还搞个多重集容斥恶心自己。

首先分析题意，不难想出转移方程：

\[ dp[i][j] = dp[i-1][j]+\sum_{k = limit[i]}^{j} dp[i-1][k] \]

然后考虑用\(O(n)\)的时间先预处理出前缀和\(dp[i-1][k-1]\)，然后大的减小的\(O(1)\)查询即可。

代码

// M.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 110, MAX_K = 1e5 + 200, MOD = 1e9 + 7;
ll n, limit[MAX_N], dp[MAX_N][MAX_K], k, mxk, prefix[MAX_K];
int main()
{
    scanf("%lld%lld", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &limit[i]), dp[i][0] = 1;
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        prefix[i] = 0;
        for (int j = 1; j <= k + 1; j++)
            prefix[j] = prefix[j - 1] + dp[i - 1][j - 1];
        for (int j = 1; j <= k; j++)
        {
            dp[i][j] = dp[i - 1][j] + prefix[j] - prefix[max(0LL, j - limit[i])];
            dp[i][j] %= MOD;
        }
    }
    printf("%d", dp[n][k]);
    return 0;
}

「Fortuna OJ」Feb 16th – Group B 解题报告

A – Binary & B – Chess

傻逼题，不分析。

C – Sum

这道题非常的有趣（精心调参之后随机化程序可以拿 90 分），正解非常的巧妙。我们可以把问题化为求\(min\{ S_{i,j} \mod P, K \leq S_{i,j} \mod P\}\)。我们先用\(O(n)\)的时间来进行前缀和的预处理，之后我们倒序处理前缀和，从后往前加入 set。在加入 set 的过程中二分查找\(s[i]+k\)和\(s[i]+k-p\)这两个目标最优解，之后记录答案即可，非常的巧妙。

// C.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 100010;
int n, k, p, ans = 0x7f7f7f7f, s[MAX_N];
set<int> st;
int main()
{
    scanf("%d%d%d", &n, &k, &p);
    for (int i = 1; i <= n; i++)
        scanf("%d", &s[i]), (s[i] += s[i - 1]) %= p;
    set<int>::iterator it;
    st.insert(s[n]);
    for (int i = n - 1; i >= 1; i--)
    {
        it = st.lower_bound(s[i] + k);
        if (it != st.end())
            ans = min(*it - s[i], ans);
        it = st.lower_bound(s[i] + k - p);
        if (it != st.end() && *it < s[i])
            ans = min(*it - s[i] + p, ans);
        st.insert(s[i]);
    }
    printf("%d", ans);
    return 0;
}

D – Jail

哦，傻逼题。——crazydave

这道题算是套路吧，用状态压缩枚举每一维符号的状态，求出最大最小值，最大值减去最小值（最小值代表着状态相反的曼哈顿贡献）即可。

// D.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1000010;
int n, d, info[MAX_N][6], st[10], ans;
void calc(int stat)
{
    int mn = (1 << 29), mx = -mn;
    for (int i = 1; i <= d; i++, stat >>= 1)
        st[i] = stat & 1;
    for (int i = 1; i <= n; i++)
    {
        int acc = 0;
        for (int j = 1; j <= d; j++)
            acc += (st[j] == 1) ? info[i][j] : -info[i][j];
        if (acc != 0)
            mn = min(mn, acc), mx = max(mx, acc);
    }
    ans = max(mx - mn, ans);
}
int main()
{
    scanf("%d%d", &n, &d);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= d; j++)
            scanf("%d", &info[i][j]);
    for (int i = 0; i < (1 << d); i++)
        calc(i);
    printf("%d", ans);
    return 0;
}