Kyooma's Blog

2023牛客多校05

  • ~14.69K 字

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

Solved Rank A B C D E F G H I J
5 / 10 214 / 1475 Ø Ø O O O - O O Ø -
  • Ø 赛后通过
  • O 在比赛中通过
  • ! 尝试了但是失败了
  • - 没有尝试

A - Jujubesister

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
#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 unit = 700;
int a[N], cnt[N], c[N];
 
template <typename T>
struct Fenwick {
    const int n;
    vector<T> a;
    Fenwick(int n) : n(n), a(n + 1) {}
    void add(int x, T v) {
        while(x <= n){
            a[x] += v;
            x += x & -x;
        }
    }
    T sum(int x) {
        T ans = 0;
        for (int i = x; i; i -= i & -i) {
            ans += a[i];
        }
        return ans;
    }
    T rangeSum(int l, int r) {
        return sum(r) - sum(l - 1);
    }
};

struct node {
    int l, r, id;
 
    bool operator < (const node &k) const {
        if (l / unit != k.l / unit) return l / unit < k.l / unit;
        return r < k.r;
    }
} q[N];

ll sum[N], res, ans[N];

void add(int i) {
    int u = a[i];
    res += abs(sum[u] - 1ll * cnt[u] * c[i]);
    sum[u] += c[i];
    cnt[u]++;
}

void sub(int i) {
    int u = a[i];
    sum[u] -= c[i];
    cnt[u]--;
    res -= abs(1ll * cnt[u] * c[i] - sum[u]);
}

void solve() {
    int n, m;
    cin >> n >> m;
    Fenwick<int> fen(n);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        c[i] = fen.sum(a[i] - 1);
        fen.add(a[i], 1);
    }
    for(int i = 1; i <= m; i++){
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }
	sort(q + 1, q + 1 + m);
    int L = 1, R = 0;
    for (int i = 1; i <= m; i++) {
        while (R < q[i].r) {
            R++;
            add(R);
        }
        while (R > q[i].r) {
            sub(R);
            R--;
        }
        while (L > q[i].l) {
            L--;
            add(L);
        }
        while (L < q[i].l) {
            sub(L);
            L++;
        }
        ans[q[i].id] = res;
    }
    for(int i = 1; i <= m; i++) cout << ans[i] << '\n';
}

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

B - Circle of Mistery

SOLUTION

难点在于发现扔掉一个点不选对逆序对个数带来的贡献是2。之后贪心即可。

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

using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 10, inf = 0x3f3f3f3f;

int a[N];

void solve(){
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    int ans = inf;
    for(int l = 1; l <= n; l++){
        int res = a[l];
        if(res >= k){
            ans = min(ans, 0);
        }
        priority_queue<int> q;
        for(int r = l + 1; r <= n; r++){
            while(!q.empty() && res + a[r] + q.top() >= k){
                res += q.top();
                q.pop();
            }
            if(res + a[r] >= k){
                ans = min(ans, r - l + (int)q.size());
            }
            if(a[r] >= 0) res += a[r];
            else q.push(a[r]);
        }
    }
    if(ans == inf) ans = -1;
    cout << ans << '\n';
}

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

C - Cheeeeen the Cute Cat

SOLUTION

若 $e_{ij}$ 有边，则由 $i$ 向 $j$ 建一条有向边，那么题目就变成了对一张无向满图中的边定向，若存在某个scc的大小为1，则答案为 $n - 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
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>

using namespace std;
const int N=1e5+10;

vector<int> e[N];
int low[N], dfn[N], tot, sta[N], top;
int ok, in[N];

void tarjan(int u){
    low[u] = dfn[u] = ++tot;
    sta[++top] = u;
    in[u] = 1;
    int x;
    for(int v :e[u]){
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[v], low[u]);
        } else if (in[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(dfn[u] == low[u]){
        int cnt = 0;
        do{
            x = sta[top--];
            in[x] = 0;
            cnt++;
        }while(x != u);
        if(cnt == 1) ok = 1;
    }
}

void solve(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1, x; j <= n; j++){
            cin >> x;
            if(x == 1){
                e[i].push_back(j);
            }
        }
    }
    int ans = n;
    for(int i = 1; i <= n; i++){
        if(!dfn[i]){
            tarjan(i);
        }
    }
    cout << ans - ok << '\n';
}

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

D - Cirno’s Perfect Equation Class

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

using namespace std;

