【水】关于WC2021T1的暴力

听取MLE声一片 @ 2021-02-06 09:39:33

by 123456zmy @ 2021-02-06 09:42:12

对于每个起点记录对于每个点可以达到的括号栈状态，直接 DFS，如果括号栈为空则答案+1

by 听取MLE声一片 @ 2021-02-06 09:44:08

@123456zmy 有没有规定上限？

by 123456zmy @ 2021-02-06 09:46:51

对于 32 分那个档，直接把整个括号栈压下位就行

by 123456zmy @ 2021-02-06 09:48:18

大概是 bool vis[N][N][2<<M]; 之类的东西

by WYXkk @ 2021-02-06 09:49:55

@听取MLE声一片 暴力 dfs

void dfs(int u,int v)
{
    if(ok[u][v]) return;
    ok[u][v]=ok[v][u]=1;
    F(i,1,k)
    for(int e1=g[i].head[u];e1;e1=g[i].nxt[e1]) for(int e2=g[i].head[v];e2;e2=g[i].nxt[e2])
    dfs(g[i].to[e1],g[i].to[e2]);
    F(i,1,n) if(i!=u&&ok[u][i]) dfs(v,i);
    F(i,1,n) if(i!=v&&ok[i][v]) dfs(i,u);
}

g 是链式前向星存图，每种一张图

主函数直接 dfs(i,i) 然后枚举点对检查

by WYXkk @ 2021-02-06 09:51:44

有一说一暴力真的很难想……

by ZhiYao @ 2021-02-06 09:53:07

@WYXkk 直接枚举点对搜然后 dep > 2 \times m 剪枝能不能过 32 啊，我自己随机的数据跑了 0,8s

by dehsirehC @ 2021-02-06 09:54:54

@ZhiYao 随便造一个数据就超时了吧？

by WYXkk @ 2021-02-06 09:56:11

@ZhiYao 不清楚，也行能过？

by dehsirehC @ 2021-02-06 09:56:39

实际上我写的是dep>13的剪枝，能得多少分呀？