Catshao

用户名：Catshao

访问量：25436

签　名：

stO KHIN Orz

等　　级
排　　名	174
经　　验	6730
参赛次数	6
文章发表	46
年　　龄	12
在职情况	学生
学　　校	双语
专　　业

　　自我简介：

TA的其他文章

【小灰】树状数组动画详解
浏览：159

vector、deque、list的速度和内存的比较
浏览：459

Dotcpp编程2021年七月月赛题面
浏览：707

你可能喜欢

【站外题解】小图灵热身赛T1-担担炮

　　作者: Catshao　　　　发表时间：2021-02-22 09:56:41 浏览：222　|　评论：0　

本题为yoj的[**担担炮**](http://oj.youdao.com/contest/105/problem/A)，但是题目需要密码才能访问。为了各位的观看体验我把原题也贴一下。

# Part 1 题目

## 描述

中国象棋中的“炮”的攻击规则为“隔子攻击”，即炮可以攻击到某个棋子当且仅当：
- 若炮和这个棋子位于同一行、或者同一列；
- 且炮和这个棋子之间恰好有1个棋子（0个或多于1个都不行）；

现在 `n∗n` 的棋盘上有 `m` 个炮，请你计算**有多少对炮可以相互攻击到**。

例如下图中，`x`代表炮，`.`代表空格子：

x x x
	. . x
	. . x

则 `(1, 1) / (1, 3)` 可以相互攻击、以及 `(1, 3) / (3, 3)` 可以相互攻击，答案为 2。

## 输入

第一行2个整数 `n`, `m`

接下来 `m` 行，每行2个整数  `(i, j)`  代表一个炮的位置，保证不会有2个炮在同一位置上

## 输出

输出一个整数，代表有多少对炮可以相互攻击到

## 样例

### 输入样例 1

3 5
	1 1
	1 2
	1 3
	2 3
	3 3
### 输出样例 1

### 输入样例 2

5 15
	5 1
	3 3
	1 1
	4 1
	2 1
	1 3
	5 2
	4 3
	3 1
	5 3
	4 5
	1 2
	2 5
	1 5
	3 5

### 输出样例 2

## 提示

### 数据范围

|  数据点         | 范围  |
| ------------   | ------------ |
| 对于30%的数据   |  n, m <= 10 |
| 对于60%的数据   |  n, m <= 100 |
| 对于80%的数据   |  n <= 10^5, m <= 100 |
| 对于100%的数据  | n, m <= 10^5  |

## 限制

时间限制：1s
内存限制：256M

# Part 2 题解

这道题的难点在于**存**这张图。首先我们看到[数据范围](#数据范围)中n达到了10^5，那么使用矩阵存这张图需要大约**9GB**的空间，会**MLE**。

我们通过观察发现，n为图的边长，而m为炮的个数。很明显，炮与图所有位置的比例为`1 : 10 ^ 5`，是一个**稀疏矩阵**。我们可以使用[**离散化**](https://blog.dotcpp.com/a/76610#Part%203%20%E7%A6%BB%E6%95%A3%E5%8C%96)，来使整张图变得紧凑。（离散化可能被构造出来的数据卡，比赛已经结束，无法提交新代码，因此不给出离散化的代码）

题目中采用的炮有两个特性：
1. **只能横着或者竖着走**，不能像马走日象走田一样。
2. **炮不计算两个子之间的空隙，只计算中间有几个子**

按照特性1，我们可以将整张图分开来，用`row[y]`来记录第`y`行的情况，用`col[x]`来记录第`x`列的情况。

按照特性2，既然不计算空隙，完全可以将空隙省掉。到这里我们已经把稀疏矩阵变成了装满东西的链表。但是，链表中装着啥呢？

```
row[1] = {true, true};
row[2] = {};
row[3] = {true, true};
...

col[1] = {true};
...
```

~~装了个寂寞。~~在之前我们用`bool`来记录每一个格子的情况，当空隙省掉后变成了清一色的`true`。我们完全可以只记录第`y`行有**多少个**炮，而不是详细记录下来。

到这里，我们已经把图压缩到极致了，空间为`2 * 10 ^ 5`。

### 样例2解释

样例1十分明显，这里我们拿样例2来举例子。

x x x x x
	x       x
	x   x x x
	
	x x x x

我们先看行`row`：
```
row[1] = 5
row[2] = 2
row[3] = 4
row[4] = 0
row[5] = 4
```

第一行有多少组炮能互相攻击呢？仔细一数发现有三对。
第二行没有，第三行为3，第四行没有，第五航为2。

发现了吗？每一行能成功互相攻击的炮为`row[i] - 2`，col经过计算同理，为`col[i] - 2`

我们只需要将其相加即可。

## 代码

```cpp
//
// Created by Cat-shao on 2021/2/21.
//

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 100100;
const long long INF = INT_MAX;

int main()
{
    int n, m, x, y, ans = 0;
    scanf("%d%d", &n, &m);

int row[MAX_N], col[MAX_N];
    // row为y，col为x
    for (int i = 0; i < m; ++i) {
        scanf("%d%d", &x, &y); // 按照行和列进行计数
        row[y] ++;
        col[x] ++;
    }

for (int i = 1; i <= n; ++i) {
        if (row[i] > 2) { // 有概率减成负数
            ans += row[i] - 2;
        }
        if (col[i] > 2) {
            ans += col[i] - 2;
        }
    }
// DEBUG时解封
//    printf("\nrow:");
//    for (int i = 1; i <= n; ++i) {
//        printf("%d ", row[i] - 2);
//    }
//    printf("\ncol:");
//    for (int i = 1; i <= n; ++i) {
//        printf("%d ", col[i] - 2);
//    }

printf("%d", ans);
    return 0;
}
```

-----------

这道题来自yoj的小图灵热身赛。

0.0分

1 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

Catshao

TA的其他文章

你可能喜欢

用筛法求之N内的素数。（C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

兰顿蚂蚁（C语言代码）

用筛法求之N内的素数。（C语言代码）

台球碰撞（C++代码）

【站外题解】小图灵热身赛T1-担担炮

评论区

精彩推荐

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

小九九（C语言代码）

数字整除（C++代码）——(22行代码)真的只需要两个变量就够了

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

小九九（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （Java代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

Catshao

TA的其他文章

你可能喜欢

用筛法求之N内的素数。 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

兰顿蚂蚁 （C语言代码）

用筛法求之N内的素数。 （C语言代码）

台球碰撞 （C++代码）

【站外题解】小图灵热身赛T1-担担炮

评论区

精彩推荐

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

小九九 （C语言代码）

数字整除 （C++代码）——(22行代码)真的只需要两个变量就够了

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

小九九 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （Java代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

用筛法求之N内的素数。（C语言代码）

兰顿蚂蚁（C语言代码）

用筛法求之N内的素数。（C语言代码）

台球碰撞（C++代码）

　　评论区

小九九（C语言代码）

数字整除（C++代码）——(22行代码)真的只需要两个变量就够了

小九九（C语言代码）