2018.9.9 nowcoder 普及组第一场

题目大意:一个只包含左右括号的字符串\(S\),希望删掉S中若干个字符，使得剩下的字符串是一个合法的括号串,有多少不同的方案。

Solution

• 状态:\(f[i][j]\)表示处理到字符串的第\(i\)个位置,现在有\(j\)个左括号没有GF右括号的保留情况总方案数
• 转移:见代码

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#define pf(x) printf("%d\n", x)

const int N = 1e4 + 10;
const int mod = 1e9 + 7;

int n;
char s[N];
int a[N], f[3][N];

int main(){
    scanf("%d", &n);
    scanf("%s", s + 1);
    int now = 0;
    f[now][0] = 1;
    for (int i = 1; i <= n; i++){
        now ^= 1;
        if(s[i] == '('){
            f[now][0] = f[now ^ 1][0] % mod;//继承上一个
            for(int j = 1; j <= n; ++j)
                f[now][j] = (f[now ^ 1][j - 1] + f[now ^ 1][j]) % mod;//现在是左括号,可以不选这个左括号,也可以选这个左括号,
        } else if(s[i] == ')'){
            f[now][n] = f[now ^ 1][n];//继承上一个
            for(int j = 0; j < n; ++j)
                f[now][j] = (f[now ^ 1][j + 1] + f[now ^ 1][j]) % mod;//现在是右括号,可以不选这个右括号, 但是选了就要减去一个左括号,于是要由上一个位置比现在多一个左括号转移来
        }
    }
    printf("%d", (f[now][0] - 1 + mod ) % mod);//会有全为空的情况
    return 0;
}

题目大意:给出\(n\)个长度为\(l\)的字符串,只包含\(a\)到\(h\)八个字母,可以最多用\(k\)次操作声明两个字母等价,且等价具有传递性,求最多可以让多少对字符串完全等价

Solution

因为只有8个字符,所以可以将字符间的情况看作联通块,联通块的情况有\(\Large\{^{n}_{m}\}\)种,也就是把\(8\)个字母划分为\(8-k\)个非空子集中的个数,为第二类斯特林数

通过枚举字母的联通快情况,我们算出\(hash\)值来判断共有多少字符串等价

可以用随机数来\(hash\),因为不需要求区间\(hash\)值,而且不容易被卡.

但是如果每次都\(O(n\cdot l)\)的求所有的hash值,很容易超时,所以我们试着去简化,预处理出每一个字符串中每一种字母的累加哈希值\(\sum\limits_{s_i=c}base^i(has[i])\)

所以我们只需要处理出对于每个字符串的每个联通块的\(hash\)就好,可以去累加联通块中的每个字符的哈希值

Example

如果\(aabb \\ abbb\) 那么 \(has[1] = \alpha, has[2] = \beta, has[3] = \gamma,has[4]=\delta\)

\(inc[1][a] = \alpha \otimes \beta,inc[1][b] = \gamma \otimes \delta\)

\(inc[1][a] = \alpha,inc[1][b]=\beta \otimes \gamma \otimes \delta\)

假使\(a = b\),那么\(bel[a] = bel[b] = 1\)

\(nw[1][1] = \alpha \otimes \beta \otimes \gamma \otimes \delta,nw[2][1] = \alpha \otimes \beta \otimes \gamma \otimes \delta\)

Code

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>

typedef long long ll;

const int N = 1005;

int n, l, k;
ll has[N], inc[105][10], bel[10], nw[105][10];
char s[105][1005];
int ord[N];

inline ll Ra(){
    return rand() * rand() * 1LL * rand();
}

inline bool cmp(int a, int b){
    for(int i = 1; i <= k; ++i)
        if(nw[a][i] < nw[b][i]) return 1;
        else if(nw[a][i] > nw[b][i]) return 0;
    return 0;
}

inline int check(){

    for(int i = 1; i <= n; ++i){
        memset(nw[i], 0, sizeof(nw[i]));
        for(int j = 1; j <= 8; ++j){
            nw[i][bel[j]] ^= inc[i][j];
        }
        ord[i] = i;
    }
    std::sort(ord + 1, ord + n + 1, cmp);
    int cnt = 1, ans = 0;
    for(int i = 2; i <= n; ++i){
        if(!cmp(ord[i], ord[i - 1]) && !cmp(ord[i - 1], ord[i])) cnt++;
        else ans += cnt * (cnt - 1) / 2, cnt = 1;//cnt要为1,因为这是记录对数
    }
    ans += cnt * (cnt - 1) / 2;
    return ans;
}

int ans = 0;
void dfs(int x, int tot){//tot表示联通块个数, x表示第x个字符
    if(x >= 8){
        if(tot != k) return ;
        ans = std::max(ans, check());
        return;
    }
    for(int i = 1; i <= tot; ++i)
        bel[x + 1] = i, dfs(x + 1, tot);
    bel[x + 1] = tot + 1, dfs(x + 1, tot + 1);
}

int main(){
    scanf("%d %d %d", &n, &l, &k);
    for(int i = 1; i <= n; ++i)
        scanf("%s", s[i] + 1);
    if(k >= 7){
        printf("%d", n * (n - 1) / 2);
        return 0;
    }
    k = 8 - k;
    for(int i = 1; i <= l; ++i){
        has[i] = Ra();
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= l; ++j){
            inc[i][s[i][j] - 'a' + 1] ^= has[j];
        }
    dfs(0, 0);
    printf("%d\n", ans);
    return 0;
}