补题链接：Here
A. 加密
简单总结一下题意：
给定一个 0-1 串，每一个连续 1 区间为一个权值，给予一次反转机会（也可以不使用）请问反转以后最小权重是多少
思路：
对于只有一次机会的话，要么反转单独的 1 或者 反转两个 1 区间中间隔的 0 如：11011
所以我们使用 vector<pari<int,int>> 存储 1 区间的左右端点然后进行判断即可
AC 代码：
// Murabito-B 21/04/09
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
string s;
cin >> s;
vector<pair<int, int>> lr;
bool flag = false;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '1') {
int j = i + 1;
while (j < s.size() && s[j] == '1') j++;
lr.push_back({i, j - 1});
// cout << i << " " << j - 1 << "
";
i = j;
// if (j == i + 1) flag = true;
}
}
if (lr.size() == 1) {
cout << (lr[0].first == lr[0].second ? 0 : 1);
return 0;
}
bool f = false;
for (int i = 1; i < lr.size() && !f; ++i) {
if (lr[i].first - lr[i - 1].second == 2) f = true;
if (lr[i].first == lr[i].second) f = true;
}
cout << (f ? lr.size() - 1 : lr.size());
return 0;
}
另外看一下官方题解：先计算原串的权值，然后枚举，(mathcal{O}(N))
#include <bits/stdc++.h>
using namespace std;
const int CN = 1e6 + 10;
int read() {
int s = 0, ne = 1;
char c = getchar();
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') ne = -1;
for (; c >= '0' && c <= '9'; c = getchar()) s = (s << 1) + (s << 3) + c - '0';
return s * ne;
}
int n;
char ch[CN];
int main() {
scanf("%s", ch + 1), n = strlen(ch + 1);
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (ch[i] == '0') continue;
int j = i;
while (ch[j] == '1') j++;
i = j - 1, cnt++;
}
int A = cnt;
for (int i = 1; i <= n; i++)
if (ch[i] == '1' && ch[i - 1] != '1' && ch[i + 1] != '1') A = cnt - 1;
int B = cnt;
for (int i = 2; i < n; i++)
if (ch[i] != '1' && ch[i - 1] == '1' && ch[i + 1] == '1') B = cnt - 1;
printf("%d
", min(cnt, min(A, B)));
return 0;
}
B. 卷积
(mex{j,k} = i) 展开来说只会有 (i = 0,1,2) 三种情况，所以 (i ge 3) 时直接输出 0 即可
注意取模位置
// Murabito-B 21/04/09
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
int n;
cin >> n;
vector<ll> a(n), b(n);
ll suma = 0, sumb = 0;
for (ll &x : a) {
cin >> x;
suma = (suma + x) % mod;
}
for (ll &x : b) {
cin >> x;
sumb = (sumb + x) % mod;
}
cout << ((suma - a[0] + mod) % mod) * ((sumb - b[0] + mod) % mod) % mod << " ";
cout << (a[0] * ((sumb + mod - b[1]) % mod) % mod + b[0] * ((suma + mod - a[1]) % mod) - a[0] * b[0] % mod) % mod << " ";
cout << ((a[0] * b[1] + mod) % mod + mod + (a[1] * b[0] + mod) % mod) % mod << " ";
for (int i = 3; i < n; ++i) cout << 0 << " ";
return 0;
}
C. 不降数
这道题在比赛中没理清关系，赛后学习一下官方题解
考虑先算低于 (n) 位的数字有多少。我们把数字看成为 (n) 的序列，然后统计差分序列的数量即可。
考虑到枚举差分序列之和 (i) ，然后通过插板法得到答案：
[sum^9_{i = 1} egin{pmatrix} i + n - 1\n - 1 end{pmatrix} =egin{pmatrix} n + 9\n end{pmatrix} - 1
]
考虑差分以后得到最终答案：
[egin{pmatrix} n + 9\n end{pmatrix} - egin{pmatrix} n + 8\n -1 end{pmatrix} =frac{9}{n}egin{pmatrix} n + 8\n -1 end{pmatrix}
]
使用 lucas 定理计算组合数即可
- 时间复杂度：(mathcal{O}(P) - mathcal{O}(logP))
// Murabito-B 21/04/10
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 100019;
ll fac[P + 10], ifac[P + 10];
ll qpow(ll a, ll b) {
ll ans = 1;
a %= P;
for (; b; a = a * a % P, b >>= 1)
if (b & 1) ans = ans * a % P;
return ans;
}
ll C(int n, int m) {
int r = fac[n] * ifac[n - m] % P;
return r * ifac[m] % P;
}
int lucas(ll n, ll m) {
if (!n) return 1;
if (m < 0 || m > n) return 0;
return 1ll * C(n % P, m % P) * lucas(n / P, m / P) % P;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
ll n;
cin >> n;
fac[0] = fac[1] = ifac[0] = 1;
for (int i = 2; i < P; ++i) fac[i] = 1ll * fac[i - 1] * i % P;
ifac[P - 1] = qpow(fac[P - 1], P - 2);
for (int i = P - 2; i; i--) ifac[i] = ifac[i + 1] * (i + 1) % P;
cout << 9ll * qpow(n % P, P - 2) * lucas(n + 8, n - 1) % P;
return 0;
}