Butteruni Blog
0%

2023杭电暑期多校2（A B D G I K）

发表于 更新于 分类于

题目链接

由易到难为：IDB，GKA，J

I. String Problem

如题，暴力走一遍即可

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;

int n, m;
int T;
string s;
int ans;
int tot;
bool cmp(int A,int B)
{
    return A>B;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>T;
    while(T--)
    {
        vector<int>vis(30);
        vector<int>ls;
        cin>>s;
        int idx=1;
        s+=" ";
        for(int i=1;i<s.length();i++)
        {
            if(s[i]==s[i-1])idx++;
            else
            {
                ls.push_back(idx);
                idx=1;
            }
        }
        sort(ls.begin(),ls.end(),cmp);
        idx=1;
        ans=0;
        tot=0;
        for(auto x:ls)
        {
            // cout<<x<<" ";
            tot+=x;
            ans=max(ans,tot-idx);
            idx++;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

D. Card Game

用 表式有空堆 个的时候最大的可转移牌数 显然有 接下来考虑 如何从 转移，包括目标堆在内，当剩下 个空堆时，可以从其他堆完整转移 张牌至目标堆，具体操作可看成完成操作 需要最多空堆数为 于是可以将 中的 先放至目标堆，接下来完成 操作。于是

化简后得到 ;

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 <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;
int t;
const ll mod = 998244353;
ll n;
ll qpow(ll a,ll b)
{
    ll res = 1;
    while(b)
    {
        if(b & 1)
            res =res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> t;
    ll st = 1;
    while(t--)
    {
        cin >> n;
        ll ans = qpow(2,n - 1);
        ans -= 1;
        ans = ((ans % mod) + mod) % mod;
        cout << ans << '\n';
    }
    return 0;
}

B. Binary Number

稍微举几个例子就能发现只需要反转全为 的连续区间即为最优，即达成最优的最小操作数为 ，接下来考虑 的情况，如果 ，此时若 ，则可以通过操作使得序列不变小， 则使序列最后一个取反，否则也可通过改变操作使序列不变。故当且仅当 时输出 ，其余输出 最后特判序列长度为 的情况，应为一直只能改变一位，最后输出取决于初值和 的奇偶性。

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
#include <iostream>
#include <string>
#include <vector>
using namespace std;

long long n, k;
string str;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        cin >> n >> k;
        cin >> str;
        vector <int> pos_0;
        bool cont = 0;
        int op = 0;
        if(n == 1)
        {
            if(k % 2 == 0)
            {
                cout << str << '\n';
            }else
            {
                int x = str[0] - '0';
                x ^= 1;
                cout << x << '\n';
            }
            continue;
        }
        for(int i = 0;i < n;++i)
        {
            if(str[i] == '0')
            {
                if(pos_0.size())
                {
                    if(i == pos_0[pos_0.size() - 1] + 1)
                    {
                        cont = 1;
                    }else
                    {
                        op++;
                    }
                }else
                {
                    op++;
                }
                if(op > k)
                    break;
                pos_0.push_back(i);
                str[i] = '1';
            }
        }
        if(op >= k)
        {
            cout << str << '\n';
        }else
        {
            if(pos_0.size())
            {
                cout << str << '\n';
            }else
            {
                if(k == 1)
                {
                    str[str.length() - 1] = '0';
                    cout << str << '\n';
                }else
                {
                    cout << str << '\n';
                }
            }
        }
    }
    return 0;
}

G. foreverlasting and fried-chicken

每次只需要找到公共儿子大于等于 的两个节点，分别以其中一个为头计算可能个数即可，找点的过程可用bitset暴力实现。

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

using i64 = int64_t;
constexpr int N = 1005;
std::bitset<N> bt[N];
constexpr i64 mod = 1e9 + 7;

i64 fpow(i64 x, i64 r)
{
    i64 result = 1;
    while (r)
    {
        if (r & 1)result = result * x % mod;
        r >>= 1;
        x = x * x % mod;
    }
    return result;
}

namespace binom {
    i64 fac[N], ifac[N];
    int __ = []
    {
        fac[0] = 1;
        for (int i = 1; i <= N - 5; i++)
            fac[i] = fac[i - 1] * i % mod;
        ifac[N - 5] = fpow(fac[N - 5], mod - 2);
        for (int i = N - 5; i; i--)
            ifac[i - 1] = ifac[i] * i % mod;
        return 0;
    }();

    inline i64 C(int n, int m)
    {
        if (n < m || m < 0)return 0;
        return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
    }

    inline i64 A(int n, int m)
    {
        if (n < m || m < 0)return 0;
        return fac[n] * ifac[n - m] % mod;
    }
}
using namespace binom;
using namespace std;
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        int n, m;
        std::cin >> n >> m;
        for (int i = 1; i <= n; i++)
            bt[i].reset();
        while (m--)
        {
            int u, v;
            std::cin >> u >> v;
            bt[u][v] = bt[v][u] = 1;
        }
        i64 ans = 0;
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
            {
                int cnt_i = bt[i].count();
                int cnt_j = bt[j].count();
                int cnt = (bt[i] & bt[j]).count();
                if (bt[i][j])
                    cnt_i--, cnt_j--;
                ans = (ans + C(cnt, 4) * C(cnt_i - 4, 2) + C(cnt, 4) * C(cnt_j - 4, 2)) % mod;
            }
        cout << ans << '\n';
    }
    return 0;
}

K. SPY finding NPY

简单概率题，对于 表示先考察前 人选到全局最大值的概率，有 其中 表示第 到 个人为全局最大值的概率， 表示前 个数的最大值落到 区间内个概率（这样才能选到第 个点）。化简得到 用前缀和维护后每个 可以 求得，又由于这图像近似一个二次函数，大概只需要枚举到 即可

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int N = 1e6 + 10;
double inv[N];
double pre[N];
int t;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0); 
    cin >> t;
    for(int i = 1;i <= 100100;++i)
    {
        inv[i] = 1.0 / i;
    }
    for(int i = 1;i <= 100100;++i)
    {
        pre[i] = pre[i - 1] + inv[i];
    }
    while(t--)
    {
        int n;
        cin >> n;
        if(n <= 2)
        {
            cout << 0 << '\n';
        }else 
        {
            double mx_pos = 0;
            int ans = 0;
            for(int i = 1;i <= n;++i)
            {
                double cur_ans = (i / ((1.0) * n)) * (pre[n - 1] - pre[i - 1]);
//                 cout << cur_ans << ' ';
                if(cur_ans > mx_pos)
                {
                    ans = i;
                    mx_pos = cur_ans;
                }else 
                {
                    break;
                }
            }
            cout << ans << endl;
        }
    }
}

A. Alice Game

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> t;
    while(t--)
    {
        ll k,n;
        cin >> k >> n;
        if(n <= k)
        {
            cout << "Alice\n" ;
        }
        else if(n == k + 1)
        {
            cout << "Bob\n";
        }
        else 
        {
            n -= k + 1;
            if(n % (2 * k + 1) == 0 && n / (2 * k + 1) % 2 == 0)
            {
                cout << "Bob" << '\n';
            }else 
            {
                cout << "Alice" << '\n';
            }
        } 
    }
}