1. 小美的密码
小美准备登录美团,需要输入密码,小美忘记了密码,只记得密码可能是 n个字符串中的一个。
小美会按照密码的长度从小到大依次尝试每个字符串,对于相同长度的字符串,小美随机尝试,并且相同的密码只会尝试一次。
小美想知道,她最少需要尝试多少次才能登录成功,最多需要尝试多少次才能登录成功。
哈希找规律
int main() {
int n;
cin>>n;
string target;
cin>>target;
map<int,int> m;//记录对应长度字符串个数
unordered_set<string> st;//避免重复
for(int i=0;i<n;i++){
string cur;
cin>>cur;
if(st.count(cur)) continue;
st.insert(cur);
m[cur.size()]++;
}
int res = 0;
for(auto [key,val]:m){
if(key==target.size()) break;
res += val;
}
cout<<res+1<<" "<<res+m[target.size()];
return 0;
}
2. 小美的数组删除
小美有一个长度为 n 的数组 a1,a2,....,an ,他可以对数组进行如下操作:
● 删除第一个元素 a1,同时数组的长度减一,花费为 x。
● 删除整个数组,花费为 k*MEX(a) (其中 MEX(a) 表示 a 中未出现过的最小非负整数。例如 [0,1,2,4] 的 MEX 为 3 )。
小美想知道将 a 数组全部清空的最小代价是多少,请你帮帮他吧。
顺序遍历同时维护快速查询的最小非负整数(使用动态规划+队列+哈希)
int main() {
int T;
cin>>T;
while(T--){
int n,k,x;
cin>>n>>k>>x;//元素数量、删除整个数组的花费系数、删除单个元素的花费
vector<int> nums(n);
for(int i=0;i<n;i++)
cin>>nums[i];
int res= INT_MAX;
queue<int> q;
for(int i=0;i<=n;i++)
q.push(i);
unordered_set<int> st;//记录已经出现的整数
vector<int> dp(n);//dp[i]表示以i为开头,之后数组不存在的最小非负整数
for(int i=n-1;i>=0;i--){
st.insert(nums[i]);
while(st.count(q.front()))
q.pop();
dp[i] = q.front();
}
int delpre = 0;
for(int i=0;i<n;i++){
res = min(res,delpre+k*dp[i]);
delpre+=x;
}
cout<<res;
}
return 0;
}
3. 小美的彩带
小美的彩带是由一条长度为 n 的彩带一直无限循环得到的,彩带的每一个位置都有一个颜色,用 ai 表示。
因此当 i>n 时,ai = ai-n 。小美每次会从左往后或从右往左剪一段长度为 x 的彩带,她想知道她每次剪下来的彩带有多少种颜色。
标签:10,小美,int,美团,2024.08,st,数组,长度,彩带
From: https://www.cnblogs.com/929code/p/18398913