Acwing159周赛题解

A

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110;

int n;

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int res = 0;
	cin >> n;
	
	while (n--) {
   
		int val;
		cin >> val;
		if (val > 0) res++;
	}
	
	cout << res << "\n";
	return 0;
}

B

因为是每次选择弹出队列的队头或者队尾, 观察到最终答案与队列弹出的顺序是没关系的, 具体来说, 假设答案弹第一个队列的第一个元素和第二个元素, 那么顺序是可以任意的, 最终答案取决于每个队列弹出次数, 因此可以用考虑使用$w[i][j]$表示, 第$i$个队列弹$j$次的最大价值, 那么问题就变成了每次选择一个队列弹出并且最大价值是多少

将每个队列看成一个物品组, 问题转化为分组背包问题

时间复杂度$O(m{n}^2)$

因为每次从队头或者队尾弹出, 因此剩余位置一定在中间的一段, 因此可以枚举长度为$n-j$的区间, 在用总和减去中间位置的和

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110, M = 10010;

int n, m;
// 从第i个队列中弹出j个元素
int w[N][N], cnt[N], s[N];
int f[M];

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
   
		int k;
		cin >> k;
		cnt[i] = k;

		memset(s, 0, sizeof s);
		for (int j = 1; j <= k; ++j) {
   
			int val;
			cin >> val;
			s[j] = s[j - 1] + val;
		}

		// 弹出元素数量是j, 那么中间位置元素数量就是k - j
		for (int j = 1; j <= k; ++j) {
   
			for (int l = 1; l <= j + 1; ++l) {
   
				int r = l + k - j - 1;
				w[i][j] = max(w[i][j], s[k] - (s[r] - s[l - 1]));
			}
		}
	}

	for (int i = 1; i <= n; ++i) {
   
		for (int j = m; j >= 0; --j) {
   
			for (int k = 1; k <= j && k <= cnt[i]; ++k) {
   
				f[j] = max(f[j], f[j - k] + w[i][k]);
			}
		}
	}

	cout << f[m] << "\n";
	return 0;
}

C

每次重组, 相当于把环上的起始位置变到其他位置, 因为不能有重复方案因此每次分割线都到换到其他位置

假设当前串是$s_1$, 目标串是$s_2$
将环上位置进行划分

• 可以将当前位置变为目标串的位置数量$cnt$
• 不能将当前串变为目标串的位置数量$n-cnt$

对于当前位置来说, 如果$s_1=s_2$, 那么可选位置位置的数量是$cnt-1$
如果$s_1\ne s_2$, 可选择的位置数量是$cnt$

使用状态机$dp$处理方案数

将集合按照第$i-1$步进行划分, 时间复杂度$O(n^2)$

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;
const int N = 1010, M = 100010, MOD = 1e9 + 7;

int n, m;
char a[N * 2], b[N];
int f[M][2];

// 检查从a字符串起始位置开始与b是否匹配
bool check(int u) {
   
    for (int i = u, j = 1; j <= n; ++j, ++i) {
   
        if (a[i] != b[j]) return false;
    }
    return true;
}

int main() {
   
    ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

    cin >> a + 1 >> b + 1 >> m;
    n = strlen(a + 1); 
    for (int i = 1; i <= n; ++i) a[i + n] = a[i];

    // s1 == s2的位置数量
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
   
        if (check(i)) cnt++;
    }

    check(1) ? f[0][0] = 1 : f[0][1] = 1;
    for (int i = 1; i <= m; ++i) {
   
        f[i][0] = (f[i - 1][0] * (LL) (cnt - 1) + f[i - 1][1] * (LL) cnt) % MOD;
        f[i][1] = (f[i - 1][0] * (LL) (n - cnt) + f[i - 1][1] * (LL) (n - cnt - 1)) % MOD;
    }

    cout << f[m][0] << "\n";
    return 0;
}