20230801

模拟赛。

前五题略。

F

nn 个文本串，mm 个模式串，求每个模式串在几个文本串里出现过。

n≤10000n \leq 10000，m≤100000m \leq 100000，时限 200ms。

对于每个文本串的后缀建 Trie，记录每个节点被几个文本串访问过。如果这个节点上一次被访问是同一个串就不计数。

询问就在 Trie 上匹配就行了。

G

给定一个 11 到 nn 的排列 {ai}\{a_i\}，求是否存在 i<j<ki < j < k 满足 ai+ak=2aka_i + a_k = 2 a_k。

多测，1≤n≤5×1051 \leq n \leq 5 \times 10 ^ 5，T≤5T \leq 5。

一个数 aia_i 可以被当成中间数，意味着它左边有两个数和它的差一样，一大一小。

可以用 bitset 判断，也可以用线段树 + 类似字符串哈希判断。从左向右扫，判断完后把当前数塞进线段树。

代码：

int merge(int x,int y,int len,int opt)
{
	if (opt) return (y * mi[len] % mod + x) % mod;
	return (x * mi[len] % mod + y) % mod;
}

void build(int x,int l,int r)
{
	tree[x].xl = l,tree[x].xr = r;
	tree[x].lh = tree[x].rh = 0;
	if (l == r) return ;
	build(ls,l,mid),build(rs,mid + 1,r);
}

void upd(int x,int qx)
{
	int l = tree[x].xl,r = tree[x].xr;
	if (l == r)
	{
		tree[x].lh = tree[x].rh = 1;
		return ;
	}
	if (qx <= mid) upd(ls,qx);
	else upd(rs,qx);
	tree[x].lh = merge(tree[ls].lh,tree[rs].lh,r - mid,0);
	tree[x].rh = merge(tree[ls].rh,tree[rs].rh,mid - l + 1,1);
}

int query(int x,int ql,int qr,int opt)
{
	int l = tree[x].xl,r = tree[x].xr;
	if (l >= ql && r <= qr) return (opt ? tree[x].rh : tree[x].lh);
	if (qr <= mid) return query(ls,ql,qr,opt);
	if (mid < ql) return query(rs,ql,qr,opt);
	if (opt) return merge(query(ls,ql,qr,opt),query(rs,ql,qr,opt),mid - max(ql,l) + 1,1);
	return merge(query(ls,ql,qr,opt),query(rs,ql,qr,opt),min(r,qr) - mid,0);
}

signed main()
{
//	freopen("test.in","r",stdin);
//	freopen("test2.out","w",stdout);
	mi[0] = 1;
	for (int i = 1;i <= 500000;i ++) mi[i] = mi[i - 1] * p % mod;
	scanf("%lld",&t);
	while (t --)
	{
		bool fl = false;
		scanf("%lld",&n);
		for (int i = 1;i <= n;i ++) scanf("%lld",a + i);
		build(1,1,n);
		for (int i = 1;i <= n;i ++)
		{
			int siz = min(a[i] - 1,n - a[i]);
			if (!siz)
			{
				upd(1,a[i]);
				continue;
			}
			int lha = query(1,a[i] - siz,a[i] - 1,0),rha = query(1,a[i] + 1,a[i] + siz,1);
			if (lha != rha)
			{
				printf("Y\n");
				fl = true;
				break;
			}
			upd(1,a[i]);
		}
		if (!fl) printf("N\n");
	}
}

H

给出一个 {1,2,⋯ ,n}\{1,2,\cdots,n\} 的全集，从其中选取子集 SS，满足：子集大小 ∥S∥≤k\|S\| \leq k，(至少选择一个数) ∏_u∈Su\prod \_{u \in S} u 是一个平方自由数(square-free integer)，即这个数的质因子幂指数均为1。求满足条件的子集数 mod  109+7\mod 10 ^9 + 7。

多测，T≤5T \leq 5，n,k≤500n,k \leq 500，时限 100ms。

考虑 nn 很小的情况，则质数也很少，直接 dp。

根号分治，发现大于 n\sqrt{n} 的质数在同一个数中最多只能同时选一个，考虑分组 dp，例如 $23 \times 2,23 \times 3,23 \times 2 \times 3,23 \times 5,\cdots$ 为一组，一组中最多选一个，且每一组中的数就是小于 n\sqrt{n} 的质数所有组合再乘上一个大质数，和前一种情况是一样的，同样 dp 即可。

注意循环方向。

20230802

AC 自动机。

模板题

略

