Asusetic
0%

2021-05-16模拟赛

发表于 分类于 Valine：
本文字数： 1.3k 阅读时长 ≈ 1 分钟

咕咕咕

2021.05.16 模拟赛

T1 LCS Again

原题 CF578D

玩了很长时间玩出来了

不算很难搞的数数题

考虑如果是类似 aaaaaa…aaaaaa\dots 的串那么随便去一个位置填一个其他字符答案就是 n(m−1)n(m-1)

进一步的，如果是类似 aaabbccc…aaabbccc\dots 这样的因为相邻的两个同样的字符没有区别，所以每组相邻的相同字符就只有一个 n(m−1)n(m-1) 的贡献

但是想 aabaab 这样的串 aa+baa+b 和 ab+aab+a 是一样的，拓展一下考虑到 ababab…ababab\dots 这样的串所有子串都会被算重一遍，所以统计这样的极长串减掉子串就好

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
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1000005;
ll n, m, ans;
char s[N];
int main() {
    cin >> n >> m;
    cin >> s + 1;
    s[0]   = "/QAQ"[0];
    ans    = 1ll * n * (m - 1);
    ll len = 1;
    for (int i = 2; i <= n; i++) {
        if (s[i] != s[i - 1]) {
            ans += n * (m - 1);
            if (len == 1) {
                len++;
                continue;
            }
        }
        if (len != 1) {
            if (s[i] == s[i - 2]) {
                len++;
            } else {
                ans -= len * (len - 1) / 2;
                if (s[i] == s[i - 1]) {
                    len = 1;
                } else {
                    len = 2;
                }
            }
        }
    }
    // cout << len << endl;
    if (len > 1)
        ans -= 1ll * len * (len - 1) / 2;
    cout << ans << endl;
    return 0;
}
//Asusetic eru quionours.

T2 赢家

赢家

纯暴力 45pts 血赚

反向统计不合法的方案

不合法的方案一定有从 11 能到的点集 SS ，和从 22 能到的点集 TT

有 S∩T=ϕS \cap T =\phi

显然 SS 与 TT 直接不能有边

同时对于剩下的点 P={x∈V∣x∉S and x∉T}P=\{x\in V|x\notin S \ \mathrm{and} \ x \notin T\}

一定是从 PP 向 S,TS,T 连边的，这里的方案是固定的

所以统计 SS 的方案即可

对于 SS 的方案同样反向统计

总方案是 2∣E(S)∣2^{|E(S)|}

不合法的方案就是 SS 的子集的方案数乘上两个点集中间边的方案数

即 dpS=2∣E(s)∣−∑t∈S2E(S−t)dp_S=2^{|E(s)|}-\sum\limits_{t \in S} 2^{E(S-t)}

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
#include <iostream>
using namespace std;
const int N = 16, mod = 1e9 + 7;
typedef long long ll;
int G[N][N];
int p2[N * N];
int n, m;
ll dp[(1 << N)][2];
int cnt[(1 << N)];
int main() {
    int tmp;
    cin >> n >> m >> tmp;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        G[u][v] = G[v][u] = 1;
    }
    p2[0] = 1;
    for (int i = 1; i <= n * n; i++) {
        p2[i] = p2[i - 1] * 2 % mod;
    }
    for (int s = 0; s < (1 << n); s++) {
        for (int i = 0; i < n; i++) {
            if ((s >> i) & 1) {
                cnt[s] = cnt[s ^ (1 << i)];
                for (int j = 0; j < n; j++) {
                    if ((s >> j) & 1) {
                        cnt[s] += G[i][j];
                    }
                }
                break;
            }
        }
    }
    for (int s = 1; s < (1 << n); s++) {
        if (s & 1) {
            dp[s][0] = p2[cnt[s]];
            for (int t = (s - 1) & s; t; t = s & (t - 1)) {
                dp[s][0] = (dp[s][0] - dp[t][0] * p2[cnt[s ^ t]]) % mod;
            }
        }
        if (s & 2) {
            dp[s][1] = p2[cnt[s]];
            for (int t = (s - 1) & s; t; t = s & (t - 1)) {
                dp[s][1] = (dp[s][1] - dp[t][1] * p2[cnt[s ^ t]]) % mod;
            }
        }
    }
    ll ans = p2[m];
    for (int s = 0; s < (1 << n); s++) {
        if (dp[s][0]) {
            for (int t = s + 1; t < (1 << n); t = (t + 1) | s) {
                if (dp[s ^ t][1]) {
                    int z = (1 << n) - 1 - t;
                    if (cnt[s ^ z] + cnt[s ^ z ^ t] - cnt[z] == m) {
                        ans =
                            (ans -
                             dp[s][0] * dp[s ^ t][1] % mod * p2[cnt[z]] % mod +
                             mod) %
                            mod;
                    }
                }
            }
        }
    }
    cout << (ans + mod) % mod;
}
//Asusetic  eru quionours.

T3 障碍赛车

障碍赛车

题面太长没看

发现只要障碍确定那么下一层的时间很好推

考虑记录 dpi,Sdp_{i,S} 表示第 ii 层距离分别为 SS 的答案，暴力转移复杂度挂掉

思考一下距离记下来这么多没必要，因为左右两个点距离只会差一，差分一下

为了避免 −1-1 以中间点为界，左边的 00 表示比右边点多一， 11 表示少一，反之同理

口胡一下会发现不可能有一样的距离

