今天刷洛谷题基础stl题。

1.CF112A Petya and Strings

题目描述

输入两个字符串，大小写无关紧要，比较它们的大小。

输入格式

两个字符串（保证长度相等）

输出格式

如果第一个字符串小于第二个字符串，则输出“-1”。如果第二个字符串小于第一个字符串，则输出“1”。如果字符串相同，则打印“0”。请注意，比较字符串时不考虑字母的大小写。

输入输出样例 #1

输入 #1

1
2
aaaa
aaaA

输出 #1

1
0

输入输出样例 #2

输入 #2

1
2
abs
Abz

输出 #2

1
-1

输入输出样例 #3

输入 #3

1
2
abcdefg
AbCdEfF

输出 #3

1
1

今日题解：

题目大意是大小写无关的字符串字典序比较，需要我们先统一一下大小写。利用ASCII码进行大小写转换，A->65 a->97

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
using ll = long long;


int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	string s1, s2;
	cin>>s1>>s2;
	int len=s1.size();

	for(int i=0; i<len; ++i) {
		if(s1[i]>='A' && s1[i]<'a') {
			s1[i]=s1[i]+32;
		}
		if(s2[i]>='A' && s2[i]<'a') {
			s2[i]=s2[i]+32;
		}
	}
	if(s1>s2) {
		cout<<"1\n";
	}
	if(s1<s2) {
		cout<<"-1\n";
	}
	if(s1==s2) {
		cout<<"0\n";
	}
	return 0;
}

2.CF44A Indian Summer

题目描述

Indian summer is such a beautiful time of the year! A girl named Alyona is walking in the forest and picking a bouquet from fallen leaves. Alyona is very choosy — she doesn’t take a leaf if it matches the color and the species of the tree of one of the leaves she already has. Find out how many leaves Alyona has picked.

输入格式

The first line contains an integer $ n $ ( $ 1<=n<=100 $ ) — the number of leaves Alyona has found. The next $ n $ lines contain the leaves’ descriptions. Each leaf is characterized by the species of the tree it has fallen from and by the color. The species of the trees and colors are given in names, consisting of no more than $ 10 $ lowercase Latin letters. A name can not be an empty string. The species of a tree and the color are given in each line separated by a space.

输出格式

Output the single number — the number of Alyona’s leaves.

输入输出样例 #1

输入 #1

1
2
3
4
5
6
5
birch yellow
maple red
birch yellow
maple yellow
maple green

输出 #1

1
4

输入输出样例 #2

输入 #2

1
2
3
4
3
oak yellow
oak yellow
oak yellow

输出 #2

1
1

今日题解：

题目大意是要我们找出键值都不重复的元素个数。注意set元素为对的声明为set<pair<type,type>> s;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
using ll = long long;


int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n;cin>>n;
	set<pair<string, string>> s;
	while(n--) {
		string s1, s2;	
		cin>>s1>>s2;
		s.insert({s1, s2});
	}
	cout<<s.size();
	return 0;
}

3.CF45C Dancing Lessons

题目描述

There are $ n $ people taking dancing lessons. Every person is characterized by his/her dancing skill $ a_{i} $ . At the beginning of the lesson they line up from left to right. While there is at least one couple of a boy and a girl in the line, the following process is repeated: the boy and girl who stand next to each other, having the minimal difference in dancing skills start to dance. If there are several such couples, the one first from the left starts to dance. After a couple leaves to dance, the line closes again, i.e. as a result the line is always continuous. The difference in dancing skills is understood as the absolute value of difference of $ a_{i} $ variable. Your task is to find out what pairs and in what order will start dancing.

输入格式

The first line contains an integer $ n $ ( $ 1<=n<=2·10^{5} $ ) — the number of people. The next line contains $ n $ symbols B or G without spaces. B stands for a boy, G stands for a girl. The third line contains $ n $ space-separated integers $ a_{i} $ ( $ 1<=a_{i}<=10^{7} $ ) — the dancing skill. People are specified from left to right in the order in which they lined up.

输出格式

Print the resulting number of couples $ k $ . Then print $ k $ lines containing two numerals each — the numbers of people forming the couple. The people are numbered with integers from $ 1 $ to $ n $ from left to right. When a couple leaves to dance you shouldn’t renumber the people. The numbers in one couple should be sorted in the increasing order. Print the couples in the order in which they leave to dance.

题意翻译
有n个人在上舞蹈课，每个人都有相应的舞蹈技能。记录男女在一起直到结尾，然后选出男女差值最小的一对，如果有多对，就从左往右输出，选出后剩下的成员紧密排在一起，直到不能找到男女搭配。问：输出组合对数，并且每队成员最初时的位置标号。

输入输出样例 #1

输入 #1

1
2
3
4
BGBG
4 2 4 3

输出 #1

1
2
3
2
3 4
1 2

输入输出样例 #2

输入 #2

1
2
3
4
BBGG
4 6 1 5

输出 #2

1
2
3
2
2 3
1 4

输入输出样例 #3

输入 #3

1
2
3
4
BGBB
1 1 2 3

输出 #3

1
2
1
1 2

今日题解

大致思路：利用优先队列最大堆实现自动排序，注意比较函数的重写，实现最小堆。每次弹出优先队列后要注意判断是否已经遍历过和判断一下如果在原队伍中(此队伍靠更新元素自己的邻居索引动态更新)删除这两个元素是否能够组成新的入优先队列的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
using namespace std;

int n, k, ans[2][100005];
string s;//存储性别字符串


struct people {
	int a;//能力值
	int l, r;//左右邻居索引
	bool x, vis;//性别0男1女 vis表示是否选出过
} a[200005];

struct peoples {
	int a;//能力差值
	int l, r;//此差值的两个原始位置
};

priority_queue<peoples> pq;

bool operator< (peoples a, peoples b) {
	if(a.a == b.a) return a.l > b.l;
	return a.a>b.a;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	cin>>n>>s;
	//初始化a数组
	for(int i=1;i<=n;++i) {
		cin>>a[i].a;
		
		if(i==1) a[i].l=0;
		else a[i].l = i-1;
		if(i==n) a[i].r = i;
		else a[i].r = i+1;
		
		a[i].x=(s[i-1] == 'G');
		//如果相邻性别不同，将其插入队列
		if(a[i].x != a[i-1].x){
			pq.push(peoples{abs(a[i].a-a[i-1].a), i-1, i});
		}
	}
	
	while(!pq.empty()) {
		//记录本次最优对
		int l=pq.top().l, r=pq.top().r;
		pq.pop();//弹出
		
		if(a[l].vis&&a[r].vis)continue;//但凡已选过，则跳过，下一个
		
		k++;//每次对数+1
		ans[0][k]=l;//记录左位置
		ans[1][k]=r;//记录右位置
		//标记已选过
		a[l].vis=true;
		a[r].vis=true;
		
		//合并剩下的区间，看是否能加入pq
        // 先获取新的左右邻居
        l = a[l].l;
        r = a[r].r;

        // 更新邻居关系
        a[l].r = r;
        a[r].l = l;
		
		if(l>0 && r<=n && a[l].x!=a[r].x) {
			pq.push(peoples{abs(a[l].a-a[r].a), l, a[l].r});
		}
		
	}
	
	cout<<k<<'\n';
	for(int i=1;i<=k;++i) {
		cout<<ans[0][i]<<' '<<ans[1][i]<<'\n';
	}
	
	
	return 0;
}