自动搬运

查看原文

来自洛谷，原作者为

	WYXkk Zzz Zzz

搬运于2025-08-24 22:20:56，当前版本为作者最后更新于2020-04-22 19:27:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先说点无关的……

我出了这题，一开始就想到了原题题解中已有的 $O(n^3)$ 解法。

之后我思考了一下，想到了原题题解中没有的一种 $O(n^2)$ 解法。

某天我兴高采烈地想着“是不是所有麻将题都会拿纯九做样例”于是就搜到了这题。

于是我 test 了半天发现他们都过不了（因为我的 解法（不是写法） 常数小）。

同时我发现 baidu 到的前几十篇题解都是 $O(n^3)$ 的。

我私信咨询了 chen_zhe，他表示不适合放公开赛，于是我就扔这儿当加强了。

接下来说解法。

首先，我们可以轻易发现下面这个 $O(n^3)$ 的解法：

枚举听的牌，加一张进去。

枚举雀头，减掉两张。

贪心判断剩下的能不能划分为若干面子：由于三组同样的顺子可以被重新划分为三组刻子，因此尽量多划分为刻子更优。从 $1$ 开始贪心即可，从 $n$ 开始也可以。

代码实现可以参考原题的第一篇题解。此处略去。

此时我们发现，雀头为 $a$ 和 $a+1$ 的时候，我们几乎是把同样的过程做了两遍——从 $1$ 到 $a-1$ 的贪心过程毫无变化，如果反着贪的话那就是 $n$ 到 $a+2$。

于是我们可以考虑 （不去掉雀头） 正着贪一遍，反着贪一遍，记录一些信息，然后再通过记录的这些信息来确定和哪些牌。当然我们必须特判贪到一半贪不动的情况。

我们可以设 $f_{i,0}$ 和 $f_{i,1}$ 分别表示贪完 $1$ 到 $i$ 后需要多少张 $i+1$ 和 $i+2$ 来补全为若干组面子， $g_{i,0}$ 和 $g_{i,1}$ 则分别表示贪完 $n$ 到 $i$ 后需要多少张 $i-1$ 和 $i-2$ 来补全为若干组面子。

这两个贪心时都非常好维护，具体细节见代码。

假如我们根据 $f_{a-1}$ 和 $g_{a+1}$ 来确定雀头为 $i$ 时的答案，那么 $\{a-1,a,a+1\}$ 这组顺子会被试图计算两次，因此不行。

于是我们应该根据 $f_{a-1}$ 和 $g_{a+2}$ 来计算雀头为 $a$ 或 $a+1$ 是否可行。

减去补全需要的个数后，判断一下两个是否都大于零，然后判断是不是一个 $\equiv0\pmod 3$ 一个 $\equiv2\pmod 3$ 即可。

这样判断和牌是 $O(n)$ 的，可以通过本题。

（虽然原题题解的后几篇中也有 $O(n)$ 的 dp 判和，但是常数过大通过不了此加强版，开了 O2 也救不了）

$\texttt{code:}$

#include<cstdio>
#include<iostream>
#include<fstream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define Set(a) memset(a,0,sizeof(a))
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define openf(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define re register
#define ri re int
#define il inline
typedef long long ll;
typedef unsigned long long ull;
template<typename T> inline T rd(T& x)
{
	T f=1;x=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(T)(c-'0');
	x*=f;
	return x;
}
ll rd(){ll x;rd(x);return x;}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
const int inf=1<<30;

const int N=5005;
int a[N],b[N],n;
int l[N][2],r[N][2];
bool check()
{
	F(i,1,n) b[i]=a[i];
	int posl=n-1;
	F(i,1,n-2)
	{
		b[i]-=l[i-1][0];
		if(b[i]<0) {posl=i;break;}
		b[i]%=3;
		l[i][0]=l[i-1][1]+b[i];l[i][1]=b[i];
	}
	F(i,1,n) b[i]=a[i];
	int posr=2;
	UF(i,n,3)
	{
		b[i]-=r[i+1][0];
		if(b[i]<0) {posr=i;break;}
		b[i]%=3;
		r[i][0]=r[i+1][1]+b[i];r[i][1]=b[i];
	}
	bool flg=false;//i-1<posl i+2>posr
	F(i,posr-1,posl)
	{
		int x=a[i]-l[i-1][0]-r[i+2][1],y=a[i+1]-l[i-1][1]-r[i+2][0];
		if(x>=0&&y>=0) if((x%3==2&&y%3==0)||(x%3==0&&y%3==2)) {flg=true;break;}
	}
	bool x=1;F(i,1,n) if(a[i]%2!=0) x=0;
	if(x) flg=1;
	return flg;
}
int ls[N],tot=0;
int main()
{
	rd(n);int k=rd();
	while(k--) ++a[rd()];
	F(i,1,n)
	{
		++a[i];
		if(check()) ls[++tot]=i;
		--a[i];
	}
	printf("%d\n",tot);
	F(i,1,tot) printf("%d ",ls[i]);
	return 0;
}

最后再吐槽几句：

这题强一点的数据比较难造，我一开始完全随机 $k$ 张，结果造出来的不是不听牌就是听所有牌。

于是我就改成先随机一个和牌的然后再去掉一张，如果听 $1$ 或者 $n$ 张就重来（除了 sub12 必听一张，sub4 几乎永远听一张），才正常一点。当然就花了更长的时间写 gen。

（因此输出 0 没分，n[newline]1 2 ... n 只有 sub 2 过 233）