Butteruni Blog
0%

2023牛客暑期多校5 （C D G H I）

发表于 更新于 分类于

题目链接

有易到难分别为：GD，C，HEI

G. Go to Play Maimai DX

直接暴力即可

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

using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m;
int a[N];
bool check(int val)
{
    deque<int>q;
    vector<int>vis(10);
    for(int i=1;i<=val;i++)
    {
        vis[a[i]]++;
        q.push_back(a[i]);
    }
    if(vis[4]>=m&&vis[3]&&vis[2]&&vis[1])return true;
    for(int i=val+1;i<=n;i++)
    {
        vis[q.front()]--;
        q.pop_front();
        vis[a[i]]++;
        q.push_back(a[i]);
        if(vis[4]>=m&&vis[3]&&vis[2]&&vis[1])return true;
    }
    return false;
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    int l=1,r=n;
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<<l;
    return 0;
}

D. Cirno's Perfect Equation Class

，暴力枚举所有因数即可

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,k,c,n;
ll gcd(ll a,ll b)
{
    return (!b)?a:gcd(b,a%b);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> t;
    while(t--)
    {
        cin >> k >> c >> n;
        ll ans = 0;
        vector<ll>factor;
        for(ll i = 1;i * i <= c;i++)
        {
            if(c % i == 0)
            {
                factor.push_back(i);
                if(c != i * i)
                    factor.push_back(c / i);
            }
        }
        for(auto x:factor)
        {
//             cout << x << " ";
            ll temp = (c - x) / k;
            if(temp == 0)
                continue;
            if(gcd(temp,x) >= n && temp * k + x == c)
            {
//                 cout << temp << " " << x << "\n";
                ans++;
            }
        }
        cout << ans << "\n";
    }
}

C. Cheeeeen the Cute Cat

试了一下不管是匈牙利还是dinic都会tle，于是

考虑题中 是否存在某种特殊性质，将 看作 后我们得到一个无向完全图即竞赛图，由竞赛图必然存在一条哈密顿路径可知最大匹配至少为 。最大匹配为 当且仅当图中存在哈密顿通路，此时图中强连通分量大小均为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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
const int N = 3010;
int deg[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n;
    cin >> n;
    int ans1 = 0,ans2 = 0;
    for(int i = 1;i <= n;++i)
    {
        for(int j = 1;j <= n;++j)
        {
            int x;
            cin >> x;
            if(x == 1)
            {
                ++deg[i];
            }
        }
    }
    sort(deg+1, deg+1+n);
    int sum = 0;
    for(int i = 1, j = 0; i <= n; ++i)
    {
        sum += deg[i];
        if(sum == i*(i-1)/2)
        {
            if(i - j == 1)
            {
                cout << n-1 << '\n';
                return 0;
            }
            j = i;
        }
    }
    cout << n << '\n';
    return 0;
}

H. Nazrin the Greeeeeedy Mouse

考虑到 不降，实际上只要让最后200个包都拿东西即可，于是 从 变成 ，接下来设计状态转移方程，定义 表示当前到达第 个奶酪，用第 个包，已经用去 空间得到的最大价值。

有

整个过程相当于做 次01背包，由于 只与 有关，空间上可以压掉一维变成 ，时间复杂度 。

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
#include <bits/stdc++.h>
using namespace std;
const int M = 210;
int n,m;
int a[M],b[M];
int dp[210][210];
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) 
    {
        cin >> a[i] >> b[i];
    }
    vector<int> sz(m);
    for (int i = 0; i < m; i++) 
    {
        cin >> sz[i];
    }
    if (m > n) 
    {
        sz.erase(sz.begin(), sz.end() - n);
        m = n;
    }
    
    for (int i = 1; i <= n; i++) 
    {
        for (int j = 0; j < m; j++) 
        {
            for (int k = sz[j]; k >= a[i]; k--) 
            {
                dp[j][k] = max(dp[j][k], dp[j][k - a[i]] + b[i]);
            }
        }
        for (int j = 0; j < m - 1; j++) 
        {
            for (int k = 0; k <= sz[j]; k++) 
            {
                dp[j + 1][0] = max(dp[j + 1][0], dp[j][k]);
            }
        }
    }
    int ans = 0;
    for(int i = 1;i <= 210;++i)
    {
        ans =  max(ans,dp[m - 1][i]);
    }
    cout << ans << '\n';
    return 0;
}

