棋 - 题目列表

形式化题目

给定一个 $3\times n$ 的棋盘，每个格子可以填 X 或 O。格子被染色：

格子是 X，且它位于连续三个 X 排成的一线里（同行、同列或两条对角线）→ 染红；
格子是 O，且它位于连续三个 O 排成的一线里 → 染蓝；
否则染黑。

每个格子有权值 $a_{i,j}$ （可以为负），分数 $=$ 所有红格权值之和 $-$ 所有蓝格权值之和。求染色方案的最大分数， $n\leqslant 10^3$ 。

思路

一句话本质：三连判定只看相邻 3 列，所以把每列压成 3bit 图案 + 3bit "已计入"标记，做 3 列滑窗的窄带状压 DP，让每个格子的权值在它滑出窗口时恰好结算一次。

问题？ 直接枚举棋盘染色有多少种方案？

每种方案 $2^{3n}$ 种， $n=1000$ 时完全不可行，但它是"按题意直接判定、绝不会错"的基准。先看这个暴力，它把 $3n$ 个格子拉平成一条 01 选择序列，生成完整棋盘后在叶子统一判定每个格子是否位于三连里：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-28 23:42
 * update_at: 2026-08-28 23:42
 */
// brute.cpp：小数据暴力解，使用 01 序列 / 选择序列递归枚举所有可能。
// 把 3*n 个格子按"行优先"拉平成一条 01 序列：choose[k] = 1 表示画 X，0 表示画 O。
// 递归只负责生成完整序列，到叶子节点再统一按题意判定每个格子是否位于三连里，
// 计算分数（红 + 蓝 -）取最大值。只能跑 n <= 4（2^(3n) 种棋盘）。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 5;          // 暴力只处理 n <= 4
const ll NEG_INF = -(1LL << 60);

int n;
ll w[3][MAXN];               // w[行][列]：权值
int choose[3 * MAXN];        // choose[k]：第 k 个格子画什么，1 = X，0 = O
ll ans;

// 判断格子 (r,c) 是否位于"连续三个和它相同"的一线里
// 方向 4 种：横(0,1)、纵(1,0)、对角线 ↘(1,1)、对角线 ↗(1,-1)
// 对每个方向，三连中心相对 (r,c) 的偏移 m 只可能是 -1、0、1
bool in_triple(int r, int c) {
    int sym = choose[r * n + c];
    int dr[4] = {0, 1, 1, 1};
    int dc[4] = {1, 0, 1, -1};
    for (int d = 0; d < 4; d++) {
        for (int m = -1; m <= 1; m++) {
            bool ok = true;
            for (int t = -1; t <= 1; t++) {
                int rr = r + (m + t) * dr[d];
                int cc = c + (m + t) * dc[d];
                if (rr < 0 || rr >= 3 || cc < 0 || cc >= n) { ok = false; break; }
                if (choose[rr * n + cc] != sym) { ok = false; break; }
            }
            if (ok) return true;
        }
    }
    return false;
}

// 统计完整棋盘的分数：红格权值和 - 蓝格权值和，黑色格子不贡献
ll calc_answer() {
    ll sum = 0;
    for (int r = 0; r < 3; r++) {
        for (int c = 0; c < n; c++) {
            if (!in_triple(r, c)) continue;            // 黑色
            int sgn = choose[r * n + c] ? 1 : -1;      // X 红 +，O 蓝 -
            sum += w[r][c] * sgn;
        }
    }
    return sum;
}

