2019牛客暑期多校训练营（第二场）

本文最后更新于：星期四, 二月 3日 2022, 9:15 晚上

A. Eddy Walker

题意：有nn个点，刚开始在00号点，每次等概率的往左右走，为最终停留在mm点的概率

思路：打表后发现概率为1n−1\frac{1}{n - 1}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll p = (ll) 1e9 + 7;

ll qpow(ll x, ll n) {
    ll res = 1;
    while (n) {
        if (n & 1) {
            res = res * x % p;
        }
        x = x * x % p;
        n >>= 1;
    }
    return res;
}

int n, m;

int main() {
    int t;
    scanf("%d", &t);
    ll ans = 1;
    while (t--) {
        scanf("%d %d", &n, &m);
        if (n == 1) {
            ans *= 1;
        } else if (m == 0) {
            ans = 0;
        } else {
            ans = ans * qpow(n - 1, p - 2) % p;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

B. Eddy Walker 2

题意：从00开始，每次有1k\frac{1}{k}的概率走1,2,⋯ .k1,2,\cdots.k步，问最后停留在nn的概率

思路：f[i]f[i]表示最后停留在ii点的概率，那么f[i]=1k⋅∑j=1kf[i−j]f[i]=\frac{1}{k} \cdot \sum_{j=1}^{k} f[i - j]，BM递推即可…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define N 1000010
const ll p = 1e9 + 7;
ll n, m, k, inv2, invk;
ll f[N], g[N], fac[N], inv[N];

ll qmod(ll base, ll n) {
    base %= p;
    ll res = 1;
    while (n) {
        if (n & 1) {
            res = res * base % p;
        }
        base = base * base % p;
        n >>= 1;
    }
    return res;
}

void add(ll &x, ll y) {
    x += y;
    if (x >= p) x -= p;
}

#define rep(i, a, n) for (int i=a;i<n;i++)
#define pb push_back
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef pair<int, int> PII;
const ll mod = 1000000007;
// head

int _;
namespace linear_seq {
    ll res[N], base[N], _c[N], _md[N];

    vector<int> Md;
    
    void mul(ll *a, ll *b, int k) {
        rep(i, 0, k + k) _c[i] = 0;
        rep(i, 0, k) if (a[i]) rep(j, 0, k) _c[i + j] = (_c[i + j] + a[i] * b[j]) % mod;
        for (int i = k + k - 1; i >= k; i--)
            if (_c[i])
                rep(j, 0, SZ(Md)) _c[i - k + Md[j]] = (_c[i - k + Md[j]] - _c[i] * _md[Md[j]]) % mod;
        rep(i, 0, k) a[i] = _c[i];
    }
    
    int solve(ll n, VI a, VI b) { // a 系数 b 初值 b[n+1]=a[0]*b[n]+...
        //        printf("%d\n",SZ(b));
        ll ans = 0, pnt = 0;
        int k = SZ(a);
        assert(SZ(a) == SZ(b));
        rep(i, 0, k) _md[k - 1 - i] = -a[i];
        _md[k] = 1;
        Md.clear();
        rep(i, 0, k) if (_md[i] != 0) Md.push_back(i);
        rep(i, 0, k) res[i] = base[i] = 0;
        res[0] = 1;
        while ((1ll << pnt) <= n) pnt++;
        for (int p = pnt; p >= 0; p--) {
            mul(res, res, k);
            if ((n >> p) & 1) {
                for (int i = k - 1; i >= 0; i--) res[i + 1] = res[i];
                res[0] = 0;
                rep(j, 0, SZ(Md)) res[Md[j]] = (res[Md[j]] - res[k] * _md[Md[j]]) % mod;
            }
        }
        rep(i, 0, k) ans = (ans + res[i] * b[i]) % mod;
        if (ans < 0) ans += mod;
        return ans;
    }
    
    VI BM(VI s) {
        VI C(1, 1), B(1, 1);
        int L = 0, m = 1, b = 1;
        rep(n, 0, SZ(s)) {
            ll d = 0;
            rep(i, 0, L + 1) d = (d + (ll) C[i] * s[n - i]) % mod;
            if (d == 0) ++m;
            else if (2 * L <= n) {
                VI T = C;
                ll c = mod - d * qmod(b, mod - 2) % mod;
                while (SZ(C) < SZ(B) + m) C.pb(0);
                rep(i, 0, SZ(B)) C[i + m] = (C[i + m] + c * B[i]) % mod;
                L = n + 1 - L;
                B = T;
                b = d;
                m = 1;
            } else {
                ll c = mod - d * qmod(b, mod - 2) % mod;
                while (SZ(C) < SZ(B) + m) C.pb(0);
                rep(i, 0, SZ(B)) C[i + m] = (C[i + m] + c * B[i]) % mod;
                ++m;
            }
        }
        return C;
    }
    
    int gao(VI a, ll n) {
        VI c = BM(a);
        c.erase(c.begin());
        rep(i, 0, SZ(c)) c[i] = (mod - c[i]) % mod;
        return solve(n, c, VI(a.begin(), a.begin() + SZ(c)));
    }
};

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld", &k, &n);
        invk = qmod(k, p - 2);
        if (n == -1) {
            printf("%lld\n", 2ll * qmod(k + 1, p - 2) % p);
            continue;
        }
        for (int i = 1; i <= m; ++i) f[i] = 0;
        f[0] = 1;
        g[0] = 1;
        for (int i = 1; i <= 2 * k; ++i) {
            if (i > k) {
                add(f[i], invk * (g[i - 1] - g[i - k - 1] + p) % p);
            } else {
                add(f[i], invk * g[i - 1] % p);
            }
            g[i] = (g[i - 1] + f[i]) % p;
        }
        vector<int> vec;
        for (int i = 0; i <= 2 * k; ++i) vec.push_back(f[i]);
        printf("%d\n", linear_seq::gao(vec, n));
    }
    return 0;
}

D.Kth Minimum Clique

题意：输出第kk个CliqueClique

思路：每次取最小权值的CliqueClique，增加CliqueClique的点，重新丢到优先队列中，重复kk次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef bitset<110> bs;

#define N 110

struct node {
    bs S;
    ll sum;

    node() {}
     
    node(bs S, ll sum) : S(S), sum(sum) {}
     
    bool operator<(const node &other) const {
        return sum > other.sum;
    }
};

int n, K;
ll v[N];
bs e[N];
priority_queue<node> pq;


int main() {
    scanf("%d %d", &n, &K);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", v + i);
    }
    for (int i = 1, x; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf("%1d", &x);
            if (x == 1) {
                e[i].set(j);
            }
        }

    }
    bs s;
    s.reset();
    pq.push(node(s, 0));
    while (!pq.empty()) {
        node u = pq.top();
        pq.pop();
        K--;
        if (K == 0) {
            printf("%lld\n", u.sum);
            return 0;
        }
        s = u.S;
        int pos = 0;
        for (int i = 1; i <= n; ++i) {
            if (s[i]) {
                pos = i;
            }
        }
        for (int i = pos + 1; i <= n; ++i) {
            if (!s[i] && ((s & e[i]) == s)) {
                s.set(i);
                pq.push(node(s, u.sum + v[i]));
                s.reset(i);
            }
        }
    }
    puts("-1");
    return 0;
}

