Day01 7.8总结

第一类：暴力题(T1, T2)

T1.小田的宝石镇

题目传送门

这题比较简单，根据下图我们能很容易看出从 11 点出发，去到所有点只有两种不同的最优方案。图见下。

两种最优方案分别是：A×5+BA \times 5 + B

和 11∗A11*A 。

第一种方案说明：从点 11 花 11 个 AA 的时间到达边上的任意一个点，如点 22 。再从这个点 ( 22 ) 到达周围的 55 个点，花费 5×B5 \times B 的时间 。

第二种方案说明：从点 11 开始，每次花 AA 时间到达边上的一个点 ( 22 ~ 77 ) ，再花 AA 时间回到点 11，每到一个点再回来都要 2×A2 \times A 的时间，不过到最后一个点时不用再回来，少走一个 AA 的时间，最后时间为 2×A×6−A=11×A2 \times A \times 6 - A = 11 \times A 。

最后判断哪种方案用时少即可。

注意: A,B≤1012A, B \le 10^{12} ，记得开 long long 。

Code:Code:

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

int main ()
{
    freopen ("gem.in", "r", stdin);
    freopen ("gem.out", "w", stdout);
    cin >> a >> b;
    if (11 * a > a + 5 * b) cout << a + 5 * b;
    else cout << 11 * a;
    return 0;
}

感受与学习：本题我认识到了分类讨论的重要性，并且要注意看数据范围，记得开 long long ！

错误原因：没有仔细思考每一种最优情况，将一个本来不是最优情况的可能性写了上去，以后在做这种有些偏思维的题时应该认真思考所有可能性(或最优的几种) ，做到不重不漏，刚好涵盖所有情况。

T2.小田的好数组

题目传送门

本题题目大意为给你一个数组，请取出一个子序列使得升序排列后与原数组排列 不完全相同 。

第一步可以想到答案要么为 00, 要么为 nn 。因为如果一个子序列满足排列后与原数组排列 不完全相同 ，那么在加上数组的其他元素后也 不完全相同 (不影响) ，那么只有全升序的数组才是输出 00。

进一步思考，会发现可以遍历从 a1a_1 到 an−1a_{n - 1} ，只要当前 ai>ai+1a_i > a_{i + 1} ，说明该数组是非升序排列的，输出 nn ，到最后则输出 00 。

注意 ：如果 n=1n = 1 ，要特判，输出 00 。

Code:Code:

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

int main ()
{
	freopen ("hsz.in", "r", stdin);
	freopen ("hsz.out", "w", stdout);
	cin >> n;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	if (n == 1) {cout << 0; return 0;}
	for (int i = 1; i < n; i ++)
		if (a[i] > a[i + 1]) ans = n;
	cout << ans;
	return 0;
}

感受与学习：本题我知道了在一些很复杂、有许多条件的情况下要理清题目意思，多想解决方案，才能化繁为简，做出题目。

错误原因：无

第二类：前缀和(T3)

T3.小田的数字合并

题目传送门

本题可以想到对于 aa 中的任意一个元素，都可以作为减数来减，只要添加最大值就好。那么可以用一个前缀和+后缀和维护数组从前往后/从后往前的和，并在求和的过程中一边用 abs 求极差最大值，输出即可。

注意：本题 ai≤109a_i \le 10^9 ，求和时要开 long long 。

Code:Code:

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

signed main ()
{
    freopen ("num.in", "r", stdin);
    freopen ("num.out", "w", stdout);
	cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        t[i] = a[i];
    }
    for (int i = 1; i < n; i ++)
    {
        a[i] += a[i - 1];
        ans = max (ans, abs (a[i] - a[i + 1]));
    }
    for (int i = n; i > 1; i --)
    {
        t[i] += t[i + 1];
        ans = max (ans, abs (t[i] - t[i - 1]));
    }
    cout << ans;
    return 0;
}

感受与学习：本题考察前缀和的应用，我明白了在做题时应该画图思考每一步，思考会出现的可能性。

错误原因：没有打好草稿，思考片面，认为情况是自以为的 单一性 ，在做出来后没有检查正确性，认为自己的答案一定是正确的(我的做法是判断左右两边直接加 n−1n - 1 个元素)。

第三类：数据结构(T4, 栈 stack)

T4.化学式的原子数

题目传送门

本题使用栈+哈希表实现

  1. 初始化一个哈希栈 stack <map <string, int> > ato; ，记住这里 unordered_map 不能用。
  2. 初始推进一个空键值对 ato.push ({}); 。
  3. 循环遍历字符串的每一位，遇到左括号则新建空键值对 ato.push ({}); ，右括号则找括号之前的哈希表并加到上一个哈希表下。是字母则将字符串与对应的值更新。
  4. 最后输出。

右括号操作提示：

  1. 先用一个临时 map 存储栈顶元素并弹出，再用临时一个数据存储临时 map 哈希表对应的数字。
  2. 再用一个数字存储现在(上一级)哈希表的数字，将它与这一级的数字相乘，得到上一级的数字，并将临时 map 的键上的值加上去。

Code:Code:

#include <bits/stdc++.h>
using namespace std;
stack <map <string, int> > ato;
string s;
int i, len;

int CntAtom ()
{
    if (i == len || ! isdigit (s[i])) return 1;
    int res = 0;
    while (isdigit (s[i]) && i < len)
        res = res * 10 + s[i] - '0', i ++;
    return res;
}

