跳转至

251017 模拟赛

T1 multi

称一个数字是好的，当且仅当它在 \(B\) 进制下的各位数字互不相同（不考虑前导 \(0\)），规定 \(0\) 是合法的。问所有 \(n\) 的倍数且合法的数字中，第二大的是谁。

\(n\le 10^{18},~B\le 12\)

先枚举数字位数。考虑 meet in the middle，将数字分成左右两半，再 \(\binom{12}{2m}\binom{2m}{m}\)（最大为 \(34650,m=4\)）枚举左右两半各占用哪些数字，然后 \(m!\) 枚举全排列，再将所有数按模 \(n\) 的余数排序（相等时优先选大的），跑一边双指针合并即可。合并时 \(j\) 往后再找一位尝试更新次大值。

代码 
 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
#include<iostream>
#include<vectors>
#include<algorithm>
#include<unistd.h>
#define int long long
using namespace std;
const int N = 12;

int n, b;
int pw[20];

int cnt[1 << N];
vector<int> s;
vector<int> res1, res2;

int mx = -1, mx2 = -1;
int l, r;

bool cmp1(int x, int y) {
    if(x * pw[r] % n != y * pw[r] % n) return x * pw[r] % n < y * pw[r] % n;
    return x > y;
}

bool cmp2(int x, int y) {
    if((x + n - 1) % n != (y + n - 1) % n) return (x + n - 1) % n < (y + n - 1) % n;
    return x < y;
}

void check(int x) {
    if(x > mx) mx2 = mx, mx = x;
    else mx2 = max(mx2, x);
}

void work(int m) {
    if(m == 1) {
        for(int i = 0; i < b; i++) {
            if(i % n == 0) check(i);
        }
        return;
    }
    l = m / 2, r = m - m / 2;
    for(int i = 0; i < (1 << b); i++) {
        s.clear(); res1.clear();
        if(cnt[i] != l) continue;
        for(int j = 0; j < b; j++) {
            if((i >> j) & 1) s.push_back(j);
        }
        do {
            if(*s.begin() == 0) continue;
            int res = 0;
            for(int i = 0; i < s.size(); i++) res = res * b + s[i];
            res1.push_back(res);
        } while(next_permutation(s.begin(), s.end()));
        sort(res1.begin(), res1.end(), cmp1);
        int j = ((1 << b) - 1) ^ i;
        for(int i = j; i; i = (i - 1) & j) {
            if(cnt[i] != r) continue;
            s.clear(); res2.clear();
            for(int j = 0; j < b; j++) {
                if((i >> j) & 1) s.push_back(j);
            }
            do {
                int res = 0;
                for(int i = 0; i < s.size(); i++) res = res * b + s[i];
                res2.push_back(res);
            } while(next_permutation(s.begin(), s.end()));
            sort(res2.begin(), res2.end(), cmp2);
            if(res2.empty()) return;
            for(int i = 0, j = res2.size() - 1; i < res1.size(); i++) {
                while(j >= 0 && (res1[i] * pw[r]) % n + (res2[j] + n - 1) % n + 1 > n) --j;
                if(j >= 0 && (res1[i] * pw[r] + res2[j]) % n == 0) check(res1[i] * pw[r] + res2[j]);
                if(j >= 1 && (res1[i] * pw[r] + res2[j - 1]) % n == 0) check(res1[i] * pw[r] + res2[j - 1]);
            }
        }
    }
}

signed main() {

    freopen("multi.in", "r", stdin);
    freopen("multi.out", "w", stdout);

    cin >> n >> b;
    pw[0] = 1;
    for(int i = 1; i < 13; i++) pw[i] = pw[i - 1] * b;
    for(int i = 1; i < (1 << N); i++) cnt[i] = cnt[i >> 1] + (i & 1);

    for(int i = b; i >= 1; i--) {
        work(i);
    }
    cout << mx2 << endl;

    return 0;
}

T2 cover

考虑 dp，设 \(f_u\) 表示子树 \(u\) 的答案。枚举子树内第一个点是否是 \(u\)，得到转移：\(f_u=\frac{1}{sz[u]}+\sum f_v\)。于是发现是诈骗题。

T3 set

