root 的博客
Day1 题解
root LV27 至高道祖 LV 1 SU @ 2024-7-20 13:35:37

T1 小田的宝石镇

题目描述

小田为你准备了七块宝石，它们分别分布在七个不同的地点，宝石之间有道路相连，如下图所示。与中心点相连的道路通过时间为 $A$ 秒，其余道路通过时间为 $B$ 秒，到达地点即可获得宝石，现在你从中心点出发，请问你拿到七块宝石的最短时间是多少呢？

输入描述

输入包含一行。第一行两个正整数 $A,B$ ，表示道路的通过时间。

输出描述

输出包含一行一个整数，表示拿到所有宝石的最短时间。

输入输出样例

输入 #1

2 2

输出 #1

输入 #2

1 3

输出 #2

说明/提示

【样例 1 解释】 一种可行的方案是 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 7$，总耗费时间为 $A+B+B+B+B+B=12$ 。 【数据范围】 对于 $10 \%$ 的数据，有： $A = B$ 。对于 $20 \%$ 的数据，有： $1 \le A,B \le 100$ 。对于所有测试数据，有： $1 \le A,B \le 10^{12}$ 。

题目解析

易看出，本题的最短路线只有两种选择: 一种是每次走从一号走到其他点，再回到一号点，走完所有点一共要走 $11$ 段距离为 $A$ 的线段： $1->2->1->3->1->4->1->5->1->6->1->7$

另一种是从一号点走到其他点后，直接走长度为 $B$ 的线段绕一圈，例如： $1->2->3->4->5->6->7$ 一共要走 $1$ 条长度为 $A$ 的线段和 $5$ 条长度为 $B$ 的线段。

所以最短距离就是从两者中选更小那个即可。

示例代码：

#include <bits/stdc++.h>  
using namespace std;  
  
long long a, b;  
  
int main() {  
    cin >> a >> b;  
  
    cout << min(11*a, a+5*b);  
    return 0;  
}

T2 小田的好数组

题目描述

小田得到了一个长度为 $n$ 的数组 $a$ ，他希望从数组中选择一个子序列，并使得这个子序列构成的数组是一个“好数组”。对于“好数组”的定义是：如果一个数组按升序排序后和原来的不完全相同，则是一个好数组。例如 $[3, 2, 2]$ 升序排列后是 $[2, 2, 3]$ ，和原来不完全相同，因此是一个好数组，而 $[1, 2, 2]$ 不是一个好数组。小田想知道，如果想要使得选择的子序列构成一个“好数组”，最长可以选择多长的子序列？说明：子序列指一个数组删除一个数字后（也可以不删），剩余的数字按其原来的顺序构成的序列。例如： $[2, 3]$ 是 $[1, 2, 4, 3]$ 的一个子序列， $[1, 2, 4, 3]$ 也是，但 $[3, 2]$ 不是。

输入描述

输入包含两行。第一行一个正整数 $n$ ，表示数组 $a$ 的长度。第二行 $n$ 的正整数 $a_{i}$ ，表示数组 $a$ 的元素。

输出描述

输出包含一行一个整数，表示可以构成“好数组”的最长子序列的长度。

输入输出样例

输入 #1

1
1

输出 #1

输入 #2

2
2 1

输出 #2

说明/提示

【样例 1 解释】 只能选择 $1$ ，但 $[1]$ 这个数组排序后还是 $[1]$ ，无法满足不完全相同的条件。 【样例 2 解释】 选择 $[2, 1]$ ，排序后是 $[1, 2]$ ，满足不完全相同的要求。 【数据范围】 对于 $10 \%$ 的数据，有： $1 \le n \le 2$ 。对于另外 $10 \%$ 的数据，有：所有 $a_i$ 完全相等。对于所有测试数据，有： $1 \le n \le 2 \times 10^{5}, 1 \le a_{i} \le 10^9$ 。

题目解析

可以发现，当数组中存在逆序对的时候，就可以选择整个数组，如果数组是完全有序的，那么就无法选择任何一段。

所以对于一个长度为 $n$ 的数组，答案只会有两种，要么是 $0$ ，要么是 $n$ 。

示例代码：

#include <bits/stdc++.h>   
using namespace std;  
  
const int N = 2e5+5;  
int n, a[N], flag;  
  
int main() {  
    cin >> n;  
    for (int i=1; i<=n; i++) {  
        cin >> a[i];  
        if (a[i] < a[i-1]) flag = 1;  
    }  
    if (flag == 1) cout << n;  
    else cout << 0;  
    return 0;  
}

