题目
问题描述
当我们在LED屏幕上显示一个字符串时，显示不同的字符可能会有不同的能耗。给定一个长度为 n 的字符串 S，由小写英文字母和每个字母的能量消耗组成。假设一个字符串的能量消耗是它所有字符能量消耗的总和。请找出 S 的所有不同子串的第 k 个最小能量消耗。
请注意，字符串 S 的子串是 S 的连续子序列。如果两个字符串 S 和 T 的长度不同，或者至少存在一个满足 S[i]≠T[i] 的位置 i，我们就说这两个字符串 S 和 T 不同。
输入
输入的第一行包含一个整数T（1≤T≤2×103）—测试用例的数量。
每个测试用例的第一行包含两个整数 n (1≤n≤105) 和 k (1≤k≤n(n+1)2)。
每个测试用例的第二行包含一个由小写英文字母组成的长度为 n 的字符串 S。
每个测试用例的第三行包含26个整数ca,cb,…,cz (1≤cα≤100)—每个字母的能量消耗。
保证所有测试用例中n的总和不超过8×105。
输出
对于每个测试用例，在单独的行中输出一个整数 — 第 k 最小的能量消耗，如果没有答案，则为 -1。
样本输入
2
5 5
ababc
3 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 15
ababc
3 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
样本输出
4
-1
解题思路
二分答案，然后使用任意一种后缀数据结构 check 即可。
如何 check？
后缀数组：所有后缀的所有前缀即所有子串。我们遍历后缀数组，对于每个后缀，其越长的前缀能耗越大，于是可以二分找到能耗小于等于要 check 的值的前缀的个数，再减去重复部分即可。而每个后缀被重复统计的部分就是 height 数组对应的值。
后缀自动机/后缀树：这两种后缀数据结构都是将本质不同的子串记录在其结点上。每个结点表示的子串都是形如Suffix(T,i)+S的串（即取 的一个后缀和 连接构成的串，在后缀树上则是
再翻转一次的串）。显然我们取的后缀越长，其表示的子串能耗越大，于是可以二分这个长
度来找到满足条件的子串的个数，每次 check 对每个结点做一次二分即可。
时间复杂度O(n㏒n㏒k)。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1000000 + 9;
const int M = 998244353;
long long f[N], _S[N];
void Pre() {
long long pow2 = 1;
for (int i = 1; i < N; ++i) {
pow2 = pow2 * 2 % M;
f[i] = (pow2 - f[i] + M) % M;
_S[i] = (f[i] + _S[i - 1]) % M;
for (int j = i + i; j < N; j += i) {
f[j] = (f[j] + f[i]) % M;
}
}
}
long long Pow2(long long n) {
long long r = 1, x = 2;
for (; n; n >>= 1) {
if (n & 1) r = r * x % M;
x = x * x % M;
}
return r;
}
struct Du {
int tot, sqrtn;
long long n, S[N * 2];
int id(long long x) { return x <= sqrtn ? x : tot - n / x; }
void Pre(long long _n) {
tot = 1; n = _n; sqrtn = sqrt(n + 0.5);
for (long long l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
S[tot++] = r < N ? _S[r] : -1;
}
}
long long Calc_S(long long n) {
if (~S[id(n)]) return S[id(n)];
long long s = 0;
for (long long l = 2, r; l <= n; l = r + 1) {
r = n / (n / l);
s += (r - l + 1) % M * Calc_S(n / l) % M;
}
s = ((Pow2(n + 1) - 2 - s) % M + M) % M;
return S[id(n)] = s;
}
long long Calc_Ans(long long n) {
Pre(n); Calc_S(n);
long long ans = Pow2(n);
for (long long l = 1, r; l <= n / 2; l = r + 1) {
r = min(n / (n / l), n / 2);
ans += (n / l - 1) * (S[id(r)] - S[id(l - 1)]) % M;
}
return (ans % M + M) % M;
}
} du;
void solve() {
long long n;
scanf("%lld", &n);
printf("%lld\n", du.Calc_Ans(n));
}
int main() {
Pre();
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}
题目
问题描述
在整数序列 a1,a2,…,an 中，如果一个递增子序列不是其他递增子序列的子序列，我们称其为极大。子序列是我们可以通过从原始序列中删除一些（可能为零）元素来获得的序列。
寻找或计算最长递增子序列是一个经典问题。现在 Yukikaze 想让你计算一些以 998244353 为模的排列中最大递增子序列的数量。长度为 n 的排列是一个数字序列，这样从 1 到 n 的每个数字都只出现一次。
输入
输入的第一行包含一个整数 T (1≤T≤104)，表示测试用例的数量。
每个测试用例的第一行包含一个整数 n (1≤n≤105)，表示排列的长度。
每个测试用例的第二行包含 n 个整数 a1,a2,…,an (1≤ai≤n)，表示排列。保证从 1 到 n 的每个数字都只出现一次。
所有测试用例中 n 的总和不会超过 2×105。
输出
对于每个测试用例，输出一个整数，表示给定置换模 998244353 中最大递增子序列的数量。
样本输入
2
4
2 1 4 3
5
1 5 2 4 3
样本输出
4
3
解题思路
定义 dp[i] 为 a[1…i] 中以 a[i] 为结尾的极长上升子序列个数。则 dp[i] 对 dp[j] 有贡献当且仅当
i 到 j 之间没有 a[i] 到 a[j] 之间的元素。 dp[i] 初值为 1 当且仅当 a[i] 前面没有比 a[i] 小的。
dp[i] 对答案有贡献当且仅当 a[i] 后面没有比 a[i] 大的。这样就有了一个朴素的 做法。
通过分治并对两侧分别维护单调栈，我们可以把时间复杂度优化到O(n*㏒?n)。
当处理区间 [l,r] 时，令 m 为 [l,r] 的中点，对 a[l,r] 中所有元素按值依次从小到大处理。对 [l,m] 和 [m+1,r] 分别建单调栈。左边单调栈中的元素值从小到大，位置从大到小。右边的单调栈中元素值从小到大，位置从小到大。处理左边的元素时直接往单调栈里丢，处理右边的元素 a[i] 时通过单调栈找到 [m+1,i-1] 中比他小的最靠右侧的元素 a[j] 。然后在左侧的单调栈中找到比 a[j] 大的第一个元素和比 a[i] 小的最后一个元素。区间 [l,m] 对 dp[i] 的贡献就来自单调栈里这两个元素之间的元素的 dp 值之和。
代码
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int P = 998244353;
int add(int a, int b) { a += b; return a < P ? a : a - P; }
int sub(int a, int b) { a -= b; return a < 0 ? a + P : a; }
const int N = 100001;
int a[N], dp[N];
void solve(int l, int r) {
if (l + 1 == r) return;
int mid = (l + r) >> 1;
solve(l, mid);
vector<int> pos(r - l);
iota(pos.begin(), pos.end(), l);
sort(pos.begin(), pos.end(), [&](int i, int j) { return a[i] < a[j]; });
vector<int> ls, rs;
vector<int> sum(1, 0);
for (int i : pos) {
if (i < mid) {
while (!ls.empty() && ls.back() < i)
sum.pop_back(), ls.pop_back();
ls.push_back(i);
sum.push_back(add(sum.back(), dp[i]));
}
else {
while (!rs.empty() && rs.back() > i)
rs.pop_back();
if (ls.empty()) continue;
int id1 = partition_point(ls.begin(), ls.end(), [&](int x) { return a[x] < a[i]; }) - ls.begin();
int id2 = rs.empty() ? 0 : partition_point(ls.begin(), ls.end(), [&](int x) { return a[x] < a[rs.back()]; }) - ls.begin();
dp[i] = add(dp[i], sub(sum[id1], sum[id2]));
rs.push_back(i);
}
}
solve(mid, r);
}
int main(void) {
int T; scanf("%d", &T);
while (T--) {
int n; scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
for (int i = 1, v = INT_MAX; i <= n; ++i) {
if (v > a[i])
dp[i] = 1;
else
dp[i] = 0;
v = min(v, a[i]);
}
solve(1, n + 1);
int ans = 0;
for (int i = n, v = 0; i >= 1; --i) {
if (v < a[i])
ans = add(ans, dp[i]);
v = max(v, a[i]);
}
printf("%d\n", ans);
}
return 0;
}
题目
问题描述
有一天，一只丧尸来到了死者草坪，它可以被看作是一个 n×m 的网格。最初，他站在左上角的单元格上，即 (1,1)。
因为丧尸的脑子坏掉了，所以他没有很好的方向感。他只能一步从(i,j) 向下移动到(i+1,j) 或从(i,j) 向右移动到(i,j+1)。
网格上有 k 个“lotato 地雷”。第 i 个矿在 (xi,yi)。万一被摧毁，他绝不会踏入装有“洛托地雷”的牢房。
那么他能达到多少细胞呢？ （包括起始单元格）
输入
第一行包含一个整数 t (1≤t≤20)，表示测试用例的数量。
每个测试用例的第一行包含三个整数 n,m,k (2≤n,m,k≤105) — 有一个 n×m 网格，网格上有 k 个“lotato mines”。
以下 k 行中的每一行都包含 2 个整数 xi,yi (1≤xi≤n,1≤yi≤m) — 在 (xi,yi) 处有一个“lotato 地雷”。可以保证在 (1,1) 处没有“lotato 地雷”，并且在同一个单元格中没有地雷。
保证∑n≤7?105，∑m≤7?105。
输出
对于每个测试用例，输出他可能到达的单元格数量。
样本输入
1
4 4 4
1 3
3 4
3 2
4 3
样本输出
10
提示
僵尸可能到达的细胞是
(1,1), (1,2), (2,1), (2,2), (2,3), (2,4), (3,1), (3,3), (4,1), (4,2).
解题思路
考虑所有点的个数减去不能到达的点的个数，即为可以到达的点的个数。
根据题意，有地雷的地方是不可以到达的。由于僵尸只会向右和向下走，当某个点的左边和上方都不可达时，该点不可达，并会对自己右边的点和下方的点造成影响。
由于空间很大但地雷数有限，可以从上往下逐行对每一行的地雷排序后进行处理。对每个地雷，找到从自己的右上角点 (x-1，y+1)开始的从左往右的连续不可达区域的范围，那么 这行的这个范围也不可达。可以用线段树来实现区间查询和区间覆盖。每一行处理完后查询该行不可达的点数，累加后用总点数减即得到答案。
代码
#include<bits/stdc++.h>
using namespace std;
#define ls (x<<1)
#define rs (x<<1|1)
const int N = 1e5 + 5;
const int inf = 0x3f3f3f3f;
vector<int>e[N];
int tr[2][N << 2], lz[2][N << 2];
void push_down(int f, int x, int l, int r, int mid) {
if (lz[f][x] == -1)return;
tr[f][ls] = lz[f][x] * (mid - l + 1);
tr[f][rs] = lz[f][x] * (r - mid);
lz[f][ls] = lz[f][rs] = lz[f][x];
lz[f][x] = -1;
}
void update(int f,int x, int l, int r, int L, int R, int v) {
if (L <= l && R >= r) {
tr[f][x] = (r - l + 1) * v;
lz[f][x] = v;
return;
}
int mid = (l + r) >> 1;
push_down(f, x, l, r, mid);
if (R <= mid)update(f, ls, l, mid, L, R, v);
else if (L > mid)update(f, rs, mid + 1, r, L, R, v);
else {
update(f, ls, l, mid, L, mid, v);
update(f, rs, mid + 1, r, mid + 1, R, v);
}
tr[f][x] = tr[f][ls] + tr[f][rs];
}
int query(int f, int x, int l, int r, int L, int R) {
if (!tr[f][x])return inf;
if (l == r)return l;
int mid = l + r >> 1;
push_down(f, x, l, r, mid);
if (L <= l && R >= r) {
if (tr[f][ls] > 0) return query(f, ls, l, mid, l, mid);
else return query(f, rs, mid + 1, r, mid + 1, r);
}
else {
if (R <= mid)return query(f, ls, l, mid, L, R);
else if (L > mid)return query(f, rs, mid + 1, r, L, R);
else return min(query(f, ls, l, mid, L, mid), query(f, rs, mid + 1, r, mid + 1, R));
}
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
for (int i = 1; i <= n; ++i)e[i].clear();
for (int i = 1; i <= (m << 2); ++i) {
tr[0][i] = tr[1][i] = 0;
lz[0][i] = lz[1][i] = -1;
}
for (int i = 0; i < k; ++i) {
int x, y;
scanf("%d %d", &x, &y);
e[x].push_back(y);
}
long long ans = 0;
update(0, 1, 1, m, 1, 1, 1);
for (int x = 1; x <= n; ++x) {
int l = 0;
sort(e[x].begin(), e[x].end());
for (auto& y : e[x]) {
if (y - 1 >= l + 1) {
int pos = query((x & 1) ^ 1, 1, 1, m, l + 1, y - 1);
if (pos != inf)update(x & 1, 1, 1, m, pos, y - 1, 1);
}
l = y;
}
if (l + 1 <= m) {
int pos = query((x & 1) ^ 1, 1, 1, m, l + 1, m);
if (pos != inf)update(x & 1, 1, 1, m, pos, m, 1);
}
ans += tr[x & 1][1];
update((x & 1) ^ 1, 1, 1, m, 1, m, 0);
}
printf("%lld\n", ans);
}
return 0;
}
|