Kyooma's Blog

2023牛客多校02

  • ~14.44K 字

题目来自: 2023牛客暑期多校训练营2

Solved Rank A B C D E F G H I J K L M
6 / 13 196 / 1526 - - - O O O Ø O O - O - -

  • Ø 赛后通过
  • O 在比赛中通过
  • ! 尝试了但是失败了
  • - 没有尝试

D - The Game of Eating

SOLUTION

贪心，从后往前就是对的

CODE
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=2e3+10;
int vis[N];
struct node{
    int x,id;
    bool operator <(const node &k)const{
        return k.x<x;
    }
};
vector<node>e[N];
void kaibai(){
    int n,i,j,m,x,y,l,r,mid,ans=0,k;
    cin>>n>>m>>k;
    for(i=1;i<=m;i++) vis[i]=0;
    for(i=1;i<=n;i++){
        e[i].clear();
        for(j=1;j<=m;j++){
            scanf("%d",&x);
            e[i].push_back({x,j});
        }
        sort(e[i].begin(),e[i].end());
    }
    for(i=k;i;i--){
        x=(i-1)%n+1;
        for(auto j:e[x]){
            if(vis[j.id]) continue;
            vis[j.id]=1;
//            printf("%d\n",j.id);
            break;
        }
    }
    for(i=1;i<=m;i++){
        if(vis[i]) printf("%d ",i);
    }
    puts("");
}
int main(void){
    int T=1;
//    ios::sync_with_stdio(0);
    cin>>T;
    while(T--){
        kaibai();
    }
}

E - Square

SOLUTION

签到题

CODE
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;
const int N=2e5+10;
void kaibai(){
    ll d,i,j,x,y,l,r,mid,ans=0,v=1;
    cin>>x;
    while(v<=1e18){
        l=0,r=1e9;
        while(l<=r){
            mid=(l+r)>>1;
            if(mid*mid/v>=x) r=mid-1;
            else l=mid+1;
        }
        if(l>1e9){
            v*=10;
            continue;
        }
        if(l*l/v==x){
            printf("%lld\n",l);
            return;
        }
        v*=10;
    }
    printf("-1\n");
}
int main(void){
    int T=1;
   ios::sync_with_stdio(0);
    cin>>T;
    while(T--){
        kaibai();
    }
}

F - Link with Chess Game

SOLUTION

打表找规律

CODE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e3 + 10;
void kaibai() {
    int n,m,x,y,z;
    cin>>n>>x>>y>>z;
    if      (n%2==0)  printf("Alice\n");
    else if (x+y+z&1) printf("Bob\n")  ;
    else              printf("Alice\n");
}

int main(void) {
    int T = 1;
    ios::sync_with_stdio(0);
    cin >> T;
    while (T--) {
        kaibai();
    }
}

G - Link with Centrally Symmetric Strings

SOLUTION

仔细分析就会发现这是个魔改了匹配规则的求回文串，任意选一种求回文串算法就行。

CODE1

Hash

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 1e6 + 10;
const pii mod = {1e9 + 7, 1e9 + 9};
const pii base = {131, 251};
pll pw[N];

pll operator*(const pll &p1, const pll &p2) {
    return {p1.first * p2.first % mod.first, p1.second * p2.second % mod.second};
}

pll operator+(const pll &p1, const pll &p2) {
    return {(p1.first + p2.first) % mod.first, (p1.second + p2.second) % mod.second};
}

pll operator-(const pll &p1, const pll &p2) {
    return {(p1.first - p2.first + mod.first) % mod.first, (p1.second - p2.second + mod.second) % mod.second};
}

struct Hash {
    vector<pll> f;
    int n{};

    void init(ll ss[], int _n) {
        n = _n;
        f.resize(n + 1, {0, 0});
        for (int i = 1; i <= n; i++) {
            ll ch = ss[i];
            f[i] = f[i - 1] * base + pll{ch, ch};
        }
    }

    pll ask(int l, int r) {//[l, r]
        return f[r] - f[l - 1] * pw[r - l + 1];
    }
}hs, sh;

ll a[N];

map<char, char> mp;

