本文为题解集。为 Yurchiu 所参加的模拟赛题目。

A factory

题意

给出一个长度为 $n$ 的正整数序列 $a$ 。

定义一个“家族”为：

是序列 $a$ 中连续的一段；
若 $a_i$ 和 $a_j$ 属于同一个家族（ $i<j$ ），则 $a_i$ 到 $a_j$ 从小到大排序后一定是公差大于 $1$ 的等差数列的子序列。

求序列 $a$ 最少可划分成的家族数。

$n\le 1\times10^5$ ， $1\le a_i\le1\times10^9$ 。

样例

7
1 5 11 2 6 4 7

3
--------------
8
4 2 6 8 5 3 1 7

2
--------------
5
5 5 5 5 5

5
--------------
8
1 3 5 5 7 9 11 1

2
--------------
8
1 3 5 5 5 9 11 1

3
--------------
8
1 3 5 5 3 3 4 6

4
--------------
9
1 2 2 2 2 2 2 5 7

8
--------------
7
1 9 1 9 1 9 1

4

点击查看题解

题解

考虑贪心。

易证区间 $[i,j]$ 合法的充要条件为：所有相邻的数之差的绝对值的 gcd 不等于 $1$ ，且 $a_i\sim a_j$ 两两不同。

gcd 不为 $1$ 很容易判，相邻的数作差，求 gcd 即可。

判断两两不同，需要 map 或者其他的东西。

每次遇到 gcd 等于 $1$ 或有重复，ans 加一即可。

代码

#include<bits/stdc++.h>
using namespace std;

namespace _yz
{
	typedef long long ll;
	const ll N=200000+10;
	ll n,a[N],ans=1,pre,dis,pgcd;
	map<ll,ll>check;
	
	ll gcd(ll a,ll b)
	{
		return b?gcd(b,a%b):a;
	}
	void main()
	{
		scanf("%lld",&n);
		for(ll i=1;i<=n;i++)
			scanf("%lld",a+i);
		if(n==1)
		{
			printf("1\n");
			return;
		}
		if(n==2)
		{
			if(abs(a[2]-a[1])==1) printf("2\n");
			else printf("1\n");
			return; 
		}
		pre=abs(a[2]-a[1]);
		pgcd=pre;
		if(pre==0||pre==1) ans++;
		check[a[1]]=1;
		check[a[2]]=1;
		for(ll i=2;i<=n-1;i++)
		{
			dis=abs(a[i+1]-a[i]);
			if(gcd(pgcd,dis)==1||check[a[i+1]])
			{
				ans++; i++;
				check.clear();
				while(i<=n-1)
				{
					dis=abs(a[i+1]-a[i]);
					if(dis==0||dis==1) ans++;
					else break;
					i++;
				}
				pre=pgcd=dis;
				check[a[i]]=1;
				check[a[i+1]]=1;
			}
			check[a[i+1]]=1;
			pre=dis;
			pgcd=gcd(pgcd,dis);
		}
		printf("%lld\n",ans);
		return;
	}
}
int main()
{
	_yz::main();
	return 0;
}

B friendship

题意

给出 $n$ 个集合，编号 $1\sim n$ 。

进行 $m$ 次操作，共 $3$ 种：

集合的交：新建一个集合，为进行操作的 $k$ 个集合的交。
集合的并：新建一个集合，为进行操作的 $k$ 个集合的并。

这两个操作的格式是 0 op k a1 ... ak。op 为 $0$ 指集合的交，为 $1$ 指集合的并；a1 ... ak 是进行操作的 $k$ 个集合的编号，新建集合的编号是当前集合总个数加一。

查询：给定两个集合 $X$ 和 $Y$ ，询问 $X\subseteq Y$ 是否一定成立。

样例

3 5
0 0 2 1 2
1 1 4
0 1 2 3 4
1 4 5
1 4 2

0
1
1
---------------
4 5
0 1 1 2
0 1 1 1
0 0 1 6
1 1 7
1 1 4

1
0

点击查看题解

题解

容易发现，交包含于进行操作的集合，进行操作的集合包含于并。

因此，我们从交到进行操作的集合连边，从进行操作的集合到并连边。这就转化图论问题，判断 $X$ 能否访问到 $Y$ ，类似于 [Idea] 充要条件。

注意， $k=1$ 时交和并等价，需特判。

代码（ $n^2$ ）

#include<bits/stdc++.h>
using namespace std;

namespace _yz
{
	typedef long long ll;
	const ll N=1000000+10;
	ll n,m,total=0,tag;
	ll cnt=0,vis[N],head[N];
	struct edge{ll nxt,to;}e[N*2];
	
