首页 模拟赛

二分答案，整除分块，dp + 推结论，曼哈顿转切比雪夫 + 4维区间dp

# A. 棍子 sticks

sticks 写成了 stick，遗憾爆零/kk

签到题，就是一道二分答案板子。

不知道是什么原因，大样例卡精度死循环，于是直接 check 了 2e62e6 次，喜提最劣解。

不得不佩服 lj\text{lj} 神机，全场就 flsfls 一个人有分orz

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
#include <bits/stdc++.h>
#define eps 1e-9
#define int long long

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 60;
int n, m, k;
double a[N], mx;

inline bool check(double mid){
    int cnt = 0, tot = 0;
    for(int i = 1; i <= n; ++i){
        if(tot == m) {cnt += (a[i] >= mid); continue;}
        int tmp = floor(a[i] / mid);
        if(tmp - 1 + tot >= m) cnt += (m - tot) + 1, tot = m;
        else if(tmp > 0) cnt += tmp, tot += (tmp - 1);
    }
    return cnt >= k && tot <= m;
}

signed main(){
//    freopen("sticks.in", "r", stdin);
//    freopen("sticks.out", "w", stdout);
    n = read(), m = read(), k = read();
    for(int i = 1; i <= n; ++i) scanf("%lf", &a[i]), mx = max(mx, a[i]);
    double l = 0, r = mx, res = 0;
    for(int i = 1; i <= 2e6; ++i){
        double mid = (l + r) / 2;
        // cout << l << " " << r << " " << mid << " " << r - l << " " << check(mid) << endl;
        if(check(mid)) res = mid, l = mid;
        else r = mid;
    }
    printf("%.12lf\n", res);
    return 0;
}

# B. 数组 count

看题 10min\text{10min} 后就想到了整除分块，结果还是想假了，把 CminC_{min} 和 CmaxC_{max} 放到一块计算了，不知道当时脑子是怎么想的。

关键样例还都过了？我直接缓缓打出一个？

还有 subtask\text{subtask}，最后自然是喜提一个 0 分。

思路比较简单，差分的思想，算 CmaxC_{max} 的答案减去 Cmin−1C_{min} - 1 的答案。对 AA 整除分块，算出 CA\frac CA，跟 BB 的范围取个交即可。

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
#include <bits/stdc++.h>
#define int long long

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

int A1, A2, B1, B2, C1, C2;
int ans;

inline void solve_1(){
    for(int i = A1; i <= A2; ++i){
        int t1 = ceil(1.0 * C1 / i), t2 = C2 / i;
		cout << t1 << " " << t2 << endl;
        ans += max(0ll, min(t2, B2) - max(t1, B1) + 1);
    }
}

inline int solve(int n){
    int res = 0;
    if(!n) return 0;
    for(int l = A1, r = 0; l <= A2; l = r + 1){
        if(n / l <= 0) break;
        r = min(A2, n / (n / l));
        int t = n / l;
        if(t >= B1) res += (min(B2, t) - B1 + 1) * (r - l + 1);
    }
    return res;
}

signed main(){
//    freopen("test.in", "r", stdin);
//    freopen("test.out", "w", stdout);
    scanf("%lld%lld%lld%lld%lld%lld", &A1, &A2, &B1, &B2, &C1, &C2);
    write(solve(C2) - solve(C1 - 1)), puts("");
    return 0;
}

# C. 十一 eleven

next_permutation 谁不会啊，喜提 20 分。

观察到部分分：每个数字位数相同。

考场上实在是想不出来这玩意有啥用/kk

稍微模拟一下可知：

  • 对于偶数位数的数：数字 xx 经过这个数之后形成的数一定是 (x+?) mod 11(x + ?) \bmod 11 这样形式的。

  • 对于奇数位数的数：数字 xx 经过之后一定是 (x−?) mod 11(x - ?) \bmod 11 这样子的。

先考虑部分分。

如果所有数都是偶数位数的，那么最终的数为：

(((0+a) mod 11+b) mod 11)⋯(((0 + a) \bmod 11 + b) \bmod 11)\cdots

所以我们只需要确定一下所有数的和是否能整除 11 即可，答案就是 n!n!。

对于奇数位数，表达式为：

(c−(b−(0+a)))(c - (b - (0 + a)))

展开之后为：

−0+a−b+c- 0 + a - b + c

不难发现这东西正负号是交替的，所以设 fi,j,kf_{i, j, k} 表示 ii 个正，jj 个负，这些数的和  mod 11\bmod 11 的值为 kk 时的方案数。

转移的时候对于新加进来的数放到正数位置还是负数位置分别考虑：

有转移方程：

fi+1,j,k+nxtp+=fi,j,kfi,j+1,k−nxtp+=fi,j,kf_{i + 1, j, k + nxt_p} += f_{i, j, k} \\ f_{i, j + 1, k - nxt_p} += f_{i, j, k}

但是一个奇数位数的数展开之后的正负号个数是固定的，分别为 cntz,cntfcnt_z, cnt_f（自己推一下吧）

部分分就做完了。

再来看满分如何做。

我们对偶数位数的数也进行一次上述 dp\text{dp}，设为 gi,j,kg_{i, j, k}。然后思考如何将两个 dp\text{dp} 数组合并。

我们考虑把偶数位数的数插入到奇数位数的数中间，所以有些偶数位数的数对答案的贡献是正，有些是负的。

枚举有多少个是正的，多少个是负的。

