Day04 7.11总结

第一类：暴力(T1, T2)

---

T1.小田的四则运算

题目传送门

本题应该是有史以来最水的一题，不过仍然要分类讨论。

注意 ：以下思想均建立在 $a \le b \le c$ 的条件下(升序排列) ，如果题目不保证升序排列，那么请将 $a, b, c$ 按从大到小排列好了再进行运算。

1. 一开始可以想到最大的是 a * b * c ，但是这只是没有 $1$ 的情况。
2. 有 $1$ 的情况有两种。第一种是 $a = 1$ (或 $a, b$ 都是 $1$ ) ，这样的话， $a \times b \times c = b \times c$ ，但这不是最佳方案，最佳方案为 $(a + b) \times c$ ，因为这样 $(a + b) \times c = ac + bc = c + bc$ ，比第一种方案优。
3. 最后有一种特殊情况： $a = b = c = 1$ ，这样的话， $a \times b \times c$ 和 $(a + b) \times c$ 一个为 $1$ ，一个为 $2$ ，都不是最优方案，最优的是 $a + b + c$ ，为 $3$ 。

综上所述，可以得出：(伪)

$\operatorname{Input : a, b, c}$

$\operatorname{Output : \max(ans)}$

$\operatorname{if (a = 1 \ and \ b = 1 \ and \ c = 1)}$ $\operatorname{Output (3) \ exit.}$

$\operatorname{if (a > 1) \ Output (a \times b \times c)}$

$\operatorname{else \ Output ((a + b) \times c)}$

可以看到是在取最大值，所以可以优化：(伪)

$\operatorname{Input : a, b, c}$

$\operatorname{Output : \max (a \times b \times c, (a + b) \times c, 3)}$

$Code:$

#include <bits/stdc++.h>
using namespace std;
int a, b, c;

int main ()
{
	freopen ("math.in", "r", stdin);
	freopen ("math.out", "w", stdout);
    cin >> a >> b >> c;
    cout << max (a * b * c, (a + b) * c, a + b + c);
    return 0;
}

感受与学习：本题我知道了要考虑在不同情况下可以达成的最优情况，如本题的有没有 $1$ 的情况。

错误原因：无

---

T2.小田的gcd构造

题目传送门

本题是一道很像数学题且看上去很难的题，但仔细一看一想， $1 \le x, y, z \le 10^{18}$ ， $1 \le a, b \le 5 \times 10^{18}$ ，那么只要让 $a, b$ 足够大，那么不就能轻松满足前两个条件： $|a + b| \ge x, |a - b| \ge y$ 了吗？至于第三个条件 $\gcd (a, b) = z$ ，那么只要让 $a, b$ 都是 $z$ 的倍数就好了。但是这里要注意：有一个差值 $|a - b|$ ，所以我们要让 $a$ 尽可能小， $b$ 尽可能大。那么一个可以设为 $z \times 1 = z$ ，另一个可以设为 $5e18 \div z \times z$ ，由于整除的存在，所以 $5e18 \div z \times z$ 就是 5e18 范围里最大的 $z$ 的倍数了。

要用 long long !

$Code:$

#include <bits/stdc++.h>
using namespace std;
long long x, y, z;

int main ()
{
	freopen ("gcd.in", "r", stdin);
	freopen ("gcd.out", "w", stdout);
    cin >> x >> y >> z;
    cout << z << ' ' << (long long)5e18 / z * z;
    return 0;
}

感受与学习：在一道数学题(或看着像数学题)中，应该找到题目中的突破点(或漏洞) 。根据不同的突破点和数学性质来解题，如 $\gcd$ ，因倍数，质数 / 合数等。

错误原因：没有发现前两个条件的漏洞，不知道如何满足，导致被这两个条件卡了好久(甚至连数据范围的差距都没发现) ，下次做数学题要善于发现突破口，如 $\gcd (x, x的倍数) = x, lcm(n,m) \times \gcd (n, m) = n \times m$ 等。

