Kyooma's Blog

2023牛客多校03

  • ~18.99K 字

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

Solved Rank A B C D E F G H I J K
5 / 11 117 / 1507 O O - O Ø - Ø O Ø O -

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

A - World Fragments I

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int N=2e5+10;
const int M=1e7+10;
void kaibai(){
    string s,t;
    cin >> s >> t;
    ll x = 0, y = 0;
    for(char i : s){
        x = x * 2 + i - '0';
    }
    for(char i : t){
        y = y * 2 + i - '0';
    }
    if(x == y){
        cout << "0\n";
    }else if(x){
        cout << abs(x - y) << '\n';
    }else{
        cout << "-1\n";
    }
}
int main(void){
    int T=1;
    ios::sync_with_stdio(0);
//    cin>>T;
    while(T--){
        kaibai();
    }
}

B - Auspiciousness

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
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int N=3e2+10;
const int M=1e7+10;
ll C[N][N];
ll fac[N*2];
ll p;
//ll po(ll x,ll y){
//    ll b=1;
//    while(y){
//        if(y&1) b=b*x%p;
//        y>>=1;
//        x=x*x%p;
//    }
//    return b;
//}
void init(){
    C[0][0]=1;
    int i,j,n=300;
    for(i=1;i<=n;i++){
        C[i][0]=1;
        for(j=1;j<=n;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
    }
    fac[0]=1;
    for(i=1;i<=2*n;i++) fac[i]=fac[i-1]*i%p;
//    inv[n]=po(fac[n],p-2);
//    for(i=n;i;i--) inv[i-1]=inv[i]*i%p;
}
ll dp[N][N][2];
void kaibai(){
    ll n,i,j,z,k;
    cin>>n>>p;
    init();
    memset(dp,0,sizeof(dp));
    ll ans=0;
    dp[0][0][0]=dp[0][0][1]=1;
    for(i=0;i<=n;i++){
        for(j=0;j<=n;j++){
//            for(k=1;k<=n-i;k++) dp[i+k][j][1]=(dp[i+k][j][1]+C[n-i][k]*dp[i][j][0])%p;
//            for(k=1;k<=n-j;k++) dp[i][j+k][0]=(dp[i][j+k][0]+C[n-j][k]*dp[i][j][1])%p;
            for(k=1;k<=n-i;k++){
                dp[i+k][j][1]=(dp[i+k][j][1]+C[n-i][k]*dp[i][j][0])%p;
                if(k>1) ans=(ans+C[n-i][k]*dp[i][j][0]%p*(k-1)%p*fac[2*n-i-j-k]%p*(i+j+k))%p;
            }
            for(k=1;k<=n-j;k++){
                dp[i][j+k][0]=(dp[i][j+k][0]+C[n-j][k]*dp[i][j][1])%p;
                if(k>1) ans=(ans+C[n-j][k]*dp[i][j][1]%p*(k-1)%p*fac[2*n-i-j-k]%p*(i+j+k))%p;
            }
//            printf("%lld %lld:%lld %lld\n",i,j,dp[i][j][0],dp[i][j][1]);
        }
    }
    ans=(ans+(dp[n][n][0]+dp[n][n][1])*2*n)%p;
//    for(i=0;i<=n;i++){
//        for(j=0;j<=n;j++){
//            if(!i&&!j) continue;
//            ans=(ans+(dp[i][j][0]+dp[i][j][1])*fac[2*n-i-j]%p*(i+j))%p;
//        }
//    }
    printf("%lld\n",ans);
}
int main(void){
    int T=1;
//    ios::sync_with_stdio(0);
    cin>>T;
//    init();
    while(T--){
        kaibai();
    }
}
/*
3
1 1000000
2 1000000
3 1000000

 4
84
3084
 0 0:1 1
0 1:2 0
0 2:1 0
1 0:0 2
1 1:4 4
1 2:6 2
2 0:0 1
2 1:2 6
2 2:7 7
74
 */

D - Ama no Jaku

SOLUTION

可以发现有解一定只有全0和全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
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int N=2e5+10;
const int M=1e7+10;
void kaibai(){
    int n;
    cin >> n;
    map<string, int> mp;
    string s;
    for(int i = 0; i < n; i++){
        cin >> s;
        mp[s]++;
    }
    if(mp.size() > 2){
        cout << "-1\n";
    }else{
        int ans = n * 2;
        string re, e;
        for(auto i : mp){
            if(re.empty()){
                re = i.first;
            }else if(e.empty()){
                e = i.first;
            }
            int res = n - i.second, cnt = 0;
            for(char j : i.first){
                if(j == '1') cnt++;
            }
            res += min(cnt, n - cnt);
            ans = min(ans, res);
        }
        for(char &i : re){
            if(i == '1'){
                i = '0';
            }else{
                i = '1';
            }
        }
        if(re != e && !e.empty()){
            cout << "-1\n";
            return;
        }
        cout << ans << '\n';
    }
}
int main(void){
    int T=1;
    ios::sync_with_stdio(0);
//    cin>>T;
    while(T--){
        kaibai();
    }
}

G - Beautiful Matrix

SOLUTION

枚举中心点，二分边长，用hash判断相等。然后再卡卡常

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 2000 + 10, Log = 20, inf = 0x3f3f3f3f;
const int mod[2] = {1000000007, 1000000009}, base[2] = {131, 251};

#define gc()(is==it?it=(is=in)+fread(in,1,Q,stdin),(is==it?EOF:*is++):*is++)
const int Q=(1<<24)+1;
char in[Q],*is=in,*it=in,c;
void read(long long &n){
	for(n=0;(c=gc())<'0'||c>'9';);
	for(;c<='9'&&c>='0';c=gc())n=n*10+c-48;
}

void read(int &n){
	for(n=0;(c=gc())<'0'||c>'9';);
	for(;c<='9'&&c>='0';c=gc())n=n*10+c-48;
}

void read(char &n){
	for(;(c=gc())<'a'||c>'z';);
	n = c;
}

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


ll hs[N][N][2], sh[N][N][2], pw[N * N][2];
char ch[N][N], re[N][N];
int n, m;

void RE(int &x, int &y){
    x = n - x + 1;
    y = m - y + 1;
}

ll geths(int lx, int ly, int rx, int ry, int p){
    ll res = hs[rx][ry][p] - hs[lx - 1][ry][p];
    if(res < 0) res += mod[p];
    res -= hs[rx][ly - 1][p];
    if(res < 0) res += mod[p];
    res += hs[lx - 1][ly - 1][p];
    if(res >= mod[p]) res -= mod[p];
    return res;
}

pll geths(int lx, int ly, int rx, int ry){
    ll a = geths(lx, ly, rx, ry, 0);
    ll b = geths(lx, ly, rx, ry, 1);
    return {a, b};
}

ll getsh(int lx, int ly, int rx, int ry, int p){
    ll res = sh[rx][ry][p] - sh[lx - 1][ry][p];
    if(res < 0) res += mod[p];
    res -= sh[rx][ly - 1][p];
    if(res < 0) res += mod[p];
    res += sh[lx - 1][ly - 1][p];
    if(res >= mod[p]) res -= mod[p];
    return res;
}

pll getsh(int lx, int ly, int rx, int ry){
    ll a = getsh(lx, ly, rx, ry, 0);
    ll b = getsh(lx, ly, rx, ry, 1);
    return {a, b};
}

bool calc(int lx, int ly, int rx, int ry){
    pll a = geths(lx, ly, rx, ry);
    int k = (lx - 1) * m + ly;
    // dbg(lx, ly, rx, ry);
    RE(lx, ly);RE(rx, ry);
    swap(lx, rx);swap(ly, ry);
    // dbg(lx, ly, rx, ry);
    k = (lx - 1) * m + ly - k;
    // dbg(k);
    pll b = getsh(lx, ly, rx, ry);
    if(k >= 0){
        a = a * pll{pw[k][0], pw[k][1]};
    }else{
        b = b * pll{pw[-k][0], pw[-k][1]};
    }
    // dbg(a.first, a.second);
    // dbg(b.first, b.second);
    return a == b;
}

void updhs(int i, int j, int a, int p){
    hs[i][j][p] = hs[i - 1][j][p] + hs[i][j - 1][p];
    if(hs[i][j][p] >= mod[p]) hs[i][j][p] -= mod[p];
    hs[i][j][p] -= hs[i - 1][j - 1][p];
    if(hs[i][j][p] < 0) hs[i][j][p] += mod[p];
    hs[i][j][p] += pw[(i - 1) * m + j][p] * a % mod[p];
    if(hs[i][j][p] >= mod[p]) hs[i][j][p] -= mod[p];
}

void updsh(int i, int j, int a, int p){
    sh[i][j][p] = sh[i - 1][j][p] + sh[i][j - 1][p];
    if(sh[i][j][p] >= mod[p]) sh[i][j][p] -= mod[p];
    sh[i][j][p] -= sh[i - 1][j - 1][p];
    if(sh[i][j][p] < 0) sh[i][j][p] += mod[p];
    sh[i][j][p] += pw[(i - 1) * m + j][p] * a % mod[p];
    if(sh[i][j][p] >= mod[p]) sh[i][j][p] -= mod[p];
}

void solve() {
    cin >> n >> m;
    // read(n);read(m);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> ch[i][j];
            // read(ch[i][j]);
            re[n - i + 1][m - j + 1] = ch[i][j];
            int a = ch[i][j] - 'a' + 1;
            updhs(i, j, a, 0);
            updhs(i, j, a, 1);
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            int a = re[i][j] - 'a' + 1;
            updsh(i, j, a, 0);
            updsh(i, j, a, 1);
        }
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            int l = 1, r = min({i, j, n - i + 1, m - j + 1});
            while(l <= r){
                int mid = (l + r) >> 1;
                if(calc(i - mid + 1, j - mid + 1, i + mid - 1, j + mid - 1)){
                    l = mid + 1;
                }else{
                    r = mid - 1;
                }
            }
            // dbg(i, j, r);
            ans += r;
            l = 1, r = min({i, j, n - i, m - j});
            while(l <= r){
                int mid = (l + r) >> 1;
                if(calc(i - mid + 1, j - mid + 1, i + mid, j + mid)){
                    l = mid + 1;
                }else{
                    r = mid - 1;
                }
            }
            // dbg(i, j, r);
            ans += r;
        }
    }
    cout << ans << '\n';
}

