🚀️题目传送门

A 小田的宝石镇

B 小田的好数组

C 小田的数字合并

D 化学式的原子数

E 小W挖宝藏

F 小z的等待时间

T1 小田的宝石镇😄

题目描述

小田为你准备了七块宝石，它们分别分布在七个不同的地点，宝石之间有道路相连，如下图所示。

与中心点相连的道路通过时间为 AA 秒，其余道路通过时间为 BB 秒，到达地点即可获得宝石，现在你从中心点出发，请问你拿到七块宝石的最短时间是多少呢？

输入描述

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

输出描述

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

思路❤️

两种情况，一个是11a，另一个是1a+5b 再取最小值

代码🎉️

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

int main(){
	freopen("gem.in","r",stdin);
	freopen("gem.out","w",stdout);
	long long a,b;
	cin>>a>>b;
	long long c=a+5*b;
	long long d=11*a;
	long long e=5*a+3*b;
	long long h=min(c,min(d,e));
	cout<<h;
}

T2 小田的好数组😄

题目描述

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

输入描述

输入包含两行。 第一行一个正整数 nn，表示数组 aa 的长度。 第二行 nn 的正整数 aia_{i}，表示数组 aa 的元素。

输出描述

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

思路❤️

数组有序cout<<0,无需cout<<n;

代码

#include<bits/stdc++.h>
using namespace std;
int a[200010],n,b[200010],l=0;
int main(){
	freopen("hsz.in","r",stdin);
	freopen("hsz.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){cin>>a[i];b[i]=a[i];}
	if(n==1){
		cout<<0;
		return 0;
	}
	sort(b+1,b+1+n);
	for(int i=1;i<=n;i++){
		if(a[i]!=b[i])l=1;
	}
	if(!l){
		cout<<0;
		return 0;
	}
	if(l){
		cout<<n;
	}
}

T3 小田的数字合并😄 😄

题目描述

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

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

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

输入描述

输入包含两行。 第一行一个正整数 nn，表示数组 aa 的长度。 第二行 nn 的正整数 aia_{i}，表示数组 aa 的元素。

输出描述

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

😕 错在哪

1.思路不清晰，以后一定要打草稿

思路

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

可以枚举，利用前缀和来后续快速求出区间和，然后枚举每个数字，分别计算其左边和右边的所有数字的差，求max。

代码🎉️

#include<bits/stdc++.h>
using namespace std;
long long a[200010],n,b[200010];
long long c=-10000;
int main(){
	freopen("num.in","r",stdin);
	freopen("num.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
	}
	for(int i=n;i>1;i--){
		a[i]+=a[i+1];
		c=max(c,abs(a[i]-a[i-1]));
	}
	for(int i=1;i<n;i++){
		b[i]+=b[i-1];
		c=max(c,abs(b[i]-b[i+1]));
	}
	cout<<c;
}

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%的数据，化学式由英文字母、数字和小括号组成

😕 错的地方

1.对算法掌握程度不够，以后要多多复习前面的算法内容

2.题目跟本没看懂，草稿纸要用上

❤️ 思路

要用用栈+哈希表来做这道题，先创建一个有序哈希表 2. 初始一个空键stk.push ({});, 遍历字符串的每一位，左括号新建空键值对astk.push ({}); ，右括号找之前的哈希表加到上一个哈希表下。字母则将字符串与和值更新。

代码🎉️

#include<bits/stdc++.h>
using namespace std;
stack<map<string, int>> st; 
string s;
int i,l;
int gt(){
	if(i==l||!isdigit((s[i])))return 1;
	int nu=0;
	while(isdigit(s[i])&&i<l){
		nu = nu*10+s[i]-'0';
		i++;
	}
	return nu;
}
string g() {
	string at;
	at+=s[i++]; 
	while(i<l&&s[i]>='a'&&s[i]<='z')at+=s[i++];
	return at;
}
int main(){
	freopen("atom.in", "r", stdin);
	freopen("atom.out", "w", stdout);
	cin>>s;
	l=s.size(),st.push({});
	while(i<l){
		char ch=s[i];
		if(ch=='('){
			i++;
			st.push({}); 
		}
		else if(ch==')'){
			i++;
			int nu=gt();
			auto at=st.top();
			st.pop();
			for(auto &it:at){
				string k=it.first; 
				int v=it.second;  
				st.top()[k]+=v*nu;
			}
		}
		else{
			string at=g();
			int nu=gt();
			st.top()[at]+=nu; 
		}
	}
	auto at=st.top();
	for(auto &it:at){
		string k=it.first;
		int v=it.second;
		cout<<k<<" "<<v<<"\n";
	}
}

T5 小W挖宝藏😄 😄

错的地方😕

1.只会暴力，不会优化，以后暴力优化都要会

思路❤️

一个搜索加标记优化，没什么好讲的

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1111][1111],f[1111][1111],c=-175,s;
int xz[10]={1,0,-1,0};
int yz[10]={0,1,0,-1};
int dfs(int i,int j){
	if(f[i][j]!=0)return f[i][j];
	for(int h=0;h<4;h++){
		int x=i+xz[h];
		int y=j+yz[h];
		if(x<=n&&x>=1&&y<=m&&y>=1&&a[x][y]<a[i][j]){
			int p=dfs(x,y)+1;
			f[i][j]=max(f[i][j],p);
		}
	}
	return f[i][j];
}
int main(){
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	cin>>n>>m;
	int x,y;
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			s=dfs(i,j)+1;
			if(s>c)c=s,x=i,y=j;
		}
	}
	cout<<x<<' '<<y<<"\n";
	cout<<c;
}

T6 小z的等待时间😄 😄 😄

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

错的地方😕

1.题目没看懂，要将强读题

思路❤️

dp 没有什么好讲的

代码

#include<bits/stdc++.h>
using namespace std;
long long a[100010],n,c,f[100010];
int main(){
	freopen("flowers.in","r",stdin);
	freopen("flowers.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		f[i]=a[i];
	}
	f[n]=a[n];
	for(int i=n-1;i>=1;i--){
		if(f[i]<=f[i+1]){
			f[i]=f[i+1]+1;
		}
	}
	cout<<f[1];
}
  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 20ms
  4. Powered by Hydro v5.0.0-beta.13 Community