2025重庆市赛部分题目

2025重庆市赛部分题目

题目链接：2025重庆市赛

A

枚举每一位，如果某一位不为0，找到1最少的一位，答案即为这一位全是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
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int n,maxn=0;
    cin >> n;
    vector<int> a(32),b(n*2+1);
    for(int i = 1; i <= n; i++)
    {
        cin>>b[i];
        b[i+n] = b[i];
    }
    for(int i = 1; i <= n*2; i++)
    {
        int x = b[i];
        for(int j=0;j<=31;j++)
        {
            int p=x%2;
            if(x%2==0)
            {
                a[j]++;
                x>>=1;
            }
            else
            {
                if(a[j]==n*2)
                {
                    x>>=1;
                    continue;
                }
                maxn=max(maxn,a[j]);
                a[j]=0;
                x>>=1;
            }
        }
    }
    int ans=0;
    for(int i=1;;i++)
    {
        if(maxn>0)
        {
            maxn-=i;
            ans++;
        }
        else
            break;
    }
    cout << ans << "\n";
}
int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while(T--)
    {
        solve();
    }
    return 0;
}
// 111 110 101 100 011 010 001

B

显然可以网络流建模，由 l 向 r 建 w 的边，在这个范围内建i+1到i的容量为无限大的边，求1到n的最大流。

显然无法暴力求解最大流，由最大流最小割，我们也可以求他的最小割。因为求最小割，我们需要将以一个点为边界分为两个集合，否则就要切容量为正无穷的边。当分为两个集合后，求的即为两个相邻点之间其权值的最小值。

B

显然我们只需要维护区间加减和求区间最小值即可

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
#include <iostream>
#include <iterator>
#include <numeric>
#include <stack>
#include <cmath>
#include <map>
#include <fstream>
#include <queue>
#include <utility>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <cstring>
#include <iomanip>
#include <unordered_map>
#include <limits>
#define ll long long
#define lt __int128
#define ull unsigned long long
#define ld long double
#define vcmp vector<vector<ll> >
#define vec vector<ll>
using namespace std;
ll n, m, q;
ll k;
const ll maxn = 2e6+5, maxm = 2e6+5;
const ll mod = 1e9+7;
// const ll mod = 998244353;
// const ll mod = 19650827;
const ll inf = 1e18;
const ll N = 1e7+100;

//Segment Tree Node
struct Node{
    ll data;
    ll l, r;
    ll lazy;
} t[maxn << 2];

//build the segment tree
void build(ll p, ll l, ll r){
    t[p].l = l;
    t[p].r = r;
    t[p].lazy = 0;
    if(l == r){
        t[p].data = 0;
        return;
    }

    ll mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    t[p].data = min(t[p << 1].data, t[p << 1 | 1].data);
}

//push down the lazy tag
void pushdown(ll p){
    if(t[p].lazy == 0) return;
    t[p<<1].lazy += t[p].lazy;
    t[p<<1|1].lazy += t[p].lazy;
    t[p<<1].data += t[p].lazy;
    t[p<<1|1].data += t[p].lazy;
    t[p].lazy = 0;
}

void add_interval(ll p, ll l, ll r, ll k){
    if(l <= t[p].l && t[p].r <= r){
        t[p].data += k;
        t[p].lazy += k;
        return;
    }

    pushdown(p);
    ll mid = (t[p].l + t[p].r) >> 1;
    if(l <= mid) add_interval(p << 1, l, r, k);
    if(r > mid) add_interval(p << 1 | 1, l, r, k);
    t[p].data = min(t[p << 1].data, t[p << 1 | 1].data);
}

ll query(ll p, ll l, ll r){
    if(l <= t[p].l && t[p].r <= r) return t[p].data;
    pushdown(p);
    ll mid = (t[p].l + t[p].r) >> 1;
    ll ans = numeric_limits<ll>::max();
    if(l <= mid) ans = min(ans, query(p << 1, l, r));
    if(r > mid) ans = min(ans, query(p << 1 | 1, l, r));
    return ans;
}

void solve() {
    cin >> n >> m;
    vec a;
    vec l(m + 1), r(m + 1), c(m + 1);
    for (ll i = 1; i <= m; i++) {
        cin >> l[i] >> r[i] >> c[i];
        a.push_back(l[i]);
        a.push_back(r[i]);
    }
    a.push_back(1);
    a.push_back(n);
    sort(a.begin(), a.end());
    ll x = unique(a.begin(), a.end()) - a.begin();

    build(1, 0, x-1);

    for (ll i = 1; i <= m; i++) {
        if(l[i] == r[i]) continue;
        ll tl = lower_bound(a.begin(), a.begin()+x, l[i]) - a.begin();
        ll tr = lower_bound(a.begin(), a.begin()+x, r[i]) - a.begin();
        add_interval(1, tl, tr-1, c[i]);
    }
    // if(lower_bound(a.begin(), a.begin()+x, n-1) == a.begin()+x) {
    //     cout << "0\n";
    //     return;
    // }
    // for(ll i = 0; i < x; i++) {
    //     cout << query(1, i, i) << " ";
    // }
    // cout << "\nok\n";
    cout << query(1, 0, x - 2) << "\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t = 1;
    cin >> t;
    // pre();
    // scanf("%lld", &t);
    while(t--){
        solve();
    }
    return 0;
}