这样状态为 dp[i][t][S]dp[i][t][S] 表示 ii 层，终点距离 tt 差分为 SS 的状态，大力转移即可，需要预处理各个状态的距离和差分

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
#include <iostream>
using namespace std;
int n, k, t, m;
struct BigNumber {
    int a[18], len;
    int &operator[](int x) {
        return a[x];
    }
    bool zero() const {
        return len == 0 && a[0] == 0;
    }
    void operator+=(const BigNumber &x) {
        if (len == 0 && a[0] == 0) {
            *this = x;
            return;
        }
        register int i;
        if (len < x.len)
            len = x.len;
        for (i = 0; i <= len; ++i) {
            a[i] += x.a[i];
            if (a[i] >= 1000000000)
                ++a[i + 1], a[i] -= 1000000000;
        }
        if (a[len + 1])
            ++len;
        return;
    }
    void pr() {
        register int i;
        printf("%d", a[len]);
        for (i = len - 1; i >= 0; --i)
            printf("%09d", a[i]);
        return;
    }
} dp[108][501][18], ans;
int p[110], dis[18][36], d0[5], d1[5], state[18][36];
int lim, U;
void pre() {
    if (k == 1) {
        d0[1] = 0;
        for (int i = 0; i < 4; ++i) {
            d0[0] = (i & 1) ? 1 : -1;
            d0[2] = (i & 2) ? 1 : -1;
            for (int x = 0; x < 7; ++x) {
                for (int j = 0; j <= 2; j++) {
                    d1[j] = (x & (1 << j)) ? 9 : d0[j] + 1;
                }
                for (int j = 1; j <= 2; j++) {
                    d1[j] = min(d1[j], d1[j - 1] + 1);
                }
                for (int j = 0; j <= 1; j++) {
                    d1[j] = min(d1[j], d1[j + 1] + 1);
                }
                dis[i][x]   = d1[1];
                state[i][x] = (d1[0] > d1[1] ? 1 : 0) | (d1[2] > d1[1] ? 2 : 0);
            }
        }
    } else {
        d0[2] = 0;
        for (int i = 0; i < 16; ++i) {
            int x = i;
            for (int j = 0; j < 2; ++j, x >>= 1)
                d0[j] = (x & 1) ? 1 : -1;
            for (int j = 3; j < 5; ++j, x >>= 1)
                d0[j] = (x & 1) ? 1 : -1;
            d0[0] += d0[1], d0[4] += d0[3];
            for (int s = 0; s < 31; ++s) {
                for (int j = 0; j <= 4; ++j)
                    d1[j] = (s & (1 << j)) ? 9 : d0[j] + 1;
                for (int j = 0; j < 4; ++j)
                    d1[j + 1] = min(d1[j + 1], d1[j] + 1);
                for (int j = 4; j; --j)
                    d1[j - 1] = min(d1[j - 1], d1[j] + 1);
                dis[i][s] = d1[2];
                int S     = 0;
                for (int j = 0; j < 2; ++j)
                    if (d1[j] > d1[j + 1])
                        S |= 1 << j;
                for (int j = 2; j < 4; ++j)
                    if (d1[j + 1] > d1[j])
                        S |= 1 << j;
                state[i][s] = S;
            }
        }
    }
}
int main() {
    cin >> n >> k >> t >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        p[x] |= (1 << (y + k));
    }
    lim = (1 << (2 * k)) - 1;
    U   = lim * 2 + 1;
    pre();
    dp[0][0][lim][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = i; j <= t; j++) {
            for (int s = 0; s <= lim; s++) {
                if (dp[i][j][s].zero())
                    continue;
                for (int X = p[i]; X < U; X = (X + 1) | p[i]) {
                    dp[i + 1][min(j + dis[s][X], t)][state[s][X]] +=
                        dp[i][j][s];
                }
            }
        }
    }
    for (int s = 0; s <= lim; ++s)
        ans += dp[n][t][s];
    ans.pr();
}

T4 Haiku

原题 ARC058E

考场上硬计数整数拆分没数出来，吃饭突然想到该状压搞

思考一下发现直接统计方案很难保证不重

所以统计不合法的

数据范围就很状压，考虑 x+y+z≤17x+y+z \le 17 所以得用 2x+y+z2^{x+y+z} 个状态

考虑直接把数字放在对应的位置上，比如

4→10004 \rightarrow 1000 3→1003 \rightarrow 100

那么符合条件的就是 x+y+z−1x+y+z-1 y+z−1y+z-1 z−1z-1 位都是 11

dpdp 统计不合法的 dpi,Sdp_{i,S} 就是前 ii 个数字状态是 SS 的方案，只要不合法就转移就可

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
/*
さびしさや
一尺消えて
ゆくほたる
*/
#include <iostream>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b /= 2;
    }
    return res;
}
ll n, x, y, z;
ll S;
ll ans;
ll bitadd(ll x, ll i) {
    return ((x << i) | (1 << (i - 1))) & (S - 1);
}
ll mask;
bool check(ll state) {
    return ((state & mask) == mask);
}
int dp[42][(1 << 18)];
int main() {
    cin >> n >> x >> y >> z;
    ans  = qpow(10, n);
    mask = (1 << (x + y + z - 1));
    mask |= (1 << (y + z - 1));
    mask |= (1 << (z - 1));
    dp[0][0] = 1;
    S        = (1 << (x + y + z));
    for (int i = 1; i <= n; i++) {
        for (int s = 0; s < S; s++) {
            for (int k = 1; k <= 10; k++) {
                ll u = bitadd(s, k);
                if (!check(u)) {
                    dp[i][u] = (dp[i][u] + dp[i - 1][s]) % mod;
                }
            }
        }
    }
    for (int s = 0; s < S; s++) {
        ans = (ans - dp[n][s] + mod) % mod;
    }
    cout << ans << endl;
}
// Asusetic eru quionours