void solve(){
	int k, n, c;
	cin >> k >> c >> n;
	int ans = 0;
	for(int i = 1; i * i <= c; i++){
		if(c % i == 0){
			int ka = c - i;
			if(ka % k == 0){
				int a = ka / k;
				if(a > 0 && __gcd(a, i) >= n){
					ans++;
				}
			}
			if(c / i != i){
				int kka = c - (c / i);
				if(kka % k == 0){
					int a = kka / k;
					if(a > 0 && __gcd(a, c / i) >= n){
						ans++;
					}
				}	
			}
		}
	}
	cout << ans << '\n';
}

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

E - Red and Blue and Green

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

using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 10;

struct node{
	int x, tp, w, y, id;
	bool operator < (const node &p) const{
		if(x == p.x){
			if(tp != p.tp) return tp < p.tp;
			if(tp == p.tp){
				return y > p.y;
			}
		}
		return x < p.x;
	}
}a[N];

int ans[N], ok, pos[N], wi[N];
pii q[N];
vector<int> e[N]; 

void gao(int u, int l, int r, int w){
	int son = 0;
	sort(e[u].begin(), e[u].end(), [&](int x, int y){
		return q[x] < q[y];	
	});
	for(int v : e[u]) son ^= wi[v];
	if(son == w){
		for(int i = l; i <= r; i++){
			if(!ans[i]){
				ans[i] = i;
				pos[i] = i;
			}
		}
		return;
	}
	if(l == r){
		ok = 0;
		return;
	}
	int pt = -1;
	for(int i = l; i <= r; i++){
		if(!ans[i]){
			ans[i] = i;
			pos[i] = i;
			pt = i;
		}
	}
	if(pt == -1){
		if(e[u].size() < 2){
			ok = 0;
			return;
		}
		int mx = 0, mn = 1e6, u0 = e[u][0], u1 = e[u][1];
		for(int i = q[u0].first; i <= q[u0].second; i++){
			mx = max(mx, ans[i]);
		}
		for(int i = q[u1].first; i <= q[u1].second; i++){
			mn = min(mn, ans[i]);
		}
		swap(ans[pos[mx]], ans[pos[mn]]);
		swap(pos[mx], pos[mn]);
		return;
	}
	for(int i = -1; i <= 1; i += 2){
		if(pos[pt + i] >= l && pos[pt + i] <= r){
			swap(ans[pos[pt + i]], ans[pos[pt]]);
			swap(pos[pt + i], pos[pt]);
			return;
		}
	}
	
}

void solve(){
	int n, m, tot = 0;
	ok = 1;
	cin >> n >> m;
	map<pii, int> mp;
	for(int i = 1, l, r, w; i <= m; i++){
		cin >> l >> r >> w;
		wi[i] = w;
		if(!mp.count({l, r})){
			mp[{l, r}] = w;
			q[i] = {l, r};
			a[++tot] = {l, 0, w, r, i};
			a[++tot] = {r, 1, w, l, i};
		}else{
			if(w != mp[{l, r}]) ok = 0;
		}
	}
	sort(a + 1, a + tot + 1);
	vector<node> stk;
	for(int i = 1; i <= tot; i++){
		if(a[i].tp == 0){
			stk.push_back(a[i]);
		}else{
			node lt = stk.back();
			stk.pop_back();
			if(!stk.empty()) {
				int fa = stk.back().id;	
				e[fa].push_back(lt.id);
			}
			gao(lt.id, lt.x, lt.y, lt.w);
		}
	}
	if(!ok){
		cout << "-1\n";
		return;
	}
	for(int i = 1; i <= n; i++){
		if(!ans[i]) ans[i] = i;
		cout << ans[i] << " \n"[i == n];
	}
}

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

G - Go to Play Maimai DX

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;
const int N=1e5+10;
int vis[N];
int a[N];
void solve(){
	int k,n,c,i,j,ans,mn=1e9,cnt=0,x;
	cin>>n>>k;
	for(i=1;i<=n;i++) scanf("%d",a+i);
	int l=1;
	for(i=1;i<=n;i++){
		x=a[i];
		if(x==4){
			vis[x]++;
			if(vis[x]==k) cnt++;
		}
		else{
			vis[x]++;
			if(vis[x]==1) cnt++;
		}
		while(cnt==4){
			x=a[l];
			if(x==4){
				if(vis[x]==k) break;
				vis[x]--;
				l++;
			}
			else{
				if(vis[x]==1) break;
				vis[x]--;
				l++;
			}
		}
		if(cnt==4) mn=min(mn,i-l+1);
	}
	printf("%d",mn);
}

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

