趁今天有空补一下前面鸽了的题解

某神仙学弟说他们学校在测雅礼day1,可是只做了一天雅礼就跑去做别的了,所以我就去蹭了一下数据(

T1 养花

小C在家种了n盆花,每盆花有一个艳丽度ai,在接下来的m天中,每天早晨他会从一段编号连续的花中选择一盆摆放在客厅, 并在晚上放回. 同时每天有特定的光照强度ki,,如果这一天里摆放在客厅的花艳丽度为x,则他能获得的喜悦度为x mod ki。

他希望知道, 每一天他能获得的最大喜悦度是多少。n,m<=10^5

真是一道分块神题。

首先考虑我们可不可以对于一段区间把它膜1~1e5的所有最大值给求出来。

乍一想可能不行,可是仔细想想,我们可以将这段区间的花的艳丽度按权值桶排,并且令
$f[i]$表示艳丽值小于等于i的最大值是多少,那么我们再令$g[i]$表示这段区间被i膜的最大值,那么我们有$g[i]=max(f[i\times j-1] \% i)(1 \leq j \&\& i \times j \leq 1e5)$
显然算g数组是调和级数的复杂度。

然而我们是随便查询区间哦,那样岂不是复杂度还要乘个m?

我们可以分块处理,查询区间的时候合并块就行,相当于一种meet in the middle的思想。

复杂度:$O(m\times sq + up\times nlogn), sq\times up = n$

#include<bits/stdc++.h> 
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 100005
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mod 998244353
int n, m, sq, up, max[330][N + 5], f[N + 5], bl, br, a[N];
int main ()
{
    scanf("%d %d", &n, &m);
    fo (i, 1, n)
        scanf("%d", &a[i]);
    sq = (int) sqrt(n);
    up = sq + 3;
    fo (i, 1, up)
    {
        int l = (i - 1) * sq + 1, r = i * sq;
        if (l > n) break;
        memset(f, 0, sizeof f);
        fo (i, l, r)
            f[a[i]] = a[i];
        fo (i, 1, N)//一定要弄到值域大小吧不然会gg
            f[i] = std::max(f[i], f[i - 1]);
        fo (j, 1, N)
        {
            for (int k = j - 1; k <= N; k += j)//枚举j的倍数-1!
                max[i][j] = std::max(max[i][j], f[k] - k - 1 + j);//第i个块膜j的最大值
        }
    }
    fo (i, 1, m)
    {
        int l, r, k;
        scanf("%d %d %d", &l, &r, &k);
        bl = (l - 1) / sq + 1;//l所在块
        br = (r - 1) / sq + 1;//r所在块
        int ans = 0;
        if (bl == br || bl + 1 == br)
        {
            fo (i, l, r)
                ans = std::max(ans, a[i] % k);
        }
        else
        {
            ++bl; --br;
            fo (i, bl, br)
                ans = std::max(max[i][k], ans);
            if (ans == k - 1)
            {
                printf("%d\n", ans);
                continue;
            }
            bl = (bl - 1) * sq;//l所在块的结尾
            br = br * sq + 1;//r所在块的开头
            fo (i, l, bl)
                ans = std::max(ans, a[i] % k);
            fo (i, br, r)
                ans = std::max(ans, a[i] % k);
        }
        printf("%d\n", ans);
    }
    return 0;
}

T2:折射

题意好麻烦呀。。。

说白了就是给了你一堆点,让你数这种折线有多少个(严格向下走,并且横坐标之间的差越来越小)

我刚开始想着从上往下扫然后计算贡献,结果会发现你要枚举前两个点才能算贡献,否则不满足横坐标约束条件,这样就三次方的复杂度了,打出gg。

因此我们需要用一种魔法的顺序来计算贡献。

按x排序,考虑当前点为i,从当前点向前枚举j

设$f[i][0/1]$表示前i个点,0为向左下射出的方案数,1为向右下射出的方案数

我们有转移

$$f[i][0] += f[j][1] (y_j \lt y_i)$$
$$f [ j] [ 1 ] += f [ i ] [ 0 ] (y_j \gt y_i)$$

你会发现这样就很巧妙地满足了横坐标的约束。

这说明了有些看似顺序很尴尬的题目,说不定瞎搞搞就能减少一个数量级的复杂度。

#include<bits/stdc++.h> 
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 60005
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mod 1000000007
int n, m, dp[N][2], ans;
struct node{
    int x, y;
    friend bool operator < (node a, node b)
    {
        return a.x < b.x;
    }
}p[N];
int main ()
{
    scanf("%d", &n);
    fo (i, 1, n)
        scanf("%d %d", &p[i].x, &p[i].y);
    std::sort(p + 1, p + n + 1);
    fo (i, 1, n)
    {
        dp[i][0] = dp[i][1] = 1;
        fd (j, i - 1, 1)
            if (p[i].y > p[j].y)
            {
                dp[i][0] = (dp[i][0] + dp[j][1]) % mod;
            }
            else
            {
                dp[j][1] = (dp[i][0] + dp[j][1]) % mod;
            }
    }
    fo (i, 1, n) ans = (ans + (dp[i][0] + dp[i][1] - 1) % mod) % mod;
    printf("%d\n", ans);
    return 0;
}
分类: 文章

quhengyi11

喵(ฅ>ω<*ฅ)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *