2018.9.9 nowcoder 普及组第一场

C-括号

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

Solution

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

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#define pf(x) printf("%d
", 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;
}

D-配对

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

Solution

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

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

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

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

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

Example

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

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

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

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

(nw[1][1] = alpha otimes eta otimes gamma otimes delta,nw[2][1] = alpha otimes eta 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
", ans);
	return 0;
}