vector在竞赛中的应用

优先队列（priority_queue)

特点

• 在队尾删除元素
• 在队头添加元素
• 每次取出的是具有最高优先权的元素（不一定先进先出）
• 访问最优元素：队列名.top

栈的应用

先进后出

特点

栈顶删除/加入

• 创建栈对象：stack<元素类型> 栈名；
• 栈顶==添加==元素：栈名.push(元素名)；
• ==删除==栈顶元素：栈名.pop();
• ==访问==栈顶元素：栈名.top();
• 判断是否为空：栈名.empty();
• 返回栈的大小：栈名.size();

栈和队列一样，没有clear之类的清空函数，只能循环调用==出栈函数==

vector的应用

vector(向量，==动态数组==)

1.向量的定义：vector< int > a;

2.向量初始化

vector< int > abc;//初始化一个size为0的vector

//初始化size，但每个元素为0

vector< int > abc(10);//初始化了10个默认值为0的元素

//初始化size，并设置初始值

vector< int > cde(10,1);//初始化10个为1的元素

基本用法

• 取向量==首元素的迭代器==：向量名.begin();

• 取向量==尾元素下一地址==:向量名.end ();

• 取向量==首元素的值==:向量名.front ();

• 取向量==尾元素的值==:向量名.back() ;

• ==下标==形式访问:int value0 =向量名[0];//类似普通数组的访问

• 往==尾部添加==一个元素:向量名.==push_back(value)==;//最常见操作

• ==删除尾部==第一个元素:向量名.pop_back() ;

• 判向量==是否为空==:向量名.empty();

• 求向量==元素个数==:向量名.size();//实际元素个数，不是容量

• ==翻转==向量: reverse(a.begin() , a.end () );

STL中vector的经典应用-==邻链表==

struct edge{int form,to,value;}//定义边

const int maxn =1e5+5;

vector< edge > Map[maxn];//一维向量相当于二维数组

若用普通二维数组存邻链表，需要1e10的空间开销，而如果图中实际变数只有1e6，无疑会造成空间浪费（超内存）。

set集合

set含义就是集合，他是一个==有序==的容器，里面的元素都是==排序好==的，支持插入，删除，查找等操作，所有的操作都是严格在log^n

时间内完成，效率高。

• set的声明： set< int > s;

• set的清空： s.clear();

• 插入一个元素x： s.insert();

  //==如果集合中之前没有，则插入成功并自动排序，否则不插入==

• 查询是否有元素x： int hav=s.count(x);//返回0或1

• 查找x并返回迭代器：set< int >::iterator it=s.find(x);

• 判断是否为空集 bool isempty=s.empty();

• 求集合元素个数:int n=s.size();

• 删除元素x:s.erase(x);

set的基本用法

set的主要用途：自动==去重==并按==升序==排序

set只能通过迭代器（iterator）访问

string类

一、string对象声明

• string str;
• string str1=”wjdnkk”;

二、求string对象长度

• string strTest=”test”;
• strTest.length();//返回4
• strTest.size();//返回4

三、string对象的链接

可以使用+和+=运算符对string对象执行字符串连接操作，（还有append成员函数实现字符串的连接）

四、string对象的比较

可以用<,<=,==,!=,>=,>运算符比较string对象，（患有compare成员函数用于比较字符串）

五、求string对象的子串

substr成员函数可以用于求字串（n,m)；

调用时，如果省略m或m超过字符串长度，则求出来的字串就是从下标n开始一直到字符串结束的部分

• string s1=”this is ok”;
• string s2=s1.substr(2,4);//s2=”is i”下标为2取4个
• s2=s1.substr(2);//s2=”is is ok”从2到最后

六、插入字符串

insert成员函数可以在string对象中插入另一个字符串，返回值为对象自身的引用。

• string s1(“Limitless”),s2(“00”);
• s1.insert(2,”123”); //s1=”Lil23mitless”
• s1.insert(3.s2); //s1=”Lil0023mitless”
• s1.insert(3,5,’X’); //s1=”LilXXXXX0023mitless”

七、删除字串

erase成员函数可以删除string对象中的子串，返回值为对象自身的引用。

• string s1(“Real Steel”);

• s1.erase(1,3); //s1=”R Steel”

• s1.erase(5); //s1=”R Ste”

八、交换两个string对象的内容

swap成员函数可以交换两个string对象的内容；

• string s1(“West”),s2(“East”);
• s1.swap(s2);

