A.Road To Zero

题意：

给定 $x、y$ ，并且给定 $a、b$ ，有两种操作：

花费 $a$ ，可以让 $x、y$ 其中一个 $\pm 1$
花费 $b$ ，可以让 $x、y$ 都 $\pm 1$

询问最少的花费使得 $x、y$ 均变为0

题解：

比较 $(x+y)*a$ 和 $min(x,y)*b+\left| x-y \right|*a$ 的大小即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    ll a, b, x, y;
    scanf("%lld%lld%lld%lld", &x, &y, &a, &b);
    ll n1 = (x + y) * a, n2 = min(x, y) * b + abs(x - y) * a;
    printf("%lld\n", n1 < n2 ? n1 : n2);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.Binary Period

题意：

给定一个 $01$ 串，可以在任意位置添加任意多的 $0、1$ ，要求最终生成的串长度不超过原来的两倍，并且这个串是个循环串且循环节最短

题解：

如果为全 $0$ 或者为全 $1$ ，那么就是串本身，否则只要补成 $010101...$ 即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    string s, a;
    cin >> s;
    for (auto p : s)
        a += "01";
    if (s.find('0') == string::npos || s.find('1') == string::npos)
        cout << s << endl;
    else
        cout << a << endl;
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.Yet Another Counting Problem

题意：

给定 $a、b$ 和 $q$ 组询问，每组询问给定 $l_i$ 和 $r_i$ ，询问 $l_i \leq x \leq r_i$ 之间有多少个 $x$ 满足 $((x \bmod a) \bmod b) \ne ((x \bmod b) \bmod a)$

题解：

可以发现 $1 \sim ab$ 会是一个循环，并且 $ab \leq 4000$ 可算，所以只要算出一个循环内的所有结果，最终结果就是 $calc(r)-calc(l-1)$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 4e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int sum[maxn];
ll a, b, q;
ll calc(ll x)
{
    return 1ll * x / (a * b) * sum[a * b] + 1ll * sum[x % (a * b)];
}
void solve()
{
    memset(sum, 0, sizeof(sum));
    scanf("%lld%lld%lld", &a, &b, &q);
    for (int i = 1; i <= a * b; i++)
        sum[i] += sum[i - 1] + (i % a % b != i % b % a);
    while (q--)
    {
        ll l, r;
        scanf("%lld%lld", &l, &r);
        printf("%lld ", calc(r) - calc(l - 1));
    }
    puts("");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

D.Multiple Testcases

题意：

给定 $n$ 个数 $a_n$ 和 $k$ ，其中 $a_i \leq k$ 。现在要将 $a_n$ 划分成一些组，要求每个组内 $\geq i$ 的数不超过 $c[i]$ 。求划分出最少的组数和每组的构成方案。

题解：

对于第一问，先将 $a_n$ 升序排序，对于 $\geq a[i]$ 的个数为 $n-i+1$ 那么 $ans=max(\lceil \frac{n-i+1}{c[i]}\rceil)$ 。对于第二问只要将 $a_1$ 放入第一组， $a_2$ 放入第二组...依次放入即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int a[maxn], c[maxn];
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= k; i++)
        scanf("%d", &c[i]);
    sort(a + 1, a + n + 1);
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, (n - i + 1 + c[a[i]] - 1) / c[a[i]]);
    printf("%d\n", ans);
    for (int i = 1; i <= ans; i++)
    {
        int cnt = 0;
        for (int j = i; j <= n; j += ans)
            cnt++;
        printf("%d ", cnt);
        for (int j = i; j <= n; j += ans)
            printf("%d ", a[j]);
        puts("");
    }
    return 0;
}

E.Placing Rooks（组合数学）

题意：

在一个 $n*n$ 的棋盘上放置 $n$ 个车，满足以下两个条件：

棋盘上的每一个空格子都能被至少一只车走到
恰好存在 $k$ 对车可以相互攻击

询问所有车的摆放方案数

题解：

要满足第一个条件，则每一行/每一列都有一个车，两者至少满足其一。对于这两种情况是等价的，下面只考虑每一行都有车，最终结果乘 $2$ 即可
在满足第二个条件的情况下，可以发现至少有 $k$ 列是空着的，那么问题就相当于把 $n$ 个不同的车放入 $n-k$ 个不同的列，发现就是一个第二类斯特林数。那么可以用容斥原理， $C_{n-k}^{0}*(n-k)^n-C_{n-k}^{1}*(n-k-1)^n+C_{n-k}^{2}*(n-k-2)^n...$ ，那么最终答案就是 $2*C_{n}^{n-k}*[C_{n-k}^{0}*(n-k)^n-C_{n-k}^{1}*(n-k-1)^n+C_{n-k}^{2}*(n-k-2)^n...]$ 。
要注意特判一下当 $n=0$ 时，答案就为 $n!$ ，当 $k>=n$ 时，答案为 $0$
了解第二类斯特林数戳我~

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
ll fac[maxn];
ll qpow(ll a, ll b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
void init()
{
    fac[0] = 1;
    for (int i = 1; i < maxn; i++)
        fac[i] = fac[i - 1] * i % mod;
}
ll c(int x, int y)
{
    return fac[x] * qpow(fac[y] * fac[x - y] % mod, mod - 2) % mod;
}
int main()
{
    init();
    int n, k;
    scanf("%d%d", &n, &k);
    if (k == 0)
    {
        printf("%lld\n", fac[n]);
        return 0;
    }
    if (k >= n)
    {
        puts("0");
        return 0;
    }
    ll ans = 0;
    for (int i = 0; i <= n - k; i++)
        ans += 1ll * qpow(mod - 1, i) * c(n - k, i) % mod * qpow(n - k - i, n) % mod;
    ans %= mod;
    printf("%lld\n", 2ll * ans % mod * c(n, n - k) % mod);
    return 0;
}

Educational Codeforces Round 86 (Rated for Div. 2)

A.Road To Zero

题意：

题解：

B.Binary Period

题意：

题解：

C.Yet Another Counting Problem

题意：

题解：

D.Multiple Testcases

题意：

题解：

E.Placing Rooks（组合数学）

题意：

题解：