---

第二类：简单算法(T3)

---

T3.小田的山峰数组

题目传送门

本题的暴力算法可以想到每次先枚举第一个区间的终点，再枚举第二个区间的终点，时间复杂度为 $O(n^2)$ ，只能拿二十分，需要考虑优化。

可以思考：如果用一个 $i$ 来枚举第一个区间的终点，并省略掉第二重枚举第二个区间终点的一些无用答案，基本就能将时间复杂度降到 $O(n)$ 至 $O(2n)$ 之间。那么第一个可以想到的优化是用前缀和优化，可以方便的求 $[a_1, a_2, a_3...a_{i - 1}],[a_i, a_{i + 1}, a_{i + 2}...a_{j - 1}, a_j],[a_{j + 1}, a_{j + 2}...a_n]$ 三个数组的和来判断是不是山峰数组。

进一步思考：假设当前枚举出了一个第一个区间的终点 $i$ ，现在我们一直往右边找，找到某个第二个区间的终点 $j$ 并且 $(i, j)$ 符合条件，并且在一直找的过程中 $j$ 是第一个能与 $i$ 组合满足条件的终点，那么思考：现在 $(i, j)$ 这个符合条件的数对能够贡献多少符合条件的可能性呢？可以想到如果现在这个数组符合条件，那么如果 $i$ 往左移或是 $j$ 往右移，有更多新的元素进到中间的数组中，那么中间数组的和必然变大，也一定是符合条件的。但是由于 $i$ 往左移的答案在之前被求过了，那么就只有 $j$ 往右移的可能性了。从 $j$ 到最右边的 $n$ ，一共有 $n - j - 1$ 个元素，再加上 $j$ 自己一个，共有 $n - j$ 种新可能，所以 ans += n - j;

现在所有 $i, j$ 的可能性都加上了，需要开始移动 $i$ 了，在移动 $i$ 的过程中 $j$ 是不变的，那么在 $i$ 移动的过程中需不需要更新答案呢？其实是不需要的。为什么呢？因为在 $i$ 往右边的过程中，数组中的元素一个一个被弹出，加上 $j$ 是第一个和 $i$ 满足条件的数对，一边弹出元素，一边中间元素减少，就不会保持为山峰数组了，所以 $i$ 往右移时是不可能有答案的。

那么 $j$ 只会一直往右移， $i$ 也只会一直往右移，时间复杂度 $O(n)$ 。

$Code:$

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n, a[N], qsum[N];
int ans, j = 2;

signed main ()
{
	freopen ("mountain.in", "r", stdin);
	freopen ("mountain.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        qsum[i] = qsum[i - 1] + a[i];
    }
    for (int i = 1; i < n - 1; i ++)
    {
    	if (qsum[i] >= qsum[n] - qsum[i]) break;
        while (qsum[i] >= qsum[j] - qsum[i] || qsum[j] - qsum[i] <= qsum[n] - qsum[j]) j ++;
        ans += n - j;
    }
    cout << ans;
    return 0;
}

感受与学习：本题我明白了在做一道双指针的题时，应该仔细思考指针的第一个是什么，第二个是什么，用什么指针，第二个指针要在什么时候走，第一个指针又要什么条件下才能走(能把人逼疯) ，应该考虑周全。

错误原因：知道是双指针，但不知道怎样实现，不知道如何让 $j$ 走的时候 不回头 ，降不下来时间复杂度，没有考虑到如何将所有无用的答案排除掉(这恰恰是双指针的关键) 。

---

第三类：数据结构(T4, 队列&模拟)

---

T4.Dota2参议院

题目传送门

本题是一道纯纯的大模拟，首先可以发现这个投票至多只会执行 两轮 ，肯定有一方会把另一方的参议员全部禁言，哪怕人数一样也是这样。

但是光有这个思想还不太够，如何实现是一个难题，不用优化很难写(一片混乱)。所以要用数据结构来优化。至于什么数据结构，适应这种环境的就只有 队列 了。