dp\text{dp} 值贡献为 fcntz,cntf,11−k×gi,cnt−i,kf_{cnt_z, cnt_f, 11 - k} \times g_{i, cnt - i, k}，但是偶数位数的数还有很多种放法。

  • 对于奇数位数中的正数：

    有 cntz!cnt_z! 种排列方式，然后新插入一个数，有 cntzcnt_z 个位置，对于插入的第二个数，有 cntz+1cnt_z + 1 个位置，以此类推。

    所以总方案数为 (cntz+i−1)!×cntz(cnt_z + i - 1)! \times cnt_z

  • 对于计数位数中的负数：

    实际上是有 cntf+1cnt_f + 1 个位置的，因为还要加上 −0-0 的位置，例子见上面。所以放第一个数时就有 cntf+1cnt_f + 1 个位置，第二个数有 cntf+2cnt_f + 2 个位置，以此类推。

    总方案数为 (cntf+cnt−i)!(cnt_f + cnt - i)!

别的就没了，具体看代码吧。

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
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 60;
const int mod = 1e9 + 7;
int n, c1, c2, cz, cf, cnt;
char s[N];
int nxt1[N], nxt2[N];
int f[N][N][15], g[N][N][15];
int fac[N], ifac[N];

inline void add(int &x, int y) {x = (x + y >= mod) ? x + y - mod : x + y;}
inline int add(int x) {return (x % 11 + 11) % 11;}
inline int sub(int x) {return x < 0 ? x + 11 : x;}
inline int mul(int x, int y) {return 1ll * x * y % mod;}

inline int qpow(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod, b >>= 1;
    }
    return res;
}

inline void init(){
    fac[0] = 1;
    for(int i = 1; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
    ifac[n] = qpow(fac[n], mod - 2);
    for(int i = n - 1; i >= 0; --i) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
}

inline int C(int n, int m){
    return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif  
    n = read(), init();
    for(int i = 1, len, x = 0; i <= n; ++i, x = 0){
        scanf("%s", s + 1), len = strlen(s + 1);
        for(int j = 1; j <= len; ++j) x = (x * 10 + s[j] - '0') % 11;
        if(len & 1) nxt1[++c1] = x;
        else nxt2[++c2] = x; 
    }

    f[0][0][0] = 1;
    for(int p = 1; p <= c1; ++p)
        for(int i = 0; i < p; ++i){
            int j = p - i - 1;
            for(int k = 0; k < 11; ++k){
                add(f[i + 1][j][add(k + nxt1[p])], f[i][j][k]);
                add(f[i][j + 1][add(k - nxt1[p])], f[i][j][k]);
            }
        }

    g[0][0][0] = 1;
    for(int p = 1; p <= c2 + 1; ++p)
        for(int i = 0; i < p; ++i){
            int j = p - i - 1;
            for(int k = 0; k < 11; ++k){
                add(g[i + 1][j][add(k + nxt2[p])], g[i][j][k]);
                add(g[i][j + 1][add(k - nxt2[p])], g[i][j][k]);
            }
        }

    if(!c1){
        int x = 0;
        for(int i = 1; i <= n; ++i) x = add(x + nxt2[i]);
        if(!x) write(fac[n]), puts("");
        else puts("0");
        return 0;
    }

    cf = c1 / 2, cz = c1 - cf;
    int ans = 0;
    for(int i = 0; i <= c2; ++i)
        for(int j = 0; j < 11; ++j){
            int res = 1ll * f[cz][cf][add(11 - j)] * g[i][c2 - i][j] % mod;
            add(ans, mul(mul(res, fac[cf + c2 - i]), mul(fac[cz + i - 1], cz)));
        }
    write(ans), puts("");
    return 0;
}

# D. 棋盘 chess

一道区间 dp\text{dp} 板题，然而考场上并没有想到/kk

首先曼哈顿距离转切比雪夫距离，坐标从 (x,y)(x, y) 变成了 (x−y,x+y)(x - y, x + y)。

然后所求距离从 ∣x1−x2∣+∣y1−y2∣|x_1 - x_2| + |y_1 - y_2| 变成了 max⁡(x1−x2,y1−y2)\max(x_1-x_2,y_1-y_2)

设 fl,r,d,uf_{l, r, d, u} 表示还剩这个矩形时，消掉这个矩形内所有点的最小代价。

使用记忆化搜索实现，每次转移的时候从四条边分别往里收缩一个单位即可。

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
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 20;
const int inf = 1e9;
int n;
char s[N][N];
int a[N][N], f[N][N][N][N];

inline int dfs(int l, int r, int d, int u){
    if(~f[l][r][d][u]) return f[l][r][d][u];
    if(l == r && d == u) return 0;
    int res = inf;
    if(d < u){
        int sd = 0, su = 0;
        for(int i = l; i <= r; ++i){
            if(a[i][u]) su += max(u - d, max(i - l, r - i));
            if(a[i][d]) sd += max(u - d, max(i - l, r - i));
        }
        res = min(res, min(sd + dfs(l, r, d + 1, u), su + dfs(l, r, d, u - 1)));
    }
    if(l < r){
        int sl = 0, sr = 0;
        for(int i = d; i <= u; ++i){
            if(a[l][i]) sl += max(r - l, max(i - d, u - i));
            if(a[r][i]) sr += max(r - l, max(i - d, u - i));
        }
        res = min(res, min(sl + dfs(l + 1, r, d, u), sr + dfs(l, r - 1, d, u)));
    }
    return f[l][r][d][u] = res;
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = 8;
    for(int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if(s[i][j] == '#') a[i + j - 1][i - j + n] = 1;
    memset(f, -1, sizeof(f));
    write(dfs(1, 15, 1, 15)), puts("");
    return 0;
}

阅读次数 次