Day07 7.15总结

第一类：暴力(T1)

---

T1.小田不想打怪兽

题目传送门

本题真是 水沝渁淼㴇㵘 到家了，都能养 鱼䲆鱻䲜 了。

大致思路是：用一个变量 ans 每次记录要击杀的怪物只数(因为每只怪物都需要一下来让它们分裂) ，初始时的 h 记录每只怪物现在的血量， t 记录怪物的数量。显而易见，每次 ans 都要加上 t ，随后 h /= 2 (或 h >>= 1) ，最后 t *= 2 ，当所有怪物血量为 $0$ 时退出循环。

$Code:$

#include <bits/stdc++.h>
using namespace std;
int h, ans, t = 1;

int main ()
{
	freopen ("aoteman.in", "r", stdin);
	freopen ("aoteman.out", "w", stdout);
    cin >> h;
    while (h)
    {
        ans += t; //加上要打的怪兽数 
        t *= 2; //要打的怪兽数*2 
        h >>= 1; //但是血量减半(右移自带向下取整) 
    }
    cout << ans;
    return 0;
}

感受与学习：像这种在一次循环中有不同的变量做着许多不同的事时，应该先明确 变量职责 ，再理好 先后顺序 。

错误原因：无

---

第二类：简单算法(T2, 二维差分, T3, 双指针, T4, 位运算, T5, 模拟, T6, 普通运算)

---

T2.小田的异或炸弹

(╯‵□′)╯炸弹！•••*～● 本题首先可以想到的暴力解法是每次输入一个 $r$ ，枚举和 $x, y$ 曼哈顿距离小于等于 $r$ 的点并改变数组中的值，最后 cnt 统计 $1$ 的个数。

但是这样的时间复杂度是 $O(mn^2)$ ，会超时，要考虑优化。

可以看到，一开始矩阵的所有元素都为 $0$ ，经过 $1$ 次异或变成 $1$ ，经过 $2$ 次变成 $0$ ， $3$ 次变成 $1$ ...... 经过奇数次变成 $1$ ，偶数次变成 $0$ ，所以第一个可以想到的是可以统计每个位置异或的次数，是奇数则 cnt ++ 。

但是这和直接改变数组的值没什么区别，时间复杂度依然是 $O(mn^2)$ ，依然要优化。

可以想到，曼哈顿距离小于等于 $r$ 其实就是走 $r$ 个格子能到达的所有地方，所以我们可以遍历每一行，算出从第 $x$ 行到每一行的行距，如果行距 $< 0$ 则说明无论走多少格都到不了这里，那么直接 continue 。

而如果行距 $\ge 0$ 说明可以到达这里，那么这一行的某些格子(或某列)就要加上 $1$ (为了以后判断奇偶性) ，那么究竟是哪些格子可以走到呢？枚举的每一行 $i$ 到给定的第 $x$ 行的距离明显就是 $|x - i| \rightarrow abs(x - i)$ 。$abs (x - i)$ 就是我们从第 $x$ 行到 $i$ 行走的 格子数 。设 $w = abs (x - i)$ ，也就是竖着走了 $w$ 格，那么还有几格可以让我们在 横方向 走呢？很明显，是 $r - w$ 格。又设 $h = r - w$ ，也就是 横走的格数 ，那么 $h$ 如果是负数，说明 不能横向走 ，直接 continue 。

随后，我们就可以将第 $i$ 行的一些格子的状态改变了，也就是将某些值加上 $1$ (判断奇偶性) 。在这里，我们纵向走了 $w$ 格之后，既能往左走 $h$ 格，也能往右走 $h$ 格，所以我们要将 $g[i][y - h], g[i][y - h + 1] ... - g[i][y + h - 1], g[i][y + h]$ 这一段值全部 $+ 1$ 。不过要注意， $y - h$ 和 $y + h$ 可能会越界，所以我们可以将 $y - h$ 和 $1$ 取最大值， $y + h$ 和 $n$ 取最小值。

现在看到"全部加 $1$" 是不是觉得有点眼熟？没错，就是用我们的 差分 来实现的，我们只需要将 csub[i][y - h] ++ ， csub[i][y + h + 1] -- 就能实现从 $y - h$ 到 $y + h$ 全部加 $1$ ，只需要最后反求一遍前缀和并统计奇数的个数就好了。不过注意！这里是每行分别求前缀和，按一维前缀和的方法求。

$Code:$

#include <bits/stdc++.h>
using namespace std;
const int N = 3e3 + 10;
int n, m, csub[N][N], cnt;

int main ()
{
	freopen ("boom.in", "r", stdin);
	freopen ("boom.out", "w", stdout);
    cin >> n >> m;
    while (m --)
    {
        int x, y, r; cin >> x >> y >> r;
        for (int i = 1; i <= n; i ++)
        {
            int w = abs (x - i), h = r - w;
        	if (h < 0) continue;
        	int l = max (1, y - h), r = min (n, y + h);
        	csub[i][l] ++, csub[i][r + 1] --;
		}
    }
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= n; j ++)
        {
            csub[i][j] += csub[i][j - 1];
            if (csub[i][j] % 2 == 1) cnt ++;
        }
    }
    cout << cnt;
    return 0;
}

