跃迁引擎启动

Codeforces Round 539 题解

发表于 更新于 分类于 阅读次数：

A Sasha and His Trip

$1$ 到 $n$ 个地点排成一行，相邻两个距离为 $1$，现在要从 $1$ 不回头走到 $n$。

走一个单位距离，消耗一点油，油箱最大容量为 $v$，每个点有一个加油站，第 $i$ 点加油的费用为 $i$ 块钱每升，求最小花费。

一开始尽量加满，然后每个位置如果油箱有空余且不能支持走完全程，就加油。

写错加油的容量，过了好久才过 T^T。

B Sasha and Magnetic Machines

给一个一个序列，选两个数 $a_i$ 和 $a_j$，选一个 $a_j$ 的因子 $x$，将两个数变成 $xa_i$ 和 $a_j \over x$，求序列总和最小能变成多少。

式子写出来

$$
\min(xa_i+{a_j \over x}-a_i-a_j)=\min((x-1)(a_i-{a_j \over x}))
$$

贪心的想，$a_i$ 肯定选最小的，$j$ 枚举即可。

C Sasha and a Bit of Relax

给一个序列，求有多少长度为偶数的连续子序列，满足序列前一半和后一半的异或和相等。

其实这个一半是骗你的，往一半上想就凉了。

实际上，就是求长度为偶数的区间，异或和为 $0$，统计一下每种异或前缀和的个数即可。

D Sasha and One More Name

将一个回文串，切几刀，拼成一个和一开始不同的回文串，求最小切几刀。

首先，判断出无解的情况，显然如果前一半每个字母都相同，不管怎么切都不会弄成一个不同的回文串。

对于一个回文串，他肯定存在一个前缀不是回文串，对称地切两刀，交换前后缀位置就是一个新的回文串，且与之前不同，所以刀数最多为 $2$。

所以就要判断能不能切一刀，可以发现这个串是一个回文循环串，由于 $1 \le n \le 5000$，暴力即可。

F Sasha and Interesting Fact from Graph Theory

求满足条件的 $n$ 个点带边权的树个数，边权取值范围是 $1$ 到 $m$，满足给定了 $a$ 和 $b$，树上 $a$ 到 $b$ 路径长度恰好为 $m$。

先只考虑 $a$ 到 $b$ 的路径，我们可以枚举这个路径上的边数 $i$，然后相当于将 $m$ 划分成了 $i$ 个数，由插空法可知有 $m-1 \choose i-1$ 种情况。路径上有 $i-1$ 个点可以随意选择，方案数为 $(i-1)!{n-2 \choose i-1}$。剩下 $n-1-i$ 条边的边权可以随意选择，方案数为 $m^{n-i-1}$。最后一部分就是求剩下的点挂在这条链上的树的个数。

由 Cayley定理，我们知道 $n$ 个带标号的点组成 $k$ 棵无根树的森林的方案数为 $k n^{n-k-1}(1 \le k \le n-1)$。

我们可以考虑将前一步选出来的路径上 $i+1$ 个点拿出来，加上剩余的点组成 $i+1$ 棵无根树。对于每棵无根树，为避免重复，将树上标号最小点设置定为根，这些根按第一部分连成树链即可。因此，只需要在最后乘上 $(i+1)n^{n-i-2}$。

代码

A

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int maxn = 100000 + 5;

int n, v;

int main() {
    cin >> n >> v;
    if (v >= n - 1) return printf("%d", n - 1), 0;
    int tot = v, ans = v;
    for (int i = 2; i <= n; i++) {
        tot--;
        if (tot < n - i) {
            int nd = min(n - i - tot, v - tot);
            tot += nd; ans += i * nd;
        }
    }
    cout << ans << endl;
    return 0;
}

B

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int maxn = 100000 + 5;

int n, a[maxn];

int main() {
    scanf("%d", &n); int sum = 0;
    for (int i = 0; i < n; i++) scanf("%d", a + i), sum += a[i];
    sort(a, a + n);
    int mn = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 2; j <= a[i]; j++) {
            if (a[i] % j) continue;
            mn = min(mn, (j - 1) * (a[0] - a[i] / j));
            // cout << (a[0] - a[i] / j) << endl;
        }

    }
    cout << sum + mn << endl;
    return 0;
}

C

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#include <map>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int maxn = 300000 + 5;

int n, a[maxn], pre[maxn];
map<int,int> mp[2];

int main() {
    scanf("%d", &n); mp[0][0]++;
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        pre[i] = pre[i - 1] ^ a[i];
        mp[i % 2][pre[i]]++;
    }
    // for (int i = 1; i <= n; i++) cout << pre[i] << ' '; cout << endl;
    ll ans = 0;
    for (auto& x: mp[0]) {
        ans += 1ll * x.second * (x.second - 1) / 2;
    }
    for (auto& x: mp[1]) {
        ans += 1ll * x.second * (x.second - 1) / 2;
    }
    cout << ans << endl;
    return 0;
}

D

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int maxn = 100000 + 5;

string s;
bool check(string s) { 
    for (int i = 0; i < s.length(); i++) if (s[i] != s[s.length() - 1 - i]) return 0;
    return 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> s;
    int n = s.length(), flag = 1;
    for (int i = 1; i < n / 2; i++) if (s[i] != s[i - 1]) {
        flag = 0; break;
    }
    if (flag) return puts("Impossible"), 0;
    for (int i = 1; i < n - 1; i++) {
        string t = s.substr(i) + s.substr(0, i);
        if (s == t) continue;
        if (check(t)) return puts("1"), 0;
    }
    puts("2");
    return 0;
}

F

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 1e9 + 7;
const int maxn = 1000000 + 5;

int f[maxn], inv[maxn], finv[maxn];
void init(){
    inv[1] = 1;
    for (int i = 2; i < maxn; i++) inv[i] = (mod - mod / i) * 1ll * inv[mod % i] % mod;
    f[0] = finv[0] = 1; 
    for (int i = 1; i < maxn; i++) {
        f[i] = f[i - 1] * 1ll * i % mod;
        finv[i] = finv[i - 1] * 1ll * inv[i] % mod;
    }
}
int C(int n, int m){
    if (m < 0 || m > n) return 0;
    return f[n] * 1ll * finv[n - m] % mod * finv[m] % mod;
}
ll qpow(ll x, ll n) {
    ll r = 1;
    while (n > 0) {
        if (n & 1) r = r * x % mod;
        n >>= 1; x = x * x % mod;
    }
    return r;
}
ll T(ll n, ll k) {
    if (k == n) return 1;
    return k * qpow(n, n - k - 1) % mod;
}

int n, m, a, b;

int main() {
    init();
    cin >> n >> m >> a >> b;
    ll ans = 0;
    for (int i = 1; i < n; i++) {
        ll tot = 1ll * C(m - 1, i - 1) * C(n - 2, i - 1) % mod * f[i - 1] % mod * qpow(m, n - i - 1) % mod * T(n, i + 1) % mod;
        ans += tot; if (ans >= mod) ans -= mod;
    }
    cout << ans << endl;
    return 0;
}