CF 1463 D. Grime Zoo
题意
给一个包含 '?' 的 01 串， 你可以在 '?' 中填入 0 或 1
每一个 '01' 子串会贡献 (x) 的恶评， '10' 子串会贡献 (y) 的恶评
求最小恶评值
当时思考情况：
想到了当 0 的个数和 1 的个数确定的时候一定是把 0 放一边，把 1 放在另一边。
但是我不知道在问号其他位置有 0，1 的时候是不是也是分两边放。
当时我算了每个问号取 0 时候的贡献和取 1 的贡献，然后我把问题转换为了 选的贡献加上问号之间的贡献
问号之间的贡献最小肯定是选一边的 0 和一边的 1， 但是还要考虑对本有数字的贡献。我当时的思考就在这里停下了。
其实就算有数字这个结论也是成立的，因为:
假设 0 和 1 的个数已经确定了， 在问号处先随机填入 0 和 1
当我们交换问号处的 0 和 1 的时候（0 在前面）， 其实就是把若干个 '01' 变成了 '10'
交换 1 和 0 的时候（1 在前面)， 就是把 '10' 变成了 '01' ，很显然我们需要一直往一个方向去靠，最后就会变成一堆 0 和一堆 1.
/*
* @Author: zhl
* @LastEditTime: 2020-12-23 14:29:24
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;
char s[N];
int x, y, s0[N], s1[N], pos[N], tot;
ll sw0[N], sw1[N];
signed main() {
scanf("%s", s + 1); int n = strlen(s + 1);
scanf("%lld%lld", &x, &y); ll res = 0;
for (int i = 1; i <= n; i++) {
s0[i] = s0[i - 1] + (s[i] == '0');
s1[i] = s1[i - 1] + (s[i] == '1');
res += (s[i] == '0') * s1[i] * y;
res += (s[i] == '1') * s0[i] * x;
}
for (int i = 1; i <= n; i++) {
if (s[i] == '?') {
pos[++tot] = i;
sw0[tot] = sw0[tot - 1] + s1[i] * y + (s1[n] - s1[i]) * x;
sw1[tot] = sw1[tot - 1] + s0[i] * x + (s0[n] - s0[i]) * y;
}
}
ll ans = 1e18;
for (int i = 1; i <= tot; i++) {
ans = min(ans, i * (tot - i) * x + sw0[i] + sw1[tot] - sw1[i]);
ans = min(ans, i * (tot - i) * y + sw1[i] + sw0[tot] - sw0[i]);
}
if (ans == 1e18)ans = 0;
cout << res + ans << endl;
}
CF 1463 E. Poman Numbers
给一个字符串和一个函数
[f(S) = egin {cases}2^{pos(S[1])} &&|S|=1\\-f(S(1,m)) + f(S(m+1,|S|)),&&|S| > 1end{cases}
]
问能不能凑出一个数 (K) ，通过有目的的选取每次的 (m)
有个结论，f[n] 的系数是 + ，f[n-1] 是 -，其他的任意
于是可以贪心做，贪心向绝对值最小的方向去搞，暂时不懂这个贪心为啥是对的。
/*
* @Author: zhl
* @LastEditTime: 2020-12-23 15:21:41
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;
ll n, k;
string s;
int main() {
cin >> n >> k;
cin >> s;
ll m = k - (1ll << (s[n - 1] - 'a')) + (1ll << (s[n - 2] - 'a'));
vector<int>cnt(26, 0);
for (int i = 0; i < n - 2; i++)cnt[s[i] - 'a']++;
for (int i = 25; i >= 0; i--) {
while (cnt[i]--) {
ll x = m - (1ll << i), y = m + (1ll << i);
m = abs(x) < abs(y) ? x : y;
}
}
cout << ((m == 0) ? "Yes" : "No") << endl;
}