E NVWLS
这题看起来不难，实际上确实也不难……
令\(len[i]\)表示第\(i\)个字典串去除元音后的长度，\(vow[i]\)表示第\(i\)个字典串的元音个数，那么可以设计一个十分好想的dp：
\(dp[i] = max(dp[i - len[j]] + vow[j])\)，其中\(j\)满足和文本串的\(i-len[j]+1 \sim i\)匹配。
那么怎么能找到匹配呢？两种写法：哈希和AC自动机。
因为打模拟赛的时候我AC自动机不熟，就搞起了哈希。
每次直接扫\(n\)个串肯定会超时，但是长度不同的串最多只有\(\sqrt{n}\)个，因此我设法枚举长度，然后在每一个长度里开一个map，为哈希值到该字典串的映射。
但仔细一想，这个复杂度是\(O(L\sqrt{n}\log n)\)的，最高能达到\(2e9\)，而且每一次的匹配都会访问这\(n\)个map，所以一直贴着复杂度上限。
为了优化，我把map改成了unordered_map（据说unordered_map和哈希复杂度相同），但改完后发现单哈希精度不够，而双哈希不知为什么，无法用pair作为unordered_map的下标。所以我整场比赛就在WA和TLE之间徘徊……
正解是AC自动机，思路和上面一模一样。只不过肯定要快一些：因为每次匹配fail指针只会跳父亲，即直接就是和当前节点匹配的点，所以时间复杂度不仅少了一个\(\log\)，而且大多数情况下不会达到上限。
但是还要有一个优化，就是每次向上跳，应该改成直接跳到祖先中匹配的字典串，比如有字典串N和NNN，我们希望到NNN的时候向上直接跳到N，而不是NN。这样时间复杂度就是严格的\(O(L\sqrt n)\)了。构造的方法就一行，直接看代码吧。
这里说一下最坏的情况，就是有400个字典串，都只有一种字符N，且长度依次递增，而文本串就是一个\(3*10^5\)长度的全N串。经过测试，总共向上跳了119920200次，竟然不到0.6秒就跑完了。
#include <bits/stdc++.h>
using namespace std;
#define In inline
#define Mem(a, x) memset(a, x, sizeof(a))
typedef long long ll;
const int maxn = 3e5 + 5;
const int maxN = 1e6 + 5;
char s[maxn];
int n;
struct Node
{
vector<char> s;
int len, vow;
}t[maxn];
In bool check(char c) {return c != 'A' && c != 'E' && c != 'I' && c != 'O' && c != 'U';}
In void solve(int x)
{
int len = strlen(s);
for(int i = 0; i < len; ++i)
{
t[x].s.push_back(s[i]);
if(check(s[i])) ++t[x].len;
else ++t[x].vow;
}
}
int ch[maxN][26], f[maxN], vMax[maxN], id[maxN], las[maxN], cnt = 0;
In void insert(int x)
{
int now = 0;
for(auto C : t[x].s)
{
int c = C - 'A';
if(!check(C)) continue;
// putchar(C);
if(!ch[now][c]) ch[now][c] = ++cnt;
now = ch[now][c];
}
if(t[x].vow >= vMax[now])
{
vMax[now] = t[x].vow;
id[now] = x;
}
}
In void build()
{
queue<int> q;
for(int i = 0; i < 26; ++i) if(ch[0][i]) q.push(ch[0][i]);
while(!q.empty())
{
int now = q.front(); q.pop();
for(int i = 0; i < 26; ++i)
{
int& p = ch[now][i];
if(p)
{
f[p] = ch[f[now]][i], q.push(p);
}
else p = ch[f[now]][i];
}
las[now] = id[f[now]] ? f[now] : las[f[now]];
//就是这一行，如果父节点是字典串，就跳到父节点，否则跳到和父亲一样的节点
}
}
In void init_AC()
{
for(int i = 1; i <= n; ++i) insert(i);
build();
}
int dp[maxn], pos[maxn], pre[maxn];
In void solve(char* s)
{
Mem(dp, -1), dp[0] = 0;
int l = strlen(s + 1), now = 0;
for(int i = 1; i <= l; ++i)
{
int c = s[i] - 'A';
now = ch[now][c];
for(int j = now; j; j = las[j])
{
if(!id[j]) continue;
int p = i - t[id[j]].len;
if(~dp[p] && dp[i] < dp[p] + vMax[j])
{
dp[i] = dp[p] + vMax[j];
pos[i] = id[j];
pre[i] = p;
}
}
}
}
int st[maxn], top = 0;
In void Print(char* s) //似乎递归输出会爆栈，但没测试过
{
int x = strlen(s + 1);
while(x) st[++top] = pos[x], x = pre[x];
for(int i = top; i; --i)
{
for(auto c : t[st[i]].s) putchar(c);
putchar(i == 1 ? '\n' : ' ');
}
}
int main()
{
// freopen("random.in", "r", stdin);
// freopen("ha.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
{
scanf("%s", s);
solve(i);
}
init_AC();
scanf("%s", s + 1);
solve(s); Print(s);
return 0;
}
L Travelling Merchant
如果没有价格变动和逆向旅行，那就变成了这个问题：有一个长度为\(n\)的序列，\(Q\)组询问，每次询问区间\([L, R]\)的最大差值\(a_j-a_i\)，且满足\(j>i\).
这个问题其实可以用线段树来解决（模拟赛的时候我竟然以为线段树不可做）：
对于线段树上的一个区间的最大差值\(ans\)，我们只要考虑买入和卖出是否在同一个子区间里，如果是，那么等于左右区间的\(ans\)的最大值，否则只能在左区间买入，右区间卖出，即右区间的最大值减去左区间的最小值。
现在先加上题中的条件，可以逆向旅行，那么建立两棵线段树就好了，分别对应正反序列。
这么做是为了处理价格随天数变化这个条件。因为这个价格变动是周期性的，所以我们对于一种方向的旅行，建立7棵线段树，分别对应第一个点是周一到周天的情况。这样总共14棵线段树就解决了本题。
代码中的复杂度准确来说是\(O(7nlogn)\)，为了图方便，查询的时候多了常数7，想优化的话是可以去掉的。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<queue>
#include<assert.h>
#include<ctime>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt)
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 1e5 + 5;
const int N = 17;
const int N7 = 7;
In ll read()
{
ll ans = 0;
char ch = getchar(), las = ' ';
while(!isdigit(ch)) las = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(las == '-') ans = -ans;
return ans;
}
In void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int n, Q, v[maxn], d[maxn];
int ha[] = {0, 1, 2, 3, 2, 1, 0};
struct Tree
{
int l, r;
int Min[N7], Max[N7], ans[N7];
Tree() {Mem(ans, 0);}
In Tree operator + (const Tree& oth)const
{
Tree ret; ret.l = l, ret.r = oth.r;
for(int i = 0; i < N7; ++i)
{
ret.Min[i] = min(Min[i], oth.Min[i]);
ret.Max[i] = max(Max[i], oth.Max[i]);
ret.ans[i] = max(max(ans[i], oth.ans[i]), oth.Max[i] - Min[i]);
}
return ret;
}
}t[2][maxn << 2];
In void build(int flg, int L, int R, int now)
{
t[flg][now].l = L, t[flg][now].r = R;
if(L == R)
{
for(int i = 0; i < N7; ++i)
t[flg][now].Min[i] = t[flg][now].Max[i] = v[L] + ha[(L - 1 - i + N7) % N7] * d[L];
return;
}
int mid = (L + R) >> 1;
build(flg, L, mid, now << 1), build(flg, mid + 1, R, now << 1 | 1);
t[flg][now] = t[flg][now << 1] + t[flg][now << 1 | 1];
}
In Tree query(int flg, int L, int R, int now)
{
if(t[flg][now].l == L && t[flg][now].r == R) return t[flg][now];
int mid = (t[flg][now].l + t[flg][now].r) >> 1;
if(R <= mid) return query(flg, L, R, now << 1);
else if(L > mid) return query(flg, L, R, now << 1 | 1);
else return query(flg, L, mid, now << 1) + query(flg, mid + 1, R, now << 1 | 1);
}
int main()
{
n = read();
for(int i = 1; i <= n; ++i) v[i] = read(), d[i] = read();
build(0, 1, n, 1);
reverse(v + 1, v + n + 1), reverse(d + 1, d + n + 1);
build(1, 1, n, 1);
Q = read();
for(int i = 1; i <= Q; ++i)
{
int L = read(), R = read(), flg = 0;
if(L > R) L = n - L + 1, R = n - R + 1, flg = 1;
Tree tp = query(flg, L, R, 1);
write(tp.ans[(L - 1) % N7]), enter;
}
return 0;
}
这道题比赛的时候我们另一个队的人做出来了，不过用的是RMQ.
但是这个RMQ的查询比较复杂：正常的查询是查两个子区间的并集的最大（小）值，但是在这道题里面，可能在两个区间不相交的部分进行买入和卖出。所以必须分类讨论：答案可能来源于两个子区间；也可能前一个不相交的小区间买入，后面卖出；也可能前面的大区间买入，后面小区间卖出。
实现起来稍有些复杂，我就没写。