int main() {
    int T = 1;
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    // cin >> T;
    pw[0][0] = pw[0][1] = 1;
    for(int i = 1; i <= 4000000; i++){
        pw[i][0] = pw[i - 1][0] * base[0] % mod[0];
        pw[i][1] = pw[i - 1][1] * base[1] % mod[1];
    }
    while (T--) solve();
    return 0;
}

H - Until the Blue Moon Rises

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int N=1e3+10;
const int M=1e7+10;
void kaibai(){
    ll n,i,x=0,y,ans=0;
    cin>>n;
    for(i=1;i<=n;i++){
        scanf("%lld",&y);
        x+=y;
    }
    if(n==1){
        if(x==1){
            puts("No");
            return;
        }
        for(i=2;i*i<=x;i++){
            if(x%i==0){
                puts("No");
                return;
            }
        }
        puts("Yes");
        return;
    }
    if(n==2){
        if(x<4){
            puts("No");
            return;
        }
        if(x%2==0){
            puts("Yes");
            return;
        }
        x-=2;
        for(i=2;i*i<=x;i++){
            if(x%i==0){
                puts("No");
                return;
            }
        }
        puts("Yes");
        return;
    }
    x=x-(n-3)*2;
    if(x>5){
        puts("Yes");
        return;
    }
    puts("No");
//    for(i=2;i*i<=x;i++){
//        if(i*i==x){
//            puts("Yes");
//            return;
//        }
//    }

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

I - To the Colors of the Dreams of Electric Sheep

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
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int N = 5e5 + 10, Log = 20, inf = 0x3f3f3f3f;
int anc[N][Log + 5], depth[N];
int ancc[N][Log + 5];
ll color[N][Log + 5], a[N];
vector<int> e[N];

void dfs(int u, int fa) {
    anc[u][0] = fa;
    color[u][0] = a[u];
    depth[u] = depth[fa] + 1;
    for (int i : e[u]) {
        if(i == fa) continue;
        dfs(i, u);
    }
}

void init(int root, int n) {//初始化
    depth[0] = 0;
    dfs(root, 0);
    for (int j = 1; j <= Log; j++) {
        for (int i = 1; i <= n; i++) {
            int fa = anc[i][j - 1];
            anc[i][j] = anc[fa][j - 1];
            color[i][j] = color[i][j - 1] & color[fa][j - 1];
        }
    }
    for(int i = 1; i <= n; i++){
        int fa = i;
        ll col = a[fa];
        for(int j = Log; j >= 0; j--){
            if(color[fa][j] & col & a[anc[fa][j]]){
                col &= color[fa][j];
                fa = anc[fa][j];
            }
        }
        // dbg(i, fa);
        ancc[i][0] = fa;
    }
    for (int j = 1; j <= Log; j++) {
        for (int i = 1; i <= n; i++) {
            int fa = ancc[i][j - 1];
            ancc[i][j] = ancc[fa][j - 1];
        }
    }
}

int rush(int u, int h) {
    for (int i = 0; i <= Log; i++) {
        if (h >> i & 1) u = anc[u][i];
    }
    return u;
}

int qry(int x, int y) {// 求x和y的lca
    if (depth[x] < depth[y]) swap(x, y);
    x = rush(x, depth[x] - depth[y]);
    if (x == y) return x;
    for (int i = Log; i >= 0; i--) {
        if (anc[x][i] != anc[y][i]) {
            x = anc[x][i];
            y = anc[y][i];
        }
    }
    return anc[x][0];
}

pair<int, ll> calc(int u, int fa){
    // dbg(u, fa);
    int res = 0;
    for(int i = Log; i >= 0; i--){
        if(depth[ancc[u][i]] > depth[fa]){
            u = ancc[u][i];
            res += (1 << i);
        }
    }
    ll col = a[fa];
    // dbg(u, res);
    int h = depth[u] - depth[fa];
    for(int i = Log; i >= 0; i--){
        if(h >> i & 1){
            col &= color[u][i];
            u = anc[u][i];
        }
    }
    return {res, col};
}

int gao(int u, int v){
    int lca = qry(u, v);
    int res = depth[u] + depth[v] - depth[lca] * 2;
    auto [r1, c1] = calc(u, lca);
    auto [r2, c2] = calc(v, lca);
    // dbg(c1, c2);
    if((c1 & c2) == 0) res++;
    res += r1 + r2;
    return res;
}

struct DSU {
    int fa[N];

    void init(int n) {
        for (int i = 0; i <= n; i++) fa[i] = i;
    }

    int find(int x) {
        return x == fa[x] ? x : fa[x] = find(fa[x]);
    }

    void merge(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            fa[fx] = fy;
        }
    }
}dsu;

