1. set去重
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
int main()
{
set<pair<string,string>> s;
int n;
cin >> n;
while(n -- ){
string a, b;
cin >> a >> b;
s.insert({a, b});
}
cout << s.size();
}
2. 栈
解题经验: 相邻 -> 栈
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
int main()
{
string s;
cin >> s;
stack<char> stk;
for(int i = 0;i < s.size();i ++ ){
if(stk.empty()) stk.push(s[i]);
else{
if(stk.top() == s[i]) stk.pop();
else stk.push(s[i]);
}
}
string res;
while(stk.size()){
res += stk.top(), stk.pop();
}
reverse(res.begin(), res.end());
cout << res << endl;
return 0;
}
3, 排序 + 前缀最大值
题目分析:相当于 找到 比当前数$x$小, 且下标最靠右的数
举例:比 $10$ 小,最靠右的数 是 $8$, 所以答案 = $4$
解题思路:
- 将原数组排序,在
q[i]
前面的数自然比q[i]
小 - 维护一个前缀最大值
maxr
,表示 比q[i]
小的数中,下标最靠右的
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 200010;
int n;
int ans[N];
int main()
{
cin >> n;
vector<pair<int,int>> q;
for(int i = 0;i < n;i ++ ){
int x;
cin >> x;
q.push_back({x, i});
}
sort(q.begin(), q.end());
int maxr = 0;
for(int i = 0;i < n;i ++ ){
int idx = q[i].second;
maxr = max(maxr, idx);
ans[idx] = maxr - idx;
}
for(int i = 0; i< n;i ++ ) cout << ans[i] - 1 << ' ';
return 0;
}