2022.1.29 练习赛题解

A – 考勤1

简单模拟

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t; cin >> t;
    while (t--) {
        int n, k;
        string s;
        cin >> n >> k >> s;
        int num = 0, maxs = 0;
        int l = -1, r = -1;
        for (int i = 0; i < n; i++) {
            if (s[i] == '0') {
                if (r == -1) {
                    l = r = i;
                } else {
                    r++;
                }
            } else {
                if (r != -1) {
                    maxs = max(maxs, r - l + 1);
                    l = r = -1;
                }
                if (s[i] == '2') {
                    num++;
                }
            }
        }
        if (r != -1) {
            maxs = max(maxs, r - l + 1);
        }
        if (num < 2 && maxs <= k) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
    return 0;
}

B – A*B Problem

分三类讨论：

$A=B$。
$A<B$。
$A>B$。

第一类很简单，直接 $O(\sqrt{N})$ 枚举就行；第二类和第三类是对偶情况只需要求解其中一个，不妨以第二类为例，显然有以下不等式：

$$A<B<\lfloor\frac{N}{A}\rfloor$$

所以对于任意一个 $A$，满足条件的 $B$ 的数量为 $\lfloor\frac{N}{A}\rfloor-A$，这也可以 $O(\sqrt{N})$ 枚举。

#include <bits/stdc++.h>
using namespace std;
long long solve(long long c) {
    long long res = 0;
    for (long long i = 1; i * i <= c; i++) {
        res += 2LL * (c / i - i) + 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    long long c;
    cin >> c;
    cout << solve(c - 1) << "\n";
    return 0;
}

C – 01串

不难看出就是 $0$ 的数量× $1$ 的数量。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    string s;
    cin >> s;
    int n = s.length();
    int one = 0, zero = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') one++;
        else zero++;
    }
    cout << 1LL * zero * one;
    return 0;
}

D – 城墙

本次猜结论还是比较容易的，结论是：若 $n$ 为奇数，则答案为 $5n+1$ ；否则答案为 $5n$ 。构造如下：

但是证明比较复杂，如下（~~我相信你也不会感兴趣的~~）：

在证明中，我们采用红绿蓝三色代表三个部落，然后定义：

$R$ 表示含有红色的行列总数；
$G$ 表示含有绿色的行列总数；
$B$ 表示含有蓝色的行列总数；
$R_r$ 表示含有红色的行数，$R_c$ 表示含有红色的列数，显然有 $R=R_r+R_c$ ，我们对 $G_r,G_c,B_r,B_c$ 也作出类似定义。

因为 $R=R_r+R_c\geq 2\sqrt{R_rR_c}$ ，并且如果我们用一个最小的矩形完美覆盖住红色区域的话，至少需要 $R_rR_c$ 个方格，这片区域不少于 $3n^2$ 个方格，所以有 $R_r+R_c\geq 2\sqrt{R_rR_c}\geq 2\sqrt{3n^2}\geq2\sqrt{3}n$ 。

同理有 $G_r+G_c\geq 2\sqrt{3}n, B_r+B_c\geq 2\sqrt{3}n$ 。

并且由于这是整数运算，我们可以推广为 $R,G,B\geq \lceil 2\sqrt{3}n \rceil$

然后我们考虑如何利用上方的定义表示 $S$ ，由于城墙只会造在两种颜色的分界处，这说明城墙的总长度等价于每行颜色变化的次数和+每列颜色变化的次数和，所以 $S\geq R+G+B-6n$ 。这个不等式描述了：如果某一行/列含有某种颜色，那么这种颜色只出现一次，因为如果多次出现显然会让分界边增多。

根据上方给出的一系列不等式，我们分类讨论：

不含有同色行/列由于不存在同色的行/列，每行/列都至少变换一次颜色，因此 $S\geq 5n$ 显然劣于我们构造的下界。
含有一种同色行/列由于有一种颜色的同色行/列出现，我们不妨假设存在蓝色的同色行。那么，我们得到：$R_c=3n,R_r\geq n$ ，并且当 $R_r=n$ 时，蓝色色块恰好是一个 $n\times 3n$ 的贴边矩形（就像样例图中那样）。于是有：
$$\begin{aligned}
S&\geq R+G+B-6n\\ & \geq \lceil2\sqrt{3}n\rceil+\lceil2\sqrt{3}n\rceil+4n-6n\\ &\geq {2\lceil2\sqrt{3}n\rceil-2n}
\end{aligned}
$$
我们可以验证这个下界在 $[1,10]$ 的范围内满足 $S\geq {2\lceil2\sqrt{3}n\rceil-2n}\geq 5n+[n\bmod2=1]$ 。
含有多种同色行/列首先不可能同时存在多种同色行和列，因为同色行和同色列都是贯通整个正方形的连通块，如果有颜色相异的同色行和列就与联通性相矛盾。因此我们只需要考虑存在多种颜色的同色行或列，这里我们以同色行为例。

