BZOJ4361:isn 题解

解法

这道题很有意思。首先搞一个 \(DP\) 来算出不同长度的不降子序列的个数,方程为:

\[ f[i, j] = \sum_{k < i, a_k \leq a_i} f[k, j – 1] \]

发现可以用树状数组优化,所以这里的复杂度为\(O(n^2 \log n)\)。设\(g[i] = \sum_{i = 1} f[i, n]\),考虑对答案的贡献。对于一个\(i\),有\(g[i] * (n – i)!\)种方案做变换,但是考虑这\((n – i)!\)中包含了提前变换完成的可能,也就是在我们从合法序列中删去了合法元素的可能,这样肯定是不行的。考虑进行容斥,贡献就是\(g[i](n-i)! – g[i+1](n – i – 1)!(i + 1)\),表示在这些里选择\(i+1\)个合法元素的方案。

继续阅读BZOJ4361:isn 题解

P2154:[SDOI2009]虔诚的墓主人题解

解法

这道题很有意思啊。如果暴力枚举,答案式子:

\[ans = \sum_{x}^n \sum_{y}^m {up_{x,y} \choose k} {left_{x,y} \choose k} {right_{x,y} \choose k} {down_{x,y} \choose k}\]

其中\(up, left, right, down\)代表上下左右的常青树棵树。如何降低复杂度?

首先,我们可以考虑进行离散化:上下左右只要有为\(0\)的情况是不可能对答案有贡献的。然后,发现空隙中上下的部分:

继续阅读P2154:[SDOI2009]虔诚的墓主人题解

[Fortuna OJ]Mar 4th – Group A 解题报告

A – 漆黑列车载运数个谎言

这道题应该是并查集域的裸题,不讲。

// A.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 200;
int n, m, fa[MAX_N << 2];
int find(int x) { return fa[x] == x ? fa[x] : fa[x] = find(fa[x]); }
void unite(int x, int y) { fa[find(x)] = fa[find(y)]; }
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= 2 * n; i++)
        fa[i] = i;
    while (m--)
    {
        int opt, x, y;
        scanf("%d%d%d", &opt, &x, &y);
        if (opt == 0)
            unite(x, y), unite(x + n, y + n);
        else if (opt == 1 || opt == 2)
            unite(x, y + n), unite(x + n, y);
        else if (find(x) == find(y) || find(x + n) == find(y + n))
            puts("1");
        else
            puts("0");
    }
    return 0;
}

继续阅读[Fortuna OJ]Mar 4th – Group A 解题报告

[Fortuna OJ]绕圈跑题解

思路

好神仙啊。

这道题思路非常的巧妙。答案很容易可以知道,为

\[ ans = \lfloor \sum_{i=1}^{n} \frac{L*C*speed[i]}{maxSpeed*C} \rfloor \]

化简得:

\[ ans = \lfloor \sum_{i=1}^{n} \frac{L*speed[i]}{maxSpeed} \rfloor \]

如果我们统计括号内的实数集和的话,会出现一些只有在计算机上才会出现的恶心误差,所以我们可以考虑分开取整再求和。这里有一个小技巧,对于两个数而言:

\[ \lfloor a – b \rfloor = \begin{cases} \lfloor a \rfloor – \lfloor b \rfloor, a的小数部分 \leq b的小数部分 \\ \lfloor a \rfloor – \lfloor b \rfloor – 1, a的小数部分>b的小数部分 \end{cases} \]

在判断小数部分的时候,我们可以把小数部分之间的大小关系转化为余数之间的大小关系进行判断,答案默认减掉那个取整的1,然后用树状数组补全那些被误删的取整项。

代码

// FOJ2930.cpp
#include <bits/stdc++.h>
#define ll long long
#define lowbit(p) (p & -p)
using namespace std;
const ll MAX_N = 1e5 + 200;
ll n, l, c, spd[MAX_N], mxspd, f[MAX_N], tree[1000100];
void update(int num)
{
    num++;
    while (num <= mxspd)
        tree[num] += 1, num += lowbit(num);
}
ll sum(int num)
{
    num++;
    ll ans = 0;
    while (num)
        ans += tree[num], num -= lowbit(num);
    return ans;
}
int main()
{
    scanf("%lld%lld%lld", &n, &l, &c);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &spd[i]);
    sort(spd + 1, spd + 1 + n), mxspd = spd[n];
    for (int i = 1; i <= n; i++)
        f[i] = (l * spd[i]) / mxspd;
    update((l * spd[1]) % mxspd);
    ll prefix = f[1], ans = 0;
    for (int i = 2; i <= n; i++)
    {
        prefix += f[i];
        ans += i * f[i] - prefix - i;
        update((l * spd[i]) % mxspd);
        ans += sum((l * spd[i]) % mxspd);
    }
    printf("%lld", ans);
    return 0;
}