2025 扬州大学 ACM-ICPC 选拔赛 题解

预期题目定位

  • 签到题：I, B, C, H\text{I, B, C, H}
  • 铜牌题：D, F, G, E\text{D, F, G, E}
  • 银牌题：A\text{A}

PS：题解题目顺序为出题人主观难度递增顺序


I - Last Problem

出题人：MarisaMagic

题意简述

输入 nn 个字符，判断有多少种字符。

解题思路 （语法）

用集合 std::set 存储字符或者用一个数组维护字符是否出现最后输出答案即可。

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

void marisa(){
    int n; cin >> n;
    set<char> st;
    for(int i = 0; i < n; i ++ ){
        char ch; cin >> ch;
        st.insert(ch);
    }
    cout << st.size() << "\n";
}

int main(){
    int T = 1; cin >> T;
    while(T -- ) marisa();

    return 0;
}

B - Magic Coins

出题人：South_Orange

题意简述

给定 nn 个魔法硬币，第 ii 枚等级为 aia_i，两个相同等级的硬币可以合成一个高一级的硬币，求可以获得的最高等级的硬币。

解题思路 （模拟、思维）

开一个桶记录各个等级硬币的数量，再从小到大合成，硬币的最大等级应该为 max⁡ai+log2n=201740\max {a_i} + {log_2n} = 201740。合成过程中注意遍历到上限即可。

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 <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <cstring>
#include <iomanip>

using ll = long long;

const int N = 202010;

int n;
int cnt[N];

void solve()
{
	cin >> n;
	for (int i = 1;i <= n;i++)
	{
		int t;
		cin >> t;
		cnt[t]++;
	}
	int mx = 0;
	for (int i = 0;i <= 202000;i++)
	{
		if (cnt[i] != 0)
		{
			mx = i;
			cnt[i + 1] += cnt[i] / 2;
		}
	}
	cout << mx << '\n';
}

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

C - Kaguya wanna Sort

出题人：MarisaMagic

题意简述

给定一个长度为 nn 的排列 a1,a2,…,ana_1, a_2, \ldots, a_n 和 mm 个栈，将排列元素依次放入栈中，求使得全部元素放入后能够以 1,2,…,n1, 2, \ldots, n 的顺序依次出栈的最小的 mm。当取出某一个栈 SS 中的一个元素时，不能取出任何其它栈中的元素直到栈 SS 变为空。

解题思路 （模拟，栈）

假设一个栈中的元素从栈底到栈顶依次为 b1,b2,…,btopb_1, b_2, \ldots, b_{top}，显然有 bi−1=bi+1b_{i - 1} = b_{i} + 1（1<i≤top1 < i \le top）。

若当前放入的元素为 xx，如果 x+1x + 1 是一个栈 SS 的栈顶元素，那么 xx 就可以放入栈 SS 中；否则，需要新开一个栈，将 xx 放入新开的栈中。

我们可以维护每个元素所在栈的编号，最终最大栈的编号就是答案。时间复杂度为 O(n)\mathcal{O}(n)。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

void marisa(){
    int n; cin >> n;
    vector<int> id(n + 5); // 每个元素所在栈的编号
    int m = 0; // 栈的编号
    for(int i = 1, x; i <= n; i ++ ){
        cin >> x;
        if(!id[x + 1]) id[x] = ++ m; // 需要新开一个
        else id[x] = id[x + 1]; // 可以放入栈中
    }
    cout << m << "\n";
}

int main(){
    ios;

    int T = 1; cin >> T;
    while(T -- ) marisa();

    return 0;
}

H - Sweet interval

出题人：South_Orange

题意简述

给定一个数组，求数组中使得 f(l,r)=⌊∑i=lrair−l+1⌋f(l,r)=\left \lfloor \frac{ \sum_{i=l}^ra_i}{r-l+1} \right \rfloor 的值最大的 (l,r)(l,r) 的对数。

解题思路 （组合数学）

易证 f(l,r)f(l,r) 的最大值的区间中的所有数都是数组中的最大数。

