img

牛客周赛 Round 5

A

模拟加取模

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
 
int main() {
    ios::sync_with_stdio(!cin.tie(nullptr));
    string s;
    cin >> s;
    int n = s.size();
    for (char& c : s) {
        if ('a' <= c && c <= 'z') {
            c = 'a' + (c - 'a' - 1 + 26) % 26;
        }
        if ('A' <= c && c <= 'Z') {
            c = 'A' + (c - 'A' + 1) % 26;
        }
    }
    cout << s;
    return 0;
}

B

直接开模

k<=(n+1)/2性质意味着一定可以构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 100010;
 
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,k; cin >> n >> k;
    int p = n - k + 1,q = 1,cnt = 0;
    for(int i=0;i<k;i++)
    {
        cout << p++ << ' ';
        cnt ++;
        if(cnt<n)
        {
            cout << q++ << ' ';
            cnt ++;
        }
    }
    for(int i=cnt;i<n;i++) cout << q++ << ' ' ;
    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
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
#define int long long
using namespace std; 
const int N = 1010;
vector<int> G[N];
int tot = 0;
int n, l, r;
string s;
 
void dfs(int u, int fa, int k, int step) {
    if (k > r) 
    {
        return;
    }
    //大于r跳过
    if (k >= l && step) 
    {
        tot++;
    }
    //满足加加
    for (auto v : G[u]) {
        int x = s[v - 1] - '0';
        if (v != fa) {
            dfs(v, u, k * 2 + x, step + 1);
            //深搜
        }
    }
}
 
signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> l >> r >> s;
    for (int i = 1; i < n; i++) 
    {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        dfs(i, -1, s[i - 1] - '0', 0);
    }
    cout << tot << "\n";
    return 0;
}

E

要使得所有点的权值乘积最小，自然需要路径最短，而路径最短的图就是菊花图。

因此，总共有以下几种路径：
- \(2-2/3-3\)
- \(2-3/3-2\)
- \(2-2-2/3-3-3\)
- \(2-2-3/2-3-2/3-2-2\)
- \(3-2-3/2-3-3\)

为什么将 \(2-2/3-3\) 和 \(2-2-2/3-3-3\) 放在一起？

因为它们的乘积因子数是相同的，只是路径中节点的位置不同，最终路径的结果是一样的。

因子数分析

组合 $ (3,2) $ 单独排列的因子数要小于它们混合组合的因子数。因此，为了使得乘积最小，我们需要尽量将数量最多的 $ (2,3) $ 放在菊花图的中心节点。

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
const int N=1e5+100;
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
int qpow(int a, int n) {
    int ans = 1;
    while (n) {
        if (n & 1) {
            ans = ans * a % mod;
        }
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}
int c[30];
void init()
{
    for(int i=1;i<=27;i++)
    {
        for(int j=1;j<=i;j++)
        {
            if(i%j==0)c[i]++;
        }
    }
}
    int n,k;
signed main() {
    ios;
    init();
    cin>>n>>k;
    int ans=1;
    if(k>=n-k)//2放在中间
    {
        ans=(ans*qpow(c[4],(k-1)))%mod;// 2 2
        ans=(ans*qpow(c[6],(n-k)))%mod;//2  3
        //长度为2的路径
        ans=(ans*qpow(c[8],(k-2)*(k-1)/2))%mod;//2 2 2
        ans=(ans*qpow(c[12],(k-1)*(n-k)))%mod;//2 2 3
        ans=(ans*qpow(c[18],(n-k)*(n-k-1)/2))%mod;//2 3 3
        //长度为3的路径
        cout<<ans<<endl;
    }
    else{//3放在中间
        ans=(ans*qpow(c[9],(n-k-1)))%mod;//3 3
        ans=(ans*qpow(c[6],k))%mod;//2 3
        //长度为2的路径
        ans=(ans*qpow(c[27],(n-k-2)*(n-k-1)/2))%mod;//3 3 3
        ans=(ans*qpow(c[12],(k-1)*k/2))%mod;//2 2 3
        ans=(ans*qpow(c[18],k*(n-k-1)))%mod;//2 3 3
       //长度为3的路径
        cout<<ans<<endl;
    }
    return 0;
}