A.African Sort

题意：

给定排列 $p$ ，每次可以选一个下标集合等概率打乱包含的数并花费集合大小的代价，求给 $p$ 排升序最优策略下最小代价的期望，对 $998244353$ 取模

题解：

待补

B.Binary Vector

题解：

随机 $n$ 个 $n$ 维 $01$ 向量，询问这个 $n$ 个向量线性无关的概率

题解：

可以算出 $f(i)=\frac{2^{i}-1}{2^{i}} \times f(i-1)=(1-\frac{1}{2^{i}}) \times f(i-1)$ 。因此可以 $O(n)$ 求出 $f(1) \sim f(n)$ ，每次和上一结果异或即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e7 + 5;
const ll mod = 1e9 + 7, inv2 = 5e8 + 4;
ll ans[maxn], f[maxn];
int main()
{
    int Pow = 1;
    ans[0] = 1ll;
    for (int i = 1; i < maxn; i++)
    {
        Pow = 1ll * Pow * inv2 % mod;
        ans[i] = 1ll * ans[i - 1] * (1 - Pow + mod) % mod;
        f[i] = ans[i] ^ f[i - 1];
    }
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n;
        scanf("%d", &n);
        printf("%lld\n", f[n]);
    }
}

C.Combination of Physics and Maths

题意：

给定一个矩阵，定义一个可非连续子矩阵的压强为矩阵内所有元素之和除以最后一行元素之和。求给定矩阵内可非连续子矩阵的最大压强

题解：

对于每一列枚举每一行为底，那么为了使分子越大位于当前行上面同一列的元素要全部取过来，这可以用前缀和维护。对于任意两列，其中同一行的压强分别为 $\frac{a}{b},\frac{c}{d}$ ，令 $\frac{a}{b} \leq \frac{c}{b}$ ，有 $\frac{a}{b} \leq \frac{a+c}{b+d} \leq \frac{c}{d}$ ，因此取多列的答案不会比取一列的优，因此只需要对每一列逐一枚举即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 210;
int a[maxn][maxn], pre[maxn];
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                scanf("%d", &a[i][j]);
        double ans = 0.0;
        for (int i = 1; i <= m; i++)
        {
            memset(pre, 0, sizeof(pre));
            for (int j = 1; j <= n; j++)
            {
                pre[j] = pre[j - 1] + a[j][i];
                ans = max(ans, pre[j] * 1.0 / a[j][i]);
            }
        }
        printf("%.8lf\n", ans);
    }
    return 0;
}

E.Easy Construction

题意：

给定一个长度为 $n$ 的序列 $a_n$ ，询问是否对 $[1,n]$ 都能找到对应长度的子序列使得子序列内元素之和 $\% n=k$ 。如果存在输出一种方案 $(0 \leq k < n)$

题解：

考虑到要对每种长度都存在，那么先考虑长度为 $n$ 的，发现当 $n$ 为偶数时， $k=\frac{n}{2}$ 才能构造出，对前 $\frac{n}{2}-1$ 对，只需要 $i,n-i$ 两两组成即可，最后一对 $\frac{n}{2},n$ ；当 $n$ 为奇数时， $k=0$ 才能构造出，对前 $\frac{n}{2}$ 对，只需要 $i,n-i$ 两两组成即可，最后一个数为 $n$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 505;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    if (k == n / 2 && (n % 2 == 0))
    {
        for (int i = 1; i < n / 2; i++)
            printf("%d %d ", i, n - i);
        printf("%d %d\n", n / 2, n);
    }
    else if (k == 0 && (n & 1))
    {
        for (int i = 1; i <= n / 2; i++)
            printf("%d %d ", i, n - i);
        printf("%d\n", n);
    }
    else
        puts("-1");
    return 0;
}

G.Grid Coloring

题意：

给 $n*n$ 的网格图的边染 $k$ 种色，要求每种色染的边数相同，不存在同色环及任意一行或一列不同色，给出一种可行的方案

题解：

首先考虑不存在的情况，当 $n=1$ 时不满足条件 $3$ ，当 $k=1$ 时不满足条件 $2、3$ ，当 $2 * n * (n + 1) \% k \ne 0$ 不满足条件 $1$ 。
对于构造方案，考虑到有 $n+1$ 行横着的，每行有 $n$ 个，有 $n$ 行竖着的，每行有 $n+1$ 个，对于相邻的两行 $n$ 和 $n+1$ 奇偶性不同，因此可以从左往右，从上往下构造，可以保证满足上述的三个条件。
图片说明

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 5e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    int n, k;
    scanf("%d%d", &n, &k);
    if (n == 1 || k == 1 || 2 * n * (n + 1) % k)
    {
        puts("-1");
        return;
    }
    int cnt = 0;
    for (int i = 0; i < n + 1; i++)
    {
        for (int j = 0; j < n; j++)
        {
            printf("%d ", ++cnt);
            cnt %= k;
        }
        puts("");
        cnt = (cnt + (n + 1)) % k;
    }

    for (int i = 0; i < n + 1; ++i)
    {
        cnt = (n + i) % k;
        for (int j = 0; j < n; ++j)
        {
            printf("%d ", ++cnt);
            cnt = (cnt + 2 * n) % k;
        }
        puts("");
        cnt = (cnt + (n + 1)) % k;
    }
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

H.Harmony Pairs

题意：

$S(x)$ 为 $x$ 各位之和，给定 $N$ ，求 $1 \leq A \leq B \leq N$ 中 $S(A)>S(B)$ 的数量 $(1 \leq N \leq 10^{100})$