void solve() {
    int n, m;
    cin >> n >> m;
    dsu.init(n);
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1, u, v; i < n; i++){
        cin >> u >> v;
        if(a[u] & a[v]) dsu.merge(u, v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    init(1, n);
    while(m--){
        int u, v;
        cin >> u >> v;
        if(dsu.find(u) != dsu.find(v)){
            cout << "-1\n";
        }else{
            cout << gao(u, v) << '\n';   
        }
    }
}

int main() {
    int T = 1;
    ios::sync_with_stdio(false);
    // cin >> T;
    while (T--) solve();
    return 0;
}

J - Fine Logic

SOLUTION

签到题，判断图是否是dag，如果是则输出拓扑序，否则正序和逆序输出 $1$ 到 $n$ 。

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;
typedef pair<int,int>pii;
const int N=1e6+10;
const int M=1e7+10;
vector<int> e[N];
int du[N];
void kaibai(){
    int n, m;
    cin >> n >> m;
    for(int i = 0, u, v; i < m; i++){
        cin >> u >> v;
        e[u].push_back(v);
        du[v]++;
    }
    queue<int> q;
    for(int i = 1; i <= n; i++){
        if(!du[i]) q.push(i);
    }
    vector<int> ans;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        ans.push_back(u);
        for(int v : e[u]){
            du[v]--;
            if(!du[v]) q.push(v);
        }
    }
    if(ans.size() == n){
        cout << "1\n";
        for(int i : ans) cout << i << ' ';
        cout << '\n';
    }else{
        cout << "2\n";
        for(int i = 1; i <= n; i++) cout << i << ' ';
        cout << '\n';
        for(int i = n; i >= 1; i--) cout << i << ' ';
        cout << '\n';
    }
}
int main(void){
    int T=1;
    ios::sync_with_stdio(0);
//    cin>>T;
    while(T--){
        kaibai();
    }
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可