遍历数组，记录所有最大数的区间长度，对于每一个区间中最大数的个数 cntcnt，都会为答案提供 cnt×(cnt+1)2\frac{cnt \times (cnt + 1)}{2} 对 (l,r)(l,r)，全部相加即是答案。

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
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <cstring>
#include <iomanip>

using ll = long long;

const int N = 2e5 + 10;

int n;
ll a[N];

void solve()
{
	cin >> n;
	ll mx = -1e10;
	for (int i = 1;i <= n;i++) cin >> a[i], mx = max(mx, a[i]);
	ll cnt = 0;
	ll ans = 0;
	for (int i = 1;i <= n;i++)
	{
		if (a[i] == mx) cnt++;
		else
		{
			ans += cnt * (cnt + 1) / 2;
			cnt = 0;
		}
	}
	ans += cnt * (cnt + 1) / 2;
	cout << ans << '\n';
}

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

D - Aya and Momizi

出题人：MarisaMagic

题意简述

在二维坐标系上有 nn 个红点和 mm 个蓝点，无重合点。若一个点被另一个点攻击当且仅当：

  • 两个点颜色不同；
  • 两点 xx 坐标或 yy 坐标相同；
  • 两点之间构成的线段上没有其它点。

判断哪些点是被攻击的。

解题思路 （排序）

