趁今天有空补一下前面鸽了的题解
某神仙学弟说他们学校在测雅礼 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;
}
0 条评论