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

B、Binary Vector

$问题其实我每太看懂，题目备注给出了前3项的递推式，分子分母分开看很容易看出关系$
$分子依次乘1乘3乘7，分母依次乘2乘4乘8，可以看出分母乘的是2^{i}，分母是2^{i}-1$
$最后答案还有一个异或和的过程，那么问题就来了，分母单独预处理算很简单，分子单独预处理也很简单$
$根据逆元来看，如果在对每一个分母求一次快速幂累乘求异或预处理就结束了！$
$如果这样写完之后，一个自测发现样例T掉了，那么很显然nlogn，n\leq 2e7，情况下是TLE的$
$那么有什么办法呢？逆元方法就错掉了吗？不对这个时候我想到了线性逆元求jc里面的逆元$
$只需要求一次qpow就可以求道最后一个数的逆元，前面的逆元就可以通过O(n)递推出来$
$这样我们就会发现时间复杂度变成了O（N+T）下面就要实现这个算法了$
$首先把分子分母算出来，求道最后一个分母的逆元，可以发现前一个分母比后一个分母除以2$
$化成答案算乘法逆元就是乘以2的逆元，到这里这个题目就解决了$

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define mk(__x__,__y__) make_pair(__x__,__y__)
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;

const int N = 2e7 + 7;
ll up[N], down[N];
ll base = 4;
ll ans[N];
ll inv2 = 500000004;

int main() {
    up[1] = 1, down[1] = 2;
    ans[1] = 500000004;
    for (int i = 2; i < N; ++i) {
        up[i] = up[i - 1] * (base - 1) % MOD;
        down[i] = down[i - 1] * base % MOD;
        base = (base << 1) % MOD;
    }
    down[N - 1] = qpow(down[N - 1], MOD - 2, MOD);
    for (int i = N - 2; ~i; --i) {
        (base *= inv2) %= MOD;
        down[i] = down[i + 1] * base % MOD;
    }
    for (int i = 2; i < N; ++i) {
        ans[i] = up[i] * down[i] % MOD;
        ans[i] ^= ans[i - 1];
    }
    int T = read();
    while (T--) {
        int n = read();
        print(ans[n]);
    }
    return 0;
}

C、Combination of Physics and Maths

$给出n*m矩阵，最大200*200，现在求选定矩阵某些列一行某些行，求选中元素和/最底下一行元素，值最大$
$最开始我想到的就是01分数规划，肯定只需要枚举最后一行，上面行肯定是选到第一行，列的话就是01分数去check$
$这样时间复杂度O(T*n*m*log(m))二分次数少了就是WA，多了就是TLE，说明这个时间复杂度是不合格的$
$接下来就是标答的做法了，假定我们选中的大于等于两行，随便分开两份之后发现$
$假设一边是\dfrac{a}{b},另外一边是\dfrac{c}{d}$
$那么根据分数可以把一遍划到分母相同，这样就可以类比到高中的不同浓度溶液混合$
$\dfrac{a+c}{b+d}是不会即高于\dfrac{a}{b},又高于\dfrac{c}{d}的，所以得证最大取值的情况下可以就取一列，接下来直接去枚举接下来O(T*n*m)$

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define mk(__x__,__y__) make_pair(__x__,__y__)
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;

const int N = 200 + 7;
int mp[N][N];
int sum[N][N];

int main() {
    int T = read();
    while (T--) {
        int n = read(), m = read();
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j) {
                mp[i][j] = read();
                sum[i][j] = mp[i][j] + sum[i - 1][j];
            }
        double ans = 1.0;
        for (int i = 2; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                ans = max(ans, sum[i][j] * 1.0 / mp[i][j]);
        printf("%.8f\n", ans);
    }
    return 0;
}

E、Easy Construction

$英文小白的痛苦，看不太懂题目，题目就是给出n和k，询问是否存在一个序列p，是1-n的某一个全排列$
$满足取其中连续长度从1到n的子串，求和\%n之后都是k$
$首先很显然，长度为n的子串只存在一个，那就是(n+1)*n/2那么直接判断这个是不是\%n昨天下符合情况就能判断是不是可以构建了$
$如果长度为n符合，那就一定存在，反之则不存在输出-1$
$当长度为奇数时，直接构造\{ n,1,n-1,2,n-2……下去即可\}$
$当长度为偶数时，当且仅当k=n/2时才会存在解，那么此时构造的序列为$
$\{ n/2,n,1,n-1,2,n-2……下去即可\}$

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define mk(__x__,__y__) make_pair(__x__,__y__)
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;

const int N = 1e5 + 7;

int main() {
    int n = read(), k = read();
    int m = (n * (n + 1) / 2) % n;
    if (m != k) { return puts("-1"), 0; }
    int cnt = 0;
    if (n & 1) {
        for (int i = 1; i <= n; ++i)
            if (i & 1)    print(n - cnt, 32);
            else print(++cnt, 32);
    }
    else {
        print(n, 32), print(n >> 1, 32);
        for (int i = 1; i <= n - 2; ++i)
            if (i & 1)    print(++cnt, 32);
            else print(n - cnt, 32);
    }
    return 0;
}

K、K-Bag

$给出长度为n的序列，在给出一个Bag串的定义是由长度为k的序列的排列放置组合而成$
$比如1,2,3,2,1,3,3,2,1,可以看出来排列不同当且仅当开头元素不同，当第一个元素相同时说明之前是出现这个排列的$
$现在很明显我们能发现每k个就是一个循环节，那么回到n串中，我们如何判断是不是其中一个子串呢？$
$打标记，切割！如果遍历到前k个字符时是一定可以凑出是莫个字符串的排列的，也就是这些点是一定存在的分割点$
$当大于k之后，就需要看滑动区间中元素是不是k个了，如果是k个元素说明这个点和第i-k个点分割性质相同$
$接下来倒着去查看一遍，如果找到了分割点，并且分割点后面都是某个子序列，说明n串就是合法的子串，否则输出NO$

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define mk(__x__,__y__) make_pair(__x__,__y__)
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;

const int N = 5e5 + 7;
int a[N], f[N];
unordered_map<int, int> mp;

int main() {
    int T = read();
    while (T--) {
        mp.clear();
        ms(f, 0);
        int n = read(), k = read(), flag = 0;
        for (int i = 1; i <= n; ++i) {
            a[i] = read();
            if (a[i] > k)    flag = 1;
        }
        if (flag) { puts("NO"); continue; }
        int cnt = 0; f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if (i > k) {
                --mp[a[i - k]];
                if (mp[a[i - k]] == 0)    --cnt;
            }
            if (!mp[a[i]])    ++cnt;
            ++mp[a[i]];
            if (cnt == k or cnt == i)    f[i] = i - k > 0 ? f[i - k] : 1;
        }
        mp.clear(); cnt = 0;
        for (int i = n; i; --i) {
            if (f[i] and cnt == n - i) { flag = 1; break; }
            if (mp[a[i]] == 0)    ++cnt;
            ++mp[a[i]];
        }
        printf("%s", flag ? "YES\n" : "NO\n");
    }
    return 0;
}

2020牛客暑期多校训练营文章被收录于专栏

快乐的爆零赛