题解：CF2059E2 Stop Gaming (Hard Version)

先讲一下题意，赛时一直在写假题。

给你

n

行

m

列矩阵

a_{i,j}

与

b_{i,j}

，

b

内元素互异。你可以对

a

进行下面的操作：

选择某一行，在它的头部插入任意一个数，其它数后推一格，并删去最后一行最后一个数。

下面是一个例子（选择第

1

行，插入

10

）：

\begin{matrix} 1 &2 &3\\ 4 &5 &6\\ 7 &8 &9 \end{matrix} \Rightarrow \begin{matrix} 10 &1 &2\\ 3 &4 &5\\ 6 &7 &8 \end{matrix}

求使

a \to b

的最小操作次数，并输出一个方案。

最小操作次数等于

n \cdot m

减去保留

a

中元素个数，所以我们要尽可能多地保留

a

中元素。

因为每次删数都是删去矩阵内最后一个数，所以留下的

a

中元素一定是

a

的一个前缀。

再看看

b

，

b

中的元素要么来自

a

，要么来自插入。

如何判断

b

中的某个数能否来自插入？

如果

b

中某个数能来自插入，那它一定曾是

a

某行的开头。

假设它前面来自

a

的元素个数为

pre

，它现在在

b

中位于第

x

列，至少应该满足：

(x-1)-pre \geq (x-1)\bmod m

，即：删去部分前面插入的数足够让它回到这一行的开头。

假如满足上面的条件，一直插入最靠后且满足条件的数就是一个方案，即这个数可以来自插入。发现这是个充要条件。

于是直接将

b

去跟

a

匹配，配上这个元素就来自

a

，没配上就考虑能否来自插入，再不能就失配，E1 就做完了。

什么？你说复杂度不对？

别忘了，

b

内元素互异。

E2 就是输出这个“一直插入最靠后且满足条件的数”的过程，预处理出每个数插入前提是前面插入多少个数，拍到线段树上模拟就好。

E1

CPP

void R()
{
	int n,m;
	cin>>n>>m;
	int N=n*m;
	vector<int> a(N),b(N),c;
	for (int &x:a) cin>>x;
	for (int &x:b) cin>>x;

	auto back=[&](auto &self,int x)->void
	{
		while (x-c.size()<x%m)
		{
			int t=c.back();
			c.pop_back();
			self(self,t);
		}
	};

	for (int i=0;i<N;i++)
	{
		if (b[i]==a[c.size()])
			c.push_back(i);
		else back(back,i);
	}

	cout<<N-c.size()<<'\n';
	return;
}

E2

略去了区间

\min

线段树板子。

CPP

void R()
{
	int n,m;
	cin>>n>>m;
	int N=n*m;
	vector<int> a(N),b(N),c,id(2*N+1),vis(2*N+1);
	SGT<Info,Tag> sgt(N);
	for (int i=0;i<N;i++)
	{
		cin>>a[i];
		id[a[i]]=i;
	}
	for (int &x:b) cin>>x;

	auto back=[&](auto &self,int x)->void
	{
		while (x-c.size()<x%m)
		{
			int t=c.back();
			c.pop_back();
			self(self,t);
		}
	};

	for (int i=0;i<N;i++)
	{
		if (b[i]==a[c.size()])
			c.push_back(i);
		else back(back,i);
	}
	for (int p:c) vis[b[p]]=1;
	for (int i=0;i<N;i++)
		if (!vis[b[i]])
		{
			int pre=lower_bound(c.begin(),c.end(),i)-c.begin();
			sgt.modify(i,{(m-pre%m)%m});
		}

	int ans=N-c.size();
	cout<<ans<<'\n';
	for (int i=0;i<ans;i++)
	{
		auto pred=[&](Info x)->bool
		{
			return x.x<=0;
		};

		int pb=sgt.findLast(0,N,pred);
		int pre=lower_bound(c.begin(),c.end(),pb)-c.begin();
		cout<<(pre+(m-pre%m)%m)/m+1<<' '<<b[pb]<<'\n';
		sgt.rangeApply(pb,N,{-1});
		sgt.modify(pb,{inf});
	}
	return;
}

题解：CF2059E2 Stop Gaming (Hard Version)

文章操作

E1

E2

相关推荐

评论

题解：CF2059E2 Stop Gaming (Hard Version)