C

显然答案的最大值为n，我们要构造答案为n的方案。

先构造一个n*n的表格，我们将[1,2], [1,3], …[1,n]放入该表格，即可使1与所有数相邻。再将[2,3],[2,4]…[2,n]放入，即可使2与所有数相邻。

一直重复该操作，直到n-1。即可使方案成立。

在vp的时候大胆guess了一下：按对角线按顺序放入1到n，答案竟然过了。

我的guess：

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;
#define int long long
int p[2005][1005];
void solve()
{
    int n;
    cin>>n;
    int mk=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            p[i][j]=mk+1;
            mk=(mk+1)%n;
        }
    }
    for(int i=n+1;i<=2*n;i++)
    {
        for(int j=i-n+1;j<=n;j++)
        {
            p[i][j]=mk+1;
            mk=(mk+1)%n;
        }
    }
    for(int j=1;j<=n;j++)
    {
        for(int i=1;i<=n;i++)
        {
            cout<<p[j+i-1][i]<<" ";
        }
        cout<<"\n";
    }
    return;
}
signed  main()
{
    ios::sync_with_stdio(0);
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }

}

F

签到题

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
#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int a,b,c;
    cin >> a >> b >> c;
    if(a>b)
    {
        cout<<"Win\n";
    }
    else
    {
        if(c>b)
        {
            cout<<"WIN\n";
        }
        else
        {
            cout<<"nowin\n";
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while(T--)
    {
        solve();
    }
    return 0;
}

L

首先注意到每一个repeat会使当前的结果翻倍，同时操作的次数只有2e5次，因此我们只需要用一个大小为2e5的栈去维护即可。

当栈不满的时候正常push和pop，当栈满的时候就不可能pop完，因此我们正常算即可。

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
#include <bits/stdc++.h>
using namespace std;
#define MOD 998244353
#define int long long
#define endl '\n'
signed main(){
    ios::sync_with_stdio(0);
    int n;
    cin>>n;
    deque<int> dq;
    int s=0,sum=0;
    for(int i=1;i<=n;i++)
    {
        string ss;
        cin>>ss;
        if(ss=="Push")
        {
            int x;
            cin>>x;
            if(s<2e5)
            {
                s++;
                dq.push_back(x);
                sum=(sum+x)%MOD;
                cout<<sum<<endl;
                continue;
            }
            else
            {
                dq.push_back(x);
                dq.pop_front();
                sum=(sum+x)%MOD;
                cout<<sum<<endl;
                continue;
            }
        }
        if(ss=="Pop")
        {
            sum=(sum+MOD-dq.back())%MOD;
            s--;
            dq.pop_back();
            cout<<sum<<endl;
            continue;
        }
        if(ss=="Repeat")
        {
            sum=sum*2%MOD;
            if(s<=1e5)
            {
                for(int j=0;j<s;j++)
                {
                    dq.push_back(dq[j]);
                }
                s*=2;
                cout<<sum<<endl;
                continue;
            }
            else
            {
                for(int j=0;j<(2e5-s);j++)
                {
                    dq.push_front(dq[s-1]);
                }
                s=2e5;
                cout<<sum<<endl;
                continue;
            }
        }
    }
    return 0;
}

H

只需要注意到紧贴上下界的球顺序相同即可成立。只需要画图即可明白其充分性与必要性

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
#include <iostream>
#include <cmath>
#include <map>
#include <fstream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <cstring>
#include <iomanip>
#include <unordered_map>
#define ll long long
#define ull unsigned long long
#define ld long double
#define vec vector<ll>
#define vcmp vector<vector<ll>>
using namespace std;

ll n, m, k, q, h;
const ll maxn = 2e5+5, maxm = 1e7+5;

/*
1 3
1 2 3
3 2 1
1 0 1
*/

void solve(){
	cin >> n;
	vec a(n+1), b(n+1), c(n+1);
	vec rid(n+1);
	for(ll i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for(ll i = 1; i <= n; i++) {
		cin >> b[i];
	}
	for(ll i = 1; i <= n; i++) {
		ll x;
		cin >> x;
		if(x != 1) {
			rid[a[i]] = 1;
		}
	}

	vec a2, b2, c2;
	for(ll i = 1; i <= n; i++) {
		if(!rid[a[i]]) a2.push_back(a[i]);
	}
	for(ll i = 1; i <= n; i++) {
		if(!rid[b[i]]) b2.push_back(b[i]);
	}

	if(a2.size() != b2.size()) {
		cout << "No\n";
	}
	bool ok = true;
	for(ll i = 0; i < a2.size(); i++) {
		if(a2[i] != b2[i]) {
			ok = false;
			break;
		}
	}
	if(ok) {
		cout << "Yes\n";
	} else {
		cout << "No\n";
	}
}

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

算法
#XCPC #算法
2025重庆市赛部分题目
https://shepherdzzx.github.io/2025CQCPC部分题目/
Author
Shepherdz
Posted on
May 27, 2025
Licensed under