牛客暑期多校训练营2
发表于：2023-07-26 | 分类： 思维
字数统计: 2.4k | 阅读时长: 11分钟 | 阅读量：

更新至E,I,K,F,D…

题E

题意：题目给定一个 xx, 要求我们找出一个 yy 要求满足 y210k=x\frac{y^2}{10^k} = x， 其中 kk 可以为任意数，例如 y=123,x=1512y = 123, x = 1512, (其中 y210k=15129101=1512=x\frac{y^2}{10^k} = \frac{15129}{10^1}=1512= x。其中 1<=x,y<=1e91<=x,y<=1e9)。

解：由于要求 y2y^2 的前几位数有 xx， 那么显然我们可以对 xx 后面加若干个 00，使得其 sqrt()sqrt() 满足 yy 的平方并逼近答案。枚举加 00 的个数即可。
(tips : 这里注意 sqrt()sqrt() 的精度问题， 需要同时判断 sqrt()sqrt() 和 sqrt()+1sqrt() + 1, 我多加了个sqrt()−1sqrt() - 1 就一直wawawa。)

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
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define pb(x) push_back(x)
#define PII pair<int, int>
#define int long long
#define ll long long
using namespace std;
const int N = 2e5 + 10, MOD = 1e9 + 7;
string get(ll x){
    string s = "";
    while(x){
        char c = x % 10 + '0';
        s = c + s;
        x /= 10;
    }
    return s;
}
bool ok(int k, int n){
    string s = get(k * k);
    int ans = 0;
    string ss = get(n); int len = ss.size();
    for(int i = 0; i < len; ++ i){
        ans = ans * 10 + (s[i] - '0');
    }
    if(ans == n) return 1;
    return 0;
}
void solve(){
    ll n; cin >> n;
    ll m = n;
    while(n <= 1e18){
        ll k = sqrt(n);
        if(ok(k, m)) {cout << k << '\n'; return ;}
        if(ok(k + 1, m)) {cout << k + 1<< '\n'; return ;}
        n *= 10;
    }
    cout << -1 << '\n';
}
signed main(){
    //ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    while(n--) solve();
    return 0;
}

题I

题意：两人轮流玩棋盘大小为 n∗mn * m 的五子棋，要求构造一个平局的情况，其中先手为 ′x′'x', 另一个人为 ′o′'o' ，（1<=n,m<=10001 <= n, m <= 1000）。

解：首先可以构造这样的局面

1
2
3
4
5
6
xoxoxoxoxo...
oxoxoxoxox...
xoxoxoxoxo...
oxoxoxoxox...
xoxoxoxoxo...
oxoxoxoxox...

此时只会出现斜对角五着连线， 这时将每三行的二三行对换，形成如下局面

1
2
3
4
5
6
xoxoxoxoxo...
xoxoxoxoxo...
oxoxoxoxox...
oxoxoxoxox...
oxoxoxoxox...
xoxoxoxoxo...

这时候如果我们直接输出 n∗mn * m, ′x′'x' 和 ′o′'o' 的差值会有 00、11 和 22 两种情况， 由于 ′x′'x' 是先手，所以多一个无妨，除此以外，对于其他不相等的情况修改一步棋即可。

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>
#define all(x) x.begin(),x.end()
#define pb(x) push_back(x)
#define PII pair<int, int>
#define ll long long
using namespace std;
const int N = 2e3 + 10;
char s[N][N];
void solve(){
    int n, m; cin >> n >> m;
    int a = 0, b = 0;
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= m; ++ j){
            if(s[i][j] == 'x') a ++;
            else b ++;
        }
    }
    if(b > a) s[3][1] = 'x';
    else if(a > b + 1) s[1][1] = 'o';
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= m; ++ j){
            cout << s[i][j];
        }
        cout << '\n';
    }
    if(b > a) s[3][1] = 'o';
    else if(a > b + 1) s[1][1] = 'x';
}
int main(){
    //ios::sync_with_stdio(0); cin.tie(0);
    for(int i = 1; i <= N - 10; ++ i){
        for(int j = 1; j <= N - 10; ++ j){
            if((i + j) & 1) s[i][j] = 'o';
            else s[i][j] = 'x';
        }
    }
    for(int i = 3; i <= N - 10; i += 3) swap(s[i], s[i - 1]);
    int n; cin >> n;
    while(n--) solve();
    return 0;
}

题K

题意：有长度 nn 的数组 aa 和 bb, 其中 aia_i 表示一个盒子里的分数， bib_i 表示盒子有没有盖子，这里 bib_i用 00 和 11 表示有没有盖子。 对于每一个盖子，我们可以将其左移或右移一个单位，也可以不移动。求我们可以获得的最大分数是多少（0<=ai1e90 <= a_i 1e9 , 0<=bi<=10 <= b_i <= 1）。

解：我们用 dp[i][1/2/3]dp[i][1/2/3] 分别表示前 ii 个 boxbox 及当前盖子的 左移/不动/右移左移/不动/右移 三种状态。