string SubAtom ()
{
    string res = "";
    res += s[i ++];
    while (i < len && s[i] >= 'a' && s[i] <= 'z')
        res += s[i ++];
    return res;
}

int main ()
{
    freopen ("atom.in", "r", stdin);
    freopen ("atom.out", "w", stdout);
    cin >> s; len = s.size ();
    ato.push ({});
    while (i < len)
    {
        if (s[i] == '(')
        {
            i ++;
            ato.push ({});
        }
        else if (s[i] == ')')
        {
            i ++;
        	int x = CntAtom ();
            map <string, int> mt = ato.top (); ato.pop ();
            for (auto itr : mt)
            {
            	string ts = itr.first;
            	int t = itr.second;
            	ato.top ()[ts] += t * x;
			}
        }
        else
        {
            string ts = SubAtom ();
            int tn = CntAtom ();
            ato.top ()[ts] += tn;
        }
    }
    for (auto itr : ato.top ()) cout << itr.first << ' ' << itr.second << '\n';
    return 0;
}

感受与学习：本题我明白了在一道数据结构的题前要思考好用什么数据结构(如本题栈+哈希表)。相信自己对于用法的判断(前提是你对本知识面足够熟悉) 。

错误原因：不相信自己的判断，没有用哈希表，应该以后对自己做的题需要用的算法和数据结构作出清晰明了、精辟准确的判断。

第四类：搜索(T5, 深搜DFS)

T5.小W挖宝藏

题目传送门

本题通过题面描述可以想到用深搜去做，但由于从 n,mn, m 中每个点都可能成为起点，所以要每个点都搜一遍。

暴力伪代码：

$$\mathbf {Input: \to n,m,a_{[110], [110]}} \\ \mathbf {Output: \to \max(\operatorname{DFSrd}(i_1,j_1)...\operatorname{DFSrd}(i_n,j_m))} \\ \mathbf {var \ list \ dx=\{-1,0,1,0\}, var \ list \ dy=\{0,1,0,-1\}} \\ \mathbf{\operatorname{DFSrd}(x,y) \ begin \to} \\ \mathbf{for \ 0 \sim 4 \to} \\ \mathbf{var \ nx \leftarrow x + dx(now)} \\ \mathbf{var \ ny \leftarrow y + dy(now)} \\ \mathbf{if(nx,ny \ Go=true \ and \ LongRange=false) \to} \\ \mathbf{\operatorname{DFSrd}(nx,ny).} \\ \mathbf{end.} \\ \mathbf{end.}$$

但这样的话每个点都有四个方向能走，时间复杂度 O(4nm)O(4^{nm}) ，需要优化。

但是我们可以发现在递归的途中有些点会重复走，如何判断当前点有没有走过了呢？答案显而易见了，记忆化搜索 ！

使用一个 f[x][y]f[x][y] 数组标记从选择的起点到 x,yx, y 能获得的最多的宝藏数，同时也能用来标记当前点有没有走过。(记忆化数组)

Code:Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m, mot[N][N], f[N][N], ans, ox, oy;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int DFSrd (int x, int y)
{
    if (f[x][y] > 0) return f[x][y];
    for (int i = 0; i < 4; i ++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx <= n && ny >= 1 && nx >= 1 && ny <= m && mot[nx][ny] < mot[x][y])
        {
            int t = DFSrd (nx, ny);
            f[x][y] = max (f[x][y], t + 1);
        }
    }
    return f[x][y];
}

int main ()
{
    freopen ("treasure.in", "r", stdin); 
    freopen ("treasure.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++) cin >> mot[i][j];
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= m; j ++)
        {
            int t = DFSrd (i, j) + 1;
            if (t > ans)
            {
            	ans = t;
            	ox = i, oy = j;
			}
        }
    }
    cout << ox << ' ' << oy << '\n' << ans;
    return 0;
}

感受与学习：本题我明白了我知识的薄弱面(搜索)，要对本知识进行加强复习。

错误原因：搜索知识不牢，没用记忆化，应该好好复习搜索题(特别是深搜，广搜都好一些 因为广搜的例题走迷宫有游戏的感觉所以记了下来 )。

第五类：DP(T6, 线性DP)

T6.小z的等待时间

题目传送门

本题是一道 简简单单 普通的DP。

f[i]f[i] 的状态表示为第 ii 朵小花被吹成高度 00 所需要的时间。那么 f[i]f[i] 有两种情况：f[i+1]>f[i]f[i + 1] > f[i] 和 f[i+1]≤f[i]f[i + 1] \le f[i] 。第一种情况是要等 f[i+1]f[i + 1] 变得比 f[i]f[i] 小一个单位时 f[i]f[i] 才能也被吹，那么

f[i]=f[i+1]+1f[i] = f[i + 1] + 1

(要差一个单位) ，而第二种情况则本来 f[i]f[i] 就能被吹到，不用更新，最后 f[1]f[1] 就是答案。

Code:Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, a[N];

int main ()
{    
    freopen ("flowers.in", "r", stdin);
    freopen ("flowers.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = n - 1; i >= 1; i --)
        if (a[i] < a[i + 1]) a[i] = a[i + 1] + 1;
    cout << a[1];
    return 0;
}

感受与学习：我知道了对于一道DP ，最重要的是知道要用DP，然后要知道怎么推状态转移方程和状态表示，我还需要对推状态转移方程多加练习。

错误原因：对推状态转移方程不熟练，需多加练习DP，特别是线性DP和背包，因为这两者是普及组常考的题。

  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 26ms
  4. Powered by Hydro v5.0.0-beta.13 Community