void dfs(int dep) {
    if (dep == 3 * n) {                                // 一条完整 01 序列生成完毕
        ll val = calc_answer();
        if (ans < val) ans = val;
        return;
    }
    // 这一层枚举第 dep 个格子的选择：0 = O，1 = X
    for (int i = 0; i <= 1; i++) {
        choose[dep] = i;
        dfs(dep + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    if (n > 4) { // 超出暴力适用范围，防止越界
        cerr << "brute.cpp 仅支持 n <= 4\n";
        return 0;
    }
    for (int r = 0; r < 3; r++)
        for (int c = 0; c < n; c++)
            cin >> w[r][c];

    ans = NEG_INF;
    dfs(0);
    cout << ans << '\n';
    return 0;
}

问题？ 一个格子是红/蓝/黑，到底由哪些格子决定？

"连续三个相同"的线只有 4 类：横（同行相邻 3 列）、纵（同列相邻 3 行）、对角线 ↘ 和 ↗（各跨相邻 3 列）。所以判定格子 $(r,c)$ 只需要看它自己、同列上下两格、左右两列同行格和两条对角线的斜邻格——也就是以它为中心、半径 2 的邻域。

问题？ 从"每个格子看邻居"出发，从左往右扫描时状态要记多少列？

格子 $(r,c)$ 的横/斜三连可以跨到 $c+2$ 列，看起来要记未来两列的信息，非常臃肿。这里换个角度：把"决定颜色"推迟到"所有相关三连都可见"时再做。包含列 $c$ 的横/斜三连，最右边只到列 $c+2$ ；因此当窗口恰好覆盖 $[c, c+1, c+2]$ 三列时，列 $c$ 中每个格子是否红/蓝已经完全确定，可以一次性结算整列（纵向三连在列内，也在这时判定）。这就是关键卡点①：三连判定只需要相邻 3 列的信息，列状态只要 3bit。状态充分性：更早的列已全部结算完毕，不再影响未来任何判定，所以只需记录最近两列。

注意 $n \leqslant 2$ 需要特判：列数不足 3 时（ $n \leqslant 2$ ）不存在横向/对角线三连，只有纵向三连，代码用 solve_small 单独处理； $n=1$ 时主流程状态里"旧列"不存在，必须特判，否则收尾访问越界。

问题？ 一个格子可能同时属于多个三连（例如全 X 时一个格子横、纵、两条对角线全是三连），贡献怎么保证只算一次？

每个三连被"发现"时如果都去加权，同一个格子会被重复计权。解决方法是给每列额外维护 3bit colored 标记：格子第一次被判定为红/蓝时打上标记并计入权值，之后再被其它三连命中时直接跳过。这就是关键卡点②。有了标记，权值结算就只发生在"该格子所在的列滑出窗口左端"这一次。

问题？ 状态具体记什么？

处理到第 $i$ 列（尚未放置）时，状态记录最近两列——列 $i-2$ （窗口旧列）与列 $i-1$ （新列）的图案（3bit）+ colored 标记（3bit），共 12bit；下一轮放置列 $i$ 形成 3 列窗口，并让列 $i-2$ 滑出结算。状态数 $2^{12}=4096$ 。转移时枚举新列图案（8 种），在 3 列窗口里判定 4 类三连：

纵向：旧列整列图案为 000 或 111；
横向：三列同一行图案相同；
对角线 ↘：格 $(0,旧)(1,中)(2,新)$ 相同；
对角线 ↗：格 $(2,旧)(1,中)(0,新)$ 相同。

旧列格子命中 → 结算权值（红 $+$ 、蓝 $-$ ）；中列、新列格子命中 → 只打 colored 标记，等它们成为旧列时再结算。

DP 转移表格

先看 12bit 状态在代码里的布局（低 6 位是窗口左端"旧列"）：

位	0…2	3…5	6…8	9…11
含义	旧列图案	旧列已计入	新列图案	新列已计入

这张表用样例 1（ $n=3$ ，权值全为 1）演示一次完整转移：初始状态是列 0、列 1 全 X 且无标记（ $dp=0$ ），枚举新列 j=2 的图案为全 X：

转移步骤	判定的三连	动作	累计 gain
初始状态	旧列=列0: 图案111 已计入000；新列=列1: 图案111 已计入000	$dp=0$	0
1. 结算旧列已计入格子	列0 无标记	无	+0
2. 纵向三连	列0 整列 XXX	三格计入并结算	+3，旧列已计入=111
3. 横向三连	三行都是列0=列1=列2=X	中列、新列打标记	中列已计入=111，新列已计入=111
4. 对角线 ↘	(0,列0)(1,列1)(2,列2) 全 X	打标记	标记已存在，跳过
5. 对角线 ↗	(2,列0)(1,列1)(0,列2) 全 X	打标记	标记已存在，跳过
新状态	旧列=列1(图案111,已计入111)，新列=列2(图案111,已计入111)	$ndp=0+3=3$	3

观察这张表：横向、两条对角线三连都命中了列 1、列 2 的格子，但因为 colored 标记，每个格子只被标记一次；而且列 0 的格子被纵向、横向、两条对角线四个三连同时命中，gain 却只加了 3 而不是 12——这正是"一格只计一次"的体现。

转移完成后，最后两列（列 $n-2$ 、 $n-1$ ）永远不会成为窗口左端，需要单独收尾结算：把已计入的格子权值加上，再补判纵向三连。延续上面的状态（列1、列2 已计入均为 111）：

收尾结算	图案	已计入	结算
列 1（ $n-2$ ）	111	111	+3
列 2（ $n-1$ ）	111	111	+3
总计			9

看这张表：列 1、列 2 的格子权值在此刻结算，加上转移阶段结算的列 0 的 3，总分 9，与样例 1 一致。每个格子的权值在整个 DP 中恰好出现一次。

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-28 23:42
 * update_at: 2026-08-28 23:42
 */
// main.cpp：T4 棋(Chess) 正式解
// 思路：3 列滑窗 + colored 标记的窄带状压 DP。
// 每列压缩成 2 个 3bit：图案 pat（1=X，0=O）与"已计入权值"标记 col。
// 状态记录相邻两列 (旧列A, 新列B)，枚举新列图案后，
// 三连判定只依赖这 3 列：纵向(整列相同)、横向(同行相同)、两条对角线。
// 每个格子的权值在它的列"滑出窗口左端"时恰好结算一次，保证不重不漏。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll NEG_INF = -(1LL << 60);
const int MAXN = 1005;

int n;
ll w[3][MAXN]; // w[行][列]：每个格子的权值

inline int bit(int x, int k) { return (x >> k) & 1; }

/* 列状态：每列 2 个 3bit（bit r 对应第 r 行）
 *   pat : 图案，bit = 1 表示 X，0 表示 O
 *   col : 已计入标记，bit = 1 表示该格子权值已经算进答案
 * 状态 s 共 12bit，低 6 位是窗口左端"旧列"，高 6 位是"新列"：
 *   s = patA | (colA<<3) | (patB<<6) | (colB<<9)
 */
inline int encode(int pa, int ca, int pb, int cb) {
    return pa | (ca << 3) | (pb << 6) | (cb << 9);
}
inline void decode(int s, int &pa, int &ca, int &pb, int &cb) {
    pa = s & 7;
    ca = (s >> 3) & 7;
    pb = (s >> 6) & 7;
    cb = (s >> 9) & 7;
}

// n <= 2：列数不够 3，只可能有"纵向三连"（整列相同 000/111）
void solve_small() {
    ll best = NEG_INF;
    for (int p0 = 0; p0 < 8; p0++) {          // 第 0 列的图案
        for (int p1 = 0; p1 < (n == 2 ? 8 : 1); p1++) { // 第 1 列的图案
            ll cur = 0;
            if (p0 == 0 || p0 == 7) {         // 第 0 列整列相同 -> 纵向三连
                int sgn = (p0 & 1) ? 1 : -1;  // X 红 +，O 蓝 -
                for (int r = 0; r < 3; r++) cur += w[r][0] * sgn;
            }
            if (n == 2 && (p1 == 0 || p1 == 7)) {
                int sgn = (p1 & 1) ? 1 : -1;
                for (int r = 0; r < 3; r++) cur += w[r][1] * sgn;
            }
            best = max(best, cur);
        }
    }
    cout << best << '\n';
}

void solve() {
    if (n <= 2) { solve_small(); return; }

    const int SZ = 1 << 12; // 4096 种状态
    static ll dp[SZ], ndp[SZ];
    for (int s = 0; s < SZ; s++) dp[s] = NEG_INF;

    // 初始：只确定第 0、1 列图案，没有任何格子计入权值
    for (int p0 = 0; p0 < 8; p0++)
        for (int p1 = 0; p1 < 8; p1++)
            dp[encode(p0, 0, p1, 0)] = 0;

    // 主循环：枚举新列 j（0 基），本轮把列 j-2 定型并结算它的权值
    for (int j = 2; j < n; j++) {
        int colFinal = j - 2; // 本轮滑出窗口左端的列
        for (int s = 0; s < SZ; s++) ndp[s] = NEG_INF;

        for (int s = 0; s < SZ; s++) {
            if (dp[s] <= NEG_INF) continue;
            int pa, ca, pb, cb;
            decode(s, pa, ca, pb, cb);

            for (int pc = 0; pc < 8; pc++) {   // 枚举新列 j 的图案
                int ca2 = ca, cb2 = cb, cc = 0; // 三列的"已计入"标记
                ll gain = 0;

                // 1. 结算旧列 j-2 中之前已被标记(计入)过的格子
                for (int r = 0; r < 3; r++)
                    if (bit(ca, r))
                        gain += w[r][colFinal] * (bit(pa, r) ? 1 : -1);

                // 2. 纵向三连：旧列整列图案相同(000/111)
                if (pa == 0 || pa == 7) {
                    int sgn = (pa & 1) ? 1 : -1;
                    for (int r = 0; r < 3; r++) {
                        if (!bit(ca2, r)) {
                            gain += w[r][colFinal] * sgn;
                            ca2 |= (1 << r);
                        }
                    }
                }

                // 3. 横向三连：同一行上旧列、中列、新列图案相同
                for (int r = 0; r < 3; r++) {
                    if (bit(pa, r) == bit(pb, r) && bit(pb, r) == bit(pc, r)) {
                        int sgn = bit(pa, r) ? 1 : -1;
                        if (!bit(ca2, r)) {     // 旧列格子：计入并立即结算
                            gain += w[r][colFinal] * sgn;
                            ca2 |= (1 << r);
                        }
                        cb2 |= (1 << r);        // 中列格子：只标记，轮到自己定型时结算
                        cc |= (1 << r);         // 新列格子：只标记
                    }
                }

                // 4. 对角线 ↘：格 (0,旧列)(1,中列)(2,新列)
                if (bit(pa, 0) == bit(pb, 1) && bit(pb, 1) == bit(pc, 2)) {
                    int sgn = bit(pa, 0) ? 1 : -1;
                    if (!bit(ca2, 0)) {
                        gain += w[0][colFinal] * sgn;
                        ca2 |= 1;
                    }
                    cb2 |= (1 << 1);
                    cc |= (1 << 2);
                }
                // 5. 对角线 ↗：格 (2,旧列)(1,中列)(0,新列)
                if (bit(pa, 2) == bit(pb, 1) && bit(pb, 1) == bit(pc, 0)) {
                    int sgn = bit(pa, 2) ? 1 : -1;
                    if (!bit(ca2, 2)) {
                        gain += w[2][colFinal] * sgn;
                        ca2 |= (1 << 2);
                    }
                    cb2 |= (1 << 1);
                    cc |= (1 << 0);
                }

                int ns = encode(pb, cb2, pc, cc);
                ndp[ns] = max(ndp[ns], dp[s] + gain);
            }
        }
        for (int s = 0; s < SZ; s++) dp[s] = ndp[s];
    }

    // 收尾：最后两列 n-2、n-1 右侧没有第三列，
    // 只可能有"纵向三连"，结算标记格子并补上纵向三连
    ll ans = NEG_INF;
    for (int s = 0; s < SZ; s++) {
        if (dp[s] <= NEG_INF) continue;
        int pa, ca, pb, cb;
        decode(s, pa, ca, pb, cb);
        ll val = dp[s];

        for (int r = 0; r < 3; r++)             // 列 n-2 的标记格子
            if (bit(ca, r)) val += w[r][n - 2] * (bit(pa, r) ? 1 : -1);
        if (pa == 0 || pa == 7) {               // 列 n-2 的纵向三连
            int sgn = (pa & 1) ? 1 : -1;
            for (int r = 0; r < 3; r++)
                if (!bit(ca, r)) val += w[r][n - 2] * sgn;
        }
        for (int r = 0; r < 3; r++)             // 列 n-1 的标记格子
            if (bit(cb, r)) val += w[r][n - 1] * (bit(pb, r) ? 1 : -1);
        if (pb == 0 || pb == 7) {               // 列 n-1 的纵向三连
            int sgn = (pb & 1) ? 1 : -1;
            for (int r = 0; r < 3; r++)
                if (!bit(cb, r)) val += w[r][n - 1] * sgn;
        }
        ans = max(ans, val);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int r = 0; r < 3; r++)
        for (int c = 0; c < n; c++)
            cin >> w[r][c];

    solve();
    return 0;
}

复杂度

状态数 $2^{12}=4096$ ，每个状态枚举 8 种新列图案，共 $n-2$ 轮主循环，收尾 $O(2^{12})$ ：

时间复杂度： $O(n \cdot 4096 \cdot 8)$ ， $n=1000$ 时约 $3.3\times 10^7$ 次操作；
空间复杂度： $O(4096)$ ，只需滚动两行 DP 数组。

总结

这道题的关键是把"格子颜色"的判定从局部视角换成窗口视角：横向/斜向三连跨相邻 3 列，所以当一列滑出 3 列窗口时，它的颜色已经确定。窄带状压 DP 的通用套路就是——先找"未来只依赖过去哪段紧凑信息"（这里是相邻 2 列），再用 colored 标记解决"一个对象被多个结构重复命中"的计权问题。这种"标记去重"的思想在网格类 DP 里很常用。

棋

目录

形式化题目

思路

DP 转移表格

代码

复杂度

总结