九、字符串的查找操作：

• string str=”The apple thinks apple is delicious”;//长度34
• string key=”apple”;
• int pos1=str.find(key);//4
• int pos2=str.find(key,10);//17

==//s.find(str) 查找字符串str在当前字符串s中第一次出现的位置==

==//s.find(str，pos) 查找字符串str在当前字符串s的[pos,end]中第一次出现的位置==

十、用STL算法操作string对象

• string s(“afgcbed”);
• sort(s.began(),s.end());
• cout<<s<<endl; //输出abcdefg
• ==next_permutation==(s.began(),s.end());求下一个字符串
• cout<<s<<endl; //输出abcdegf
• reverse(s.began(),s.end());//翻转字符串
• cout<<s<<endl;//

STL中的==迭代器==

• 迭代器：遍历容器中数据的对象。对储存于容器中的数据进行处理时，迭代器能==按预先定义的顺序==从一个成员移向另一个成员。
• ==通过迭代器可以在不了解容器内部原理的情况下遍历容器==

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> ivec;
    vector<int>::iterator iter;
    ivec.push_back(4);
    ivec.push_back(3);
    ivec.push_back(2);
    for(iter=ivec.begin();iter!=ivec.end();iter++)
    {
        cout<<*iter<<endl;
	}
}

STL–map(映射)

• map是一个键值对（key/value)容器，对于迭代器来说可以修改value，而不能修改key。==Map会根据key自动排序==

map类型通常可以理解为关联数组：可使用==键作为下标==来获取一个值。关联的本质在于：元素的值与某个特定的键相关联，而并非通过元素在数组中的位置来获取。

map的基本用法

• map<int,string> m;//定义一个空map m;
• m.count(k);//返回m中键值等于k的元素的个数
• m.find(k);//存在则返回指向该元素的迭代器，否则返回结束地址end（）；
• m.erase(k);//删除m中==键为k==的元素，但会删除元素的个数（1或0）
• m.erase(p);//从m中删除==迭代器p==所指向的元素
• m.insert(e);//e是一个用在m上的value_type类型的值（一个pair）

next_permutation

• ==next_permutation通常用于生成序列的全排列==
• int a[]={1,2,3};
• do{
• cout<<a[0]<<” “<<a[1]<<” “<<a[2]<<endl;
• }while(next_permutation(a,a+3));
• 若当前调用已经到达最大字典序，比如321，则返回函数false

D - Homogeneous Squares

发表于 2021-01-22

ICPC训练联盟2021冬令营（4）D - Homogeneous Squares

1.题目

Assume you have a square of size n that is divided into n × n positions just as a checkerboard. Two positions (x1, y1) and (x2, y2), where 1 ≤ x1, y1, x2, y2 ≤ n, are called “independent” if they occupy different rows and different columns, that is, x1 ≠ x2 and y1 ≠ y2. More generally, n positions are called independent if they are pairwise independent. It follows that there are n! different ways to choose n independent positions.

Assume further that a number is written in each position of such an n × n square. This square is called “homogeneous” if the sum of the numbers written in n independent positions is the same, no matter how the positions are chosen. Write a program to determine if a given square is homogeneous!

Input

The input contains several test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 1000). Each of the next n lines contains n numbers, separated by exactly one space character. Each number is an integer from the interval [−1000000, 1000000].

The last test case is followed by a zero.

Output

For each test case output whether the specified square is homogeneous or not. Adhere to the format shown in the sample output.

Sample Input

1
2
3
4
5
6
7
8

2
1 2
3 4
3
1 3 4
8 6 -2
-3 4 0
0

Sample Output

1
2

homogeneous
not homogeneous

2.题目解析

注意for循环，不符合条件是及时跳出循环，否则超时！！！

3.代码实现

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

#include <iostream>
#include <stdio.h>

using namespace std;

int n,a[1009][1009];

int main(){
    while(~scanf("%d",&n),n)
        {
    	for(int i=0;i<n;++i)
    	{
    		for(int j=0;j<n;++j)
    		{
    			scanf("%d",&a[i][j]);
    		}
    	}
    	int flag=1;//判断跳出的标记
    	for(int i=0;i<n-1;++i)//遍历
    	{
    		for(int j=0;j<n-1;++j)
    		{
    			if((a[i][j]+a[i+1][j+1])!=(a[i+1][j]+a[i][j+1]))
    			{
    				flag=0;
    				break;//不符合条件时，直接跳出循环。
    			}
    		}
    		if(!flag) break;
    	}
    	if(!flag) puts("not homogeneous");
    	else puts("homogeneous");
    }
    return 0;
}