用队列去优化。开始两方各有一个队列，队中的元素记录的是双方参议员从前往后的下标。每次判断两队队首元素(位置的大小) ，谁小就说明哪方可以先做出行动，也就是禁止掉对方队首的人的权利。每次一个参议员行使完权利时就会被移到队列的最后，并将他原本在队列中的位置加上 $n$ ，然后将他现在的位置 pop 掉，而另一个被禁的人也会被 pop 掉，只不过不会在队尾再次加上自己而已。所以每次两边队首的人都会被弹出，区别只在于哪方能再次出场而已。那么可以很容易想到用 while 去模拟，条件是双方队列都不为空，这样投票就可以继续进行。

而如果循环结束了，就说明有一方的队列空了(也就是有一方全部没人了) ，这时判断哪方队列为空并输出对方阵营代表对方胜利即可。

$Code:$

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

int main ()
{
    freopen ("dota.in", "r", stdin);
    freopen ("dota.out", "w", stdout);
    cin >> t;
    while (t --)
    {
        string s;
        cin >> s;
        int n = s.size ();
		queue <int> qR, qD;
        for (int i = 0; i < n; i ++)
            if (s[i] == 'R') qR.push (i);
            else qD.push (i);
        while (qR.size () && qD.size ())
        {
            if (qR.front () < qD.front ()) qR.push (qR.front () + n);
            else qD.push (qD.front () + n);
            qR.pop (), qD.pop ();
        }
        if (qR.empty ()) cout << "Dire\n";
        else cout << "Radiant\n";
    }
    return 0;
}

感受与学习：本题依然是大模拟，只是需要用数据结构优化。下次我应该对使用数据结构的场景进行熟悉，如：模拟树、深搜、运算(表达式求值)时用栈；约瑟夫问题、模拟任务调度时用队列。

错误原因：模拟时思维混乱，草稿云里雾里(看不懂) ，想不到用什么方式表示各种各样的复杂的变量，十分的 头昏脑涨 混乱不堪，下次注意。

---

第四类：搜索(T5, 广搜)

---

T5.小W走迷宫

题目传送门

本题是一道非常水的纯广搜模版题，甚至连刚学完广搜例题(走迷宫) 的人都能做出来 虽然我没做出来 。基本上和广搜例题一模一样，只不过改了起点和终点位置，其他什么都没有变。

用一个 vis[][] 标记数组来标记已经走过的点， g[][] 表示原地图， dx[], dy[] 方向数组记录方向。每次遇到能走的点就将其加入队列中，遇到越界跳过，遇到已经走过的点或是地图上不能走的点跳过，随后将这个点标记，把每一条路的路径都走出来，最终第一个到达终点的路径就是最短的了。

$Code:$

#include <bits/stdc++.h>
using namespace std;
int n, m;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
char mg[25][25];
bool vis[25][25];

struct mazeJ
{
    int x, y;
    int step;
};

queue <mazeJ> rd;

int BFSrd ()
{
    while (rd.size ())
    {
        int x = rd.front ().x, y = rd.front ().y;
        int now = rd.front ().step; rd.pop ();
        if (mg[x][y] == '*')
            return now;
        for (int i = 0; i < 4; i ++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 1 || nx > n || ny < 1 || ny > n) continue;
            if (vis[nx][ny] || mg[nx][ny] == '#') continue;
            rd.push ({nx, ny, now + 1});
            vis[nx][ny] = true;
        }
    }
    return -1;
}

int main ()
{
	freopen ("mg.in", "r", stdin);
	freopen ("mg.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            cin >> mg[i][j];
            if (mg[i][j] == '@') rd.push ({i, j, 0});
        }
    cout << BFSrd ();
    return 0;
}

感受与学习：本题真的是一道模版题，只有 50 分是因为 粗心 眼瞎没有在将能走的点走完后标记这个点，导致有的地图可能会死循环，下次再遇到模版题时，一定要认真仔细检查，不能有任何错误。