T3 小田的数字合并

题目描述

小田又得到了一个长度为 $n$ 的数组 $a$ ，他这次想要最大化 $a$ 的极差。小田可以对数组做如下操作任意次（前提是数组中至少有两个数字）：

选择一个正整数 $i(1 \le i \lt n)$ ，接着将 $a_i$ 和 $a_{i+1}$ 合并为一个数字，结果为两者的和。（即：将 $a_i$ 变为 $a_{i} + a_{i+1}$ ，然后删除 $a_{i+1}$ ，当然操作完后 $a$ 的长度也会减一。）

小田想知道他最大能将数组极差变为多少呢，请你帮帮他吧！说明：极差指数组中最大值和最小值之差。

输入描述

输入包含两行。第一行一个正整数 $n$ ，表示数组 $a$ 的长度。第二行 $n$ 的正整数 $a_{i}$ ，表示数组 $a$ 的元素。

输出描述

输出包含一行一个整数，表示小田操作完后，数组 $a$ 的最大极差。

输入输出样例

输入 #1

4
3 2 2 3

输出 #1

输入 #2

5
2 1 3 2 4

输出 #2

说明/提示

【样例 1 解释】 合并 $a_{2}, a_{3}, a_{4}$ ，数组变为 $[3, 7]$ ，极差为 $4$ 。另一种方案是合并 $a_{1}, a_{2}, a_{3}$ ，结果一样。 【样例 2 解释】 合并 $a_{3}, a_{4}, a_{5}$ ，数组变为 $[2, 1, 9]$ ，极差为 $8$ 。 【数据范围】 对于 $10 \%$ 的数据，有： $n = 3$ 。对于另外 $10\%$ 的数据，有： $a_i$ 呈升序排列。对于所有测试数据，有： $1 \le n \le 2 \times 10^{5}, 1 \le a_{i} \le 10^9$ 。

题目解析

容易想到，最大化极差中的最小值肯定是一个数，而不会是好几个数合并得来的，而其最大值一定是最小值左边或者右边的所有数字全部合并得来的。

所以可以考虑枚举，利用前缀和来帮助我们后续快速求出区间和，然后枚举每个数字，分别计算其左边和右边的所有数字的和与这个数字的差，对这个差取最大值，就是要求的答案了。

示例代码：

#include <bits/stdc++.h>   
using namespace std;  
  
const int N = 2e5+5;  
long long n, a[N], sum[N], maxx=0;  
  
int main() {   
    cin >> n;  
    for (int i=1; i<=n; i++) {  
        cin >> a[i];  
        sum[i] = sum[i-1] + a[i];  
    }  
  
    for (int i=2; i<=n; i++) maxx = max(maxx, sum[n]-sum[i-1]-a[i-1]);
      
    for (int i=1; i<=n-1; i--) maxx = max(maxx, sum[i]-a[i+1]);  
    
    cout << maxx;  
    return 0;  
}

T4 化学式的原子数

题目描述

给定一个字符串化学式，请计算每种原子的数量。原子总是以一个大写字母开始，接着跟随0个或者任意个小写字母，表示原子的名字。如果数量大于1，原子后会跟着数字表示原子的数量。如果数量等于1则不会跟数字。

例如："H20"和"H2O2"是可行的，但"H1O2"是不行的。两个化学式连在一起可以构成新的化学式。
例如："H2O2He3Mg4"也是化学式。由括号括起的化学式并佐以数字(可选择性添加)也是化学式。
例如"(H2O2)"和"(H2O2)3"。

请你编写程序计算原子的数量，要求原子的名字按字典序排序，后面跟着输出他的数量，一个一行。

输入描述

一行，一个字符串，表示合法的化学式。

输出描述

输出每个原子的数量，要求按原子名字典序排序，后面跟上原子数量。

输入输出样例

输入 #1

H2O

输出 #1

H 2
O 1

输入 #2

H2MgO2

输出 #2

H 2
Mg 1
O 2

输入 #3

K4(ON(SO3)2)2

输出 #3

K 4
N 2
O 14
S 4

说明/提示

【数据范围】 化学式字符串长度最多1000，并且总是合法的。 10%的数据，化学式只有大写字母，且不含括号 30%的数据，化学式只有大小写字母和数字，且不含括号 100%的数据，化学式由英文字母、数字和小括号组成

解析：