E题题解

发表于 2021-01-20

E - Satellites

题目描述

The radius of earth is 6440 Kilometer. There are many Satellites and Asteroids moving around the earth. If two Satellites create an angle with the center of earth, can you find out the distance between them? By distance we mean both the arc and chord distances. Both satellites are on the same orbit (However, please consider that they are revolving on a circular path rather than an elliptical path).

Input The input file will contain one or more test cases. Each test case consists of one line containing two-integer s and a, and a string ‘min’ or ‘deg’. Here s is the distance of the satellite from the surface of the earth and a is the angle that the satellites make with the center of earth. It may be in minutes (′ ) or in degrees (◦ ). Remember that the same line will never contain minute and degree at a time.

Output For each test case, print one line containing the required distances i.e. both arc distance and chord distance respectively between two satellites in Kilometer. The distance will be a floating-point value with six digits after decimal point.

Sample Input

500 30 deg

700 60 min

200 45 deg

Sample Output

3633.775503 3592.408346

124.616509 124.614927

5215.043805 5082.035982

解析

角度单位是分(′ )和度(◦ )，1°=60′。设圆心角angle[0，180°]。则圆弧距离distance1=(2 * PI * r * angle)/360;直线距离distance2=r * sin((angle*PI)/2 * 180) * 2;

如果以分为单位，将上式的angle替换成angle/60即可；

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
const double r=6440;
int main()
{
    double a1,a2;
    char s[10];
    while(cin>>a1>>a2>>s)
    {
        if(s[0]=='m')//判断输入度数的单位
            a2=a2/60;//分转度
        double angle=M_PI*a2/180;//转换为弧度制
        double arc=angle*(a1+r);//计算弧长
        double dis=2*(a1+r)*sin(angle/2);//计算两点直线距离
        if(a2>180)
            arc=2*M_PI*(a1+r)-arc;//角度大于180的情况
        cout<<setprecision(6)<<setiosflags(ios::fixed)<<arc<<" "<<dis<<endl;
    }
    return 0;
}

ICPC训练联盟2021寒假冬令营（5）H-排名

发表于 2021-01-23

1.题目

今天的上机考试虽然有实时的Ranklist，但上面的排名只是根据完成的题数排序，没有考虑
每题的分值，所以并不是最后的排名。给定录取分数线，请你写程序找出最后通过分数线的
考生，并将他们的成绩按降序打印。

Input

测试输入包含若干场考试的信息。每场考试信息的第1行给出考生人数N ( 0 < N
< 1000 )、考题数M ( 0 < M < = 10 )、分数线（正整数）G；第2行排序给出第1题至第M题的正整数分值；以下N行，每行给出一
名考生的准考证号（长度不超过20的字符串）、该生解决的题目总数m、以及这m道题的题号
（题目号由1到M）。
当读入的考生人数为0时，输入结束，该场考试不予处理。

Output

对每场考试，首先在第1行输出不低于分数线的考生人数n，随后n行按分数从高
到低输出上线考生的考号与分数，其间用1空格分隔。若有多名考生分数相同，则按他们考
号的升序输出。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14

4 5 25
10 10 12 13 15
CS004 3 5 1 3
CS003 5 2 4 1 3 5
CS002 2 1 2
CS001 3 2 3 5
1 2 40
10 30
CS001 1 2
2 3 20
10 10 10
CS000000000000000001 0
CS000000000000000002 2 1 2
0

Sample Output

1
2
3
4
5
6
7

3
CS003 60
CS001 37
CS004 37
0
1
CS000000000000000002 20

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

