题目解析
给定的地图, 再给定组BOSS的所释放技能的信息
求出最后安全格子的数量
解题思路
有两种想法
1、
如果当前BOSS释放一行的技能时，那么在释放当前技能前的非安全区的地方是当前释放技能前的所有一列的技能
如下图橙色框框 框出的为当前释放技能前的所有一列的技能
如下图 红色框框为当前释放一行的技能
当前释放技能之前所有一列的技能与当前释放一行技能重叠的部分为绿色画出来的部分
当前释放完技能的安全区 = 当前释放技能前的安全区 - 当前的一行的数量 + 当前释放技能前的所有一列的技能数量
释放一列的技能同样如此
2、
将所有技能都往左下角堆，那么就是下图
橙色为一列的技能 红色为一行的技能 绿色为重叠部分
一列的格子数 n； 一行的格子数 m； 释放一行的技能数 h； 释放一列的技能数 p
利用TreeSet进行 行列的去重 来进行计算
代码
1
import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
public static void main(String[] args)
{
int n = sc.nextInt(), m = sc.nextInt(), q = sc.nextInt();
// 记录一行的技能
TreeSet<Integer> h = new TreeSet<Integer>();
// 记录一列的技能
TreeSet<Integer> p = new TreeSet<Integer>();
// 安全格子
int ans = n * m;
while (q-- > 0)
{
int op = sc.nextInt(), x = sc.nextInt();
if (op == 0)
{
if (h.contains(x))
continue;
ans -= m - p.size();
h.add(x);
} else
{
if (p.contains(x))
continue;
ans -= n - h.size();
p.add(x);
}
}
out.println(ans);
out.flush();
out.close();
}
static Scanner sc = new Scanner(System.in);
static PrintWriter out = new PrintWriter(System.out);
}
2
import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
static int N = (int) 1e6;
public static void main(String[] args)
{
int n = sc.nextInt(), m = sc.nextInt(), q = sc.nextInt();
TreeSet<Integer> res = new TreeSet<Integer>();
int h = 0, p = 0;
while (q-- > 0)
{
int op = sc.nextInt(), x = sc.nextInt();
int y = op * N + x;
if (!res.add(y))
continue;
if (op == 0)
h++;
else
p++;
}
out.println(n * m - (h * m + p * n - h * p));
out.flush();
out.close();
}
static Scanner sc = new Scanner(System.in);
static PrintWriter out = new PrintWriter(System.out);
}