codeforces 17C Balance

题意

给定一个串，字符集{'a', 'b', 'c'}，操作是：选定相邻的两个字符，把其中一个变成另一个。可以做0次或者多次，问最后可以生成多少种，使得任意一种字符和其他字符的个数相差都不超过1.

题解

一个生成串压缩之后必定都是初始串的子序列，那么只要能枚举所有子序列，其他的很好搞定。

对于枚举的每个子序列，如果它是由初始串最早能生成的产生，那么肯定不会重。

基于这一点，f(i, a, b, c)表示当前由初始串1~i生成子序列，三个字符分别的个数，类似背包转移即可。

代码

#include<bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define rep(i, a, b) for(int i=(a); i<(b); i++)

#define sz(a) (int)a.size()

#define de(a) cout << #a << " = " << a << endl

#define dd(a) cout << #a << " = " << a << " "

#define all(a) a.begin(), a.end()

#define endl "\n"

typedef long long ll;

typedef pair<int, int> pii;

typedef vector<int> vi;

//---

const int N = 155, P = 51123987;

int n, m;

int ne[N][3], f[N][55][55][55];

string s;

void add(int &a, int b) {

	if((a+=b)>=P) a-=P;

}

int main() {

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	cin >> n >> s;

	s = " " + s;

	memset(ne, -1, sizeof(ne));

	for(int i = sz(s)-1; ~i; --i) {

		rep(j, 0, 3) ne[i][j] = ne[i+1][j];

		if(i) ne[i][s[i]-'a'] = i;

	}

	m = (n+2)/3;

	f[0][0][0][0] = 1;

	rep(i, 0, n+1) {

		rep(a, 0, m+1) rep(b, 0, m+1) rep(c, 0, m+1) {

			rep(j, 0, 3) if(~ne[i][j]) {

				int t = ne[i][j];

				add(f[t][a+(j==0)][b+(j==1)][c+(j==2)], f[i][a][b][c]);

			}

		}

	}

	int ans = 0, l = n/3, r = m;

	rep(i, 1, n+1) {

		rep(a, l, r+1) rep(b, l, r+1) rep(c, l, r+1) if(a+b+c==n) {

			add(ans, f[i][a][b][c]);

		}

	}

	cout << ans << endl;

	return 0;

}

巴特西

codeforces 17C Balance（动态规划）

codeforces 17C Balance

题意

题解

代码

最新文章

热门文章