AC 自动机 + DP

先用 AC 自动机预处理后直接 DP。

性质：一个给出的串的结束节点跳 fail 到的节点代表这个串最长的、是别的给出串的前缀的后缀。跳若干个 fail 能到的节点代表了所有这样的后缀。

于是，就可以在求 fail 时从 fail 指针指向的节点那里顺便维护一些东西，例如这个节点是否代表串的结束 / 代表了几个串的结束 / 代表了哪些串的结束（结合状压）……从而在 DP 时符合题目的限制。

题目：P4052, P3041, P2322, AcWing 2371, P3193

fail 树 + 数据结构

解决一些子串包含问题。

把 Trie 树上所有 fail 指针拉出来，反过来，就形成了一棵树。一个点是另一个点的祖先代表一个串是另一个串的后缀。而子串是前缀的后缀，树上问题也可以结合数据结构等等解决。

题目：P4600, P2414, （I 题找不到）

20230803

模拟赛。

A~E 都是普及难度（？）。

F 是树剖 + 线段树或者直接倍增，P3976 不带修改版本。

G

我们已经知道了小C开设了一个工厂。现在工人们正在流水线上制造汽车。NN 个工人分别用 11 到 NN 编号，11 号工人位于流水线最左端，NN 号位于最右端。每一个工人都有他特定的工作，并需要一定的时间来完成。

每一辆汽车从 11 号工人(小C)开始制造，当他完成他的工作后立刻交给 22 号工人制造，22 号工人完成后立刻交给 33 号工人，这样一直到 ii 号工人最终完成汽车的制造。制造汽车时必须按照由 11 到 NN 的顺序。

对于第 ii 个工人，我们知道他完成他工作所需的时间 TiT_i。对于每一辆汽车 jj，知道制造这辆汽车的复杂系数 CjC_j。所以工人 ii 完成他所负责的汽车 jj 的工作所需的总时间为 Ti×CjT_i \times C_j。

每当一个工人完成他所负责的工作时，必须立刻交给下一个工人，没有任何时间间隔。也就是说，当工人 ii 完成工作时，工人 i+1i+1 必须空闲，没有正在完成的工作。所以小C想要知道最少需要多少时间才可以按照顺序制造完全部的汽车(编号小的汽车必须先造)。

请帮小C写一个程序，计算出最少所需的时间。

1≤N,M≤1051 \leq N,M \leq 10^5，1≤Ti,Ci≤1041 \leq T_i,C_i \leq 10^4。

第 11 台机器开始造后，要等 xx 分钟后才能开始造下一台，

$$x + C_2 \sum _{i=1} ^{j-1} T_i \geq C_1 \sum _{i=1} ^{j} T_i,1 \leq j \leq n $$

前缀和一下，变为

$$x + C_2 S_{j-1} \geq C_1 S_j,1 \leq j \leq n\\ x \geq C_1 S_j - C_2 S_{j-1},1 \leq j \leq n\\ x \geq C_1 \times \max \{S_j - \frac{C_2}{C_1} S_{j-1} \},1 \leq j \leq n $$

然后就可以斜率优化了。

H

有 NN 个字符串和 QQ 个询问。每一个询问都是由0个，1个或多个小写英文字母和一个""，组成的字符串。例如"", "kulto", "ana"。每一个""可以表示任意一个字符串（可以是空串）。对于每一个询问请求出有多少字符串可以与其匹配（即直接删去""或将"*"替换成字符串可以与最开始输入的 NN 个字符串中的几个相等）。

1≤N,Q≤1000001 \leq N,Q \leq 100000，字符串总长不超过 3×1063 \times 10 ^ 6。

有两种做法。

一种是把前面的 NN 个字符串末尾加一个特殊字符后再拼一个到后面，每个询问的字符串后面接一个特殊字符后把 * 前面的挪到后面，就比如样例：

5 3
eedecc
ebdecb
eaba
ebcddc
eb
e*
*dca
e*c

经过处理后，字符串变为：

eedecc#eedecc
ebdecb#ebdecb
eaba#eaba
ebcddc#ebcddc
eb#eb
#e
dca#
c#e

这样，就可以同时匹配前缀和后缀，原问题变成了询问的字符串在几个字符串中出现过。而且每个询问的字符串只可能在同一个字符串中出现一次，所以比昨天的最后一题简单。直接 AC 自动机解决。

20230804

模拟赛。

A~F 略。

G 是博弈 + dfs 题，赛时判断先后手写错了丢了一半分。

