Exqule Forever

Nothing with me, but Forever.

ARC068 写题记录

发布于 2020-10-14 | 分类于 贪心 、 组合数学 、 计数dp 、 调和级数 、 差分 、 计数 、 树状数组 、 动态规划 | 12分钟 | 2305字数 | 浏览量：

[ARC068]写题记录

X: Yet Another Die Game：记录详情

题意看了好久才懂。

大概考虑每次翻转一定是 5,6 之间来还转动，那么每两次的贡献值为 11，特判一下最后需要得分为 0，或小于等于 6，或大于 6。

#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;
const lint INF = 1e18 + 1e9;

lint F(lint X) {
    return (X > 0 ? (X > 6 ? 2 : 1) : 0);
}

int main(void) {

    lint X = readlint;
    printf("%lld\n", (X / 11) * 2 + F(X % 11));

    return 0;
}

Card Eater：记录详情

大概考虑对于同一种权值的卡牌，如果他的数量为奇数，那么一定能够经过操作使得数量为 1；如果他的数量为偶数，那么一定能够经过操作使得数量为 2。最后我们统计一下卡牌数为偶数的数量 cntcnt。

如果这个数为偶数，那么一定可以不损失任何的非配对卡牌来达到目的状态；否则，即使我们会多失去一张卡牌作为代价来达到目的状态，但是这也是必不可少的。（从奇偶性的角度考虑，我们发现我们必然会删去偶数个数的牌数，而实际上我们必要删去的卡牌数为奇数，那么意味着必然会多删去一张卡牌作为代价。）

#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, Tp = 1e5;
const lint INF = 1e18 + 1e9;

int a[MAXN], n, cnt, Ans;

int main(void) {

    n = readint;
    for (int i = 1; i <= n; i ++) ++ a[readint];
    for (int i = 1; i <= Tp; i ++) {
        if (a[i] & 1) ++ Ans;
        else if (a[i]) ++ cnt;
    }
    if (cnt & 1) -- Ans;
    printf("%d\n", Ans + cnt);

    return 0;
}

Snuke Line：记录详情

考虑一个必要的观察：对于一个商品能在车站 [l,r][l,r] 中售卖，必然使得编号为 [1,r−l+1][1,r-l+1] 的列车能够的得到贡献；否则对于编号大于 r−l+1r-l+1 的列车，该区间 [l,r][l,r] 中的所有数，至多仅有一个车站使得售卖该商品。

那么我们考虑把一个车站拆分成两个部分予以计入贡献。对于 [1,r−l+1][1,r-l+1] 的部分考虑使用差分数组预处理，在遍历列车编号时累计加入；对于大于 r−l+1r-l+1 的部分，考虑对于所有的区间 [li,ri][l_i,r_i] 按照区间长度从小到大排序，如果当前遍历的车站编号大于此时指针所在的 ri−li+1r_i-l_i+1 时，我们就把其以区间修改的形式加入序列。每次统计当前列车编号的答案，考虑枚举该编号的倍数求和（区间修改，单点查询，树状数组维护差分序列），并加上此时差分数组的权值。（之所以能够直接枚举编号的倍数求和的正确性，是因为对于每一个区间 [l,r][l,r] 中最多会有 1 个车站会产生 1 的贡献）显然发现枚举倍数的总数为调和级数，所以总的时间复杂度为 O(nlog⁡2n)\text{O}(n \log ^2 n)。（此处视 n,mn,m 同级别）

#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
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 lowbit(x) (x & -x)
const int inf = 1e9 + 1e7, MAXN = 3e5 + 1e1;
const lint INF = 1e18 + 1e9;

struct Node {
    int l, r;
    bool friend operator <(const Node &A, const Node &B) {
        return (B.r - B.l > A.r - A.l);
    }
} c[MAXN];
int a[MAXN], b[MAXN], n, m, cur, tmp, pos = 1;

void Modify(int p, int w) {
    for (int i = p; i <= m; i += lowbit(i)) b[i] += w;
    return ;
}

int Query(int p) {
    int res = 0;
    for (int i = p; i; i -= lowbit(i)) res += b[i];
    return res;
}

int main(void) {

    n = readint, m = readint;
    for (int i = 1; i <= n; i ++) c[i].l = readint, c[i].r = readint;
    for (int i = 1; i <= n; i ++) ++ cur, --a[c[i].r - c[i].l + 2];
    sort(c + 1, c + n + 1);
    for (int i = 1; i <= m; i ++) {
        cur += a[i], tmp = 0;
        while (pos <= n && i >= c[pos].r - c[pos].l + 2) {
            Modify(c[pos].l, 1), Modify(c[pos ++].r + 1, -1);
        }
        for (int j = 1; j * i <= m; j ++) tmp += Query(j * i);
        printf("%d\n", tmp + cur);
    }
    return 0;
}