你需要将 \(1\sim n\) 总共 \(n\) 个数字放到 \(m\) 个无标号集合中（集合不可以为空），满足存在一种给集合标号的方案，使得 \(\forall i\in[1,n],~\max S_i\ge\min S_{i+1}\)，特别的，认为 \(S_{m+1}=S_{1}\)。

问总方案数对 \(10^9+7\) 取模的结果。

\(n,m\le 500\)

发现可以将集合按照 \(\max S_i\) 从小到大排序，这样右边的集合总是可以向左边的集合连边。我们需要让左边的集合向右边连边，使得所有集合串成一个环。手模一下发现只要不存在断层就是有解的。这样我们就可以容斥，容易做到 \(O(n^4)\)。

发现按集合进行转移是不好做的。考虑从小到大按照数字（值域）进行转移，上面的限制等价于对于每一个小区间 \([i,i+1]\) 都被至少一个集合完全覆盖。发现加入一个数字，\([i,i+1]\) 被覆盖的次数要么加一（新开一个集合，\(i\) 作为最小值），要么减一（\(i\) 作为先前某个集合的最大值），要么不变（\(i\) 既非最小值又非最大值），同时不能为 \(0\)。因此设 \(f_{i,j,k}\) 表示前 \(i\) 个数字形成了 \(j\) 个集合，\([i,i+1]\) 被 \(k\) 个集合覆盖的方案数。转移是 \(O(1)\) 的，因此总复杂度 \(O(n^3)\)。

这里再介绍另一种方法。考虑枚举划分方案，然后将每一段的斯特林数乘起来，再乘以 \(-1\) 的段数加一次方，得到答案。记斯特林数的生成函数为 \(F(x,y)\)，我们可以分别算出分 \(k\) 段的方案数 \([x^ny^m](F(x,y)-1)^{k}\)，再乘以容斥系数加起来。

尝试求解 \(g_{i,j,k}=[x^ny^m](F(x,y)-1)^{k}\) 的递推式。先写出 \(F(x,y)\) 的系数递推式，获得一些启发：

\[ \begin{Bmatrix}n\\ m\end{Bmatrix}=\begin{Bmatrix}n-1\\ m-1\end{Bmatrix}+m\begin{Bmatrix}n-1\\ m\end{Bmatrix} \]

那么 \(F(x,y)\) 有：

\[ F(x,y)=1+xy\Bigl(F(x,y)+\frac{\partial F(x,y)}{\partial y}\Big) \]

对 \(\bigl(F(x,y)-1\big)^{k}\) 对 \(y\) 求偏导，可以分离出一项 \(\frac{\partial F(x,y)}{\partial y}\)，从而借助上式转化：

\[ \begin{align*} \frac{\partial\bigl(F(x,y)-1\big)^{k}}{\partial y}&=\frac{\partial\bigl(F(x,y)-1\big)^{k}}{\partial\bigl(F(x,y)-1\big)}\frac{\partial\big(F(x,y)-1\big)}{\partial y}\\&=k\Bigl(F(x,y)-1\Big)^{k-1}\Bigl(\frac{F(x,y)-1}{xy}-F(x,y)\Big)\\ &=\frac{k}{xy}\bigl(F(x,y)-1\big)^k-k\bigl(F(x,y)-1\big)^k-k\bigl(F(x,y)-1\big)^{k-1} \end{align*} \]

现在就可以推递推式了。考虑式子中的 \([x^{i-1}y^{j-1}]\) 次项系数：

\[ jg_{i-1,j}=kg_{i,j,k}-kg_{i-1,j-1,k}-kg_{i-1,j-1,k-1} \]

于是：

\[ g_{i,j,k}=\frac{j}{k}g_{i-1,j}+g_{i-1,j-1,k}+g_{i-1,j-1,k-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
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
#define int long long
using namespace std;
const int MOD = 1e9 + 7;
const int N = 510;

int n, m, ans;

int s[N][N];
int g[2][N][N];

int inv[N];

signed main() {

    freopen("set.in", "r", stdin);
    freopen("set.out", "w", stdout);

    ios::sync_with_stdio(0);
    cin.tie(0);

    inv[1] = 1;
    for(int i = 2; i < N; i++) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;

    cin >> n >> m;
    s[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            s[i][j] = (s[i - 1][j - 1] + j * s[i - 1][j]) % MOD;
        }
    }

    ans = s[n][m];
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            g[1][i][j] = s[i][j];
        }
    }
    for(int k = 2; k <= m; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                g[k & 1][i][j] = inv[k] * (j * g[k & 1][i - 1][j] % MOD + k * g[k & 1][i - 1][j - 1] % MOD + k * g[(k & 1) ^ 1][i - 1][j - 1] % MOD) % MOD;
            }
        }
        if(k & 1) (ans += g[k & 1][n][m]) %= MOD;
        else (ans += MOD - g[k & 1][n][m]) %= MOD;
    }

    cout << ans << endl;

    return 0;
}

