首页 > 代码库 > 校内训练0611 围墙

校内训练0611 围墙

【题目大意】

围墙可以看成是一个长度为 n 的括号序列,与此同时还有一个长度为 n 的排列 P,一个围墙被称为稳的,当且仅当:

(1)这个括号序列是合法的。

(2)构造一张 n 个点的图, 当且仅当第 i 个位置是左括号时, 点 i 向点 Pi 连边,最后形成的图必须满足每个点度数均为一。

保证对于任意 i 有 Pi!=i。

求一种合法方案。保证有解。

n <= 100

【题解】

我们考虑这是个置换,所以一定形成了很多不相交的环。

对于每个环,我们只能选一段、不选、选一段、不选这样交替下去。

显然只有偶环是有解的,所以只考虑偶环。

每个偶环有2种方案(第一个选,第一个不选),直接枚举是O(2^(n/2))的,复杂度接受不了。

我们发现,2元环的左括号一定放在前面更优(更容易形成括号序列),所以贪心放,剩下的最小是4元环,枚举即可,所以复杂度是O(2^(n/4))。

写个dfs然后发现常数太大。。。(还是过了)

技术分享
# include <vector>
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 200 + 10;
const int mod = 1e9+7;

# define RG register
# define ST static

int n, p[M], ans[M];
int h[M][M], hn[M], a[M], an;
int m; 

int head[M], nxt[M], to[M], tot = 0;
inline void add(int u, int v) {
    ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v;
}
inline void adde(int u, int v) {
    add(u, v), add(v, u);
}

bool vis[M]; 
inline void dfs(int x, int fa) {
    if(vis[x]) return ; 
    vis[x] = 1; 
    a[++an] = x;
    for (int i=head[x]; i; i=nxt[i]) 
        if(to[i] != fa) dfs(to[i], x); 
}

inline void solve(int x) {
    an = 0;
    dfs(x, 0);
    if(an == 2) {
        if(a[1] < a[2]) ans[a[1]] = 1;
        else ans[a[2]] = 1;
    } else {
        ++m; hn[m] = an; 
        for (int i=1; i<=an; ++i) h[m][i] = a[i];
    }
}

inline bool chk() {
    int sum = 0;
    for (int i=1; i<=n; ++i) {
        sum = sum + (ans[i] ? 1 : -1);
        if(sum < 0) return false;
    }
    for (int i=1; i<=n; ++i) putchar(ans[i] ? ( : )); 
    puts("");
    return true;
}

bool ok;
inline void gans(int x) {
    if(ok) return ; 
    if(x == m + 1) {
        if (chk()) ok = 1;
        return ;
    }
    for (int i=1; i<=hn[x]; ++i) ans[h[x][i]] = (i&1);
    gans(x+1);
    for (int i=1; i<=hn[x]; ++i) ans[h[x][i]] ^= 1;
    gans(x+1);
}

int main() {
    freopen("c.in", "r", stdin);
    freopen("c.out", "w", stdout); 
    cin >> n;
    for (int i=1; i<=n; ++i) scanf("%d", &p[i]); 
    for (int i=1; i<=n; ++i) adde(i, p[i]);
    for (int i=1; i<=n; ++i) if(!vis[i]) solve(i); 
//    for (int i=1; i<=m; ++i, puts("\n"))
//        for (int j=1; j<=hn[i]; ++j)
//            printf("%d ", h[i][j]); 
    gans(1); 
    return 0;
}
View Code

 

校内训练0611 围墙