AcWing_第 78 场周赛

AcWing 4719. 商品种类_set

4719. 商品种类

•    题目
•    提交记录
•    讨论
•    题解
•    视频讲解

货架中摆放着 nn 件商品，每件商品都有两个属性：名称和产地。

当且仅当两件商品的名称和产地都相同时，两件商品才视为同一种商品。

请你统计，货架中一共有多少种不同的商品。

输入格式

第一行包含整数 nn。

接下来 nn 行，每行包含两个字符串，分别表示一件商品的名称和产地。

输入字符串的长度范围为 [1,10][1,10]，且仅包含小写字母。

输出格式

一个整数，表示商品种类数量。

数据范围

前 44 个测试点满足 1≤n≤51≤n≤5。
所有测试点满足 1≤n≤1001≤n≤100。

输入样例1：

5
b y
m r
b y
m y
m g

输出样例1：

4

输入样例2：

3
abc def
abc def
abc def

输出样例2：

1

// 	AcWing 4719. 商品种类_set
#include
using namespace std;
 
const int N=111;
struct A
{
    string a,b;
 
    bool operator < ( const A& in ) const
    {
        return ( in.a == a ) ? ( in.b < b ) : ( in.a < a ) ;
    }
};
set st;
// set< pair > st;	
 
int main()
{
    string a,b;
    int n,i;
 
    scanf("%d",&n );
    for( i=1;i<=n;i++ )
    {
        cin>>a>>b;
 
        st.insert( (A){ a,b } );
        // st.insert( make_pair( a,b ) );
    }
    cout<size()<
 
    return 0;
}
// set具有天然的排序与去重功能，
// 结构体不是基本类型（基本类型有默认的排序准则），因此需要重载 < 运算符。
//（相当于给自定义类型一个排序准则）。
// bool operator <(const HolePos & a)const ;运算符重载必须是const。

---

AcWing 4720. 字符串_栈

4720. 字符串

•    题目
•    提交记录
•    讨论
•    题解
•    视频讲解

给定一个由小写字母构成的字符串 ss。

如果字符串中存在两个字母相同且相邻，则称它们为相同连续字母对。

我们不希望 ss 中存在相同连续字母对。

所以，每当在 ss 中发现一个相同连续字母对时，就应当将这对字母从 ss 中删除，如果删除某一对后，出现了新的相同连续字母对，则新的对也应当被删除。

总之，最终得到的字符串中不能存在相同连续字母对。

输出最终得到的字符串。

可以证明，不论按何种顺序删除相同连续字母对，最终得到的字符串都是一样的。

输入格式

共一行，一个由小写字母构成的字符串 ss。

输出格式

输出最终得到的字符串。

保证结果不为空。

数据范围

前 55 个测试点满足 1≤|s|≤201≤|s|≤20。
所有测试点满足 1≤|s|≤2×1051≤|s|≤2×105。

输入样例1：

aabbcddddefggbbaa

输出样例1：

cef

输入样例2：

abcddcef

输出样例2：

abef

输入样例3：

abacabaabacabaa

输出样例3：

a

// 	AcWing 4720. 字符串_栈
#include
using namespace std;
 
const int N=1e6+7;
char ans[N];
 
int main()
{
    string s;
    int i,pos;
 
    cin>>s;
    
    pos=0;
    for( i=0;isize();i++ )
    {
        ans[++pos]=s[i];
        if( pos>=2 && ans[pos-1]==ans[pos] ) pos-=2;
    }
    for( i=1;i<=pos;i++ ) putchar( ans[i] ); 
 
    return 0;
}

---

acwing 4721. 排队_单调队列

4721. 排队

•    题目
•    提交记录
•    讨论
•    题解
•    视频讲解

nn 个小朋友排成一排，从左到右依次编号为 1∼n1∼n。

第 ii 个小朋友的身高为 hihi。

虽然队伍已经排好，但是小朋友们对此并不完全满意。

对于一个小朋友来说，如果存在其他小朋友身高比他更矮，却站在他右侧的情况，该小朋友就会感到不满。

每个小朋友的不满程度都可以量化计算，具体来说，对于第 ii 个小朋友：

• 如果存在比他更矮且在他右侧的小朋友，那么他的不满值等于其中最靠右的那个小朋友与他之间的小朋友数量。
• 如果不存在比他更矮且在他右侧的小朋友，那么他的不满值为 −1−1。

请你计算并输出每个小朋友的不满值。

注意，第 11 个小朋友和第 22 个小朋友之间的小朋友数量为 00，第 11 个小朋友和第 44 个小朋友之间的小朋友数量为 22。

输入格式

第一行包含整数 nn。

第二行包含 nn 个整数 h1,h2,…,hnh1,h2,…,hn。

输出格式

共一行，输出 nn 个整数，第 ii 个整数为第 ii 个小朋友的不满值。

数据范围

前 55 个测试点满足 2≤n≤52≤n≤5。
所有测试点满足 2≤n≤1052≤n≤105，1≤hi≤1091≤hi≤109。

输入样例1：

6
10 8 5 3 50 45

输出样例1：

2 1 0 -1 0 -1

输入样例2：

7
10 4 6 3 2 8 15

输出样例2：

4 2 1 0 -1 -1 -1 

输入样例3：

5
10 3 1 10 11

输出样例3：

1 0 -1 -1 -1 

// acwing 4721. 排队_单调队列
#include
using namespace std;
 
const int N=1e5+6;
int in[N],sk[N],ans[N];
 
int main()
{
    int n,i,top,x,y,mid;
 
    scanf("%d",&n );
    for( i=1;i<=n;i++ ) scanf("%d",&in[i] );
 
    memset( ans,-1,sizeof( ans ) );
    sk[n]=n;				// sk[] 存的是下标 
    top=n;
    for( i=n-1;i;i-- )      // 从后往前遍历
    {
    	// 出现相等的数字 因为需要满足严格小于 所以当前 数字下标放进单调队列 不进入二分  
        if( in[i]<=in[sk[top]] ) { sk[--top]=i; continue; } 	// 遇到小的 保留 放进栈里
        
        x=top,y=n;          // 二分 找到答案
        while( x// 找到小的最大值 
        {
            mid=( x+y+1 )>>1;
            if( in[sk[mid]]// 比他更矮 严格小于
            else                        y=mid-1;
        }
//        cout<
        ans[i]=sk[x]-i-1;
    }
    for( i=1;i<=n;i++ )
    {
        if( i!=1 ) putchar(' ');
        printf("%d",ans[i] );
    }
    putchar('\n');
 
    return 0;
}