LibreOJ#6374. 「SDWC2018 Day1」网格 – 题解

主要思路

容斥好题!

我们先不考虑 \(k\) 个非法向量的事。先考虑分两维做掉那个跳跃限制,再做掉不动的情况。

对于一维的跳跃限制,以 \(x\) 轴为例,可以做成一个组合数的容斥:

\[ \text{设} f(i) \text{为至少有} i \text{步超过了跳跃限制} \\ f(i) = {R \choose i} {T_x – i(Mx + 1) + R – 1 \choose R – 1} \\ ans_x = \sum_{i = 0}^R (-1)^i f(i) \]

继续阅读LibreOJ#6374. 「SDWC2018 Day1」网格 – 题解

BZOJ 4671:异或图题解

主要思路

我们发现,直接算一个连通块非常的困难。这个时候可以尝试容斥。我们发现至少一个的特别好算:划分至少\(i\)个连通块的答案记为\(g(i)\)。\(g(i)\)比较好算,可以考虑 DFS 枚举出每一个点所在的连通块根,然后把连通情况放入线性基中,如果线性基插入失败,那么说明当前的情况不能被表示出,且该状态符合划分,那么计入小答案\(tot\),最后对答案的贡献就是:\(2^{tot}\)。

现在考虑如何用\(g(i)\)算恰好\(i\)个连通块的答案\(f(i)\)。考虑搞下容斥系数,使得\(f(i)\)只被计算一次:

\[ \sum_{i = 1}^n \begin{Bmatrix} n \\ i \end{Bmatrix} coefficient(i) = [n = 1] \]

打表出来就是:

\[ coefficient(i) = (-1)^{i – 1} (i – 1)! \]

继续阅读BZOJ 4671:异或图题解

BZOJ4665:小 w 的喜糖题解

解法

这道题是 DP + 容斥,正好是我不怎么会的类型。设状态\(f[i][j]\)为「考虑了前\(i\)个状态之后有\(j\)个颜色与原来一样的方案数(注意这里颜色不一样不是本质不同的)」。可以推出式子:

\[ dp[i][j] = \sum_{k = 0}^j dp[i – 1][j – k] {cnt[i] \choose k} \frac{cnt[i]!}{(cnt[i] – k)!} \]

继续阅读BZOJ4665:小 w 的喜糖题解

Codeforces Round #548 (Div. 2) 解题报告 (CF1139)

A – Even Substrings

很简单,扫描的时候如果所在数位为偶数位,向答案添加当前数位即可。

// A.cpp
#include <bits/stdc++.h>
using namespace std;
char str[66000];
int main()
{
    int ans = 0, len;
    scanf("%d", &len), scanf("%s", str + 1);
    for (int i = 1; i <= len; i++)
        if (((str[i] - '0') & 1) == 0)
            ans += i;
    printf("%d", ans);
    return 0;
}

继续阅读Codeforces Round #548 (Div. 2) 解题报告 (CF1139)