ICPC2019 North America Qualifier test部分题目题解

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的查询比较复杂:正常的查询是查两个子区间的并集的最大(小)值,但是在这道题里面,可能在两个区间不相交的部分进行买入和卖出。所以必须分类讨论:答案可能来源于两个子区间;也可能前一个不相交的小区间买入,后面卖出;也可能前面的大区间买入,后面小区间卖出。
实现起来稍有些复杂,我就没写。

上一篇:axios请求超过定义时长则直接给结果提示


下一篇:CodeForces-1213D2 Equalizing by Division (hard version)