P3589:「POI2015」KUR – 题解

主要思路

乍一看很难直接做，我们考虑从那个长度为 \(m\) 的串开始搞，发现每个 \(01\) 都对应的是一个不等式条件：

\[ a(s + i) + b < p \]

其中在 \(m\) 串的位置中为 \(i\)，在 \(S\) 中的位置为 \(s + i\)。列了这么多之后进行区间交，然后发现性质 \(\gcd(a, n) = 1\)，代表 \(ai \bmod n\) 是一一对应的，所以我们求最后的值的个数只需要减去 \([n – m + 1, n – 1]\) 内符合条件的数即可。

代码

// P3589.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6 + 200;

int n, a, b, p, m, ltot;
char str[MAX_N];
pair<int, int> limits[MAX_N << 2];

void create(int l, int r)
{
    if (l <= r)
        limits[++ltot] = make_pair(l, r);
    else
        limits[++ltot] = make_pair(l, n - 1), limits[++ltot] = make_pair(0, r);
}

int main()
{
    scanf("%d%d%d%d%d%s", &n, &a, &b, &p, &m, str);
    int ans = 0;
    for (int i = 0; i < m; i++)
        if (str[i] == '0')
            create((p + n - 1LL * i * a % n) % n, (0LL + n - 1 - 1LL * i * a % n) % n);
        else
            create((n - 1LL * i * a % n) % n, (p + n - 1LL * i * a % n - 1) % n);
    for (int i = 1; i < m; i++)
        create((0LL + b + n - 1LL * a * i % n) % n, (0LL + b + n - 1LL * a * i % n) % n);
    sort(limits + 1, limits + 1 + ltot);
    int tmp = -1;
    for (int i = 1; i <= ltot; i++)
    {
        if (limits[i].first > tmp)
            ans += limits[i].first - tmp - 1, tmp = limits[i].second;
        else
            tmp = max(tmp, limits[i].second);
    }
    printf("%d\n", ans + n - 1 - tmp);
    return 0;
}

P4093:「HEOI2016/TJOI2016」序列 – 题解

主要思路

大概就是要求一个子序列，使得在所有变化中始终长度最长。我们可以考虑分治，讨论变化的点的左右位置，然后用树状数组维护一下即可。

代码

// P4093.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200;

int n, m, ai[MAX_N], mx[MAX_N], mn[MAX_N], dp[MAX_N], nodes[MAX_N], idx[MAX_N];

inline int lowbit(int x) { return x & (-x); }

void update(int x, int d)
{
    for (; x <= n; x += lowbit(x))
        nodes[x] = max(nodes[x], d);
}

void clear(int x)
{
    for (; x <= n; x += lowbit(x))
        nodes[x] = 0;
}

int query(int x, int ret = 0)
{
    for (; x; x -= lowbit(x))
        ret = max(ret, nodes[x]);
    return ret;
}

void solve(int l, int r)
{
    if (l == r)
        return (void)(dp[l] = max(dp[l], 1));
    int mid = (l + r) >> 1;
    solve(l, mid);
    for (int i = l; i <= r; i++)
        idx[i] = i;
    sort(idx + l, idx + mid + 1, [](const int &a, const int &b) { return mx[a] < mx[b]; });
    sort(idx + mid + 1, idx + r + 1, [](const int &a, const int &b) { return ai[a] < ai[b]; });
    for (int i = mid + 1, ptr = l; i <= r; i++)
    {
        while (ptr <= mid && mx[idx[ptr]] <= ai[idx[i]])
            update(ai[idx[ptr]], dp[idx[ptr]]), ptr++;
        dp[idx[i]] = max(dp[idx[i]], query(mn[idx[i]]) + 1);
    }
    for (int i = mid + 1, ptr = l; i <= r; i++)
        while (ptr <= mid && mx[idx[ptr]] <= ai[idx[i]])
            clear(ai[idx[ptr]]), ptr++;
    solve(mid + 1, r);
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]), mx[i] = mn[i] = ai[i];
    for (int i = 1, x, y; i <= n; i++)
        scanf("%d%d", &x, &y), mx[x] = max(mx[x], y), mn[x] = min(mn[x], y);
    solve(1, n);
    int ans = *max_element(dp + 1, dp + 1 + n);
    printf("%d\n", ans);
    return 0;
}

BZOJ5093:「Lydsy1711月赛」图的价值 – 题解

主要思路

算是个简单题吧。

首先列个暴力式子：

\[ \sum_G \sum_{i = 1}^n d_i^k \]

发现很不现实。我们考虑把点拆开来考虑，因为全集里面可以直接独立的来算。考虑某个点度数为 \(x\) 的方案数，就变成了：

\[ n \sum_{x = 0}^{n – 1} x^k f(x) \]

其中 \(f(x)\) 代表的是一个图某个点的度数为 \(x\) 的方案数。其实稍微思考下就知道，我们可以把这个点剥离出来，强制连边之后再生成一个图即可：

\[ \begin{aligned} f(x) &= {n – 1 \choose x} 2^{n – 1 \choose 2} \\ ans &= n \sum_{x = 0}^{n – 1} x^k {n – 1 \choose x} 2^{n – 1 \choose 2} \\ &= n2^{n – 1 \choose 2} \sum_{x = 0}^{n – 1} x^k {n – 1 \choose x} \end{aligned} \]

Continue reading →