T4 tinyds

给定 \(n\) 个有序四元组 \((a_i,b_i,c_i,d_i)\)，你需要将它们分给两个人 \(A,B\)，满足每个四元组至少分给一个人，每个人至少分到一个四元组。定义一个分配方案的代价为

\[ \max_{i\in A}\{a_i\}+\max_{i\in A}\{b_i\}+\max_{i\in B}\{c_i\}+\max_{i\in B}\{d_i\} \]

最小化代价。

\(\sum n\le 10^6\)

发现没有什么很直接的做法。考虑将四元组放到二维平面上的 \((a_i,b_i)\) 位置，那么枚举一个位置 \((x,y)\)，然后将 \((x,y)\) 左下角的所有点都分给第一个人，其余点分给第二个人。我们希望对每个位置维护第二个人产生的代价。考虑对横坐标扫描线，记 \(ca[i]\) 表示 \(a_j>i\) 的 \(j\) 中 \(c_j\) 最大的是多少，\(da,cb,db\) 同理。那么代价可以表示成 \(\max(cb[i],ca)+\max(db[i],da)+i+a\)。由于从右向左扫描时 \(ca,da\) 单调递增，同时 \(cb[i],db[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
107
108
109
110
111
112
113
114
115
116
117
#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;
const int N = 1e6 + 10;
const ll INF = 0x003f3f3f3f3f3f3f;

struct Pt {
    int a, b, c, d;
} a[N];

int T, n; ll ans;

ll ca[2 * N], da[2 * N], cb[2 * N], db[2 * N], ba[2 * N];

ll num[2 * N]; int nn;
void lisanhua() {
    for(int i = 1; i <= n; i++) num[++nn] = a[i].a, num[++nn] = a[i].b;
    sort(num + 1, num + 1 + nn);
    nn = unique(num + 1, num + 1 + nn) - (num + 1);
    for(int i = 1; i <= n; i++) a[i].a = lower_bound(num + 1, num + 1 + nn, a[i].a) - num;
    for(int i = 1; i <= n; i++) a[i].b = lower_bound(num + 1, num + 1 + nn, a[i].b) - num;
}

int mn_a, mx_a;
namespace SegT {
    ll mn[8 * N], tag[8 * N];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    inline void push_up(int p) { mn[p] = min(mn[lc(p)], mn[rc(p)]); }
    inline void move_tag(int p, ll tg) { tag[p] += tg, mn[p] += tg; }
    inline void push_down(int p) {
        if(tag[p]) move_tag(lc(p), tag[p]), move_tag(rc(p), tag[p]), tag[p] = 0;
    }
    void build(int p, int l, int r) {
        tag[p] = 0;
        if(l == r) {
            mn[p] = num[l] + cb[l + 1] + db[l + 1];
            return;
        }
        int mid = (l + r) >> 1;
        build(lc(p), l, mid);
        build(rc(p), mid + 1, r);
        push_up(p);
    }
    void add(int p, int l, int r, int ql, int qr, ll v) {
        if(ql > qr) return;
        if(ql <= l && r <= qr) return move_tag(p, v);
        int mid = (l + r) >> 1; push_down(p);
        if(ql <= mid) add(lc(p), l, mid, ql, qr, v);
        if(mid < qr) add(rc(p), mid + 1, r, ql, qr, v);
        push_up(p);
    }
}

int main() {

    freopen("tinyds.in", "r", stdin);
    freopen("tinyds.out", "w", stdout);

    cin >> T;
    while(T--) {
        cin >> n; ans = INF; nn = 0;
        for(int i = 1; i <= n; i++) cin >> a[i].a >> a[i].b >> a[i].c >> a[i].d;
        if(n == 1) { cout << (ll)a[1].a + a[1].b + a[1].c + a[1].d << '\n'; continue; }
        lisanhua();
        for(int i = 0; i <= nn + 5; i++) ca[i] = da[i] = cb[i] = db[i] = -INF, ba[i] = INF;
        sort(a + 1, a + 1 + n, [](const Pt &a, const Pt &b) { return a.a < b.a; } );
        mn_a = a[1].a; mx_a = a[n].a;
        for(int i = 1; i <= n; i++) {
            ba[a[i].a] = min(ba[a[i].a], (ll)a[i].b);
            ca[a[i].a] = max(ca[a[i].a], (ll)a[i].c);
            da[a[i].a] = max(da[a[i].a], (ll)a[i].d);
        }
        sort(a + 1, a + 1 + n, [](const Pt &a, const Pt &b) { return a.b < b.b; } );
        for(int i = 1; i <= n; i++) {
            cb[a[i].b] = max(cb[a[i].b], (ll)a[i].c);
            db[a[i].b] = max(db[a[i].b], (ll)a[i].d);
        }
        for(int i = 1; i <= nn; i++) ba[i] = min(ba[i], ba[i - 1]);
        for(int i = nn; i >= 1; i--) ca[i] = max(ca[i], ca[i + 1]);
        for(int i = nn; i >= 1; i--) cb[i] = max(cb[i], cb[i + 1]);
        for(int i = nn; i >= 1; i--) da[i] = max(da[i], da[i + 1]);
        for(int i = nn; i >= 1; i--) db[i] = max(db[i], db[i + 1]);
        for(int i = nn + 1; i >= 1; i--) if(cb[i] < 0) cb[i] = INF;
        for(int i = nn + 1; i >= 1; i--) if(db[i] < 0) db[i] = INF;
        SegT::build(1, 1, nn);
        ba[mx_a + 1] = 1;
        for(int i = mx_a, j1 = nn + 1, j2 = nn + 1; i >= mn_a; i--) {
            if(ba[i] != ba[i + 1]) SegT::add(1, 1, nn, ba[i + 1], ba[i] - 1, INF);
            if(ca[i + 1] != ca[i + 2]) {
                SegT::add(1, 1, nn, j1, nn, ca[i + 1] - ca[i + 2]);
                while(j1 > 1 && (cb[j1] < ca[i + 1] || cb[j1] == INF)) SegT::add(1, 1, nn, j1 - 1, j1 - 1, ca[i + 1] - cb[j1]), j1--;
            }
            if(da[i + 1] != da[i + 2]) {
                SegT::add(1, 1, nn, j2, nn, da[i + 1] - da[i + 2]);
                while(j2 > 1 && (db[j2] < da[i + 1] || db[j2] == INF)) SegT::add(1, 1, nn, j2 - 1, j2 - 1, da[i + 1] - db[j2]), j2--;
            }
            ans = min(ans, SegT::mn[1] + num[i]);
        }
        cb[n + 1] = db[n + 1] = 0;
        for(int i = 1; i <= n; i++) ca[i] = max(ca[i - 1], (ll)a[i].c);
        for(int i = 1; i <= n; i++) da[i] = max(da[i - 1], (ll)a[i].d);
        for(int i = n; i >= 1; i--) cb[i] = max(cb[i + 1], (ll)a[i].c);
        for(int i = n; i >= 1; i--) db[i] = max(db[i + 1], (ll)a[i].d);
        for(int i = 1; i <= n; i++) ans = min(ans, max(ca[i - 1], cb[i + 1]) + max(da[i - 1], db[i + 1]) + num[a[i].a] + num[a[i].b]);
        for(int i = 1; i <= n; i++) ca[i] = max(ca[i - 1], (ll)num[a[i].a]);
        for(int i = 1; i <= n; i++) da[i] = max(da[i - 1], (ll)num[a[i].b]);
        for(int i = n; i >= 1; i--) cb[i] = max(cb[i + 1], (ll)num[a[i].a]);
        for(int i = n; i >= 1; i--) db[i] = max(db[i + 1], (ll)num[a[i].b]);
        for(int i = 1; i <= n; i++) ans = min(ans, max(ca[i - 1], cb[i + 1]) + max(da[i - 1], db[i + 1]) + a[i].c + a[i].d);
        cout << ans << '\n';
    }

    return 0;
}