设红点的值为 00，蓝点的值为 11，存储每个点的坐标、值和编号。先按照 xx 坐标为第一关键字，yy 为第二关键字排序，枚举相邻两个点，如果 xx 相同且值不同，那么这两点是被攻击的；再按照 yy 坐标为第一关键字，xx 为第二关键字排序，枚举相邻两个点，如果 yy 相同且值不同，那么这两点也是被攻击的。最后按要求输出答案，时间复杂度 O((n+m)log⁡(n+m))\mathcal{O}((n + m)\log (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
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;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

struct node{ int x, y, val, id; }; // 点坐标，值，编号

void marisa(){
    int n, m; cin >> n >> m;
    vector<node> p(n + m + 1);
    for(int i = 1; i <= n; i ++ ){
        cin >> p[i].x >> p[i].y;
        p[i].val = 0, p[i].id = i;
    }
    for(int i = n + 1; i <= n + m; i ++ ){
        cin >> p[i].x >> p[i].y;
        p[i].val = 1, p[i].id = i;
    }
    vector<bool> atk(n + m + 1); // 记录每个点是否被攻击
    // 第一次排序：x 为第一关键字，y 为第二关键字
    sort(begin(p) + 1, end(p), [](const node& a, const node& b){
        if(a.x != b.x) return a.x < b.x; // 排序使得相同x的点相邻
        return a.y < b.y;
    });
    for(int i = 1; i < n + m; i ++ ){
        if(p[i].x == p[i + 1].x && p[i].val != p[i + 1].val){
            atk[p[i].id] = atk[p[i + 1].id] = true;
        }
    }
    // 第二次排序：y 为第一关键字，x 为第二关键字
    sort(begin(p) + 1, end(p), [](const node& a, const node& b){
        if(a.y != b.y) return a.y < b.y; // 排序使得相同y的点相邻
        return a.x < b.x;
    });
    for(int i = 1; i < n + m; i ++ ){
        if(p[i].y == p[i + 1].y && p[i].val != p[i + 1].val){
            atk[p[i].id] = atk[p[i + 1].id] = true;
        }
    }
    for(int i = 1; i <= n + m; i ++ ){
        cout << atk[i];
        if(i == n) cout << "\n";
    }
}

int main(){
    ios;

    int T = 1; // cin >> T;
    while(T -- ) marisa();

    return 0;
}

F - Cirno’s Circular Sequence

出题人：MarisaMagic

题意简述

给定一个环形序列 a1,a2,…,ana_1, a_2, \ldots, a_n。每次操作可以选择一个下标 xx 使得 ax←ax−a(x mod n)+1a_x \leftarrow a_x - a_{(x \bmod n) + 1}，并删除 a(x mod n)+1a_{(x \bmod n) + 1}。求最终剩下元素的最大值。

解题思路 （模拟，思维，数学）

考虑 全部为正数 的情况（包括 00）。我们可以选定序列中最小的数 amina_{min}，然后用 amina_{min} 依次减去其后面的 n−2n - 2 个数得到一个元素 xx，再用最后剩下的 11 个数减去这个元素 xx。由此答案为 前 n−1n - 1 大的数减去最小的数，即 ∑i=1nai−2×amin\sum_{i=1}^{n} a_i - 2 \times a_{min}。没有比这个更大的结果。

考虑 全部为负数 的情况（包括 00）。我们可以选定序列中最大的数 amaxa_{max}，用这个数依次减去 n−1n - 1 个数，最终剩下的一个元素就是答案，即 最大的数减去前 n−1n - 1 小的数，即 ∑i=1n∣ai∣+2×amax\sum_{i=1}^{n}|a_i| + 2 \times a_{max}。没有比这个更大的结果。

其实 全部为负数 的情况也可以通过看作是 全部为正数，将每个 aia_i 变为其绝对值即可，可以统一这两个情况的答案为 ∑i=1n∣ai∣−2×∣ai∣min\sum_{i=1}^{n}|a_i| - 2 \times |a_i|_{min}。

考虑 有正数也有负数 的情况。我们一定可以找到一种方法使得最终答案为序列所有数绝对值之和，即 ∑i=1n∣ai∣\sum_{i=1}^{n}|a_i|。一种可行的方法为：找到环形序列中一个在负数前面的正数，选定这个正数，将剩余其它的数全部转变为负数，最后再用这个正数依次减去剩下的负数，最终答案就是 ∑i=1n∣ai∣\sum_{i=1}^{n}|a_i|。

例如环形序列为 {−1,2,−3,1,2,−2,3}\{ -1, 2, -3, 1, 2, -2, 3 \}，我们按照上面的思路，选定 a2=2a_2 = 2 这个正数，序列变化为：{−1,2,−3‾,1‾,2,−2,3}\{ -1, {\color{red}{2}}, \underline{-3}, \underline{1}, 2, -2, 3 \} →\rightarrow {−1,2,−4‾,2‾,−2,3}\{ -1, {\color{red}{2}}, \underline{-4}, \underline{2}, -2, 3 \} →\rightarrow {−1,2,−6,−2‾,3‾}\{ -1, {\color{red}{2}}, -6, \underline{-2}, \underline{3} \} →\rightarrow {−1,2,−6,−5}\{ -1, {\color{red}{2}}, -6, -5 \} →\rightarrow {14}\{ 14 \}。

综上所述：

  • 当 全部为正数 或者 全部为负数 时，答案为 ∑i=1n∣ai∣−2×∣ai∣min\sum_{i=1}^{n}|a_i| - 2 \times |a_i|_{min}；
  • 否则，答案为 ∑i=1n∣ai∣\sum_{i=1}^{n}|a_i|。

特别地，当 n=1n = 1 时，答案是 a1a_1。时间复杂度 O(n)\mathcal{O}(n)

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;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using ll = long long;

void marisa(){
    int n; cin >> n;
    vector<int> a(n + 1);
    ll sum = 0; int mn = 1e9;
    bool all_minus = true, all_plus = true;
    for(int i = 1; i <= n; i ++ ){
        cin >> a[i];
        sum += abs(a[i]);
        mn = min(mn, abs(a[i]));
        if(a[i] > 0) all_minus = false;
        if(a[i] < 0) all_plus = false;
    }
    if(n == 1){ // 特判只有一个数的情况
        cout << a[1] << "\n";
        return;
    }
    if(all_plus || all_minus) cout << sum - 2 * mn << "\n";
    else cout << sum << "\n";
}

int main(){
    ios;

    int T = 1; cin >> T;
    while(T -- ) marisa();

    return 0;
}

G - Reach for the Moon

出题人：MarisaMagic

题意简述

给定 nn 个不同的点 (xi,yi)(x_i, y_i)，可以任意添加 mm 个点。求满足 xi+1−xi=1,yi+1=yix_{i+1} - x_i = 1, y_{i+1} = y_{i} 或者 xi+1=xi,yi+1−yi=1x_{i+1} = x_i, y_{i+1} - y_i = 1 的最长上升点列的长度。

解题思路 （动态规划 DP）

考虑动态规划，设 fi,kf_{i,k} 为以第 ii 个点为结尾，前面加入 kk 个点的最长上升点列长度。由此可得状态转移方程：

fi,k=max⁡(fj,k−d+d+1),   1≤i≤n, 0≤k≤m, 1≤j<if_{i,k} = \max(f_{j, k - d} + d + 1), \ \ \ 1 \le i \le n, \ 0 \le k \le m, \ 1 \le j < i

其中 d=∣xi−xj∣+∣yi−yj∣−1d = |x_i - x_j| + |y_i - y_j| - 1 表示从点 (xj,yj)(x_j, y_j) 到 点 (xi,yi)(x_i, y_i) 所需添加的点数。

在更新 fi,kf_{i, k} 的状态时，需要确保前面所有 xx 坐标小于 xix_i 的点结尾的最长点列长度被计算出来，还要确保 xx 坐标相同时，前面所有 yy 坐标小于 yiy_i 的点结尾的最长点列长度被计算出来。故我们在进行 dp 前，需要先对所有点以 xx 为第一关键字递增，以 yy 为第二关键字递增排序。

我们还可以随意往后添加任意 m−km - k 个点，故最终答案为 max⁡(fi,k+(m−k))\max(f_{i, k} + (m - k))。时间复杂度 O(n2m)\mathcal{O}(n^2 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
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define x first
#define y second

void marisa(){
    int n, m; cin >> n >> m;
    vector<pair<int, int>> p(n + 1);
    for(int i = 1; i <= n; i ++ ) cin >> p[i].x >> p[i].y;
    sort(begin(p) + 1, end(p));
    int ans = 0;
    vector<vector<int>> f(n + 1, vector<int>(m + 1));
    for(int i = 1; i <= n; i ++ ) f[i][0] = 1;
    for(int i = 1; i <= n; i ++ ){ // 枚举结尾
        for(int k = 0; k <= m; k ++ ){ // 枚举加入点数
            for(int j = 1; j < i; j ++ ){ // 枚举前一个点
                if(p[i].y < p[j].y) continue;
                // d: 和前一个点之间所需加入点数
                int d = (p[i].x - p[j].x) + (p[i].y - p[j].y) - 1; 
                if(k >= d) f[i][k] = max(f[i][k], f[j][k - d] + d + 1);
            }
            ans = max(ans, f[i][k] + (m - k)); // 可以再随便加入m-k个点
        }
    }
    cout << ans << "\n";
}

int main(){
    ios;

    int T = 1; // cin >> T;
    while(T -- ) marisa();

    return 0;
}

E - Greenwich in the Sky

出题人：MarisaMagic

题意简述

给定一个 nn 点 mm 条边的简单无向图，第 ii 条边长度为 2i2^i，求长度最小的简单环 且环边数量至少为 33。递增输出环上边的编号，若无解则输出 −1-1。

解题思路 （贪心，生成树，搜索）

考虑贪心，从小到大枚举每条边。由于 ∑i=1k2i<2k+1\sum_{i=1}^k 2^i < 2^{k+1}，故贪心思路正确。使用 Kruskal 算法，用并查集维护：

  • 如果加入第 ii 条边到生成树不会构成环，则加入到生成树中；
  • 否则，第 ii 条边就是构成最小环的最后一条边。记录 uiu_i 和 viv_i 分别为起点和终点，并退出枚举。

然后用 dfs 从起点开始搜索找到生成树上到终点的路径，在搜索过程中加入边到答案中。最后加上最后一条边，按要求输出答案。时间复杂度 O(nlog⁡n)\mathcal{O}(n \log n)。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using pii = pair<int, int>;
const int N = 1e5 + 10;

int fa[N];

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

void marisa(){
    int n, m; cin >> n >> m;
    vector<pii> edges(m + 1);
    for(int i = 1; i <= m; i ++ ){
        cin >> edges[i].first >> edges[i].second;
    }

    // 生成树找到第一个出现的环
    int src = 0, des = 0, last_i = 0; // 起点，终点，最后边
    vector<vector<pii>> e(n + 1); // 生成树
    for(int i = 1; i <= n; i ++ ) fa[i] = i;
    for(int i = 1; i <= m; i ++ ){
        const auto& [u, v] = edges[i];
        int fx = find(u), fy = find(v);
        if(fx == fy){ // 构成环
            src = u, des = v; // 记录环的起点和终点
            last_i = i; // 记录构成最小环的最后一条边
            break;
        }
        fa[fx] = fy; // 不会构成环，加入到生成树
        e[u].emplace_back(v, i); 
        e[v].emplace_back(u, i);
    }

    if(!src){ // 没有环
        cout << -1 << "\n";
        return;
    }

    vector<int> ans, vec; // dfs 找到 src -> des 的路径
    function<void(int, int)> dfs = [&](int u, int fa){
        if(u == des){
            ans = vec;
            return;
        }
        for(const auto& [v, i] : e[u]){
            if(v == fa) continue;
            vec.emplace_back(i);
            dfs(v, u);
            vec.pop_back();
        }
    };

    dfs(src, 0);

    ans.emplace_back(last_i); // 加上 des -> src 的边
    sort(begin(ans), end(ans));
    for(size_t i = 0; i < ans.size(); i ++ ){
        cout << ans[i] << " \n"[i == ans.size() - 1];
    }
}

int main(){
    ios;

    int T = 1; cin >> T;
    while(T -- ) marisa();

    return 0;
}

A - Symphony of Lights

出题人：South_Orange

题意简述

给点一个 nn 行 mm 列的棋盘，要求构造一种局面使得每列的棋子数为 aia_i 且无任何两个棋子相邻。

解题思路 （构造）

由于限制的是每列多少个,于是来考虑行nn 。

如果nn为偶数，每列都只能放 n2\frac n2 个，与相邻的列无关，直接判断即可。

否则至少能放 n2\frac n2 个，最多能放 n2+1\frac n2+1 个，差异在于放在奇数位置上或偶数位置上。

如果 max⁡ai\max a_i 超过了 n2+1\frac n2+1 或小于 n2\frac n2 了就不再考虑，这些可以特判。
我们称，满足ai=n2+1a_i=\frac n2+1的列ii叫做顶满了的列。

我们可以发现如果顶满了的列都在奇数列或偶数列，直接强制保证顶满的列都填奇数位置，由于其他列都未顶满，n2\frac n2 个位置就够用了，对于每列从前往后交替(注：交替指奇偶位置交替)填即可，没有影响。于是考虑某两个顶满的列 i,ji,j 满足 i<ji<j 满足 j−i≡1j- i\equiv 1 ( mod 2) ,即中间行数为偶行。

此时如果你不进行操作，你强制两列都放奇数位置，中间的列就可能出现问题，更具体的，你需要将 j−1j-1 的奇数位置空出来，否则无法构造。

考虑构造一种方法让其空出来，由于原来不操作时，这些列是交替填的，我们希望让中间某两行打破这个交替。

那么我们就从后往前尽量让当前行不与上一行交替，可能会剩下一些必定交替，此时再正常的按交替的填，直到某两行打破交替，后面的构造就都会切换奇偶交替的状态了，使得 j−1j-1 的奇数位置能空出来。

如果从 ii 构造至 jj 都还没构造出来则说明无解，否则用相同的方法处理后面顶满的列即可。

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
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <cstring>
#include <iomanip>

using ll = long long;

const int N = 310;

int n, m;
int a[N];
int b[N];
vector<int> mm;
int ans[N][N];

void solve()
{
	cin >> n >> m;
	bool flag = false;
	for (int i = 1;i <= m;i++)
	{
		cin >> a[i];
		b[i] = a[i];
		if (a[i] > (n + 1) / 2) flag = true;
		else if (a[i] == (n + 1) / 2)
		{
			if (n % 2 == 1 && !mm.empty() && mm.back() == i - 1) flag = true;
			else mm.push_back(i);
		}
	}

	if (flag) // 某一列棋子过多或在奇数行情况下出现了相邻两列棋子都放满的情况
	{
		cout << "No\n";
		return;
	}

	if (n % 2 == 0 || mm.empty()) // 偶数行或无棋子放满的情况
	{
		cout << "Yes\n";
		for (int j = 1;j <= m;j++)
			for (int i = 1;i <= n;i++)
			{
				if (b[j] && (i + j) % 2 == 0)
				{
					ans[i][j] = 1;
					b[j]--;
				}
				else if (b[j] == 0) break;
			}
		for (int i = 1;i <= n;i++)
		{
			for (int j = 1;j <= m;j++)
				cout << ans[i][j];
			cout << '\n';
		}
		return;
	}

	for (auto j : mm) // 将需要放满的列先放上棋子
		for (int i = 1;i <= n;i += 2)
			ans[i][j] = 1;

	for (int p = 1;p < mm.size();p++) {
		if ((mm[p] - mm[p - 1]) % 2 == 1) { // 中间有偶数列，尝试调整奇偶性
			int pre = mm[p - 1], suf = mm[p];
			for (int j = pre + 1;j < suf;j++) { //这里是尽量不交替
				int t, i;
				for (t = 1, i = n - (((j - pre) & 1) ^ 1);t <= a[j] && i > 0;t++, i -= 2) {
					if (ans[i][j - 1] || ans[i][j + 1]) break;
					ans[i][j] = 1;
				}
				for (i = ((j - pre) & 1) + 1;t <= a[j];t++, i += 2) { //这里是必定交替
					if (ans[i][j - 1] || ans[i][j + 1]) {
						cout << "No\n";
						return;
					}
					ans[i][j] = 1;
				}
			}
		}
		else { // 中间有奇数列，直接交替放置
			int pre = mm[p - 1] + 1, suf = mm[p] - 1;
			for (int j = 0;j <= suf - pre;j++) {
				for (int i = 1;i <= n;i++) {
					if ((i + j) % 2 == 0 && b[pre + j]) {
						ans[i][pre + j] = 1;
						b[pre + j]--;
					} else if (b[pre + j] == 0) break;
				}
			}
		}
	}
	int pre = mm.front() - 1, suf = mm.back() + 1;
	for (int j = 0;pre - j > 0;j++)
	{
		for (int i = 1;i <= n;i++)
			if ((i + j) % 2 == 0 && b[pre - j])
			{
				ans[i][pre - j] = 1;
				b[pre - j]--;
			}
			else if (b[pre - j] == 0) break;
	}
	for (int j = 0;suf + j <= m;j++)
	{
		for (int i = 1;i <= n;i++)
			if ((i + j) % 2 == 0 && b[suf + j])
			{
				ans[i][suf + j] = 1;
				b[suf + j]--;
			}
			else if (b[suf + j] == 0) break;
	}
	cout << "Yes\n";
	for (int i = 1;i <= n;i++)
	{
		for (int j = 1;j <= m;j++)
			cout << ans[i][j];
		cout << '\n';
	}
}

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T = 1;
	//cin >> T;
	while (T--)
	{
		solve();
	}
	return 0;
}
咏唱光芒 > 扬大校内选拔赛
#C++ #算法 #算法竞赛 #Luogu #YAC #选拔赛 #ACM #ICPC
2025 扬州大学 ACM-ICPC 选拔赛 题解
https://marisamagic.github.io/2025/03/08/2025YZUACM/
作者
MarisaMagic
发布于
2025年3月8日
许可协议