如果红绿蓝三色的单色行都存在，那么每列至少会变换两次颜色，也就是说 $S\geq 6n$ 显然劣于我们猜想的下界。
如果只存在红绿两色的单色行，那么每列至少变换一次颜色，同时由于蓝色方块数为 $3n^2$ ，而蓝色方块最多只能摆在 $3n-p$ 行中，因此蓝色方块至少出现在 $\frac{3n^2}{3n-p}$ 列中。由此推出行的颜色变化次数 $\geq \frac{3n^2}{3n-p}$ ，列的颜色变化次数 $\geq 3n+3n-p$ 。
$$
\begin{aligned}
S&\geq 6n-p+\frac{3n^2}{3n-p} \\
&=3n+3n-p+\frac{3n^2}{3n-p} \\
&\geq 3n+2\sqrt{3n^2} \\
&=(3+2\sqrt{3})n\\
\end{aligned}
$$
我们根据基本不等式可以推出这种情况下 $S$ 的理想下界是 $\lceil(3+2\sqrt{3})n\rceil$ ，由于 $\lceil(3+2\sqrt{3})n\rceil\geq 5n+1$ 在 $n\geq 1$ 的定义域下恒成立，因此这种情况也劣于我们猜想的下界。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        cout << 5 * n + (n & 1) << '\n';
    }
    return 0;
}

E – Number of Pairs

简单的容斥，记 $f(k)$ 表示 $a_i+a_j\geq l$ 的对数，那么答案就是 $f(l)-f(r+1)$ ，对于每个询问二分查询即可。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n, l, r;
        cin >> n >> l >> r;
        vector<int> a(n);
        for (auto& i : a) {
            cin >> i;
        }
        sort(a.begin(), a.end());
        auto cal = [&](int k) {
            long long res = 0;
            for (int i = 0; i < n; i++) {
                int p = max(i + 1, lower_bound(a.begin(), a.end(), k - a[i]) - a.begin());
                res += n - p;
            }
            return res;
        };
        cout << cal(l) - cal(r + 1) << "\n";
    }
    return 0;
}

F – 方块染色

一个简单的组合问题（当然也可以dp做），首先要求有 $K$ 对相邻不同色方块，所以我们需要在所有 $N-1$ 个空隙中选择 $K$ 个位置，然后给这些连续的方块再染上不同的颜色。

因此答案为 $\binom{N-1}{K}M(M-1)^{K}$ 。

G – ABAB

由 $A$ 个 $a$ 和 $B$ 个 $b$ 构成的所有字符串一共有 $\binom{A+B}{A}$ 种。

当我们确定字符串第一位是 $A$ 的时候，就只剩下 $\binom{A+B-1}{A-1}$ 种了。如果此时 $K\leq \binom{A+B-1}{A-1}$ ，那么就意味着第一位确实是 $A$ ，否则就是 $B$ 。

重复上述过程直到我们找到字典序第 $K$ 大的字符串。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int A, B;
    long long K;
    cin >> A >> B >> K;
    K--;
    int N = A + B;
    vector<vector<long long>> binom(N + 1, vector<long long>(N + 1, 1));
    for (int i = 2; i <= N; i++) {
        for (int j = 1; j < i; j++) {
            binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j];
        }
    }
    string S;
    for (int i = 0; i < N; i++) {
        bool a = false;
        if (A > 0) {
            long long cnt = binom[A + B - 1][A - 1];
            if (K < cnt) {
                a = true;
            }
        }
        if (a) {
            S += 'a';
            A--;
        } else {
            S += 'b';
            K -= binom[A + B - 1][A - 1];
            B--;
        }
    }
    cout << S;
    return 0;
}

H – 青原樱

相当于 $m$ 个不同小球放入 $n$ 个空位，要求任意两个小球不相邻，求方案数。

假设我们先从 $n$ 个位置中将 $m$ 个小球占用的坑位拿走，此时还剩下 $n-m$ 个位置，这个时候我们再把小球和其对应的位置插回去就好了。一共有 $n-m+1$ 个隔板位置可以插入，因此答案就是 $\binom{n-m+1}{m}m!$ 。

I – 数列递推

$$
\begin{aligned}
f_i&=f_{i-1}+2f_{i-2}+3\\
f_{i-1}&=f_{i-2}+2f_{i-3}+3\\
\Rightarrow f_i-f_{i-1}&=f_{i-1}+2f_{i-2}+3-(f_{i-2}+2f_{i-3}+3)\\
\Rightarrow f_i&=2f_{i-1}+f_{i-2}-2f_{i-3}
\end{aligned}
$$

矩阵加速递推即可。

J – 王座

在环上走就相当于是在做模意义下的运算，列出方程：$S+Kx \% N = 0$，exgcd解出最小整数解即可。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
long long exgcd(long long a, long long b, long long& x, long long& y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    long long g = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return g;
}

ll x, y; // 最小非负整数解
bool solve(ll a, ll b, ll c) { // ax+by=c
    ll g = gcd(a, b);
    if (c % g) return false;
    a /= g, b /= g, c /= g;
    bool flag = false;
    if (b < 0) b = -b, flag = true;
    exgcd(a, b, x, y);
    x = (x * c % b + b) % b;
    if (flag) b = -b;
    y = (c - a * x) / b;
    if (!c) x = y = 0; // ax+by=0
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n, s, k;
        cin >> n >> s >> k;
        if (solve(k, -n, -s)) {
            cout << x << "\n";
        } else {
            cout << "-1\n";
        }
    }
    return 0;
}

A – 考勤1

B – A*B Problem

C – 01串

D – 城墙

E – Number of Pairs

F – 方块染色

G – ABAB

H – 青原樱

I – 数列递推

J – 王座

K – 随机游走

L – 数论测试

M – 简单易懂的蓄水池

发送评论编辑评论

A – 考勤1

B – A*B Problem

C – 01串

D – 城墙

E – Number of Pairs

F – 方块染色

G – ABAB

H – 青原樱

I – 数列递推

J – 王座

K – 随机游走

L – 数论测试

M – 简单易懂的蓄水池

发送评论 编辑评论

发送评论编辑评论