H 是 fail 树 + 线段树优化 DP。

20230805

模拟赛。

A 题略。

B 是 Lucas 定理 + 高维前缀和，用组合数和 Lucas 定理推出来一个结论，但是打表找规律 + 高维前缀和过了。

C

/se 有一条数轴，上面有 nn 条线段，第 ii 条为 [li,ri][l_i, r_i]。现在他想把这 nn 条线段划分为不超过 kk 个集合，每条线段必须恰好属于其中一个集合。定义一个集合的权值为集合里所有线段的交的长度，定义一种划分方案的权值为所有集合的权值之和。求所有满足条件的划分方案中最大的权值。

1≤k≤n≤50001 \leq k \leq n \leq 5000，1≤li<ri≤1e61 \leq l_i < r_i \leq 1e6。

首先通过观察样例猜测出一个贪心策略：把所有线段按照长度排列，取最长的 k−1k-1 条单独放出来，剩下的放在同一个集合里。

显然这是一个假做法，但是在比赛中数据加强前 A 了（）

当最优方法中存在交为空的集合时，这种做法是正确的。

可以发现最优方法中最多有一个集合交为空，否则可以只保留集合中最长的，把剩下的扔到另一个交为空的集合里。

所以只剩下一种情况：最优方法中不存在交为空的集合。

又可以发现：一定存在一种最优方法，完全包含另一条线段的线段要么和被它包含的线段放一起，要么自己单独放一个集合。

调整法证明：完全包含另一条线段的线段和被它包含的线段放一起时，这条线段就没有任何作用。所以这条线段和别的不被它包含的线段放一起时，可以把它移到被它包含的线段那里，这样只会使答案变大。

所以就可以把所有包含其他线段的线段单独拉出来，剩下的线段按左端点排序后，右端点一定单调不递减。

又可以发现，把这些线段分为连续的几段是最优的，每一段 [L,R][L,R] 的价值为 max⁡(0,rL−lR)\max (0,r_L - l_R)。

直接 DP + 前缀和优化，再和前面拉出来的线段一起求答案即可。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;

int n,k;
struct node
{
	int l,r;
}a[5010];
int lng[5010],nw[5010],tmp,tmpn;
int f[5010][5010],g[5010][5010],ans;

signed main()
{
	freopen("se.in","r",stdin);
	freopen("se.out","w",stdout);
	scanf("%lld%lld",&n,&k);
	for (int i = 1;i <= n;i ++) scanf("%lld%lld",&a[i].l,&a[i].r);
	sort(a + 1,a + n + 1,[](node x,node y){return x.r - x.l > y.r - y.l;});
	for (int i = 1;i < k;i ++) ans += a[i].r - a[i].l;
	for (int i = 1;i <= n;i ++)
	{
		bool fl = false;
		for (int j = 1;j <= n;j ++)
		{
			if (i == j) continue;
			if (a[i].l <= a[j].l && a[i].r >= a[j].r && !(a[i].l == a[j].l && a[i].r == a[j].r && i < j))
			{
				fl = true;
				break;
			}
		}
		if (fl) lng[++ tmp] = i;
		else nw[++ tmpn] = i;
	}
	sort(nw + 1,nw + tmpn + 1,[](int x,int y){return a[x].l < a[y].l;});
	memset(f,-0x3f,sizeof(f)),memset(g,-0x3f,sizeof(g));
	g[0][0] = f[0][0] = 0;
	for (int i = 1;i <= tmpn;i ++)
		for (int j = 0;j <= k;j ++)
		{
			g[i][j] = max(g[i - 1][j],f[i - 1][j] + a[nw[i]].r);
			if (j) f[i][j] = g[i][j - 1] - a[nw[i]].l;
//			printf("%d %d %d %d\n",i,j,f[i][j],g[i][j]);
		}
	for (int i = 0;i <= k;i ++)
	{
		int res = f[tmpn][i];
		for (int j = 1;j <= k - i;j ++) res += a[lng[j]].r - a[lng[j]].l;
		ans = max(ans,res);
	}
	printf("%lld\n",ans);
}

D

/fn 有一棵 nn 个点的树，树上每个点有一个正整数权值 aia_i。定义点集的一个子集 SS 是连通的，当且仅当在树上仅保留 SS 内的点以及它们之间的边后，这张图是连通的，定义 SS 的权值为其包含的所有节点的权值之积。/fn 想要知道，这棵树上有多少非空的连通的且权值 ≤m\leq m 的子集 SS，答案对 109+710^9 + 7 取模。

