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

B. Binary Vector

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

题解：

O(n) 维护2的幂和2的幂的逆元。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int N = 2e7 + 5;
 
ll f[N], c[2 * N];
 
void init() {
    f[1] = 500000004;
    ll a = 2, b = f[1];
    for(int i = 2; i < N; ++i) {
        a = a * 2 % mod;
        b = b * f[1] % mod;
        f[i] = f[i - 1] * (a - 1) % mod;
        f[i] = f[i] * b % mod;
    }
    for(int i = 2; i < N; ++i)
        f[i] ^= f[i - 1];
}
 
int main()
{
    init();
    int t, n;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        cout<<f[n]<<'\n';
    }
    return 0;
}

C. Combination of Physics and Maths

传送门

题意：定义矩阵的压强为所有元素的和 / 最后一行的和。给一个n * m的矩阵，选取若干行和若干列，相交位置的元素提出来作为子矩阵，问所有子矩阵的最大压强

思路：若从原矩阵中选一行作为子矩阵的最后一行，为了使压强最大，选中列在该行上面的所有元素肯定都要选中，即行的选取一定是从第一行到某一行都选；若有两列的压强分别为a / b，c / d，且a / b >= c / d，那么有 a / b >= (a + c) / (b + d) >= c / d，即最优解一定是单列，所以 n ^ 2 扫一遍就好了

-----------------------------------------证明-----------------------------------------

已知，证明

（下面转自https://blog.csdn.net/puss0/article/details/103778756

-----------------------------------------------------------------------------------------

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 205;
int a[N];

int main() {
    int t, n, m, x;
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &m);
        memset(a, 0, sizeof(a));
        double ans = 0.0;
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= m; ++j) {
                scanf("%d", &x);
                a[j] += x;
                ans = max(ans, 1.0 * a[j] / x);
            }
        }
        printf("%.8f\n", ans);
    }
    return 0;
}

E. Easy Construction

传送门

题意：构造一个1~n的序列，使得 i 对任意的1~n，序列中存在一个长度为 i 的连续子序列满足该子序列的和 % n == k

思路：

1~n的和是sum = (n + 1) * n / 2，发现当 n 是偶数的时候sum % n == n / 2，若可以构造必须k == n / 2；n是奇数的时候sum % n == 0，必须k == 0，否则不能构造。

n是偶数：n, n / 2, 1, n - 1, 2, n - 2, 3, n - 3 ....

n是奇数：n, 1, n - 1, 2, n - 2, 3, n - 3....

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e3 + 5;

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    if((n & 1) && k == 0) {
        printf("%d", n);
        for(int i = 1; i <= n / 2; ++i)
            printf(" %d %d", i, n - i);
        printf("\n");
    }
    else if(!(n & 1) && k == n / 2) {
        printf("%d %d", n, n / 2);
        for(int i = 1; i < n / 2; ++i)
            printf(" %d %d", i, n - i);
        printf("\n");
    }
    else
        printf("-1\n");
    return 0;
}

K. K-Bag

传送门

题意：定义k-bag由若干个1~k的排列组成，给一个序列判断是否是k-bag的子序列

思路：（尺取）

（1）有< 1或 > k的元素，NO

（2）所有数只出现了一次，YES

（3）找到第一个重复出现的元素，记录第一次出现的位置k1和第二次出现的位置k2，从(k1, k2]中选取一个位置作为第二段的开头，向后判断是否符合题意

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N = 2e6 + 10;
 
int a[N];
 
int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        int n, k;
        scanf("%d%d", &n, &k);
        bool flag1 = 1;
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            if(a[i] < 1 || a[i] > k)
                flag1 = 0;
        }
        if(!flag1) {
            cout<<"NO"<<'\n';
            continue;
        }
        unordered_map<int, int>mp;
        int k1 = -1, k2 = -1;
        for(int i = 1; i <= n; ++i) {
            if(mp[a[i]]) {
                k1 = mp[a[i]];
                k2 = i;
                break;
            }
            mp[a[i]] = i;
        }
        if(k1 == -1) {
            cout<<"YES"<<'\n';
            continue;
        }
        mp.clear();
        int l = k1 + 1, r = k1 + 1, cnt = 0, num = 0;
        bool flag = 1;
        while(1) {
            if(l > k2) {
                flag = 0;
                break;
            }
            bool f = 1;
            while(r <= n && num < k) {
                if(mp[a[r]] == cnt) {
                    num++;
                    mp[a[r]]++;
                    r++;
                }
                else {
                    f = 0;
                    break;
                }
            }
            if(!f) {
                mp[a[l]]--;
                num--;
                l++;
            }
            else if(num == k) {
                num = 0;
                cnt++;
            }
            if(r == n + 1)
                break;
        }
        if(flag) cout<<"YES"<<'\n';
        else cout<<"NO"<<'\n';
    }
    return 0;
}