F. Partition problem

题意：有2⋅N2\cdot N个人，将这2⋅N2\cdot N个人分为两个集合，每个集合为NN个人，总的贡献是每对属于两个集合的人的贡献

思路：爆搜C2⋅NNC_{2\cdot N} ^ {N}，所以总复杂度为O(N⋅C2⋅NN)O(N \cdot C_{2 \cdot N} ^ {N})

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define N 40

int n, m;
int v[N][N];
ll ans, tnow;
int arr[N], brr[N];

inline void calc() {
    ll res = 0;
    for (register int i = 1; i <= m; ++i) {
        for (register int j = 1; j <= m; ++j) {
            res += v[arr[i]][brr[j]];
        }
    }
    ans = max(ans, res);
}

void DFS(int pos, int cnt, ll now) {
    // 1
    if (cnt == n - pos + 1) {
        int tmp = arr[0];
        tnow = now;
        for (register int i = pos; i <= n; ++i) {
            arr[++arr[0]] = i;
            for (int j = 1; j <= m; ++j) {
                tnow += v[i][brr[j]];
            }
        }
        ans = max(ans, tnow);
        arr[0] = tmp;
        return;
    }
    if (cnt) {
        arr[++arr[0]] = pos;
        tnow = now;
        for (int j = 1; j <= brr[0]; ++j) {
            tnow += v[pos][brr[j]];
        }
        if (pos < n) {
            DFS(pos + 1, cnt - 1, tnow);
        } else {
            ans = max(ans, tnow);
        }
        --arr[0];
    }
    //0
    brr[++brr[0]] = pos;
    tnow = now;
    for (int i = 1; i <= arr[0]; ++i) {
        tnow += v[arr[i]][pos];
    }
    if (pos < n) {
        DFS(pos + 1, cnt, tnow);
    } else {
        ans = max(ans, tnow);
    }
    --brr[0];
}