可以理解当前 ii 位置有盖子时，如果我们将其左移，那么左边那个位置原本就是没有盖子的，也就是对前面的 dp[i−1][1]dp[i - 1][1] 进行状态转移dp[i][1]=dp[i−1][1]+a[i−1];dp[i][1] = dp[i - 1][1] + a[i - 1]; ，另外两种状态依此类推。
当此位置没有盖子时，我们考虑将空盖子左移时是对前一个没有影响的情况，即 dp[i−1][1]dp[i - 1][1] 和 dp[i−1][2]dp[i - 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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1 << 30
const int N = 1e6 + 10;
int a[N], b[N];
ll dp[N][4];
int main(){
    int n; cin >> n;
    for(int i = 1; i <= n; ++ i) cin >> a[i];
    for(int i = 1; i <= n; ++ i) cin >> b[i];
    for(int i = 1; i <= n; ++ i){
        if(b[i]){
            dp[i][1] = dp[i - 1][1] + a[i - 1];
            dp[i][2] = max(dp[i - 1][1], dp[i - 1][2]) + a[i];
            dp[i][3] = max({dp[i - 1][1], dp[i - 1][2], dp[i - 1][3]}) + a[i + 1];
        }else {
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][2] = max({dp[i - 1][1], dp[i - 1][2], dp[i - 1][3]});
        }
    }
    cout << max({dp[n][1], dp[n][2], dp[n][3]});
}

(擦擦擦擦，我开始将连续盖子分块，然后取最小的1/2/31/2/3个罐子扔了，然后模拟了两个小时还是通过0.270.27，心态整崩了、、、)

题F

题意：给定一个 nn，表示有一个长度为 nn 的链，其中结点下标为 1<=i<=n1<=i<=n，且每个相邻的结点差值为 11，题目给定 R、G、BR、G、B 三种颜色的初始位置下标， AA 和 BB 二人轮流操作，每次移动一个颜色到一个相邻的结点，当一个人移动后三种颜色的坐标 (R,G,B)(R,G,B) 重复出现时 loselose。

解：因为每次操作仅能使得一个颜色的 +1+1 或 −1-1， 我们可以构造一个边长为 nn 的正方体，当且仅当棋子走到走过的位置点时 loselose，这里联系到二分图博弈模型：当且仅当起始点位于最大匹配上时先手必胜。
当 nn 为偶数时，任何起始点开始走完所有点时都是先手必胜。
当 nn 为奇数时，当 (R,G,B)(R,G,B) 三点坐标和为奇数时，无法走完全部的点，此时先手必败。 反之坐标和为偶数时能在奇数步内走完全部点， 先手必胜。

1
2
3
4
5
6
7
8
9
10
11
12
#include<iostream>
using namespace std;
int main(){
    int T; cin >> T;
    while(T --){
        int n, a, b, c; cin >> n >> a >> b >> c;
        if(n & 1){
            if((a + b + c) & 1) cout << "Bob\n";
            else cout << "Alice\n";
        }else cout << "Alice\n";
    }
}

题D

题意：共有 nn 个人，mm 道菜，nn 个人要轮流共点 kk 道菜。每个人对每道菜的满意度不同，给定 n∗mn*m 个满意度，如何选菜使得总满意度最大
（1<=n<=20001<=n<=2000,1<=k<=m<=20001<=k<=m<=2000,1<=Ai,j(满意度)<=1e91<=A_{i,j}(满意度)<=1e9，每个菜最多点一次，升序输出答案）。

解：如果从前往后贪心，对当前的人来说后面的人可能选择自己最喜欢的菜，所以他应该选择后面的人没选过的菜中自己最喜欢的。因此我们倒着选菜，每个人选择自己最喜欢的菜，这样对于正序的某个人 ii 来说，自己应该选择除去 k−(i+1)k-(i+1) 个菜之后自己最喜欢的菜，n,mn,m 的范围不超过 20002000, O(n∗m)O(n * m) 暴力即可。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1 << 30
const int N = 2e3 + 10;
int a[N][N], st[N];
void solve(){
    int n, m, k; cin >> n >> m >> k;
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= m; ++ j){
            cin >> a[i][j];
        }
    }
    for(int i = 1; i <= m; ++ i) st[i] = 0;
    vector<int> ans;
    for(int i = k - 1; i >= 0; -- i){
        int x = i % n + 1, k = -1;
        for(int j = 1; j <= m; ++ j){
            if(st[j]) continue;
            if(k == -1 || a[x][j] > a[x][k]) k = j;
        }
        st[k] = 1; ans.push_back(k);
    }
    sort(ans.begin(), ans.end());
    for(auto i: ans) cout << i << ' ';
    cout << '\n';
}
int main(){
    int T; cin >> T;
    while(T --) solve();
}

题G

题意：给定一个字符串 ss， 判断其是否为对称字符串 SS， 其中 SS 的定义如下

1
2
3
1、S是空字符串。
2、S由'o','s','x','z'等若干个组成。
3、S由若干个形如bSq,dSp,qSb,nSu,uSn,oSo...组成

若干个 SS 直接拼接在一起也为 SS。

解：马拉车，会了再写。

模拟 动态规划 Nim游戏 马拉车
上一篇:
牛客暑期多校训练营3
下一篇:
牛客暑期多校训练营1

    • Copyright © 2019 - 2020 yuang01 | Powered by Hexo | Theme Bamboo