#include <iostream>
#include <algorithm>
using namespace std;
#define N 1005
int que[15];
struct ks
{
    char name[25];//考生号
    int num;//解决问题总数
    int sum;//分数
}stu[N];
bool cmp(const ks &a,const ks &b)
{
    if(a.sum==b.sum)
        return strcmp(a.name,b.name)<0?1:0;//比较考生号
    else
        return a.sum>b.sum;
}
int main()
{
    int stu_num,text_num,line,a,cnt;//stu_num考生人数，text_num考题数
    while(cin>>stu_num&&stu_num)
    {
        cnt=0;
        int j;
        cin>>text_num>>line;
        for(j=1;j<=text_num;j++)
            cin>>que[j];
        for(j=1;j<=stu_num;j++)
        {
            stu[j].sum=0;//初始化成绩求和
            cin>>stu[j].name>>stu[j].num;
            while(stu[j].num--)
            {
                cin>>a;//做对的题号
                stu[j].sum+=que[a];//求总成绩
            }
            if(stu[j].sum>=line)
                cnt++;//计算过分数线的人树
        }
        sort(stu+1,stu+1+stu_num,cmp);//排序
        cout<<cnt<<endl;
        for(j=1;j<=stu_num;j++)
        {
            if(stu[j].sum>=line)
                cout<<stu[j].name<<" "<<stu[j].sum<<endl;
            else
                break;
        }
    }
    return 0;
}

ICPC（6）A - Doubles

As part of an arithmetic competency program, your students will be given randomly generated lists of from 2 to 15 unique positive integers and asked to determine how many items in each list are twice some other item in the same list. You will need a program to help you with the grading. This program should be able to scan the lists and output the correct answer for each one. For example, given the list

1 4 3 2 9 7 18 22
your program should answer 3, as 2 is twice 1, 4 is twice 2, and 18 is twice 9.

Input

The input will consist of one or more lists of numbers. There will be one list of numbers per line. Each list will contain from 2 to 15 unique positive integers. No integer will be larger than 99. Each line will be terminated with the integer 0, which is not considered part of the list. A line with the single number -1 will mark the end of the file. The example input below shows 3 separate lists. Some lists may not contain any doubles.

Output

The output will consist of one line per input list, containing a count of the items that are double some other item.

Sample Input

1
2
3
4

1 4 3 2 9 7 18 22 0
2 4 8 10 0
7 5 11 13 1 3 0
-1

Sample Output

1
2
3

3
2
0

1.set解析及其用法

头文件 #include < set >

set

set头文件主要包括set和multiset两个容器。他们都是有序集合，不过set存的元素不可重复。

两者内部实现都是红黑树，在使用方法上差别不大，支持的函数基本相同。

声明方式

1
2
3

set<int> s;
multiset<int> t;
set<int>::iterator it;

s与t都是维护int类型数据的有序容器，其中t内的元素可重。迭代器it仅支持++和−−。我们以int类型的数据为例：

s.size()

返回元素个数。

s.empty()

判断set是否为空，为空则是逻辑真，否则就是逻辑假。

s.clear()

清空set。

s.begin()/s.end()

返回set的首迭代器和尾迭代器。第一个元素/最后一个元素

s.insert(x)/s.erase(it/x)

插入一个intint类型的数据，删除一个迭代器或者元素x。如果x已经是在集合中的了，并且是set而不是multiset，那么就不会执行插入操作。时间复杂度为O(log)。如果是multiset则会把所有等于x的元素全部删除，复杂度为O(log+k)，k为元素个数。

s.find(x)

查找等于xx的元素，返回一个迭代器。若不存在，则返回s.end()s.end()。复杂度O(log)O(log)的。

s.lower_bound(x)/s.upper_bound(x)

第一个是找set中大于等于xx的最小的元素，第二个是找set中严格大于xx的最小的元素，以迭代器的形式返回。时间复杂度为O(log)。若不存在，则返回s.end()。

s.count(x)

返回集合中等于x的元素个数。复杂度为O(log+k)，k为元素个数。

迭代器iterator

1. 迭代器(iterator)是一中检查容器内元素并遍历元素的数据类型。

Iterator（迭代器）模式又称Cursor（游标）模式，用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。或者这样说可能更容易理解：Iterator模式是运用于聚合对象的一种模式，通过运用该模式，使得我们可以在不知道对象内部表示的情况下，按照一定顺序（由iterator提供的方法）访问聚合对象中的各个元素。

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

#include <iostream>
#include <set>
using namespace std;

int main()
{
    set<int>s;
    set<int>::iterator t;//创建一个迭代器t
    int temp;
    cin>>temp;
    while(temp!=-1)
    {
        s.clear();
        while(temp!=0)
        {
            s.insert(temp);
            cin>>temp;
        }
        int c=0;
        for(t=s.begin();t!=s.end();t++)
        {
            if(s.count((*t)*2)!=0)//返回集合中等于（*t*2）的元素个数。
                c++;
        }
        cout<<c<<endl;
        cin>>temp;
    }
    return 0;
}