dp做题笔记4

dp做题笔记4

这次题目主要来源于Codeforces的dp专题

CF1594B Gregor and the Pawn Game

题意：

给定一个 N×N 的棋盘，第一行有若干敌方棋子，第 N 行有若干己方棋子，有两种走方式，问有多少己方棋子能到第一行。0表示该格没有棋子，1表示该格有棋子

行走方式：

若前方无棋子可直线走。斜着走并吃敌方棋子。

思路：

        贪心即可，能走直线则走直线，否则走左或者走右

 

#include

using namespace std;
const int maxn = 2e5 + 5;
char a[maxn], b[maxn];
bool vis[maxn];

void solve() {
	memset(vis, 0, sizeof(vis));
	int n; cin >> n;
	scanf("%s%s",a + 1, b + 1);
	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		if (b[i] == '1' && a[i] == '0') ++ans; //直走
		else if (b[i] == '1' && a[i] == '1') {
			//左走
			if (i > 1 && a[i - 1] == '1' && !vis[i - 1]) {
				vis[i - 1] = true;
				++ans;
			//右走
			}else if (i < n && a[i + 1] == '1' && !vis[i + 1]) {
				vis[i + 1] = true;
				++ans;
			}
		}
	}
	cout << ans << endl;
}

int main() {
	int tt; cin >> tt;
	while (tt--) {
		solve();
	}

	return 0;
}

CF1539B Love Song

题意：

        将字符串中的字符重复特定次数后输出字符串长度，以题可知a重复一次，b两次，c三次……（并不是第几个出现就重复几次）

思路：前缀和

#include

using namespace std;
const int maxn = 1e5 + 5;

int main() {
	int n, q; cin >> n >> q;
	vector sum(n + 1);
	for (int i = 0; i < n; ++i) {
		char c; cin >> c;
		sum[i + 1] = sum[i] + c - 'a' + 1;
	}
	while (q--) {
		int l, r; cin >> l >> r;
		--l;
		cout << sum[r] - sum[l] << endl; 
	}


	return 0;
}

CF1323A  Even Subset Sum Problem

题意：

        给你n个正整数，让你找到它的一个子集使得这个子集的和是偶数

思路：

        如果数列中有偶数直接输出即可， 否则输出前两个奇数。

#include

using namespace std;
const int maxn = 105;

void solve() {
	int n; cin >> n;
	int a[maxn];
	for (int i = 0; i < n; ++i) cin >> a[i];
	int i;
	for (i = 0; i < n; ++i){
		if (a[i] % 2 == 0) break;
	}
	if (i < n) printf("1n%dn", i + 1);
	else if (n < 2) printf("-1n");
	else printf("2n1 2n");
}

int main() {
	int tt; cin >> tt;
	while (tt--) {
		solve();
	}

	return 0;
}

CF1566B MIN-MEX Cut

题意：

        将一个01字符串分割成若干连续子串，使每个子串的Mex之和最小。01字符串的Mex为该字符串中未出现的最小非负整数。

思路：

        不难看出一个 01 串的 MEX 最大可取到 22，若想要最小化所有分割子串的 MEX 之和，我们可以把 00 区间（连续的 00）和 11 区间（连续的 11）分割出来。所以，最后的答案就是 00 区间的个数和 22 之间取最小值。

#include

using namespace std;
const int maxn = 105;

void solve() {
	string s; cin >> s;
	int zero = 0;
	for (int i = 0; i < s.size(); ++i) {
		if (s[i]=='0') {
			++zero;
			while (i < s.size() && s[i] == '0') ++i;
		}
	}
	cout << min(zero, 2) << endl;

}

int main() {
	int tt; cin >> tt;
	while (tt--) {
		solve();
	}

	return 0;
}

CF1245C Constanze's Machine

题意：

        给你一个字符串，其中两个u 可以变成w，两个n可以变成m，可以不变，问有多少种可能的字符串

思路：

        先写几个出来看看结果

        n 1
        ​nn 2
        ​nnn 3
        ​nnnn 5
        ​nnnnn 8 这不斐波那契数列吗！！！于是我们大胆的推测状态转移方程就是斐波那契数列

#include

using namespace std;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;

long long f[maxn];

void solve() {
	string s; cin >> s;
	f[0] = f[1] = 1;
	if (s[0] == 'w' || s[0] == 'm') {
		cout << 0 << endl;
		return ;
	}
	for (int i = 1; i < s.size(); ++i) {
		if (s[i] == s[i - 1] && (s[i] == 'u' || s[i] == 'n'))
			f[i + 1] = (f[i] + f[i - 1]) % mod;
		else f[i + 1] = f[i];
		if (s[i] == 'w' || s[i] == 'm') {
			cout << 0 << endl;
			return ;
		}
	}
	cout << f[s.size()] << endl;
}

int main() {
	int tt = 1; //cin >> tt;
	while (tt--) {
		solve();
	}

	return 0;
}

CF180C Letter

题意：

        给你一个字符串，每一次 *** 作可以将大写字母改成小写，反之亦然。问经过最少的 *** 作数，使得此串的大写字母全部都在小写字母的左边。

思路：

        dp，考虑s[i]左右两边的大小写情况，我们设L[i]表示i左侧小写字母的个数，R[i]表示i右侧大写字母的个数，可以得到,

        若s[i]为小写字母 则 ans = min{L[i - 1] + R[i], ans}

        若s[i]为大写字母 则 ans = min{R[i +1] + L[i], ans}

#include

using namespace std;
const int maxn = 1e5 + 5;

bool check(char a) {
	if (a >= 'a' && a <= 'z') return false;
	if (a >= 'A' && a <= 'Z') return true;
	return false;
}

void solve() {
	char s[maxn];
	scanf("%s", s + 1);
	int len = strlen(s + 1);
	int l[maxn] = {0};
	int r[maxn] = {0};
	for (int i = 1; i <= len; ++i) {
		if (!check(s[i])) ++l[i];
		l[i] += l[i - 1];
	}
	for (int i = len; i >= 1; --i) {
		if (check(s[i])) ++r[i];
		r[i] += r[i + 1];
	}
	int ans = len;
	for (int i = 1; i <= len; ++i) {
		if (check(s[i])) ans = min(ans, l[i] + r[i + 1]);
		else ans = min(ans, l[i - 1] + r[i]);
	}
	cout << ans << endl;
}

int main() {
	int tt = 1; //cin >> tt;
	while (tt--) {
		solve();
	}

	return 0;
}