1≤n≤20001 \leq n \leq 2000，1≤m≤1061 \leq m \leq 10^6，ai≤ma_i \leq m。

显然可以树上 DP，f[i][j]f[i][j] 表示节点 ii 为根，连通块权值为 jj 的方案数，但是时间复杂度爆炸。

发现实际上有用的状态数很少，于是考虑用 map 存 DP 数组，在赛时数据加强前可以通过（）

实际上，转移时不需要知道当前连通块的权值是多少，只需要知道再乘多少会爆炸，所以把状态改为 f[i][j]f[i][j] 表示节点 ii 为根，连通块的权值最多再乘 jj 的方案数。

根据数论分块，jj 只有 O(n)O(\sqrt{n}) 这么多，状态数大大减少，但是转移的时间复杂度还是太高了。

发现现在的转移是合并两个背包，但是如果只是向背包中加入一个物品就可以通过。

考虑点分治，DP 时就只需要考虑重心作为根的情况，dfs 到一个点时只需要存自己到重心这条链的背包，且自己是必选的。只需要把父亲的背包拉下来，加上自己，传给儿子后计算完加上儿子的方案数即可。“把父亲的背包拉下来，加上自己”相当于计算这条链到自己就结束了，下面的都不选了的方案数，“传给儿子后加上儿子的方案数”相当于计算选自己和子树内其他节点的方案数。这样就成功地把转移变为了向背包中加入一个物品，可以通过。就很妙。时间复杂度 O(nmlog⁡n)O(n\sqrt{m}\log n)。

代码：

#include <iostream>
#include <cstdio>
using namespace std;

const int mod = 1e9 + 7;

int n,m;
int a[2010];
int to[4010],nxt[4010],head[2010],cnt;
int B[1000010],id[1000010],len;
int siz[2010],vis[2010],root,nsiz,nmax;
int f[2010][10010],ans;

void add(int x,int y)
{
	to[++ cnt] = y;
	nxt[cnt] = head[x];
	head[x] = cnt;
}

void fndroot(int x,int la)
{
	siz[x] = 1;
	int maxsiz = 0;
	for (int i = head[x];i;i = nxt[i])
	{
		int u = to[i];
		if (u == la || vis[u]) continue;
		fndroot(u,x);
		siz[x] += siz[u];
		maxsiz = max(maxsiz,siz[u]);
	}
	maxsiz = max(maxsiz,nsiz - siz[x]);
	if (maxsiz < nmax) root = x,nmax = maxsiz;
}

void solve(int x,int la)
{
	for (int i = head[x];i;i = nxt[i])
	{
		int u = to[i];
		if (u == la || vis[u]) continue;
		for (int j = 1;j <= len;j ++) f[u][j] = 0;
		for (int j = 1;j <= len;j ++)
			f[u][id[B[j] / a[u]]] = (f[u][id[B[j] / a[u]]] + f[x][j]) % mod;
		solve(u,x);
		for (int j = 1;j <= len;j ++)
			f[x][j] = (f[x][j] + f[u][j]) % mod;
	}
}

void dfs(int x)
{
	vis[x] = 1;
	for (int i = 1;i <= len;i ++) f[x][i] = 0;
	f[x][id[m / a[x]]] = 1;
	solve(x,x);
	for (int i = 1;i <= len;i ++) ans = (ans + f[x][i]) % mod;
	for (int i = head[x];i;i = nxt[i])
	{
		int u = to[i];
		if (vis[u]) continue;
		nsiz = siz[u];
		root = 0,nmax = 1e9;
		fndroot(u,x);
		dfs(root);
	}
}

int main()
{
	freopen("fn.in","r",stdin);
	freopen("fn.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i = 1;i <= n;i ++) scanf("%d",a + i);
	for (int i = 1;i < n;i ++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	for (int i = 1;i <= m;)
	{
		int j = m / (m / i);
		if (j > m) j = m;
		B[++ len] = m / i,id[m / i] = len;
		i = j + 1;
	}
//	printf("%d\n",len);
	nsiz = n,nmax = 1e9;
	fndroot(1,0);
	dfs(root);
	printf("%d\n",ans);
}

刚开始重心求错了 WA 了一堆

20230807

模拟赛。

A 是分类讨论，B 是圆方树 + dsu on tree / 莫队，C 是分类讨论，D 是 P5841。

  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. 粤ICP备2021104657号
  3. Worker 0, 17ms
  4. Powered by Hydro v4.14.1 Community