H - Nazrin the Greeeeeedy Mouse

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

using namespace std;
const int N=2e2+10;
int a[N],b[N];
int sz[N];
int sta[N];
int dp[N][N][N];
int f[N][N];
void solve(){
	int k,n,m,c,i,j,mn=1e9,x,ans=0,y;
	cin>>n>>m;
	for(i=1;i<=n;i++) scanf("%d%d",a+i,b+i);
	if(m>200){
		for(i=1;i<=m-200;i++) scanf("%d",&x);
		m=200;
		for(i=1;i<=m;i++) scanf("%d",sz+i);
	}
	else{
		for(i=1;i<=m;i++) scanf("%d",sz+i);
	}
	for(i=1;i<=n;i++){
		memset(sta,0,sizeof(sta));
		for(j=i;j<=n;j++){
			for(k=200;k>=a[j];k--){
				sta[k]=max(sta[k],sta[k-a[j]]+b[j]);
			}
			for(k=1;k<=200;k++){
				sta[k]=max(sta[k],sta[k-1]); 
			}
			for(k=0;k<=200;k++){
				dp[i][j][k]=sta[k];
			}
		}
	}
	for(i=1;i<=m;i++){
		for(j=1;j<=n;j++){
			for(k=j;k<=n;k++){
				f[i][k]=max(f[i][k],f[i-1][j-1]+dp[j][k][sz[i]]);
			}
		}
	}
	for(i=1;i<=m;i++){
		for(j=0;j<=n;j++) ans=max(ans,f[i][j]);
	}
	printf("%d",ans);
}

int main(){
	int T = 1;
	while(T--) solve();
	return 0;
}

I - The Yakumo Family

SOLUTION

拆位算贡献，可以参考 这篇博客 。

首先，对于这个问题：，可以记一个异或前缀和（记作 ），那么可以将式子转化为 ，这个式子可以简单拆位之后计算，时间复杂度为 。

接下来对于题目要求的三个不相交区间，我们可以预处理出 以及 ，那么题目的式子可以转化为 ，至此时间复杂度依旧是 的，然后可以考虑枚举 或者 。

以枚举 $r$ 为例，在枚举过程中， 是可以直接获得的，所以先不考虑它，接下来考虑如何求出这个式子： ，而这个式子和第一个问题中的式子类似，将第一个问题中的记录01数量改为记录 值的和即可。

时间复杂度 。

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e5 + 10, Log = 30, mod = 998244353;

int f[2][Log + 5], g[2][Log + 5];

int pre[N], suf[N]; // \sum sr ^ sl-1

int a[N], s[N], rs[N];

void solve() {
    int n;
    cin >> n;
    for(int i = 0; i < Log; i++){
        f[0][i] = g[0][i] = 1;
    }
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        s[i] = s[i - 1] ^ a[i];
        pre[i] = pre[i - 1];
        for(int j = 0; j < Log; j++){
            int u = s[i] >> j & 1;
            pre[i] += (1ll << j) * f[u ^ 1][j] % mod;
            if(pre[i] >= mod) pre[i] -= mod; 
            f[u][j]++;
        }
    }
    for(int i = n; i >= 1; i--){
        rs[i] = rs[i + 1] ^ a[i];
        suf[i] = suf[i + 1];
        for(int j = 0; j < Log; j++){
            int u = rs[i] >> j & 1;
            suf[i] += (1ll << j) * g[u ^ 1][j] % mod;
            if(suf[i] >= mod) suf[i] -= mod; 
            g[u][j]++;
        }
    }
    memset(f, 0, sizeof(f));
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        int res = 0;
        for(int j = 0; j < Log; j++){
            int u = s[i] >> j & 1;
            res += (1ll << j) * f[u ^ 1][j] % mod;
            if(res >= mod) res -= mod;
            f[u][j] += pre[i];
            if(f[u][j] >= mod) f[u][j] -= mod;
        }
        ans += 1ll * res * suf[i + 1] % mod;;
        if(ans >= mod) ans -= mod;
    }
    cout << ans << '\n';
}

int main() {
    int T = 1;
    ios::sync_with_stdio(false);
    // cin >> T;
    while (T--) solve();
    return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可