对于括号序列相关的题目，通常的解法使用递归或者栈，本题我们用栈+哈希map来解决。从左到右遍历化学式，使用哈希map记录当前遍历到的原子及其数量，初始时需要添加一个空的哈希map到栈内。对于遍历到的字符：

如果是左括号，push一个空哈希表到栈中
如果是右括号，说明当前层遍历完了，若括号右侧有数字，取出该数，否则视为括号右侧为1，然后将栈顶哈希表pop出，并将弹出的原子数乘上取出的数字，加到上一层（当前栈顶）的哈希表中。
不是括号则为原子，取出原子，若后面还有数字，则取出数字，否则视作数字为1，然后将 原子：数字 键值对添加到哈希表中。

遍历结束后，栈顶的哈希表就记录了所有原子及其个数，遍历输出即可。

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

stack<map<string, int>> stk; // 哈希栈
string s;
int i, len;

int get_num() // 取数字
{
	if (i == len || !isdigit((s[i]))) return 1;
	int num = 0;
	while (isdigit(s[i]) && i < len)
	{
		num = num * 10 + s[i] - '0';
		i++;
	}
	return num;
}

string get_atom() // 取原子
{
	string atom;
	atom += s[i++]; // 首字母
	while (i < len && s[i] >= 'a' && s[i] <= 'z')
		atom += s[i++];
	return atom;
}