int main() {
    scanf("%d", &n);
    m = n;
    n <<= 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf("%d", &v[i][j]);
        }
    }
    DFS(1, m, 0ll);
    printf("%lld\n", ans);
    return 0;
}

H.Second Large Rectangle

题意：找第二大的全为11的矩阵

思路：找出第一个最大的矩阵，然后将四个角分别赋值为00，然后找最大的矩阵，取MAXMAX

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;

#define N 1010
int n, m;
int G[N][N], T[N][N], l[N][N], r[N][N], up[N][N];

void get(int G[][N], int &x, int &y, int &row, int &col) {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            l[i][j] = r[i][j] = j;
            up[i][j] = 1;
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 2; j <= m; ++j) {
            if (G[i][j] == 1 && G[i][j] == G[i][j - 1]) {
                l[i][j] = l[i][j - 1];
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = m - 1; j >= 1; --j) {
            if (G[i][j] == 1 && G[i][j] == G[i][j + 1]) {
                r[i][j] = r[i][j + 1];
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (i > 1 && G[i][j] == 1 && G[i][j] == G[i - 1][j]) {
                l[i][j] = max(l[i][j], l[i - 1][j]);
                r[i][j] = min(r[i][j], r[i - 1][j]);
                up[i][j] = up[i - 1][j] + 1;
            }
            if (G[i][j] == 1) {
                int tcol = r[i][j] - l[i][j] + 1;
                int trow = up[i][j];
                if (tcol * trow > row * col) {
                    col = tcol;
                    row = trow;
                    x = i - up[i][j] + 1;
                    y = l[i][j];
                }
            }
        }
    }
}

int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                scanf("%1d", G[i] + j);
                T[i][j] = G[i][j];
            }
        }
        int x, y, tx, ty, row = 0, col = 0, trow = 0, tcol = 0;
        get(G, x, y, row, col);
        //  cout << x << " " << y << " " << row << " " << col << endl;
        if (row == 0) {
            printf("0\n");
        } else {
            T[x][y] = 0;
            get(T, tx, ty, trow, tcol);
            T[x][y] = 1;
            T[x + row - 1][y] = 0;
            get(T, tx, ty, trow, tcol);
            T[x + row - 1][y] = 1;
            T[x][y + col - 1] = 0;
            get(T, tx, ty, trow, tcol);
            T[x][y + col - 1] = 1;
            T[x + row - 1][y + col - 1] = 0;
            get(T, tx, ty, trow, tcol);
            printf("%d\n", trow * tcol);
        }
    }
    return 0;
}

2019牛客多校

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！