感受与学习：本题就是一道二维差分的例题，只需要将问题的几个部分转化为更简单的问题，如 异或 其实就是加 $1$ 并判断奇偶性，这样就可以让我们的问题更明了，更方便理解，就可以运用以前学过的知识来写了。

错误原因：没有转化一些看似很复杂的题面部分，考试时根本没有往 差分 这方面去想，下次应该将复杂的题面联系到自己学过的知识并加以综合运用。

---

T3.小田的钻石

题目传送门

暂未做出 ...

---

T4.小田的01背包

题目传送门

暂未做出 ...

---

T5.小田抓牛

题目传送门

本题应该是这次考试最纯正的模拟题，只需要每次模拟它们的移动方向即可。移动方向如下：

• 用两个变量 $cx, cy$ 记录牛的位置，初始时判断字符 'C' 在哪里， $cx$ 和 $cy$ 就赋值为当时的 $i$ 和 $j$ 。记录小田位置的 $tx, ty$ 同样处理，判断字符 'T' 的位置即可。

• 用两个变量 $cgox, cgoy$ 记录当前牛面朝的方向(值只可能是 [-1, 0], [0, -1], [1, 0] 和 [0, 1] 代表行走时 $cx, cy$ 加上的值) ，对应小田的 $tgox, tgoy$ 同理。

• 用一个 tme 变量记录当前时间。另外，对死循环的判断是：一共有 $10 \times 10 = 100$ 个格子，每个格子都有 $4$ 种状态，牛的行走状态就有 $4 \times 100 = 400$ 个格子，所以共有 $400$ 种状态。又乘上小田的 $400$ 种状态，共有 $400 \times 400 = 160000$ 种状态，所以只要 tme >= 160000 ，就输出 $0$ 并结束。

• 初始化 cgox = -1, cgoy = 0, tgox = -1, tgoy = 0 ，表示向北(上) 。对于牛，每次定义两个变量 ncx, ncy 表示牛将要去的地方的坐标 (ncx = cx + cgox, ncy = cy + cgoy) ，小田的坐标亦如此。如果 g[ncx][ncy] != '*' 说明牛要去的地方没有障碍物，可以直接将 cx 赋值为 ncx ， cy 赋值为 ncy ，不过要处理越界的问题，越界则不处理。如果前方有障碍物，那么转向，写一个 Move (int &x, int &y) 函数判断 (x, y) 的值的不同情况。情况如下：

  void Move (int &x, int &y)
  {
      if (x == -1) x = 0, y = 1;
      else if (y == -1) x = -1, y = 0;
      else if (x == 1) x = 0, y = -1;
      else x = 1, y = 0;
  }
  

  小田的移动大致相同，不过换成了 tx, ty 和 ntx, nty 。

• 如果 cx == tx && cy == ty ，说明小田已经追上了牛，那么直接输出 tme 并退出。

$Code:$

#include <bits/stdc++.h>
using namespace std;
char g[15][15];
int cx, cy, tx, ty, cgox = -1, cgoy, tgox = -1, tgoy;
int tme;

void Move (int &x, int &y)
{
    if (x == -1) x = 0, y = 1;
    else if (y == -1) x = -1, y = 0;
    else if (x == 1) x = 0, y = -1;
    else x = 1, y = 0;
}

int main ()
{
	freopen ("cow.in", "r", stdin);
	freopen ("cow.out", "w", stdout);
    for (int i = 1; i <= 10; i ++)
        for (int j = 1; j <= 10; j ++)
        {
            cin >> g[i][j];
            if (g[i][j] == 'C') cx = i, cy = j;
            else if (g[i][j] == 'T') tx = i, ty = j;
        }
    while (true)
    {
    	if (tme > 160000) {cout << 0; return 0;}
        if (tx == cx && ty == cy) {cout << tme; return 0;}
        int ntx = tx + tgox, nty = ty + tgoy;
        if (g[ntx][nty] != '*' && ntx >= 1 && ntx <= 10 && nty >= 1 && nty <= 10)
            tx = ntx, ty = nty;
        else Move (tgox, tgoy);
        int ncx = cx + cgox, ncy = cy + cgoy;
        if (g[ncx][ncy] != '*' && ncx >= 1 && ncx <= 10 && ncy >= 1 && ncy <= 10)
            cx = ncx, cy = ncy;
        else Move (cgox, cgoy);
        tme ++;
    }
    return 0;
}

感受与学习：本题是一道纯模拟，对于这种模拟，最重要的是变量的用处，其次是先后顺序，注意代码的目的并思考怎么能达到这个目的。

错误原因：无

---

T6.小田的分数转换

题目传送门

暂未做出 ...