题解 P6454 【麻将 加强版】

· · 题解

先说点无关的……

我出了这题，一开始就想到了原题题解中已有的 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）