E. Red and Blue and Green

由于本人不会数据结构，所以本题做法比较奇怪。

考虑满足区间 ，若区间内已有子区间 和 满足各自条件，若该情况下能使得 满足条件则跳过，否则交换 ，此时子区间上逆序对奇偶性不变， 内新增逆序对 使得奇偶性改变从而满足条件。考虑到单个元素自身可成为一个独立且 的区间，我们可以对 个要求都采用如上区间分割的操作即可

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
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N = 2e5 + 10;
vector<pii> quest;
int l[N],r[N],w[N],ans[N];
bool vis[N];
int n,m;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= m;++i)
    {
        cin >> l[i] >> r[i] >> w[i];
        quest.push_back(make_pair(r[i] - l[i] + 1,i));
        if(l[i] == r[i] && w[i])
        {
            cout << -1 << '\n';
            return 0;
        }
    }
    sort(quest.begin(),quest.end());
    for(int i = 1;i <= n;++i) //添加每个元素作为满足 w = 0 的独立区间
    {
        m++;
        l[m] = r[m] = i,w[m] = 0; 
    }
    for(int i = 1;i <= n;++i)
        ans[i] = i;
    for(auto cur_quest:quest)
    {
        int ll = l[cur_quest.second],rr = r[cur_quest.second],ww = 0;
        vector<int> son;
        for(int i = 1;i <= m;++i)
        {
            if(!vis[i] && i != cur_quest.second && ll <= l[i] && rr >= r[i])
            {
                son.push_back(i);
                vis[i] = 1;
                ww ^= w[i];
            }
        }
        if(ww != w[cur_quest.second])
        {
            for(auto x : son)
            {
                if(r[x] != rr)
                {
                    int idx1,idx2;
                    for(int i = ll;i <= rr;++i)
                    {
                        if(ans[i] == r[x])
                            idx1 = i;
                        else if(ans[i] == r[x] + 1)
                            idx2 = i;
                    }
                    swap(ans[idx1],ans[idx2]);
                    break;
                }
            }
        }
    }
    for(int i = 1;i <= n;++i)
    {
        cout << ans[i] << " ";
    }
    cout << "\n";
    return 0;
}

I. The Yakumo Family

考虑维护异或后的区间乘法，可以通过判断区间异或和的二进制数上每一位是否为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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
const ll mod = 998244353;
ll a[N];
ll pre[N];
ll sum[35][2];
ll dp[5][N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n;
    cin >> n;
    for(int i = 1;i <= n;++i)
    {
        cin >> a[i];
    }
    for(int i = 1;i <= n;++i)
    {
        pre[i] = pre[i - 1] ^ a[i];
    }
    vector<ll>ans;
    ans.resize(n + 10);
    for(int i = 0;i <= n;++i)
        dp[0][i] = 1;
    for(int t = 1;t <= 3;++t)
    {
        memset(sum,0,sizeof(sum)); //每次清空sum数组
        for(int i = 0;i <= n;++i)
        {
            for(int j = 0 ;j < 30;++j) //1e9开到30位
            {
                dp[t][i] = (sum[j][~pre[i] >> j & 1] * (1 << j) + dp[t][i]) % mod;
            }
            for(int j = 0;j < 30;++j)
            {
                sum[j][pre[i] >> j & 1] = (sum[j][pre[i] >> j & 1] + dp[t - 1][i]) % mod;
            }
        }
        for(int i = 1;i <= n;++i)
        {
            dp[t][i] = (dp[t][i - 1] + dp[t][i]) % mod;
        }
    }
    cout << dp[3][n] << endl;
}