题解：

数位 $dp$ $dp[i][j][k][l][m]$ , $i$ 表示当前位置， $j$ 表示之前位置的数值之差， $k$ 表示 $A$ 是否有限制， $l$ 表示 $B$ 是否有限制， $m$ 表示之前位置 $A$ 是否已经 $\leq B$ 。因为 $N \leq 10^{100}$ 因此两数之差最多不会超过 $1000$ ，为了防止 $j$ 值出现负数，因此令 $j$ 初始为 $1000$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int base = 1000;
ll dp[105][2005][2][2][2];
string str;
ll dfs(int pos, int sum, bool lima, bool limb, bool limit)
{
    if (pos < 0)
        return sum > base;
    if (dp[pos][sum][lima][limb][limit] != -1)
        return dp[pos][sum][lima][limb][limit];
    int up1 = lima ? str[pos] - '0' : 9;
    int up2 = limb ? str[pos] - '0' : 9;
    ll res = 0;
    for (int i = 0; i <= up1; i++)
        for (int j = 0; j <= up2; j++)
        {
            if (!limit && i > j)
                continue;
            res += dfs(pos - 1, sum + i - j, lima && i == up1, limb && j == up2, limit || j > i);
            res %= mod;
        }
    return dp[pos][sum][lima][limb][limit] = res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> str;
    memset(dp, -1, sizeof(dp));
    int len = str.length();
    int L = 0, R = len - 1;
    while (L < R)
        swap(str[L++], str[R--]);
    cout << dfs(len - 1, base, 1, 1, 0) << "\n";
    return 0;
}

J.Josephus Transform

题意：

给一个长度为 $n$ 的排列和 $m$ 次操作，每个操作可以表示为 $(k, x)$ ，即进行 $x$ 次以 $k$ -约瑟夫变换。问最后排列长啥样。

题解：

对于每一次的 $k$ -约瑟夫变换，都可以视为一次置换群的结合操作，所以我们首先需要求出这个置换群是什么，假设上一次被取出来的数字是第 $pos$ 个（初始时为 $1$ ），此时环内还剩下 $cnt$ 个数字，则下一次需要被选出的数字是剩下数字的第 $(pos - 1 + k - 1 ) \% cnt + 1$ 个，这个操作可以利用线段树上二分实现。求出单次的置换群， $x$ 次就是置换群的 $x$ 次幂。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int ans[maxn], temp[maxn], a[maxn], T[maxn << 2], n, m;
bool used[maxn];
vector<int> seq;
void build(int rt, int l, int r)
{
    if (l == r)
    {
        T[rt] = 1;
        return;
    }
    int mid = l + r >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    T[rt] = T[rt << 1] + T[rt << 1 | 1];
}
int query(int rt, int l, int r, int k)
{
    T[rt]--;
    if (l == r)
        return l;
    int mid = l + r >> 1;
    if (T[rt << 1] >= k)
        return query(rt << 1, l, mid, k);
    else
        return query(rt << 1 | 1, mid + 1, r, k - T[rt << 1]);
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        ans[i] = i;
    while (m--)
    {
        build(1, 1, n);
        int x, k, pos = 1, cnt = n;
        scanf("%d%d", &k, &x);
        for (int i = 1; i <= n; i++)
        {
            pos = (pos - 1 + k - 1) % cnt + 1;
            a[i] = query(1, 1, n, pos);
            cnt--;
        }
        memset(used, 0, sizeof(used));
        for (int i = 1; i <= n; i++)
        {
            if (!used[i])
            {
                seq.clear();
                int now = i;
                while (!used[now])
                {
                    seq.push_back(now);
                    used[now] = 1;
                    now = a[now];
                }
                for (int j = 0; j < seq.size(); j++)
                    temp[seq[j]] = ans[seq[(j + x) % seq.size()]];
            }
        }
        for (int i = 1; i <= n; i++)
            ans[i] = temp[i];
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", ans[i]);
    puts("");
    return 0;
}

K.K-Bag

题意：

K-bag序列定义为由多个 $1-k$ 的排列顺序连接起来的序列。询问给定序列是不是k-bag的连续子序列

题解：

遍历序列可以算出每个序列到下个序列的长度，因为不能保证 $[1,k]$ 就是一个完整的序列，但是可以得知如果合法，那么 $[1,k]$ 中一定存在一个合法排列的首地址，因此遍历 $[1,k]$ ，判断距离下一个排列的长度是否始终为 $k$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 5e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int a[maxn], len[maxn];
unordered_map<int, int> cnt;
void solve()
{
    int n, k;
    scanf("%d %d", &n, &k);
    int flag = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        if (a[i] > k || a[i] < 1)
            flag = 1;
    }
    if (flag)
    {
        puts("NO");
        return;
    }
    int pos = 1;
    for (int i = 1; i <= n; i++)
    {
        while (cnt[a[pos]] == 0 && pos <= n)
        {
            cnt[a[pos]]++;
            pos++;
        }
        len[i] = pos - i;
        cnt[a[i]]--;
    }
    for (int i = 1; i <= k && i <= len[1] + 1; i++)
    {
        bool flag = true;
        for (int j = i; j <= n; j += k)
        {
            if (len[j] + j == n + 1)
                continue;
            else if (len[j] != k)
            {
                flag = false;
                break;
            }
        }
        if (flag)
        {
            puts("YES");
            return;
        }
    }
    puts("NO");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

2020牛客暑期多校训练营（第六场）