int main()
{
    freopen("atom.in", "r", stdin);
    freopen("atom.out:, "w", stdout);
	cin >> s;
	len = s.size();
	stk.push({});
	while (i < len)
	{
		char ch = s[i];
		if (ch == '(')
		{
			i++;
			stk.push({}); // 遇到左括号新起一个空哈希表
		}
		else if (ch == ')')
		{
			i++;
			// 算出括号右边数字
			int num = get_num();
			auto atom_num = stk.top();
			stk.pop();
			for (auto &it:atom_num)
			{
				string k = it.first; // 原子名
				int v = it.second;  // 数量
				stk.top()[k] += v*num;
			}
		}
		else
		{
			string atom = get_atom();
			int num = get_num();
			stk.top()[atom] += num; // 统计原子数
		}
	}
	auto atn = stk.top();
	for (auto &it:atn)
	{
		string k = it.first;
		int v = it.second;
		cout << k << " " << v << endl;
	}
	return 0;
}

T5 小W挖宝藏

解析

本题读起来是一个简单的深搜模版, 但是这题每个点出发有可能，所以我们每个点都要开始dfs，最后取他们的最大值。dfs部分和类似的迷宫差不多,用两个数组表示4个方向,改变方向直接xx=x+dx[i] , yy=y+dy[i] 接下来判断这个方向是否在地图范围内，当然还要判断这个点是否能爬到，也就是高度要前一个低 , 很明显，因为低的不可能爬向高的，所以我们不需要再开一个数组去记录这个点是否走过。接下来，就要往四个方向搜索，取四个方向中距离最长的，然后+1，这就是这个点的结果了。但是我们从数据的范围可以发现,最大的地图有100*100,那么如果能走的路有很多的话,而且连续的话,最复杂的环形路就是100! , 很显然，直接dfs会TLE。那么就需要记忆化来优化。用a[i][j]表示从(i,j)点出发能走的最长距离。每次搜索一次记忆一次即可。看下面的例子:

先去找(1,1)的最长距离，很明显为1 接着找(1,2)的最长距离，很明显为1 接着找(1,3)的最长距离，为2((1,3)->(1,2)) 然后找(2,1)的最长距离，为2((2,1)->(1,1)) 然后是(2,2)的最长距离，如果没有记忆化，那么搜索过程为：(2,2)->(2,1)->(1,1) 但是（2,1）之前已经搜过了，再去搜就是浪费时间，之前搜索已经知道(2,1)的值为2，那么搜索过程就是缩短为：(2,2)->(2,1),即为3

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

int n, m, f[105][105], arr[105][105];
int maxn = 0;
int dx[4] = { 0 , 0 , 1 , -1 };
int dy[4] = { -1 , 1 , 0 , 0 };
int a,b;
int dfs( int x , int y ){
    if( f[x][y] > 0 ) //记忆化搜索 
    {
        return f[x][y];
    }
    for( int i = 0; i < 4; i ++ ) //深搜模版
    {
        int gx = x + dx[i];
        int gy = y + dy[i];
        if( gy >= 1 && gy <= m && gx >= 1 && gx <= n && arr[x][y] > arr[gx][gy] )
        {
        	int tmp = dfs(gx , gy);
        	f[x][y]  = max(tmp + 1 , f[x][y]); //记忆化 记录更大的
        }
    }
   
    return f[x][y] ;
}

int main()
{
    cin >> n >> m;
    for( int i = 1; i <= n;i ++ )
    	for( int j = 1; j <= m; j ++ )
    		cin >> arr[i][j];
    
    for( int i = 1; i <= n; i ++ )
    {
        for( int j = 1; j <= m; j ++ )
        {
           	if(dfs( i , j ) + 1>maxn){
           		maxn=dfs( i , j ) + 1;
           		a = i,b = j; //记录位置 
			}
        }
    }
    cout << a <<' '<< b << endl ;
	cout << maxn;
    return 0;
}

T6 小z的等待时间

题目描述 小z在等待朋友，他和朋友计划出去游玩，但是朋友来的实在太慢了，无聊的他在研究路边的小花。他发现路边一共有 $n$ 朵小花，小花排成一排，每朵小花的高度为 $h_i$ 。在等待朋友的每一分钟，小z都会让小花的高度减少，直到所有小花减少到 $0$ 的时候，朋友就到了！小花们高度减少的规则也很简单，每一分钟，对于所有小花 $i(1 \leq i \leq n)$ ，如果 $i=n$ 或者 $h_i > h_{i+1}$ ，那么这些小花的高度就会变 $max(0,h_i-1)$ 。其中 $h_i$ 是第 $i$ 朵小花的高度。那么，小z还要等朋友多少分钟呢？问题虽然简单！但等着急躁的小z根本无心计算！这个简简单单的问题就只能交给你来解决啦！输入每个测试用例的第一行都包含一个整数 $n$ ( $1 \le n \le 10^5$ ) --花朵的数量。每个测试用例的第二行包含 $n$ 个整数 $h_1, h_2, \ldots, h_n$ ( $1 \le h_i \le 10 ^ 9$ ) --花朵的高度。输出对于每个测试用例，输出一个整数 - 所有 $1 \le i \le n$ 在 $h_i=0$ 之前经过的分钟数。样例输入1 3 1 1 2 样例输出1 4 样例输入2 2 3 1 样例输出2 3 样例输入3 1 9 样例输出3 9 样例输入4 5 7 4 4 3 2 样例输出4 7 提示对于10%的数据， $n$ 不会超过 $100$ . 对于50%的数据, $h_i$ 不会超过 $10000$ . 对于100%的数据，满足上文的输入描述。

题目解析：本题是比较简单的线性DP，其实用递推就能得到思路。 状态表示： $f[i]$ 来表示第 $i$ 朵花高度变成 $0$ 所需要的时间 初始化：每个 $f[i]$ 初始化显然为 $h_i$ 结果：显然 $f[1]$ 是结果，因为第 $1$ 朵花必定是最后高度减少为 $0$ 的。 状态计算： $h[i]$ 要为 $0$ ，那么考虑 $h_i$ 和 $h_i$ 的关系，如果 $h_i \leq h_{i+1}$ 的话，那么 $f[i]=f[i+1]+1$ 如果 $h_i > h_{i+1}$ ，那么会发现不用更新 $f_i$ ，因为前者比后者高，那么花的时间要么和 $i+1$ 一样，要么比它时间长。代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, f[100005];

signed main() {
    cin>>n;
    for(int i = 1 ; i <= n ; i++) cin>>f[i];
    
    for(int i = n - 1 ; i >= 1 ; i --) 
        if(f[i] <= f[i + 1]) 
            f[i] = f[i + 1] + 1;
            
    cout<<f[1]<<endl;
    return 0;
}

Day1 题解

T1 小田的宝石镇

题目描述

输入描述

输出描述

输入输出样例

输入 #1

输出 #1

输入 #2

输出 #2

说明/提示

题目解析

T2 小田的好数组

题目描述

输入描述

输出描述

输入输出样例

输入 #1

输出 #1

输入 #2

输出 #2

说明/提示

题目解析

T3 小田的数字合并

题目描述

输入描述

输出描述

输入输出样例

输入 #1

输出 #1

输入 #2

输出 #2

说明/提示

题目解析

T4 化学式的原子数

题目描述

输入描述

输出描述

输入输出样例

输入 #1

输出 #1

输入 #2

输出 #2

输入 #3

输出 #3

说明/提示

解析：

T5 小W挖宝藏

解析

T6 小z的等待时间

状态

开发

支持

关于

登录