void solve(){
    string s;
    cin >> s;
    int n = s.size();
    for(int i = 1; i <= n; i++){
        a[i] = s[i - 1] - 'a' + 1;
        if(!mp.count(s[i - 1])){
            cout << "No\n";
            return;
        }
        s[i - 1] = mp[s[i - 1]];
    }
    hs.init(a, n);
    reverse(s.begin(), s.end());
    for(int i = 1; i <= n; i++){
        a[i] = s[i - 1] - 'a' + 1;
    }
    sh.init(a, n);
    for(int i = 1; i <= n; i++){
        int j = i, ok = 0;
        while(j <= n){
            if(hs.ask(i, j) == sh.ask(n - j + 1, n - i + 1)){
                ok = 1;
                break;
            }
            j++;
        }
        if(!ok){
            cout << "No\n";
            return;
        }
        i = j;
    }
    cout << "Yes\n";
}

int main(){
    int T = 1;
    ios::sync_with_stdio(false);
    mp['d'] = 'p';
    mp['p'] = 'd';
    mp['b'] = 'q';
    mp['q'] = 'b';
    mp['u'] = 'n';
    mp['n'] = 'u';
    mp['o'] = 'o';
    mp['x'] = 'x';
    mp['s'] = 's';
    mp['z'] = 'z';
    pw[0] = {1, 1};
    for(int i = 1; i <= N - 1; i++) pw[i] = pw[i - 1] * base;
    cin.tie(nullptr);
    cin >> T;
    while(T--) solve();
    return 0;
}
CODE2

Manacher

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
81
82
83
84
85
86
87
88
89
90
91
92
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 4e6 + 10, inf = 0x3f3f3f3f;

map<char, int> mp;

bool jud(int x, int y) {
    if (x >= 7 && y >= 7) return x == y;
    if (x < 7 && y < 7) return x + y == 7;
    return false;
}

int f[N], g[N];
char a[N], s[N];

bool jud(char u, char v){
    if(mp.count(u) && mp.count(v)){
        int res = jud(mp[u], mp[v]);
        return res;
    }
    return u == v;
}

void up(int &x, int b){
    if(x < b) x = b;
}
void Manacher() {
    int n = strlen(a + 1);
    for (int i=1;i<=n;++i) {
        if (!mp.count(a[i])) {
            cout << "No\n";
            return;
        }
    }
    int m;
    for (int i = 1; i <= n; ++i) s[i << 1] = a[i], s[i << 1 | 1] = '#';
    s[0] = '$', s[1] = '#', s[m = (n + 1) << 1] = '@';
    for(int i = 0; i <= m; i++) {
        g[i]=f[i] = 0;
    }
    f[1] = 1;
    for (int r = 0, p = 0, i = 2; i < m; ++i) {
        if (i%2==0&&mp.count(s[i]) && mp[s[i]] < 7 ) {
            continue;
        }
        f[i] = r > i ? min(r - i, f[p*2-i]) : 1;
        for (; jud(s[i - f[i]], s[i + f[i]]); f[i]++);
        if (i + f[i] > r) r = i + f[i], p = i;
    }
    for(int i = 2; i < m; i++){
		up(g[i-f[i]+1],i+1);
    }
    for(int i = 1; i <= m; i++) up(g[i], g[i - 1]);
    for (int i=2;i<m;i+=2) f[i/2]=g[i]-i;
    int now = 1;
    while(now  <= n ){
		if (f[now]==0) {
            cout << "No\n";
            return;
		}
        now = now+f[now];
    }
    assert(now==n+1);
    cout << "Yes\n";
}

char b[N];

void kaibai() {
    scanf("%s", a + 1);
    Manacher();
}

int main(void) {
    int T = 1;
    mp['b'] = 3;
    mp['q'] = 4;
    mp['d'] = 2;
    mp['p'] = 5;
    mp['n'] = 1;
    mp['u'] = 6;
    mp['o'] = 7;
    mp['x'] = 8;
    mp['s'] = 9;
    mp['z'] = 10;
    scanf("%d", &T);
    while (T--) {
        kaibai();
    }
}

H - 0 and 1 in BIT

SOLUTION

假设 $x$ 的二进制串长度为 $k$，那么一次A操作相当于将 $x$ 变为 $2^k - 1 - x$，一次B操作即为 $x = x + 1$，再考虑B操作在A操作前的情况，即 $x = 2^k - 1 - (x + 1)$，也就是B操作由加1变为了减1。于是就能发现B操作对于最终的 $x$ 的贡献为 $1$ 还是 $-1$，取决于这个B操作后的A操作个数的奇偶性，由于题目还需要区间询问，因此可以用线段树维护分开维护加和减的贡献。

CODE
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e5 + 10, inf = 0x3f3f3f3f;

string s;

int a_add, a_sub, cnt;

struct Seg{
    int add[N << 2], sub[N << 2], sum[N << 2];

