Codeforces Round 970 (Div. 3)（VP）

A. Sakurako's Exam

总结：一看n <= 20,直接暴力+剪枝即可

inline void solve(){
	int a, b;
	cin >> a >> b;

	vector<int> d;
	d.reserve(a + b);
	while (a --) {
		d.push_back(1);
	}
	while (b --) {
		d.push_back(2);
	}

	auto dfs = [&](auto&& self, int idx, int sum) ->bool{
		if (idx == (int)d.size()) {
			return sum == 0;
		}
		return self(self, idx + 1, sum + d[idx] * 1) || self(self, idx + 1, sum + d[idx] * -1);
	};

	cout << (dfs(dfs, 0, 0) ? "YES" : "NO") << '\n';
}

B. Square or Not

总结：模拟遍历一遍即可，判断首末行单独判断

inline void solve(){
	int n;
	cin >> n;

	string s;
	cin >> s;

	if (!mapp[n]) {
		cout << "No\n";
		return;
	}

	int length = mapp[n];

	bool ok = true;
	for (int i = 0; i < n / length; ++i) {
		bool is_one = (!i || (i == (n / length) - 1));
		auto cur = s.substr(i * length, length);
		if (cur[0] != '1' || cur.back() != '1') {
			ok = false;
			break;
		}
		auto cnt = count(cur.begin(), cur.end(), '1');
		if (is_one) {
			if (cnt != length) {
				ok = false;
				break;
			}
		}
		else {
			if (cnt != 2) {
				ok = false;
				break;
			}
		}
	}

	cout << (ok ? "Yes\n" : "No\n");

}

C. Longest Good Array

总结：依然是暴力破解，就是看一个最大终止数值的问题（要求求和<=dif)

inline void solve(){
	long long a, b;
	cin >> a >> b;

	long long dif = (b - a);

	long long l = 0, r = dif;

	auto valid = [dif](long long x) {
		return x * (x + 1) / 2 <= dif;
	};
	while (l < r) {
		long long mid = (l + r + 1) >> 1;
		if (valid(mid))  {
			l = mid;
		}
		else {
			r = mid - 1;
		}
	}

	cout << (l + 1) << '\n';
}

D. Sakurako's Hobby

总结：求出连通分量即可，因为是permutaton数组，所以保证每个点一定在一个环中，具体的tarjan代码参考我的github，有用请点star
https://github.com/yxc-s/programming-template/blob/master/Graph/Tarjan.cpp

 inline void solve(){
	int n;
	cin >> n;

	vector<vector<int>> al(n + 1);
	for (int i = 1; i <= n; ++i) {
		int v;
		cin >> v;
		al[i].push_back(v);
	}

	auto circles = Tarjan::getScc(al);

	string s;
	cin >> s;

	vector<int> ans(n + 1);
	for (const auto& cur : circles) {
		int cnt = 0;
		for (const auto& x : cur) {
			cnt += s[x - 1] == '0';
		}
		for (const auto& x : cur) {
			ans[x] = cnt;
		}
	}

	for (int i = 1; i <= n; ++i) {
		cout << ans[i] << " \n"[i == n];
	}

}

E. Alternating String

总结：分奇偶两种情况讨论，奇数的话就依次考虑移除当前数的最小代价（需要维护一个前缀和后缀奇偶各个字符出现的次数）
偶数的话就直接计算

inline void solve(){
int n;
cin >> n;

string s;
cin >> s;

int ans = 0x3f3f3f3f;
if (n & 1) {
    vector<vector<vector<int>>> pref(n, vector<vector<int>> (2, vector<int>(26, 0)));
    auto suff = pref;
    for (int i = 1; i < n; ++i) {
        pref[i] = pref[i - 1];
        pref[i][(i + 1) & 1][s[i - 1] - 'a'] ++;
    }
    for (int i = n - 2; i >= 0; --i) {
        suff[i] = suff[i + 1];
        suff[i][(i + 1) & 1][s[i + 1] - 'a'] ++;
    }
    for (int i = 0; i < n; ++i) {
        int sum_odd = 0;
        int sum_even = 0;
        int max_odd = 0;
        int max_even = 0;
        int par = (i + 1) & 1;
        for (int j = 0; j < 26; ++j) {
            max_odd = max({max_odd, pref[i][1][j] + suff[i][0][j]});
            max_even = max({max_even, pref[i][0][j] + suff[i][1][j]});
            sum_odd += pref[i][1][j] + suff[i][0][j];
            sum_even += pref[i][0][j] + suff[i][1][j];
        }
        ans = min(ans, sum_odd - max_odd + sum_even - max_even + 1);
    }
}
else {
    array<int, 26> odd = {};
    array<int, 26> even = {};
    for (int i = 0; i < n; ++i) {
        auto& cur = (i + 1) & 1 ? odd : even;
        cur[s[i] - 'a'] ++;
    }
    ans = accumulate(odd.begin(), odd.end(), 0) - *max_element(odd.begin(), odd.end()) + 
        accumulate(even.begin(), even.end(), 0) - *max_element(even.begin(), even.end());
}

cout << ans << '\n';

}