练习地址
点此前往练习
小美的仓库整理
小美是美团仓库的管理员，她会根据单据的要求按顺序取出仓库中的货物，每取出一件货物后会把剩余货物重新堆放，使得自己方便查找。已知货物入库的时候是按顺序堆放在一起的。如果小美取出其中一件货物，则会把货物所在的一堆物品以取出的货物为界分成两堆，这样可以保证货物局部的顺序不变。
已知货物最初是按1~n的顺序堆放的，每件货物的重量为w_i,小美会根据单据依次不放回的取出货物。请问根据上述操作，小美每取出一件货物之后，重量和最大的一堆货物重量是多少？
输入描述:
输入第一行包含一个正整数n，表示货物的数量。(1<=n,m<=50000)输入第二行包含n个正整数，表示1 ~ n号货物的重量w_i。(1<=w_i<=100)输入第三行有n个数，表示小美按顺序取出的货物的编号，也就是一个1~n的全排列。
输出描述:
输出包含n行，每行一个整数，表示每取出一件货物以后，对于重量和最大的一堆货物，其重量和为多少。
输入例子1:
5
3 2 4 4 5
4 3 5 2 1
输出例子1:
9
5
5
3
0
例子说明1:
原本的状态是{{3,2,4,4,5}}，取出4号货物后，得到{{3,2,4},{5}}，第一堆货物的和是9，,然后取出3号货物得到{{3,2}{5}}，此时第一堆和第二堆的和都是5，以此类推。
思路：
题中是每次删除序列中的一个元素，要求最大的未删除的元素序列和。由于插入处理比删除简单，因此可以将删除看成插入的逆过程：
开始时，序列是空的，此时最大连续和为0；首先在1号位置插入3，此时最大连续和为3；接着在2号位置插入2，此时最大连续和为5；然后在5号位置插入5，此时最大连续和也为5；最后在3号位置插入4，此时最大连续和为9。
逆序输出上述的最大连续和就是题目所要求的结果了。
那么如何维护插入过程中的连续最大和呢？这里采用记录另一头端点的策略。
即在遍历序列的过程中，维护一个记忆数组mark，使得对每一段连续序列[l,l+1,…,r]，mark[l] = r, mark[r] = l。
如果这种性质满足，就只需要对每个元素计算|mark[i] - i|，并取最大值即可。
可以发现，当单独插入一个点u,只需要设置mark[u] = u，就能满足要求，因为u的左右端点都是它本身。
Ref：维护连续最大和思路：点此查看详情
题解：点此查看详情
代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int> w(n),x(n+1);
//记录连续区间的另一头
unordered_map<int,int> mark;
//记录连续区间的和
unordered_map<int,int> sum;
vector<int> out(n+1,0);
for(int i = 0; i < n; i++)
{
cin>>w[i];
}
for(int i = n; i >= 1; i--)
{
cin>>x[i];
//将排列从{1：n}转换成{0：n-1}
x[i]--;
}
for(int i = 1; i <= n; i++)
{
int v=x[i];
mark[v]=v;
sum[v]=w[v];
out[i]=max(out[i-1],sum[v]);
for(auto u:{v-1,v+1})
{
auto it=mark.find(u);
if(it!=mark.end())
{
int m=mark[v],n=mark[u];
mark[m]=n;
mark[n]=m;
sum[m]=sum[n]=sum[m]+sum[n];
out[i]=max(out[i-1],sum[m]);
}
}
}
//逆序输出
for(int i = n-1; i >= 0; i--)
{
cout<<out[i]<<endl;
}
return 0;
}
小美的跑腿代购
小美的一个兼职是美团的一名跑腿代购员，她有n个订单可以接，订单编号是1~n，但是因为订单的时效性，她只能选择其中m个订单接取，精明的小美当然希望自己总的获利是最大的，已知，一份订单会提供以下信息，跑腿价格v，商品重量w kg，商品每重1kg，代购费用要加2元，而一份订单可以赚到的钱是跑腿价格和重量加价之和。小美可是开兰博基尼送货的人，所以自然不会在意自己会累这种事情。请问小美应该选择哪些订单，使得自己获得的钱最多。
请你按照选择的订单编号的从小到大顺序，如果存在多种方案，输出订单编号字典序较小的方案。
输入描述:
输入第一行包含两个正整数n，m，表示订单的数量和小美可以接的订单数量(1<=n,m<=10000)接下来有n行，第i行表示i-1号订单的信息。每行有两个正整数v和w，表示一个订单的跑腿价格和商品重量。(1<=v,w<=1000)
输出描述:
输出包含m个1~n之间的正整数，中间用空格隔开，表示选择的订单编号。
输入例子1:
5 2
5 10
8 9
1 4
7 9
6 10
输出例子1:
2 5
思路：
由于要求输出的是订单编号，因此定义一个pair，存储订单编号和对应的价格。
首先按照价格降序排序，当价格相等时，按照编号升序排序；接着对需要的订单数再进行编号的升序排序。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> Node;
bool compare1(Node a,Node b)
{
if(a.second==b.second)
return a.first<b.first;
return a.second>b.second;
}
bool compare2(Node a,Node b)
{
return a.first<b.first;
}
int main()
{
int n,m;
cin>>n>>m;
int v,w;
Node nums[n];
for(int i=0;i<n;i++)
{
cin>>v>>w;
nums[i].first=i+1;
nums[i].second=v+w*2;
}
sort(nums,nums+n,compare1);
sort(nums,nums+m,compare2);
for(int i=0;i<m;i++)
cout<<nums[i].first<<" ";
return 0;
}
小美的用户名
小美是美团的前端工程师，为了防止系统被恶意攻击，小美必须要在用户输入用户名之前做一个合法性检查，一个合法的用户名必须满足以下几个要求：
-
用户名的首字符必须是大写或者小写字母。
-
用户名只能包含大小写字母，数字。
-
用户名需要包含至少一个字母和一个数字。
如果用户名合法，请输出“Accept”，反之输出“Wrong”。
输入描述:
输入第一行包含一个正整数T，表示需要检验的用户名数量。(1<=T<=100)接下来有T行，每行一个不超过20的字符串s，表示输入的用户名。
输出描述:
对于每一个输入的用户名s，请输出一行，即按题目要求输出一个字符串。
输入例子1:
5
Ooook
Hhhh666
ABCD
Meituan
6666
输出例子1:
Wrong
Accept
Wrong
Wrong
Wrong
思路：
首先判断输入的用户名首字符如果不是字母，就是Wrong；接着遍历输入的用户名字符，对其中的数字和字母进行计数，如果都大于0，才是Accept。
代码：
#include<bits/stdc++.h>
using namespace std;
bool Judge(string s)
{
if(s.size()==0)
return false;
if(!isalpha(s[0]))
return false;
int digit=0,alpha=0;
for(int i = 0;i < s.size(); i++)
{
if(isdigit(s[i]))
digit++;
else if(isalpha(s[i]))
alpha++;
else
return false;
}
return alpha>0&&digit>0;
}
int main()
{
int n;
string s;
cin>>n;
vector<string> out(n);
for(int i = 0;i < n; i++)
{
cin>>s;
if(Judge(s))
out[i] ="Accept";
else
out[i]="Wrong";
}
for(int i = 0;i < n; i++)
{
cout<<out[i]<<endl;
}
}
小美的区域会议
小美是美团总部的高管，她想要召集一些美团的区域负责人来开会，已知美团的业务区域划分可以用一棵树来表示，树上有n个节点，每个节点分别代表美团的一个业务区域，每一个区域有一个负责人，这个负责人的级别为A_i。
已知小美召集人员开会必须满足以下几个条件：
-
小美召集的负责人所在的区域必须构成一个非空的连通的图，即选取树上的一个连通子图。
-
这些负责人中，级别最高的和级别最低的相差不超过k。
请问小美有多少种召集负责人的方式，当且仅当选取的集合不同时我们就认为两种方式不同。由于方案数可能非常大，所以请对109+7取模。
输入描述:
输入第一行包含两个整数n和k，表示区域的数量，和不能超过的级别。(1<=n,k<=2000)接下来有n-1行，每行有两个正整数a和b，表示a号区域和b号区域有一条边。(1<=a,b<=n)最后一行有n个整数，第i个整数表示i号区域负责人的级别。
输出描述:
输出仅包含一个整数，表示可以选择的方案数对109+7取模之后的结果。
输入例子1:
5 1
1 2
2 3
3 4
4 5
2 2 2 2 2
输出例子1:
15
例子说明1:
显然一个区域的方案有{1}，{2}，{3}，{4}，{5},两个区域的方案有4个，三个区域的方案有3个，四个区域的方案有2个，五个区域的方案有1个，共15个。
思路：
暴力枚举法：
- 枚举所得到连通子图里最小的A[i]；
- 每次枚举以该值对应的结点i为根DFS建树，一个结点j在这棵树的前提条件是A[i]<A[j] ≤ A[i] + k。
上述枚举思路有一个问题，当数组A中存在重复值时，上述枚举方式会重复计数。因此需要修正一下，将条件改为A[j] ≤ A[i] + k且(A[i], i) < (A[j], j)。
Ref：题解及思路：点此查看详情
以下代码只过了8/10组用例，AC代码详见评论区。
代码：
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> graph;
vector<int> level;
int k,i=0;
const int mod = 1e9+7;
int dfs(int u,int pre)
{
long long out=1;
for(auto v:graph[u])
{
if(v!=pre&&((level[v]>level[i]&&level[v]<=level[i]+k)||(level[v]==level[i]&&v<i)))
{
out*=(dfs(v,u)+1);
out%=mod;
}
}
return out;
}
int main()
{
int n,r;
cin>>n>>k;
int a,b;
long long out=0;
graph.resize(n);
for(int i=1;i<=n-1;i++)
{
cin>>a>>b;
graph[a-1].push_back(b-1);
graph[b-1].push_back(a-1);
}
for(int i=1;i<=n;i++)
{
cin>>r;
level.push_back(r);
}
while(i<n)
{
out=(out+dfs(i,-1)%mod);
i++;
}
cout<<out;
return 0;
}
总结
第一题：
- C++ STL中的
unordered_map：无序关联式容器。
-
unordered_map 容器和 map 容器一样，以键值对（pair类型）的形式存储数据，存储的各个键值对的键互不相同且不允许被修改。
-
unordered_map 容器底层采用的是哈希表存储结构，该结构本身不具有对数据的排序功能，所以此容器内部不会自行对存储的键值对进行排序。
- 头文件：
#include<unordered_map>
- 创建
unordered_map容器：unordered_map<T1,T2> umap;
- 插入元素：
umap.insert(make_pair(a,b));
- 删除元素：
umap.erase(a);可通过位置和key删除。
- 交换2 个 unordered_map 容器存储的键值对：
umap1.swap(umap2);前提是必须保证这 2 个容器的类型完全相等。
- 容器中键值对个数：
umap.size();
- 容器所能容纳键值对的最大个数：
umap.max_size();
- 容器中存储的键 key 对应的值：
umap.at(key);如果 key 不存在，则会抛出 out_of_range 异常。
- 查找以 key 为键的键值对：
umap.find(key);如果找到，则返回一个指向该键值对的正向迭代器；反之，则返回一个指向容器中最后一个键值对之后位置的迭代器。
- 在容器中查找以 key 键的键值对的个数：
umap.count(key);
- 清空容器：
umap.clear();
第二题：
- 对于
sort函数，用它进行排序时，一般都按需求写一个比较规则函数。
- 一般的升序和降序排序：
- 升序：
sort(begin,end,less<data_type>());
- 降序：
sort(begin,end,greater<data_type());
第三题：
- 字符串常用函数
-
string.size()：字符串的长度。
-
isdigit(s[i])：判断s[i]是否是数字；isalpha(s[i]):判断s[i]是否是字母。
