套题1

T1

给出一个 (n) 长的 (01) 串；
每次操作可以将一个 (0) 转化为 (1)，或者反向操作；
要求最少能使所有 (0) 在 (1) 前面的操作数；

solve

预处理关于 (1) 的前缀和
枚举 (0, 1) 的交界点进行判断

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>

using namespace std;
const int N = 1e5 + 10;

char s[N];
int A[N];

int main() {
	scanf("%s", s + 1);
	int n = strlen(s + 1);
	for(int i = 1; i <= n; i ++) 
		if(s[i] == '0') A[i] = 0;
		else A[i] = 1;
	for(int i = 1; i <= n; i ++) A[i] += A[i - 1];
	int Answer = (1 << 30);
	for(int i = 1; i <= n + 1; i ++) {
		int now = A[i - 1] + (n - i + 1) - (A[n] - A[i - 1]);
		Answer = min(Answer, now);
	}
	cout << Answer;
	return 0;
}

---

T2

给定 (n), 求有多少对 ((x, y)) 满足

1. (x < y)
2. (x, y) 中出现的 ([0, 9]) 的数码种类相同

solve

由于只要求种类相同
只需记录每个种类出现的次数
然后组合数计算即可

在记录种类时有个技巧
假设 (x) 映射出来的数为 (a)
若 (i) 存在于 (x) 的数码中
则对 (a) 加 (2 ^ i)
这样的话，不会存在 (x) 不同 (a) 相同的情况
可以计算 (a <= 1024)

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;
const int size = 1024;

int n;
int f[size];
long long ans;
bool v[10];
int u[10] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++) {
		int a = i, b = 0;
		memset(v, 0, sizeof v);
		while(a) v[a % 10] = 1, a /= 10;
		for(int j = 0; j <= 9; j ++) if(v[j]) b += u[j];
		f[b] ++;
	}
	for(int i = 0; i < size; i ++) ans += 1ll * f[i] * (f[i] - 1) / 2;
	cout << ans;
	return 0;
}

---

T3

给出长度为 (n) 的序列
求最长子序列满足
偶数项 (>) 相邻的两项，且差 (<= k)

slove

(n ^ 2) dp
(f_i) 表示第 (i) 个为奇数项时到 (i) 的最长子序列
(g_i) 表示第 (i) 个为偶数项时到 (i) 的最长子序列

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>

using namespace std;

const int N = 2e6 + 10;

int n, k, A[N], f[N], g[N];

int main() {
	cin >> n >> k;
	for(int i = 1; i <= n; i ++) cin >> A[i];
	for(int i = 1; i <= n; i ++) {
		int Max = 0;
		for(int j = 1; j < i; j ++) {
			if(A[i] <= A[j] && A[j] - A[i] >= k) {
				Max = max(Max, g[j]);
			} 
		}		
		f[i] = Max + 1;
		Max = -1;
		for(int j = 1; j < i; j ++) {
			if(A[i] >= A[j] && A[i] - A[j] >= k) {
				Max = max(Max, f[j]);
			}
		}
		g[i] = Max + 1;
	}
	int Answer = 0;
	for(int i = 1; i <= n; i ++) Answer = max(max(g[i], f[i]), Answer);
	cout << Answer;
	return 0;
}

(O(n)) 贪心

#include<bits/stdc++.h>

using namespace std;
const int maxn = 2000008;

int n, m, a[maxn];

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 0; i < n; i ++) scanf("%d", a + i);
	int ans = 1, k = 0, cur = a[0];
	for(int i = 1; i < n; i ++)
		if(k) {
			if(cur - m >= a[i]) k = 0, cur = a[i], ans ++;
			else cur = max(cur, a[i]);
		} else {
			if(a[i] - m >= cur)	k = 1, cur = a[i], ans ++;
			else cur = min(cur, a[i]);
		}
	printf("%d
", ans);
	return 0;
}