OI笔记 | 2022.12 做题记录（二）
- Compress Words
- Mivik的神力
- 「JOISC 2017 Day 4」绑架 2
- Anthem of Berland
- 『JROI-4』沈阳大街 2
- [CTSC2017]吉夫特
- [SDOI2016]排列计数
- OSU!
- [CSP-S 2021] 廊桥分配
- [GXOI/GZOI2019]逼死强迫症
Compress Words
给出 $n$ 个字符串，把它们拼接起来，并且考虑相邻两个字符串，找到前一个的后缀与后一个的前缀的最长公共部分，在答案的字符串中，这一公共部分只算一次。
例如 $sample$ 和 $please$ 这两个串，拼接后变成 $samplease$。
题解
我们考虑 KMP 中 $next$ 数组，它就是某一字符串中前缀和后缀的最大公共部分的长度 border。
例如当前的答案字符串为 $sample$，我们新输入一个字符串 $please$，可以把答案字符串拼接到新字符串之后： $\color{red}{ple}asesam\color{red}{ple}$，然后跑一遍 KMP 就可以找到这个最大公共部分的长度 $next_{tp}=3$，然后我们只要在答案后面加上不是公共部分的子串，在原字符串中的下标为区间 $[next_{tp}+1, len]$。
考虑细节：我们要在拼接时中间加一个特殊字符，否则考虑极端情况，两个字符串相同，那 border 是原串的两倍就寄了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e6 + 10;
int nxt[MAX_N];
char s[MAX_N], ans[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int n = read(), anslen = 0;
for(int i = 1; i <= n; i++) {
scanf("%s", s + 1);
int olen = strlen(s + 1);
int len = min(olen, anslen), tp = olen;
s[++tp] = '.';
for(int j = 1; j <= len; j++)
s[++tp] = ans[anslen - len + j];
nxt[0] = nxt[1] = 0;
int j = 0;
for(int i = 2; i <= tp; i++) {
while(j > 0 && s[i] != s[j + 1]) j = nxt[j];
if(s[i] == s[j + 1]) j++;
nxt[i] = j;
}
for(j = nxt[tp] + 1; j <= olen; j++)
ans[++anslen] = s[j];
}
for(int i = 1; i <= anslen; i++)
putchar(ans[i]);
return 0;
}
Mivik的神力
给定一个 $n$ 个数的数列，有 $t$ 次询问，每次询问给出两个数 $l,q$，求以下式子的值：
\[\sum_{i=l}^{l+q-1} \max_{l\le j\le i}a_j\]数据要求强制在线
$n\leq 500000$，$t\leq 500000$
题解
设 $i$ 后第一个比 $a_i$ 大的位置为 $fa_i$，可以用单调栈 $O(n)$ 处理出来。
那么可以跳跃处理，则区间 $[i,fa_i - 1]$ 对答案的贡献为 $a_i \times (fa_i - i)$。但是如果遇到单调递增的序列这个优化就没用了。
所以考虑每个位置都有唯一一个可以跳到的位置，很像树形结构，那么可以类比而处理出每个节点到根节点的距离： $sum_i=sum_{fa_i} +(fa_i-i)\times a_i$ 。这样就像是区间内的最大值的儿子是它前面的一些较小值，则直接前缀和减一下就能得到最大值左边的贡献。
另外考虑用 ST 表维护查询区间 $[l,r]$ 内最大值出现的位置 $mx$，则最大值右边的贡献为 $(r - mx + 1) \times a_{mx}$。
时间复杂度 $O(n\log n + m)。$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 5e5 + 10, MAX_LOG = 20;
int a[MAX_N], st[MAX_N][MAX_LOG], log_2[MAX_N], fa[MAX_N];
ll sum[MAX_N], lastans;
stack<int> s;
int n, q, u, v, l, len, x, mx;
inline ll read() {...}
inline void write(ll x) {...}
int Max(int i, int j) {return a[i] > a[j] ? i : j;}
void pre() {
log_2[1] = 0, log_2[2] = 1;
for(int i = 3; i <= n; i++)
log_2[i] = log_2[i >> 1] + 1;
for(int j = 1; j <= MAX_LOG; j++)
for(int i = 1; i + (1 << (j - 1)) - 1 <= n; i++)
st[i][j] = Max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
for(int i = n; i >= 1; i--)
sum[i] = sum[fa[i]] + 1ll * (fa[i] - i) * a[i];
}
int main() {
n = read(), q = read();
for(int i = 1; i <= n; i++) {
a[i] = read(), st[i][0] = i;
while(!s.empty() && a[i] > a[s.top()]) {
fa[s.top()] = i;
s.pop();
}
s.push(i);
}
while(!s.empty()) {
fa[s.top()] = n + 1;
s.pop();
}
pre();
while(q--) {
u = read(), v = read();
l = 1 + (u ^ lastans) % n, len = 1 + (v ^ (lastans + 1)) % (n - l + 1);
x = log_2[len];
mx = Max(st[l][x], st[(l + len - 1) - (1 << x) + 1][x]);
write(lastans = (sum[l] - sum[mx] + 1ll * a[mx] * (l + len - mx)));
putchar('\n');
}
return 0;
}
「JOISC 2017 Day 4」绑架 2
某地的道路网可视为由 $H$ 条东西向道路与 $W$ 条南北向道路构成的网格，相邻的两条平行道路之间的距离为 $1 :\textrm{km}$。东西向道路从北到南依次编号为 $ 1\ldots H $，南北向道路从西到东依次编号为 $ 1\ldots W $ 。
东西向道路和南北向道路相交形成路口，规定 $ x $ 号南北向街道和 $ y $ 号东西向街道形成的路口的坐标是 $ (x, y) $ 。
每条道路有一个车流指数。$i$ 号东西向道路 $(1\le i\le H)$ 的车流指数为 $A_{\;!i}$ ，$j$ 号南北向道路 $(1\le j\le W)$ 的车流指数为 $B_j$ 。所有道路的车流指数互不相同。
给出 $Q$ 个互不相同的坐标 $(S_1, T_1), (S_2, T_2),\ldots,(S_Q, T_Q)$ 作为备选起点。对于每个备选起点，请计算：如果按照下述规则移动，最多可以移动多远。
- 移动开始时，可以任意选择方向。
- 当到达十字路口时：
- 如果 直行方向的道路的车流指数 比 该十字路口的另一条道路的车流指数 小，就转弯。你可以选择左转还是右转。但如果你在城市边界上，可能只能左转/右转。
- 如果 直行方向的道路的车流指数 比 该十字路口的另一条道路的车流指数 大，就直行。但如果前面没路（比如到了城市边界），就只能停在此处。
- 不能掉头。
$2 \le H, W \le 5\times 10^4, 1\le Q\le 100,$ $1\le A_i, B_j\le 10^9$
题解
某谷网校讲了这题的分治写法，但是感觉不是很会写，于是找了题解看，发现记忆化搜索优化之后是能过的。
具体来说，我们可以用 ST 表倍增地找到当前你往某一方向直行最多走到哪个位置必须转弯，即找到第一个大于这一方向车流指数的那一行/列，这个预处理和查询在 $O(n\log n)$ 以内。
然后主要是用 map 进行记忆化搜索，注意用横/纵方向 0/1 作为状态否则开不下。状态数理论上是 $O(n^2)$ 的但是似乎可以证明实际上没有那么大，大概只有 $O(n)$ ？实际上提交没有出现 MLE 也证明了这一点。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 5e4 + 10, MAX_LOG = 17;
int n, m, q;
int a[MAX_N][MAX_LOG], b[MAX_N][MAX_LOG];
map<int, ll> ans[2][MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
ll solve(int x, int y, bool face) {
if(x > n || x < 1 || y > m || y < 1) return -1;
if(ans[face][x][y]) return ans[face][x][y];
ll ret = 0;
if(face == 1) {
int L = x - 1, R = x + 1;
for(int i = MAX_LOG - 1; i >= 0; i--) {
if(L - (1 << i) >= 0 && b[y][0] > a[L - (1 << i) + 1][i]) L -= (1 << i);
if(R + (1 << i) <= n + 1 && b[y][0] > a[R][i]) R += (1 << i);
}
ret = max(ret, solve(L, y, 0) + x - L);
ret = max(ret, solve(R, y, 0) + R - x);
}
else {
int L = y - 1, R = y + 1;
for(int i = MAX_LOG - 1; i >= 0; i--) {
if(L - (1 << i) >= 0 && a[x][0] > b[L - (1 << i) + 1][i]) L -= (1 << i);
if(R + (1 << i) <= m + 1 && a[x][0] > b[R][i]) R += (1 << i);
}
ret = max(ret, solve(x, L, 1) + y - L);
ret = max(ret, solve(x, R, 1) + R - y);
}
return ans[face][x][y] = ret;
}
int main() {
n = read(), m = read(), q = read();
for(int i = 1; i <= n; i++)
a[i][0] = read();
for(int i = 1; i <= m; i++)
b[i][0] = read();
for(int j = 1; j < MAX_LOG; j++) {
for(int i = 1; i + (1 << (j - 1)) - 1 <= n; i++)
a[i][j] = max(a[i][j - 1], a[i + (1 << (j - 1))][j - 1]);
for(int i = 1; i + (1 << (j - 1)) - 1 <= m; i++)
b[i][j] = max(b[i][j - 1], b[i + (1 << (j - 1))][j - 1]);
}
while(q--) {
int s = read(), t = read();
write(max(solve(s, t, 0), solve(s, t, 1)));
putchar('\n');
}
return 0;
}
Anthem of Berland
给定 $s$ 串和 $t$ 串，其中 $s$ 串包含小写字母和问号，$t$ 串只包含小写字母。
假设共有 $k$ 个问号。
你需要给把每个问号变成一个小写字母，共有 $26^k$ 种可能。
对于每种可能，设 $t$ 匹配 $s$ 的次数为 $f_i$，请输出 $\max(f_i)$ 。
$1\leq \lvert s\rvert ,\lvert t\rvert \leq 10^5,\lvert s\rvert \cdot \lvert t\rvert \leq 10^7$
题解
设 $\lvert s\rvert = n, \lvert t\rvert = m$。
考虑用 kmp 匹配加上 dp。我们用 $dp_{i,j}$ 表示考虑 $s$ 的前 $i$ 个字符，且 kmp 的 fail 指针指在 $t$ 的第 $j$ 位时的最大匹配次数。
那么 dp 转移就是 $dp_{i+1,j} = \max(dp_{i+1,j}, dp_{i,j} + [to = m + 1])$，其中 $to$ 是如果这一位相等就往后跳 $1$ 位，否则跳 $next$，而最终会跳到的位置。
然后这个 $to$ 可以预处理一个数组 $b_{i,j}$ 表示 fail 指针指在 $t$ 的第 $i$ 位，匹配到字符 $j(j\in [0,25])$ 时最后会跳到的位置。
问号的问题暴力枚举 $26$ 种情况即可。
时间复杂度 $O(26nm)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10, INF = (1 << 30);
char s[MAX_N], t[MAX_N];
int b[MAX_N][26], nxt[MAX_N];
vector<vector<int>> dp;
inline void write(ll x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + 48);
}
int main() {
scanf("%s %s", s + 1, t + 1);
int n = strlen(s + 1), m = strlen(t + 1), ans = 0;
dp.resize(n + 5);
for(int i = 1; i <= n + 2; i++)
dp[i].resize(m + 5);
for(int i = 2, j = 0; i <= m; i++) {
while(j > 0 && t[i] != t[j + 1]) j = nxt[j];
if(t[i] == t[j + 1]) j++;
nxt[i] = j;
}
t[m + 1] = '.';
for(int i = 1; i <= m + 1; i++) {
for(int j = 0; j <= 25; j++) {
if(i > 1 && t[i] - 'a' != j) b[i][j] = b[nxt[i - 1] + 1][j];
else if(t[i] - 'a' == j) b[i][j] = i + 1;
else b[i][j] = 1;
}
}
for(int i = 1; i <= n + 1; i++)
for(int j = 1; j <= m + 1; j++)
dp[i][j] = -INF;
dp[1][1] = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m + 1; j++) {
int to = b[j][s[i] - 'a'];
if(s[i] == '?') {
for(int k = 0; k <= 25; k++) {
to = b[j][k];
dp[i + 1][to] = max(dp[i + 1][to], dp[i][j] + (to == m + 1));
}
}
else dp[i + 1][to] = max(dp[i + 1][to], dp[i][j] + (to == m + 1));
}
}
for(int i = 1; i <= m + 1; i++)
ans = max(ans, dp[n + 1][i]);
write(ans);
return 0;
}
『JROI-4』沈阳大街 2
给定两个长度为 $n$ 的序列 $A,B$，满足：
-
$\forall 1\le i<n,A_i \ge A_{i+1}$
-
$A_n\ge \min\limits_{i=1}^n(B_i)$
$\pi$ 是一个长度为 $n$ 的排列，定义价值函数 $f(\pi)$：
\[f(\pi)=\prod_{i=1}^n\min(A_i,B_{\pi(i)})\]每种排列出现的概率相等，求 $f(\pi)$ 的期望对 $998244353$ 取模的结果。
即求:
\[\left(\dfrac{1}{n!}\sum_\pi f(\pi)\right) \bmod 998244353\]$1\le n\le 5000$，$1\le A_i,B_i\le 10^9$。
题解
我们考虑转化一种计数的角度，从每个权值出发来考虑这个乘积的和式。
首先将 $A,B$ 两个数列分别染色并合并成新的数列 $C$。想象在数轴上把所有 $C$ 中的数从大到小列出来。
那么问题转化为在数轴上选两个不同颜色的点进行配对，权值为靠右的数的值，求所有选法的权值和。
然后就是一个 dp 模型：设 $dp_{i,j}$ 为考虑前 $i$ 大的数，分成 $j$ 组的权值和。那么转移方程为：
\[dp_{i,j}=dp_{i-1,j-1}\cdot C_i \cdot (cnta - j + 1) + dp_{i-1,j}\]其中 $cnta$ 为 $i$ 前面有多少个与 $i$ 颜色不同的点，减掉 $(j-1)$ 就是剩下的可供配对的点数。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const int MOD = 998244353, MAX_N = 5e3 + 10;
pll c[MAX_N << 1];
ll cnt[2], dp[MAX_N << 1][MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
ll qpow(ll x, ll y) {
ll ret = 1;
while(y) {
if(y & 1) (ret *= x) %= MOD;
(x *= x) %= MOD;
y >>= 1;
}
return ret;
}
int main() {
int n = read();
ll f = 1;
for(int i = 1; i <= n; i++)
(f *= i) %= MOD;
f = qpow(f, MOD - 2);
for(int i = 1; i <= n; i++)
c[i].first = read(), c[i].second = 0;
for(int i = n + 1; i <= 2 * n; i++)
c[i].first = read(), c[i].second = 1;
sort(c + 1, c + 2 * n + 1, greater<pll>());
dp[0][0] = 1;
for(int i = 1; i <= 2 * n; i++) {
cnt[c[i].second]++;
dp[i][0] = 1;
for(int j = 1; j <= min(i, n); j++) {
int cnta = cnt[!c[i].second];
dp[i][j] = dp[i - 1][j];
if(cnta >= j) (dp[i][j] += dp[i - 1][j - 1] * c[i].first % MOD * (cnta - j + 1) % MOD) %= MOD;
}
}
write(f * dp[2 * n][n] % MOD);
return 0;
}
[CTSC2017]吉夫特
输入一个长度为 $n$ 的数列 $a_1, a_2, \cdots , a_n$ 问有多少个长度大于等于 $2$ 的不上升的子序列满足：
\[\prod _{i=2}^{k} \binom{a_{b_{i-1}}}{a_{b_i}} \bmod 2 = \binom{a_{b_1}}{a_{b_2}} \times \binom{a_{b_2}}{a_{b_3}} \times \cdots \binom{a_{b_{k-1}}}{a_{b_k}} \bmod 2 > 0\]这里的子序列为 $a_{b_1},a_{b_2},a_{b_3},\cdots, a_{b_k}$。
输出这个个数对 $1000000007$ 取模的结果。
$1\leq n\leq 211985$，$1\leq a_i\leq 233333$。所有的 $a_i$ 互不相同，也就是说不存在 $i, j$ 同时满足 $1\leq i < j\leq n$ 和 $a_i = a_j$。
题解
我们发现，如果要满足这个连乘模 $2$ 为 $1$，需要满足每个组合数 $\binom{a_i}{a_j}$ 模 $2$ 都为 $1$。根据 Lucas 定理，这等同于把 $a_i$ 和 $a_j$ 分别二进制拆位后每位的组合数都为 $1$。
拆位后的组合数只有四种情况：$\binom{0}{0},\binom{1}{0},\binom{0}{1},\binom{1}{1}$，其中只有 $\binom{0}{1}$ 为 $0$，所以可以发现如果想让原组合数不为 $0$，那么 $a_j$ 的每一位都要小于或等于 $a_i$，也就是说 $a_j\subseteq a_i$。
那么我们可以写出 $O(n^2)$ 的朴素 dp：
\[dp_{i} = 1 + \sum_{j<i} ([a_i\subseteq a_j]\cdot dp_j)\]$70pts$ 代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 3e5 + 10, MOD = 1e9 + 7;
int a[MAX_N], dp[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
bool in(int x, int y) {return ((x & y) == x) && ((x | y) == y);}
int main() {
int n = read(), ans = 0;
for(int i = 1; i <= n; i++) {
a[i] = read(); dp[i] = 1;
for(int j = 1; j < i; j++)
(dp[i] += in(a[i], a[j]) * dp[j]) %= MOD;
(ans += dp[i] - 1) %= MOD;
}
write(ans);
return 0;
}
然后我们可以换一个角度来枚举，直接枚举 $a_i$ 的所有子集然后刷表 dp 即可。时间复杂度为 $O(3^{\log \max{a_i}})$ 。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 3e5 + 10, MOD = 1e9 + 7;
int x, ans, n, dp[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
n = read();
for(int i = 1; i <= n; i++) {
x = read();
for(int j = x & (x - 1); j; j = (j - 1) & x)
(dp[j] += dp[x] + 1) %= MOD;
(ans += dp[x]) %= MOD;
}
write(ans);
return 0;
}
[SDOI2016]排列计数
求有多少种 $1$ 到 $n$ 的排列 $a$，满足序列恰好有 $m$ 个位置 $i$，使得 $a_i = i$。
答案对 $10^9 + 7$ 取模。
$1 \leq T \leq 5 \times 10^5$，$1 \leq n \leq 10^6$，$0 \leq m \leq 10^6$。
题解
我们先固定 $m$ 个位置，有 $\binom{n}{m}$ 种选法。然后剩下的 $n-m$ 个位置的排法就是错排数 $D_{n-m}$。
错排数的递推式为 $D_i = (i - 1) \times (D_{n-1} + D_{n-2})$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e6 + 1, MOD = 1e9 + 7;
int D[MAX_N], inv[MAX_N], fac[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
ll qpow(ll x, ll y) {
ll ret = 1;
while(y) {
if(y & 1) (ret *= x) %= MOD;
(x *= x) %= MOD;
y >>= 1;
}
return ret;
}
void pre() {
fac[1] = 1, fac[2] = 2, D[0] = 1, D[1] = 0, D[2] = 1;
for(int i = 3; i < MAX_N; i++) {
fac[i] = (1ll * fac[i - 1] * i) % MOD;
D[i] = 1ll * (i - 1) * (D[i - 1] + D[i - 2]) % MOD;
}
inv[MAX_N - 1] = qpow(fac[MAX_N - 1], MOD - 2);
for(int i = MAX_N - 2; i >= 0; i--)
inv[i] = (1ll * inv[i + 1] * (i + 1)) % MOD;
}
ll C(ll n, ll m) {
if(n < m) return 0;
return 1ll * fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}
int main() {
pre();
int T = read();
while(T--) {
int n = read(), m = read(), ans = 0;
if(n >= m) ans = 1ll * C(n, m) * D[n - m] % MOD;
write(ans), putchar('\n');
}
return 0;
}
OSU!
osu 是一款群众喜闻乐见的休闲软件。
我们可以把 osu 的规则简化与改编成以下的样子:
一共有 $n$ 次操作，每次操作只有成功与失败之分，成功对应 $1$，失败对应 $0$，$n$ 次操作对应为 $1$ 个长度为 $n$ 的 01 串。在这个串中连续的 $X$ 个 $1$ 可以贡献 $X^3$ 的分数，这 $x$ 个 $1$ 不能被其他连续的 $1$ 所包含（也就是极长的一串 $1$，具体见样例解释）
现在给出 $n$，以及每个操作的成功率，请你输出期望分数，输出四舍五入后保留 $1$ 位小数。
$n \leq 1 \times 10 ^ 5$。
题解
这题考察了期望的线性性：
\[E((x+1)^3) = E(x^3 + 3x^2 + 3x+1)=E(x^3) + 3E(x^2) + 3E(x) + 1\]那么如果我们设 $f_i$ 为前 $i$ 位的的期望分数，则有：
\[f_i = p_i \times (f_{i-1} + 3 g_{i-1} + 3h_{i-1} + 1) + (1-p_i)\times f_{i-1}\]其中 $g_i,h_i$ 就是二次方和一次方的期望，同样可以递推：
\[g_i = (g_{i-1} \times 2h_{i-1} + 1) \times p_i\] \[h_i = (h_{i-1} + 1) \times p_i\]我们维护的一次方和二次方的期望都是对于成功而言的，所以不用加 $(1-p_i)\times h_i$ 或 $(1-p_i)\times g_i$。可以从我们最终的式子那里体会到这个细节。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10;
double e3[MAX_N], e2[MAX_N], e1[MAX_N], p;
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int n = read();
for(int i = 1; i <= n; i++) {
scanf("%lf", &p);
e1[i] = (e1[i - 1] + 1) * p;
e2[i] = (e2[i - 1] + 2 * e1[i - 1] + 1) * p;
e3[i] = e3[i - 1] + (3 * e2[i - 1] + 3 * e1[i - 1] + 1) * p;
}
printf("%.1lf", e3[n]);
return 0;
}
[CSP-S 2021] 廊桥分配
当一架飞机抵达机场时，可以停靠在航站楼旁的廊桥，也可以停靠在位于机场边缘的远机位。乘客一般更期待停靠在廊桥，因为这样省去了坐摆渡车前往航站楼的周折。然而，因为廊桥的数量有限，所以这样的愿望不总是能实现。
机场分为国内区和国际区，国内航班飞机只能停靠在国内区，国际航班飞机只能停靠在国际区。一部分廊桥属于国内区，其余的廊桥属于国际区。
L 市新建了一座机场，一共有 $n$ 个廊桥。该机场决定，廊桥的使用遵循“先到先得”的原则，即每架飞机抵达后，如果相应的区（国内/国际）还有空闲的廊桥，就停靠在廊桥，否则停靠在远机位（假设远机位的数量充足）。该机场只有一条跑道，因此不存在两架飞机同时抵达的情况。
现给定未来一段时间飞机的抵达、离开时刻，请你负责将 $n$ 个廊桥分配给国内区和国际区，使停靠廊桥的飞机数量最多。
$1 \le n \le {10}^5$，$m_1, m_2 \ge 1$，$m_1 + m_2 \le {10}^5$，所有 $a_{1, i}, b_{1, i}, a_{2, i}, b_{2, i}$ 为数值不超过 ${10}^8$ 的互不相同的正整数，且保证对于每个 $i \in [1, m_1]$，都有 $a_{1, i} < b_{1, i}$，以及对于每个 $i \in [1, m_2]$，都有 $a_{2, i} < b_{2, i}$。
题解
考虑飞机的到达顺序一定的情况下，它被分配到的廊桥可以视为是一定的。我们不妨把廊桥从小到大编号 $1\sim n$，假设每个飞机来时都被分配到空闲的且编号最小的廊桥。
于是我们就可以分别对于国内区和国外区模拟一遍飞机抵达、离开的过程，预处理出每个飞机到达的廊桥。这样就可以同时预处理出 $sum_i$ 即前 $i$ 个廊桥接待了多少架飞机。
然后枚举分配给国内区和国外区的数量即可。
时间复杂度：$O(n\log n)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_N = 1e5 + 10;
int n, m1, m2;
pii a[MAX_N], b[MAX_N];
int suma[MAX_N], sumb[MAX_N], ans;
inline ll read() {...}
inline void write(ll x) {...}
void solve(pii *t, int *sum, int m) {
priority_queue<int, vector<int>, greater<int>> p;
priority_queue<pii, vector<pii>, greater<pii>> q;
for(int i = 1; i <= n; i++)
p.push(i);
for(int i = 1; i <= m; i++) {
while(!q.empty() && q.top().first <= t[i].first) {
p.push(q.top().second);
q.pop();
}
if(!p.empty()) {
q.push((pii){t[i].second, p.top()});
sum[p.top()]++;
p.pop();
}
}
for(int i = 1; i <= n; i++)
sum[i] += sum[i - 1];
}
int main() {
n = read(), m1 = read(), m2 = read();
for(int i = 1; i <= m1; i++)
a[i].first = read(), a[i].second = read();
for(int i = 1; i <= m2; i++)
b[i].first = read(), b[i].second = read();
sort(a + 1, a + m1 + 1), sort(b + 1, b + m2 + 1);
solve(a, suma, m1), solve(b, sumb, m2);
for(int i = 0; i <= n; i++)
ans = max(ans, suma[i] + sumb[n - i]);
write(ans);
return 0;
}
[GXOI/GZOI2019]逼死强迫症
ITX351 要铺一条 $2 \times N$ 的路，为此他购买了 $N$ 块 $2 \times 1$ 的方砖。可是其中一块砖在运送的过程中从中间裂开了，变成了两块 $1 \times 1$ 的砖块！
ITX351 由此产生了一个邪恶的想法：他想要在这条路上故意把两块 $1 \times 1$ 的砖块分开铺，不让两块砖有相邻的边，其他砖块可以随意铺，直到整条路铺满。这样一定可以逼死自身强迫症 sea5！
也许下面的剧情你已经猜到了——他为此兴奋不已，以至于无法敲键盘。于是，他请你帮忙计算一下，有多少种方案可以让自己的阴谋得逞。
$N \le 2 \times 10^9$
题解
考虑如果没有这个 $1\times 1$ 的砖块，那这个方案数就是经典递推了，最后一个砖块横着摆或者竖着摆两种加起来，则 $2\times i$ 的方格的方案数 $F_i = F_{i-1}+F_{i-2}$，即斐波那契数列。
再考虑 $1\times 1$ 的砖块。设 $dp_i$ 为 $2\times i$ 的方格的方案数，那么首先考虑这一位不放 $1\times 1$ 的砖块的情况，则有 $dp_{i-1},dp_{i-2}$ 这两个贡献。
如果这一格放 $1\times 1$ 的砖块，我们假设另一个 $1\times 1$ 砖块一定在 $1\sim (i - 3)$ 的范围放，则我们发现这两个砖块之间的排列方式是固定的，不贡献方案数。于是枚举另一个砖块的位置 $j$，贡献为 $\sum\limits_{j = 1}^{i-3} F_j$。维护一个前缀和即可。
但是我们发现这个 $n$ 非常大，不能 $O(Tn)$。于是矩阵快速幂加速一下。
时间复杂度 $O(T\log n)$，带个 $125$ 的矩阵乘法常数。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
inline ll read() {...}
inline void write(ll x) {...}
struct matrix {
ll a[6][6];
matrix() {memset(a, 0, sizeof(a));}
matrix operator * (const matrix &t) const {
matrix ret;
for(int k = 1; k <= 5; k++)
for(int i = 1; i <= 5; i++)
for(int j = 1; j <= 5; j++)
ret.a[i][j] = (ret.a[i][j] + a[i][k] * t.a[k][j] % MOD) % MOD;
return ret;
}
} base, tran;
void pre() {
base.a[1][1] = 2, base.a[3][1] = 1, base.a[4][1] = 1, base.a[5][1] = 1;
tran.a[1][1] = 1, tran.a[1][2] = 1, tran.a[1][3] = 2, tran.a[1][5] = 2;
tran.a[2][1] = 1, tran.a[3][3] = 1, tran.a[3][4] = 1, tran.a[4][3] = 1;
tran.a[5][3] = 1, tran.a[5][5] = 1;
}
matrix qpow(matrix x, int y) {
matrix ret;
for(int i = 1; i <= 5; i++)
ret.a[i][i] = 1;
for(; y; y >>= 1, x = x * x)
if(y & 1) ret = ret * x;
return ret;
}
int main() {
pre();
int T = read();
while(T--) {
int n = read();
if(n < 3) write(0), putchar('\n');
else {
matrix ans = qpow(tran, n - 3) * base;
write(ans.a[1][1]), putchar('\n');
}
}
return 0;
}
♥