Solitaire：记录详情

考虑现在构造的序列是否合法，当且仅当存在一个三元上升子序列则为不合法。然而容斥后考虑这件事容易计数重复，此时一个重要的观察就是如果此时已经填好的删除序列中的前 kk 个，那么一定是两个容许交错的下降子序列。考虑我们使得构造删除序列中前 kk 个数，而后的数任意选择，那么显然贡献为 2n−k−12^{n-k-1}（考虑剩余元素从队首或队尾出队，最后出队的元素两种方式等价）。那么意味着对于删除序列的第 kk 个之后的数，一定不能大于此前序列的最大值，这个充分的条件从侧面规定了我们对于前 kk 个数的选择。那么我们考虑对于前 kk 个数进行 dp 计数，另一个重要的结论则是不论序列如何构成，我们一定存在方案使得他可以表示为 {a},{b}\{a\},\{b\} 两个序列满足 {a}\{a\} 中任何时候的最小元素一定小于 {b}\{b\} 中。此时考虑令 dpi,jdp_{i,j} 表示此时选到第 ii 位，此时 {a}\{a\} 序列中最小值为 jj。由于我们并不关注此时的具体选择，我们只关心状态转移之间的数量，那么显然有转移方程

dpi,j=dpi−1,j+∑l=jkdpi−1,ldp_{i,j} = dp_{i-1,j} + \sum_{l = j}^{k} dp_{i - 1,l}

不过注意到几个边界的处理，满足 j≤n−i+1j \leq n - i + 1 并且当 j=1j = 1 时 dpi−1,jdp_{i-1,j} 对 dpi,jdp_{i,j} 不产生贡献（此时我们已经找到了 1）。时间复杂度为 O(n⋅k)\text{O}(n \cdot 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> ()
const int inf = 1e9 + 1e7, MAXN = 2e3 + 1e1, Mod = 1e9 + 7;
const lint INF = 1e18 + 1e9;

lint dp[MAXN], Ans;
int n, k;

int main(void) {

    n = readint, k = readint, dp[0] = Ans = 1;
    for (int i = 1; i < n - k; i ++) (Ans *= 2) %= Mod;
    for (int i = 1; i <= k; i ++) for (int j = i; j < n; j ++) (dp[j] += dp[j - 1]) %= Mod;
    printf("%lld\n", dp[n - 1] * Ans % Mod);

    return 0;
}

然后我们可以发现一个可观的方式优化 dp 转移，大概把 dpi,jdp_{i,j} 的转移方程视为从 (0,0)(0,0) 到 (n,k)(n,k) 的路径满足不穿过对角线且不存在由 dpn,k−1dp_{n,k-1} 到 dpn,kdp_{n,k} 的方案数。前一部分限制可以考虑使用卡塔兰数的组合意义，然后后一部分可以容斥一下到 (n,k)(n,k) 的路径数减去到 (n,k−1)(n,k - 1) 的路径数。时间复杂度为 O(n)\text{O}(n) 。

#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 = 2e5 + 1e1, Mod = 1e9 + 7;
const lint INF = 1e18 + 1e9;

lint fac[MAXN], inv[MAXN], Ans;
int n, k;

lint Qpow(lint A, int B) {
    lint res = 1;
    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 ? 0 : fac[A] * inv[B] % Mod * inv[A - B] % Mod); }

lint Catalan(int A, int B) { return (C(A + B - 1, A) - C(A + B - 1, A + 1) + Mod) % Mod; }

int main(void) {

    n = readint, k = readint, fac[0] = 1;
    for (int i = 1; i <= n + k; i ++) fac[i] = fac[i - 1] * i % Mod;
    inv[n + k] = Inv(fac[n + k]), Ans = Qpow(2, n - k - 1);
    for (int i = n + k; i; i --) inv[i - 1] = inv[i] * i % Mod;
    (Ans *= (Catalan(n, k) - Catalan(n, k - 1) + Mod) % Mod) %= Mod;
    printf("%lld\n", Ans);

    return 0;
}
# 贪心 # 组合数学 # 计数dp # 调和级数 # 差分 # 计数 # 树状数组 # 动态规划
2020/10/14 随笔 上一篇
2020/10/13 随笔 下一篇
0%