	void add(ll a,ll b)
	{
		e[++cnt]=(edge){head[a],b};
		head[a]=cnt;
	}
	ll dfs(ll now,ll ed)
	{
		if(now==ed) return 1;
		ll ret=0;
		vis[now]=tag;
		for(ll i=head[now];i;i=e[i].nxt)
		{
			ll to=e[i].to;
			if(vis[to]==tag) continue;
			ret=max(ret,dfs(to,ed));
		}
		return ret;
	}
	void main()
	{
		ll type,opt,cnt,tmp,x,y;
		scanf("%lld%lld",&n,&m);
		total=n;
		for(ll i=1;i<=m;i++)
		{
			scanf("%lld",&type);
			if(type==0)
			{
				total++;
				scanf("%lld%lld",&opt,&cnt);
				if(cnt==1)
				{
					scanf("%lld",&tmp);
					add(total,tmp);
					add(tmp,total);
					continue;
				}
				for(ll j=1;j<=cnt;j++)
				{
					scanf("%lld",&tmp);
					if(opt==0) add(total,tmp);
					else add(tmp,total);
				}
			}
			else
			{
				scanf("%lld%lld",&x,&y);
				tag++;
				if(dfs(x,y)) printf("1\n");
				else printf("0\n");
			}
		}
		return;
	}
}
int main()
{ 
	_yz::main();
	return 0;
}

C empire

题意

给定 $n+1$ 座城市，编号 $0\sim n$ 。其中：

从第 $(i-1)$ 座城市坐火车到第 $i$ 座城市需要花费 $a_i$ 的费用。
在第 $i$ 座城市上车需要缴纳 $b_i$ 的税款**。税款不是乘坐火车的费用**。
如果连续地乘坐一段火车的费用大于这次上车前所需缴纳的税款，则这次上车前的税款可以被免除，否则免去乘坐这段火车的费用。
给定 $k$ ，每一次乘坐都不能连续经过（即不包括上车时所在的城市）超过 $k$ 座城市。

求从第 $0$ 座城市到达第 $n$ 座城市的最小花费。

样例

4 2
4 3 2 1
1 2 4 4
    
11
----------
4 2
4 3 2 1
1 2 10 3
    
12
---------
4 2
1 3 2 4
1 1 1 1

10
---------
4 2
1 3 2 4
1 3 2 4

10

部分分代码

#include<bits/stdc++.h>
using namespace std;

namespace _yz
{
	typedef long long ll;
	const ll N=500000+10,N1=30+10;
	const ll N2=10000+10,K2=1000+10;
	const ll inf=5000000000000+2147483647;
	ll n,m,a[N],b[N],p[N];
	ll cheat1=1,ans=inf;
	ll f1[N1][N1],minb=inf;
	ll f2[K2][N2],mx[N2];
	// f1[i][j] 最后一段 (i,j] 的最小值 
	// f2[i][j] 最后一段 (j-i,j] 的最小值
	
	struct node{ll id,val;};
	queue<node>q;
	
	ll get(ll l,ll r)
	{
		return p[r]-p[l];
	}// (l,r] 的和 
	void cheat2()
	{
		for(ll i=0;i<=n;i++)
		{
			for(ll j=0;j<=n;j++)
			{
				f1[i][j]=inf;
			}
		}
		for(ll i=1;i<=m;i++)
		{
			f1[0][i]=max(get(0,i),b[1]);
		}
		for(ll j=1;j<=n;j++)
		{
			for(ll i=0;i<=j-1;i++)
			{
				if(j-i>m) continue;
				for(ll k=0;k<=i-1;k++)
				{
					ll fee=max(get(i,j),b[i+1]);
					f1[i][j]=min(f1[i][j],
								 f1[k][i]+fee);
				}
				if(j==n)
				{
					ans=min(ans,f1[i][j]);
				}
				//printf("f[%lld][%lld]=%lld\n",i,j,f1[i][j]);
			}
		}
		printf("%lld\n",ans);
	}
	void cheat3()
	{
		for(ll i=1;i<=n;i++)
			mx[i]=inf;
		mx[1]=max(get(0,1),b[1]);
		for(ll j=2;j<=n;j++)
		{
			for(ll i=1;i<=m;i++)
			{
				f2[i][j]=mx[j-i]+max(get(j-i,j),b[j-i+1]);
				mx[j]=min(mx[j],f2[i][j]);
			}
		}
		printf("%lld\n",mx[n]);
	}
	void main()
	{
		scanf("%lld%lld",&n,&m);
		for(ll i=1;i<=n;i++)
		{
			scanf("%lld",a+i);
			p[i]=p[i-1]+a[i];
		}
		for(ll i=1;i<=n;i++)
		{
			scanf("%lld",b+i);
			if(b[i]!=1&&b[i]!=a[i]) cheat1=0;
			minb=min(minb,b[i]);
		}
		if(cheat1)
		{
			printf("%lld\n",p[n]);
			return;
		}
		if(n==m)
		{
			printf("%lld\n",max(p[n],minb));
			return;
		}
		if(n<=30&&m<=5)
		{
			cheat2();
			return;
		}
		if(n<=10000&&m<=1000)
		{
			cheat3();
			return;
		}
		return;
	}
}
int main()
{ 
	freopen("empire.in","r",stdin);
	freopen("empire.out","w",stdout); 
	_yz::main();
	return 0;
}
/*
4 2
1 3 2 4
1 1 1 1

10
---------
4 2
1 3 2 4
1 3 2 4

10
---------
4 2
4 3 2 1
1 2 4 4

11
---------
4 2
4 3 2 1
1 2 10 3

12
---------
*/