火烈鸟门户网站开发,动漫制作专业总结,丽水市建设监理协会网站在哪里,admin后台管理系统【题目来源】
洛谷：AT_abc466_d [ABC466D] Placing Rooks
【题目描述】
There is a grid with \(N\) rows and \(N\) columns.
Initially, nothing is placed on the grid.
Starting from this state, Takahashi perf…
【题目来源】
洛谷：AT_abc466_d [ABC466D] Placing Rooks
【题目描述】
There is a grid with \(N\) rows and \(N\) columns.
Initially, nothing is placed on the grid.
Starting from this state, Takahashi performs \(M\) operations on the grid in order. The \(i\)-th operation \((1\leq i\leq M)\) is as follows.Remove all pieces placed on the cells in the \(R_i\)-th row from the top.
Next, remove all pieces placed on the cells in the \(C_i\)-th column from the left.
Finally, place a piece on the cell at the \(R_i\)-th row from the top and the \(C_i\)-th column from the left.Output the number of pieces placed on the grid after the \(M\) operations.
有一个 \(N\) 行 \(N\) 列的网格。
最初，网格上没有任何棋子。
从这个状态开始，高橋按顺序对网格进行 \(M\) 次操作。第 \(i\) 次操作 \((1\leq i\leq M)\) 如下：移除从上数第 \(R_i\) 行中所有已放置的棋子。
接着，移除从左数第 \(C_i\) 列中所有已放置的棋子。
最后，在从上数第 \(R_i\) 行、从左数第 \(C_i\) 列的格子上放置一个棋子。输出 \(M\) 次操作后网格上放置的棋子数量。
【输入】
The input is given from Standard Input in the following format:\(N\) \(M\)
\(R_1\) \(C_1\)
\(R_2\) \(C_2\)
\(\vdots\)
\(R_M\) \(C_M\)【输出】
Output the number of pieces placed on the grid after the \(M\) operations.
【输入样例】
3 6
1 1
1 2
3 3
3 2
1 3
1 3【输出样例】
2【核心思想】问题分析：在 \(N \times N\) 网格上进行 \(M\) 次操作，每次操作先清空第 \(R_i\) 行和第 \(C_i\) 列的所有棋子，然后在 \((R_i, C_i)\) 放置一枚棋子。求 \(M\) 次操作后网格上的棋子数量。这是一个逆序贪心 + 集合覆盖问题，核心在于分析每次操作对最终状态的影响——只有最后一次在某行或某列放置的棋子才可能保留。算法选择：逆序处理：从最后一次操作往前遍历，判断当前操作的棋子是否会被后续操作清除
行/列占用标记：用布尔数组记录某行或某列是否已被后续操作处理过关键步骤：读入数据：读取 \(N, M\) 和数组 \(R[1..M], C[1..M]\)
逆序遍历（\(i\) 从 \(M\) 到 \(1\)）：若 \(used\_r[R_i] = false\) 且 \(used\_c[C_i] = false\)：该棋子不会被后续任何操作清除（后续操作要么行不同要么列不同），\(ans \leftarrow ans + 1\)\(used\_r[R_i] \leftarrow true\)，\(used\_c[C_i] \leftarrow true\)输出结果：\(ans\)时间/空间复杂度：时间复杂度：\(O(M)\)，单次逆序遍历
空间复杂度：\(O(N + M)\)，存储操作数组和标记数组逆序贪心与覆盖分析的核心思想：后续操作的决定性：第 \(i\) 次操作放置的棋子 \((R_i, C_i)\) 会被后续操作 \(j i\) 清除，当且仅当存在某个 \(j\) 满足 \(R_j = R_i\) 或 \(C_j = C_i\)。因为操作 \(j\) 会先清空第 \(R_j\) 行和第 \(C_j\) 列
逆序视角的简化：从后往前看，若某行 \(R_i\) 和某列 \(C_i\) 都未被"后续"（即更晚的）操作处理过，则第 \(i\) 次操作的棋子一定保留到最后。一旦某行或某列被标记，所有更早的该行列操作都会被清除
贪心保留策略：每遇到一个新的（行, 列）组合就计数，因为后续不会再有操作同时清除这个特定的行和列
集合覆盖的本质：最终保留的棋子对应一个行集合和一个列集合，要求每个保留棋子的行和列都是唯一的，即构成一个部分匹配
适用于具有"后操作覆盖先操作"特征的问题，逆序处理可以将动态清除转化为静态判定【算法标签】
贪心
【代码详解】
#include bits/stdc++.h
using namespace std;
#define int long long
const int N = 300005; // 常量：最大操作次数int n, m; // n: 网格大小; m: 操作次数
int ans; // ans: 最终网格上的棋子数量
int r[N]; // r[i]: 第 i 次操作的行号
int c[N]; // c[i]: 第 i 次操作的列号
bool used_r[N]; // used_r[x]: 行 x 是否已被后续操作处理过
bool used_c[N]; // used_c[x]: 列 x 是否已被后续操作处理过signed main()
{cin n m; // 读入网格大小和操作次数for (int i = 1; i = m; i++) // 读入 m 次操作的行号和列号cin r[i] c[i];for (int i = m; i = 1; i--) // 逆序遍历操作，从最后一次往前处理{// 如果当前操作的行和列都未被后续操作占用，则该棋子会保留到最后if (!used_r[r[i]] !used_c[c[i]])ans++;used_r[r[i]] = true; // 标记该行已被处理used_c[c[i]] = true; // 标记该列已被处理}cout ans endl; // 输出最终保留的棋子数量return 0;
}【运行结果】
3 6
1 1
1 2
3 3
3 2
1 3
1 3
2 火烈鸟门户网站开发动漫制作专业总结
火烈鸟门户网站开发,动漫制作专业总结,丽水市建设监理协会网站在哪里,admin后台管理系统【题目来源】
洛谷：AT_abc466_d [ABC466D] Placing Rooks
【题目描述】
There is a grid with \(N\) rows and \(N\) columns.
Initially, nothing is placed on the grid.
Starting from this state, Takahashi perf…
【题目来源】
洛谷：AT_abc466_d [ABC466D] Placing Rooks
【题目描述】
There is a grid with \(N\) rows and \(N\) columns.
Initially, nothing is placed on the grid.
Starting from this state, Takahashi performs \(M\) operations on the grid in order. The \(i\)-th operation \((1\leq i\leq M)\) is as follows.Remove all pieces placed on the cells in the \(R_i\)-th row from the top.
Next, remove all pieces placed on the cells in the \(C_i\)-th column from the left.
Finally, place a piece on the cell at the \(R_i\)-th row from the top and the \(C_i\)-th column from the left.Output the number of pieces placed on the grid after the \(M\) operations.
有一个 \(N\) 行 \(N\) 列的网格。
最初，网格上没有任何棋子。
从这个状态开始，高橋按顺序对网格进行 \(M\) 次操作。第 \(i\) 次操作 \((1\leq i\leq M)\) 如下：移除从上数第 \(R_i\) 行中所有已放置的棋子。
接着，移除从左数第 \(C_i\) 列中所有已放置的棋子。
最后，在从上数第 \(R_i\) 行、从左数第 \(C_i\) 列的格子上放置一个棋子。输出 \(M\) 次操作后网格上放置的棋子数量。
【输入】
The input is given from Standard Input in the following format:\(N\) \(M\)
\(R_1\) \(C_1\)
\(R_2\) \(C_2\)
\(\vdots\)
\(R_M\) \(C_M\)【输出】
Output the number of pieces placed on the grid after the \(M\) operations.
【输入样例】
3 6
1 1
1 2
3 3
3 2
1 3
1 3【输出样例】
2【核心思想】问题分析：在 \(N \times N\) 网格上进行 \(M\) 次操作，每次操作先清空第 \(R_i\) 行和第 \(C_i\) 列的所有棋子，然后在 \((R_i, C_i)\) 放置一枚棋子。求 \(M\) 次操作后网格上的棋子数量。这是一个逆序贪心 + 集合覆盖问题，核心在于分析每次操作对最终状态的影响——只有最后一次在某行或某列放置的棋子才可能保留。算法选择：逆序处理：从最后一次操作往前遍历，判断当前操作的棋子是否会被后续操作清除
行/列占用标记：用布尔数组记录某行或某列是否已被后续操作处理过关键步骤：读入数据：读取 \(N, M\) 和数组 \(R[1..M], C[1..M]\)
逆序遍历（\(i\) 从 \(M\) 到 \(1\)）：若 \(used\_r[R_i] = false\) 且 \(used\_c[C_i] = false\)：该棋子不会被后续任何操作清除（后续操作要么行不同要么列不同），\(ans \leftarrow ans + 1\)\(used\_r[R_i] \leftarrow true\)，\(used\_c[C_i] \leftarrow true\)输出结果：\(ans\)时间/空间复杂度：时间复杂度：\(O(M)\)，单次逆序遍历
空间复杂度：\(O(N + M)\)，存储操作数组和标记数组逆序贪心与覆盖分析的核心思想：后续操作的决定性：第 \(i\) 次操作放置的棋子 \((R_i, C_i)\) 会被后续操作 \(j i\) 清除，当且仅当存在某个 \(j\) 满足 \(R_j = R_i\) 或 \(C_j = C_i\)。因为操作 \(j\) 会先清空第 \(R_j\) 行和第 \(C_j\) 列
逆序视角的简化：从后往前看，若某行 \(R_i\) 和某列 \(C_i\) 都未被"后续"（即更晚的）操作处理过，则第 \(i\) 次操作的棋子一定保留到最后。一旦某行或某列被标记，所有更早的该行列操作都会被清除
贪心保留策略：每遇到一个新的（行, 列）组合就计数，因为后续不会再有操作同时清除这个特定的行和列
集合覆盖的本质：最终保留的棋子对应一个行集合和一个列集合，要求每个保留棋子的行和列都是唯一的，即构成一个部分匹配
适用于具有"后操作覆盖先操作"特征的问题，逆序处理可以将动态清除转化为静态判定【算法标签】
贪心
【代码详解】
#include bits/stdc++.h
using namespace std;
#define int long long
const int N = 300005; // 常量：最大操作次数int n, m; // n: 网格大小; m: 操作次数
int ans; // ans: 最终网格上的棋子数量
int r[N]; // r[i]: 第 i 次操作的行号
int c[N]; // c[i]: 第 i 次操作的列号
bool used_r[N]; // used_r[x]: 行 x 是否已被后续操作处理过
bool used_c[N]; // used_c[x]: 列 x 是否已被后续操作处理过signed main()
{cin n m; // 读入网格大小和操作次数for (int i = 1; i = m; i++) // 读入 m 次操作的行号和列号cin r[i] c[i];for (int i = m; i = 1; i--) // 逆序遍历操作，从最后一次往前处理{// 如果当前操作的行和列都未被后续操作占用，则该棋子会保留到最后if (!used_r[r[i]] !used_c[c[i]])ans++;used_r[r[i]] = true; // 标记该行已被处理used_c[c[i]] = true; // 标记该列已被处理}cout ans endl; // 输出最终保留的棋子数量return 0;
}【运行结果】
3 6
1 1
1 2
3 3
3 2
1 3
1 3
2