Codeforces 1174D:Ehab and the Expected XOR Problem 题解

主要思路

这道题还蛮妙的,自己比较顺利的思考出来了。

考虑设置前缀异或和\(\{ S_i \}\),根据异或按位处理的性质,显然对于所有的\(S_i\)都会小于\(2^n\)。最后,我们可以把限制变成:

  • 不存在两个相同的前缀和。
  • 不存在一对前缀和,其异或值为\(x\)。

针对\(x\)的大小关系,我们可以分成两种情况:

  • \(x \geq 2^n\),不存在一对\((S_i, S_j)\)的异或为\(x\),因为存在更高的位并不会被消除。
  • \(x < 2^n\),我们发现每选择一个数作为前缀和,整个\(2^n\)中就会少一个对应的可以被选择的数。所以,我们每次选一个作为\(S_i\)的数时,都要把\(S_i xor \ x\)打标记。

结合一下就可以了。

继续阅读Codeforces 1174D:Ehab and the Expected XOR Problem 题解

「2018泉州国庆集训#3」 – 解题报告

A – 人类基因组

这套题全都是暴力出奇迹系列。

我们枚举一个端点,然后判断以这个点为右端点是否能计入答案。我们把序列做个前缀和\(prefix[]\),然后发现计入答案的条件当且仅当\(prefix[i – n]\)小于等于\([i – n + 1, i]\)的最小值。这样可以保证所有的前缀都能为非负数。

然后用 sb 线段树搞下就行了,太特么傻逼了。

继续阅读「2018泉州国庆集训#3」 – 解题报告

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;
}