错误原因：同上，眼瞎。应该好好温习一下模版题。

---

第五类：图论(T6, Dijkstra最短路)

---

T6.小W去旅行

题目传送门

本题又是一道裸的模板题 (虽然我又双叒叕没做出来) 。可以看到 $1 \le n \le 20, 1 \le m \le n (n - 1) \div 2 \rightarrow \max:190$ ，数据范围非常的小(用 $O(n^3)$ 的 $Floyd$ 都能过) ，加上只有正权边，所以可以用朴素 Dijkstra 来做。不过相比于原题，本题还是有一些不一样的地方。如没有重边，是无向图(两个城市间可以互相去) ，输出时如果没有路径则输出" No path " ，并且要求不是从 $1$ 号点到 $n$ 号点等。让我们一个一个解决。(为方便，下文将题目所述的 a 和 b ，也就是起点和终点，统称为 st 和 ed )

1. 无向图：在用邻接矩阵存图时，不仅要赋值 g[x][y] 为 z ，还要将 g[y][x] 也赋值为 z 。

2. 输出 No path ：这个很好办，在主函数判断一下，如果 Dijkstra () 返回的值为 $-1$ ，则输出 No path ，否则输出 dist[ed] 。

3. 要求不是从 $1$ 号点走到 $n$ 号点：这个乍一看好像很难做到，可能会想到类似 Floyd 的思想：如果我按 Dijkstra 的思想写，万一可以通过别的路径到达点 ed 呢？

   但这样的情况其实是不会发生的，因为 图中只有正权边 ，所以从 st 到 ed 的最短路是一定的，不可能可以通过其他点到达且路径更短(这只在负权图里才有) 。

   Tips: 本题要求的起点不是 $1$ ，而是 $st$ 。所以初始化 dist 时不是 dist[1] = 0 ，而是 dist[st] = 0 。

$Code:$

#include <bits/stdc++.h>
using namespace std;
int n, m, g[25][25];
int dist[25], st, ed;
bool vis[25];

int Dijkstra ()
{
    memset (dist, 0x3f, sizeof (dist));
    dist[st] = 0;
    for (int i = 1; i < n; i ++)
    {
        int x = -1;
        for (int j = 1; j <= n; j ++)
            if (! vis[j] && (x == -1 || dist[j] < dist[x])) x = j;
        vis[x] = true;
        for (int y = 1; y <= n; y ++)
        	if (g[x][y] != 0x3f3f3f3f && dist[y] > dist[x] + g[x][y])
        		dist[y] = dist[x] + g[x][y];
    }
    if (dist[ed] == 0x3f3f3f3f) return -1;
    return dist[ed];
}

int main ()
{
	freopen ("city.in", "r", stdin);
	freopen ("city.out", "w", stdout);
    cin >> n >> m;
    memset (g, 0x3f, sizeof (g));
    for (int i = 1; i <= n; i ++) g[i][i] = 0;
    for (int i = 1; i <= m; i ++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        g[x][y] = min (g[x][y], z);
        g[y][x] = min (g[y][x], z);
    }
    cin >> st >> ed;
    int ans = Dijkstra ();
    if (ans == -1) cout << "No path";
    else cout << ans;
    return 0;
}

感受与学习：本题已经水得不能再水了(可是我错了) ，考试时知道是 Dijkstra ，也能背模版，但却不知道在原模版的基础上怎么样改，我注意到了无向图和 No path 的输出，也知道要将模版中的 $1$ 和 $n$ 改成 $st$ 和 $ed$ ，但在改 $st$ 和 $ed$ 时却不知道怎么改，怎么也改不对。

错误原因：对模版掌握不扎实，导致考试时只是改了一个小小的起终点，就 使我头脑旋转 错了。应对最短路、搜索、基础算法(如高精度) 、建图的两种方法等模版在心里记牢，烂熟于心。