    void pu(int u){
        add[u] = add[u << 1 | 1];
        sub[u] = sub[u << 1 | 1];
        sum[u] = sum[u << 1 | 1] + sum[u << 1];
        if(sum[u << 1 | 1] & 1){
            add[u] += sub[u << 1];
            sub[u] += add[u << 1];
        }else{
            add[u] += add[u << 1];
            sub[u] += sub[u << 1];
        }
    }

    void build(int u, int l, int r){
        if(l == r){
            if(s[l - 1] == 'A') sum[u] = 1;
            else add[u] = 1;
            sub[u] = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pu(u);
    }

    void qry(int u, int l, int r, int ql, int qr){
        if(r < ql || l > qr) return;
        if(ql <= l && r <= qr){
            cnt += sum[u];
            if(sum[u] & 1){
                swap(a_add, a_sub);
            }
            a_add += add[u];
            a_sub += sub[u];
            return;
        }
        int mid = (l + r) >> 1;
        qry(u << 1, l, mid, ql, qr);
        qry(u << 1 | 1, mid + 1, r, ql, qr);
    }
}seg;

void kaibai() {
    int n, q;
    cin >> n >> q;
    cin >> s;
    seg.build(1, 1, n);
    ll ans = 0;
    while(q--){
        int l, r, len;
        string t;
        cin >> l >> r >> t;
        l = (ans ^ l) % n + 1;
        r = (ans ^ r) % n + 1;
        len = t.size();
        if(l > r) swap(l, r);
        ll x = 0, mx = (1ll << ((int)t.size()));
        for(char i : t){
            x = x * 2 + i - '0';
        }
        a_add = a_sub = cnt = 0;
        seg.qry(1, 1, n, l, r);
        if(cnt & 1) x = (mx - 1) - x;
        x += a_add;
        x -= a_sub;
        x %= mx;
        if(x < 0) x += mx;
        ans = x;
        t = "";
        while(x){
            t += '0' + (x % 2);
            x >>= 1;
        }
        while(t.size() < len) t += '0';
        reverse(t.begin(), t.end());
        cout << t << '\n';
    }
}

int main(void) {
    int T = 1;
    ios::sync_with_stdio(0);
    while (T--) {
        kaibai();
    }
}

I - Link with Gomoku

SOLUTION

签到构造题，感觉乱构造都能过。需要注意的是先手下的棋子个数要等于后手或者比后手多1。

CODE
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;
typedef long long ll;
const int N = 1e3 + 10;
bool ans[N][N];

void kaibai() {
    int n, m, is = 0;
    cin >> n >> m;
    if(~n&1){
        swap(n, m);
        is = 1;
    }
    for(int i = 1; i <= m; i++){
        ans[1][i] = ans[1][i - 1] ^ 1;
    }
    for(int i = 2; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(~i&1) ans[i][j] = ans[i - 1][j];
            else ans[i][j] = ans[i - 1][j] ^ 1;
        }
    }
    if(!is){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(ans[i][j]) cout << "x";
                else cout << "o";
            }
            cout << '\n';
        }
        return;
    }
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            if(ans[j][i]) cout << "x";
            else cout << "o";
        }
        cout << '\n';
    }
}

int main(void) {
    int T = 1;
    ios::sync_with_stdio(0);
    cin >> T;
    while (T--) {
        kaibai();
    }
}

K - Box

SOLUTION

dp

CODE
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;
typedef long long ll;
const int N=1e6+10;
int b[N];
int a[N];
ll dp[N][3];
void kaibai(){
    int n,i,j,x,y,l,r,mid,ans=0,v=1;
    cin>>n;
    for(i=1;i<=n;i++) cin>>a[i];
    for(i=1;i<=n;i++) cin>>b[i];
    for(i=0;i<=n;i++){
        for(j=0;j<3;j++) dp[i][j]=-1e18;
    }
    dp[0][0]=dp[0][1]=0;
    for(i=1;i<=n;i++){
        if(b[i]){
            dp[i][0]=dp[i-1][0]+a[i-1];
            dp[i][1]=max(dp[i-1][0]+a[i],dp[i-1][1]+a[i]);
            dp[i][2]=max(dp[i-1][0],max(dp[i-1][1],dp[i-1][2]+a[i]));
        }
        else{
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
            dp[i][1]=dp[i-1][2]+a[i];
        }
    }
    cout<<max(dp[n][0],max(dp[n][1],dp[n][2]));
}
int main(void){
    int T=1;
    ios::sync_with_stdio(0);
    while(T--){
        kaibai();
    }
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可