题解 P3757 【[CQOI2017]老C的键盘】

Vemn_Noob · 2019-09-26 21:20:43 · 题解

一种神奇的建图方式+搜索

• 分享一下这个独特的想法 ，但是只有10pts的大爆搜

• 好像逛了逛题解，没人像我这样建图（也许是我太水？）

• 大家都是建的完全二叉树

• 我这个能过n<14的点（指只有10分），其他的点不是TLE就是爆了

• 大意是若a<b

• 则从b向a连一条单向边

• 然后对于每两个没有祖宗关系的（即兄弟关系的云云 ），连无向边

  解释：对于样例2，可建这个图

• 可以看出，只要在入度为0的点出发，然后在出度为0的点结束，遍历完所有节点，就是一个合法排列，对每个入度为0的节点都搜一次，就可以得到结果ans

• 例如 4->3->5->2->1就是一个合法的东东

• 当然了，死因是跑得太慢，也许搜索还能优化

• Code：

#include<bits/stdc++.h>
#define p 1000000007
using namespace std;
struct edge{
    long long to,next,dis;
}e[1250];
long long n,ans=0;
long long now,head[1250];
long long in[1250],out[1250],note[1250];
bool pd[1250][1250],vis[1250],diff[1250][1250];
queue<long long>q[1250],q2[1250];
inline void add(long long u,long long v)
{
    e[++now].to=v;
    e[now].next=head[u];
    head[u]=now;
}
inline void dfs(long long u,long long o)
{
    for(long long i=head[u];i;i=e[i].next)
    {
        long long v=e[i].to;
        pd[o][v]=pd[v][o]=1;
        pd[u][v]=pd[v][u]=1;//记录是否是横叉边
        pd[v][v]=pd[u][u]=1;
        dfs(v,o);
    }
}
inline void find(long long u,long long fath,long long depth)
{
    if(depth==n)
    {
        if(!out[u])ans++,ans%=p;
        return;
    }
    for(long long i=head[u];i;i=e[i].next)
    {
        long long v=e[i].to;
        if(vis[v]||v==fath)continue;
        if(in[u])continue;
        while(!q[u].empty())
        {
            long long x=q[u].front();
            q2[u].push(x);//拓扑排序
            q[u].pop();
            in[x]--;
        }
        vis[v]=1;
        find(v,u,depth+1);
        while(!q2[u].empty())
        {
            long long x=q2[u].front();
            q[u].push(x);
            q2[u].pop();
            in[x]++;
        }
        vis[v]=0;
    }
}
int main()
{
    cin>>n;
    for(long long i=2;i<=n;i++)
    {
        char c;
        cin>>c;
        if(c=='<')add(i,i/2),q[i].push(i/2),diff[i][i/2]=1,pd[i][i/2]=pd[i/2][i]=1,in[i/2]++,out[i]++;
        if(c=='>')add(i/2,i),q[i/2].push(i),diff[i/2][i]=1,pd[i][i/2]=pd[i/2][i]=1,in[i]++,out[i/2]++;
    }
    for(long long i=1;i<=n;i++)
        dfs(i,i);
    for(long long i=1;i<=n;i++)
        for(long long j=1;j<=n;j++)
        {
            if(i==j||pd[i][j]||pd[j][i])continue;
            pd[i][j]=pd[j][i]=1;
            add(i,j);
            add(j,i);//判断是否连无向边
        }
    for(long long i=n;i>=1;i--)
    {
        vis[i]=1;//大爆搜开始了
        if(!in[i])find(i,0,1);
        vis[i]=0;
    }
    cout<<ans%p<<endl;
    return 0;
}