Znzryb's Blog
0%

CF-1078-D. Table Cut（绷不住了，真是贪心了，贪了）

Posted on Edited on

题目大意

给定一个大小为n×mn \times m的表格，其中每个单元格包含00或11。任务是通过一条从左上角到右下角的切割线将其分成两部分。切割线只能向右或向下走。

设aa为切割后表格一部分中的1的数量，bb为表格另一部分中的1的数量。目标是最大化a⋅ba \cdot b的值。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 tt (1≤t≤1041 \le t \le 10^4)。随后是测试用例的描述。

每个测试用例的第一行包含两个整数 nn 和 mm (1≤n,m≤3⋅1051 \leq n, m \leq 3 \cdot 10^{5}, 2≤n⋅m≤3⋅1052 \leq n \cdot m \leq 3 \cdot 10^{5}) — 表中的行数和列数。

接下来的 nn 行中，每行包含 mm 个整数，其中第 ii 行的第 jj 个数对应值为 ai,ja_{i, j} (0≤ai,j≤10 \leq a_{i, j} \leq 1)。

保证所有测试用例中 n⋅mn \cdot m 的总和不超过 3⋅1053 \cdot 10^{5}。

输出

对于每个测试用例，在输出数据的第一行输出一个数字 - 乘积的最大值。

在第二行，输出一个由 nn 个字符 ‘D’ 和 mm 个字符 ‘R’ 组成的字符串，表示下一次切割的方向，其中 ‘D’ 表示向下切割，而 ‘R’ 表示向右切割。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
3
5 5
1 0 1 1 0
0 1 0 1 1
1 0 1 0 0
0 1 0 1 0
0 0 0 0 1
5 4
0 0 1 0
0 1 1 1
1 0 0 1
0 1 0 1
0 0 1 0
3 2
1 0
0 1
1 1

1
2
3
4
5
6
30
RDRDRDRDDR
20
DRRDRDDDR
4
DRDRD

注意

这些图片展示了第一个和第二个测试用例的正确切割方式，从而实现产品的最大价值。

image

image

思路讲解

绷不住了，我想了半天的DP解法，结果和我讲，其实这道题目根本不用DP，就贪心啊，然后这个答案总归是最大的，就是把它尽量均匀的切分成两半，总是可以的。

image

就是形如上图这样子切分，可以证明啊，其实也不用证明了。你直接感觉你就知道把它们尽量均匀的切分成两半是非常可行的，是完全可行的。

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
    for (int x=1;x<=N;++x) {
        ll to_sum=sum+pre_sum[x][M];
// #ifdef LOCAL
//         debug(to_sum);
//         debug(sum);
// #endif
        if (to_sum>=half && !is_in) {
            ll bpy=1;
            is_in=true;
            for (ll y=M;y>=1;--y) {
                sum+=maze[x][y];
                if (sum==half) {
                    bpy=y;
                    break;
                }
            }
            for (int y=1;y<bpy;++y) {
                ans.push_back('R');
            }
            ans.push_back('D');
            for (int y=bpy;y<=M;++y) {
                ans.push_back('R');
            }
        }else {
            ans.push_back('D');
        }
        sum=to_sum;
    }

AC代码

AC

https://codeforces.com/contest/2194/submission/362089758

源代码

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
/**
 * Problem: D. Table Cut
 * Contest: Codeforces Round 1078 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2194/problem/D
 * Created: 2026-02-09 14:03:01
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define debug3d(a)                                         \
cerr << #a << " = [\n";                                \
for (int i = 0; i < (int)(a).size(); i++)              \
{                                                      \
cerr << "  [\n";                                   \
for (int j = 0; j < (int)(a[i]).size(); j++)       \
{                                                  \
cerr << "    [";                               \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k];     \
cerr << "]\n";                                 \
}                                                  \
cerr << "  ]\n";                                   \
}                                                      \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<vector<int>> maze(N+2,vector<int>(M+2));
    vector<vector<ll>> pre_sum(N+2,vector<ll>(M+2));
    ll sum1=0;
    for (int x=1;x<=N;++x) {
        for (int y=1;y<=M;++y) {
            cin>>maze[x][y];
            sum1+=maze[x][y];
        }
    }
    string ans;
    for (int x=1;x<=N;++x) {
        partial_sum(all(maze[x]),pre_sum[x].begin());
    }
    ll sum=0,half=sum1/2;
    bool is_in=false;
    for (int x=1;x<=N;++x) {
        ll to_sum=sum+pre_sum[x][M];
// #ifdef LOCAL
//         debug(to_sum);
//         debug(sum);
// #endif
        if (to_sum>=half && !is_in) {
            ll bpy=1;
            is_in=true;
            for (ll y=M;y>=1;--y) {
                sum+=maze[x][y];
                if (sum==half) {
                    bpy=y;
                    break;
                }
            }
            for (int y=1;y<bpy;++y) {
                ans.push_back('R');
            }
            ans.push_back('D');
            for (int y=bpy;y<=M;++y) {
                ans.push_back('R');
            }
        }else {
            ans.push_back('D');
        }
        sum=to_sum;
    }
    ll a=sum1/2,b=sum1-a;
    cout<<a*b<<"\n";
    cout<<ans<<"\n";
#ifdef LOCAL    // 校验器
    if (count(all(ans),'D')==N && count(all(ans),'R')==M) {

    }else {
        cout<<"WA\n";
        return;
    }
    ll col=0,row=0;
    ll a_num=0,b_num=0;
    for (auto ch:ans) {
        if (ch=='R') {
            ++col;
        }else {
            row++;
            a_num+=pre_sum[row][col];
            b_num+=pre_sum[row][M]-pre_sum[row][col];
        }
    }
    if (a_num*b_num==a*b) {

    }else {
        cout<<"WA\n";
    }
#endif

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2194/submission/362089758

DRDRRD

1
3 2
1 0
0 1
1 1

_______________[ Stress test, testcase 16 INPUT ]_______________
1
1 4
0 0 0 1

_______________[ Stress test, testcase 16 OUTPUT]_______________
0
DRRRRR
WA

*/

心路历程（WA，TLE，MLE……）